Multiagent Reinforcement Learning in Games with an Iterated Dominance Solution
Multiagent reinforcement learning (MARL) attempts to optimize policies of intelligent agents interacting in the same environment. However, it may fail to converge to a Nash equilibrium in some games. We study independent MARL under the more demanding solution concept of iterated elimination of strictly dominated strategies. In dominance solvable games, if players iteratively eliminate strictly dominated strategies until no further strategies can be eliminated, we obtain a single strategy profile. We show that convergence to the iterated dominance solution is guaranteed for several reinforcement learning algorithms (for multiple independent learners). We illustrate an application of our results by studying mechanism design for principal-agent problems, where a principal wishes to incentivize agents to exert costly effort in a joint project when it can only observe whether the project succeeded, but not whether agents actually exerted effort. We show that MARL converges to the desired outcome if the rewards are designed so that exerting effort is the iterated dominance solution, but fails if it is merely a Nash equilibrium.
Code (0)
등록된 구현이 없습니다.
Tasks
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Learning in Multiagent Systems: An Introduction from a Game-Theoretic Perspective
We introduce the topic of learning in multiagent systems. We first provide a quick introduction to the field of game theory, focusing on the equilibrium concepts of iterated dominance, and Nash equilibrium. We show some …
Dominance Solvability in Random Games
We study the effectiveness of iterated elimination of strictly-dominated actions in random games. We show that dominance solvability of games is vanishingly small as the number of at least one player's actions grows. Fur…
Towards Cooperation in Sequential Prisoner's Dilemmas: a Deep Multiagent Reinforcement Learning Approach
The Iterated Prisoner's Dilemma has guided research on social dilemmas for decades. However, it distinguishes between only two atomic actions: cooperate and defect. In real-world prisoner's dilemmas, these choices are te…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Cautious Belief and Iterated Admissibility
We define notions of cautiousness and cautious belief to provide epistemic conditions for iterated admissibility in finite games. We show that iterated admissibility characterizes the behavioral implications of "cautious…
A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning
To achieve general intelligence, agents must learn how to interact with others in a shared environment: this is the challenge of multiagent reinforcement learning (MARL). The simplest form is independent reinforcement le…
Deep Reinforcement Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)