2012/06/27 by Ruggiero Cavallo, David C. Parkes, Cavallo, Ruggiero +3 · 1 citation
Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.1206.6820
openalex publication_date 2012/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a multi-agent system in a dynamic and uncertain environment. Each\nagent's local decision problem is modeled as a Markov decision process (MDP)\nand agents must coordinate on a joint action in each period, which provides a\nreward to each agent and causes local state transitions. A social planner knows\nthe model of every agent's MDP and wants to implement the optimal joint policy,\nbut agents are self-interested and have private local state. We provide an\nincentive-compatible mechanism for eliciting state information that achieves\nthe optimal joint plan in a Markov perfect equilibrium of the induced\nstochastic game. In the special case in which local problems are Markov chains\nand agents compete to take a single action in each period, we leverage Gittins\nallocation indices to provide an efficient factored algorithm and distribute\ncomputation of the optimal policy among the agents. Distributed, optimal\ncoordinated learning in a multi-agent variant of the multi-armed bandit problem\nis obtained as a special case.\n