Replication-proof Bandit Mechanism Design with Bayesian Agents
This work addresses a strategic manipulation issue in bandit mechanisms for Bayesian agents, offering incremental improvements over existing methods by adapting to a more complex agent knowledge model.
The paper tackles the problem of designing bandit mechanisms that prevent strategic agents from replicating their arms to increase payoff, focusing on Bayesian agents who know only the distribution of their arms' mean rewards. It provides sufficient and necessary conditions for replication-proofness in single-agent settings, presents an algorithm that meets these conditions, extends it to multi-agent settings, and proves a sublinear regret upper bound matching prior work.
We study the problem of designing replication-proof bandit mechanisms when agents strategically register or replicate their own arms to maximize their payoff. Specifically, we consider Bayesian agents who only know the distribution from which their own arms' mean rewards are sampled, unlike the original setting of by Shin et al. 2022. Interestingly, with Bayesian agents in stark contrast to the previous work, analyzing the replication-proofness of an algorithm becomes significantly complicated even in a single-agent setting. We provide sufficient and necessary conditions for an algorithm to be replication-proof in the single-agent setting, and present an algorithm that satisfies these properties. These results center around several analytical theorems that focus on \emph{comparing the expected regret of multiple bandit instances}, and therefore might be of independent interest since they have not been studied before to the best of our knowledge. We expand this result to the multi-agent setting, and provide a replication-proof algorithm for any problem instance. We finalize our result by proving its sublinear regret upper bound which matches that of Shin et al. 2022.