We provide the first anonymity-preserving algorithm for a centralized decision maker in linear bandit-based multiuser systems. Our algorithm employs successive elimination techniques for linear bandits to build an assignment multi-graph (from users to arms) along with a greedy matching algorithm that efficiently allocates the arms to users. We provide lower and upper bounds for this problem, showing that our algorithm is regret optimal up to a √ 𝐶𝐾 factor. CCS Concepts • Theory of computation → Sequential decision making; Online learning algorithms; • Security and privacy → Data anonymization and sanitization; Privacy protections.