Output details

Ranking games that have competitiveness-based strategies

<12> The computational complexity of Nash equilibria (NE) has been recently settled in terms of the PPAD class. It is then unlikely that there exists a polynomial-time algorithm computing NE for any game. This raises the question of whether this problem remains hard for meaningful games. In this work we consider a rich class of strategic games, modelling contests, and prove a number of results concerning the computation of (approximate) NE in polynomial-time. A preliminary version of this work appeared in a key conference of Algorithmic Game Theory, ACM Conference EC10. (All the submitted papers use alphabetical ordering of authors.)