Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
This work addresses fundamental challenges in multiplayer game theory for competitive settings like Mahjong and Poker, offering a principled solution to secure fair outcomes, though it is incremental in advancing beyond existing methods.
The paper tackles the problem of securing an equal expected payoff in multiplayer symmetric constant-sum games, where traditional equilibria lack guarantees, by developing efficient algorithms that provably achieve approximate equal share and demonstrating their effectiveness in worst-case scenarios where prior methods fail.
This paper examines multiplayer symmetric constant-sum games with more than two players in a competitive setting, including examples like Mahjong, Poker, and various board and video games. In contrast to two-player zero-sum games, equilibria in multiplayer games are neither unique nor non-exploitable, failing to provide meaningful guarantees when competing against opponents who play different equilibria or non-equilibrium strategies. This gives rise to a series of long-lasting fundamental questions in multiplayer games regarding suitable objectives, solution concepts, and principled algorithms. This paper takes an initial step towards addressing these challenges by focusing on the natural objective of equal share -- securing an expected payoff of C/n in an n-player symmetric game with a total payoff of C. We rigorously identify the theoretical conditions under which achieving an equal share is tractable and design a series of efficient algorithms, inspired by no-regret learning, that provably attain approximate equal share across various settings. Furthermore, we provide complementary lower bounds that justify the sharpness of our theoretical results. Our experimental results highlight worst-case scenarios where meta-algorithms from prior state-of-the-art systems for multiplayer games fail to secure an equal share, while our algorithm succeeds, demonstrating the effectiveness of our approach.