On Strictly Competitive Multi-Player Games

Abstract

We embark on an initial study of a new class of strategic (normal-form) games, so-called ranking games, in which the payoff to each agent solely depends on his position in a ranking of the agents induced by their actions. This definition is motivated by the observation that in many strategic situations such as parlor games, competitive economic scenarios, and some social choice settings, players are merely interested in performing optimal relative to their opponents rather than in absolute measures. A simple but important subclass of ranking games are single-winner games where in any outcome one agent wins and all others lose. We investigate the computational complexity of a variety of common game-theoretic solution concepts in ranking games and deliver hardness results for iterated weak dominance and mixed Nash equilibria when there are more than two players and pure Nash equilibria when the number of players is unbounded. This dashes hope that multi-player ranking games can be solved efficiently, despite the structural restrictions of these games.