Ranking games that have competitiveness-based strategies

DOI10.1016/J.TCS.2013.01.013MaRDI QIDQ1945930zbMATH OpenOpenAlexFDO

Authors Leslie Ann Goldberg, Paul W. Goldberg, Piotr Krysta, Carmine Ventre

Publication date 17 April 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.5844

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05) Noncooperative games (91A10) Other game-theoretic models (91A40)

Abstract: An extensive literature in economics and social science addresses contests, in which players compete to outperform each other on some measurable criterion, often referred to as a player's score, or output. Players incur costs that are an increasing function of score, but receive prizes for obtaining higher score than their competitors. In this paper we study finite games that are discretized contests, and the problems of computing exact and approximate Nash equilibria. Our motivation is the worst-case hardness of Nash equilibrium computation, and the resulting interest in important classes of games that admit polynomial-time algorithms. For games that have a tie-breaking rule for players' scores, we present a polynomial-time algorithm for computing an exact equilibrium in the 2-player case, and for multiple players, 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 approximation schemes for two special cases: constant-sized set of strategies, and constant number of players.

Recommendations

• Ranking games
• scientific article; zbMATH DE number 1499098
• Winner-take-all games: the strategic optimisation of rank
• Terminal ranking games
• Games and winning strategies
• A multiple criteria ranking method based on game cross-evaluation approach
• Scheduling games with rank-based utilities
• Ranking participants in tournaments by means of rating functions

Cited in

(8)

• Cost-sharing games with rank-based utilities
• Scheduling games with rank-based utilities
• Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy
• The contest game for crowdsourcing reviews
• Winner-take-all games: existence of equilibria and three player dice
• Cost-sharing games with rank-based utilities
• Coordination mechanisms with rank-based utilities
• Ranking games

This page was built for publication: Ranking games that have competitiveness-based strategies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1945930)