Ranking Games that have Competitiveness-based Strategies

摘要

This paper studies —from the perspective of efficient computation— a type of competition that is widespread throughout the plant and animal kingdoms, higher education, politics and artificial, contests. In this setting, an agent gains utility from his relative performance (on some measurable criterion) against other agents, as opposed to his absolute performance. We model this situation using ranking games in which each strategy corresponds to a level of competitiveness, and incurs an upfront cost that is higher for more competitive strategies. We study the Nash equilibria of these games, and polynomial-time algorithms for computing them. For games in which there is no tie between agents' levels of competitiveness we give a polynomial-time algorithm for computing an exact equilibrium in the 2-player case, and a characterization of Nash equilibria that shows an interesting parallel between these games and unrestricted 2-player games in normal form. When ties are allowed, via a reduction from these games to a subclass of anonymous games, we give polynomial-time approximation schemes for two special cases: constant-sized set of strategies, and constant number of players. The latter result is improved to a fully polynomial-time approximation scheme when the constant number of players only compete to win the game, i.e. to be ranked first.