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.
Anonymous games represent a class of finite games that relate to the discretized contests considered here. Anonymous games are games where a player's payoff depends on his own action and on the distribution of actions taken by the other players, but not on the identities of the players who chose each action. Anonymous games admit polynomial-time approximation schemes (PTAS's) @cite_3 @cite_4 but may be PPAD-complete to solve exactly. The algorithms for anonymous games can be applied to an interesting subclass of the discretized contests that we study here. In particular they apply to a special case in which all players have the same (finite) set of score levels available to them, with prizes being shared in the event of ties (which is a standard assumption in much of the literature).
@cite_4 @cite_3
2950776615 2740520762 1855561663 2127813674
We present efficient approximation algorithms for finding Nash equilibria in anonymous games, that is, games in which the players utilities, though different, do not differentiate between other players. Our results pertain to such games with many players but few strategies. We show that any such game has an approximate pure Nash equilibrium, computable in polynomial time, with approximation O(s^2 L), where s is the number of strategies and L is the Lipschitz constant of the utilities. Finally, we show that there is a PTAS for finding an epsilon Abstract We study the computation of Nash equilibria of anonymous games, via algorithms that use adaptive queries to a game's payoff function. We show that exact equilibria cannot be found via query-efficient algorithms, and exhibit a two-strategy, 3-player anonymous game whose exact equilibria require irrational numbers. We obtain positive results for known sub-classes of anonymous games. Our main result is a new randomized query-efficient algorithm for approximate equilibria of two-strategy anonymous games that improves on the running time of previous algorithms. It is the first to obtain an inverse polynomial approximation in poly-time, and yields an efficient polynomial-time approximation scheme. We present a novel polynomial time approximation scheme fortwo-strategy anonymous games, in which the players’ utilityfunctions, although potentially different, do not differentiateamong the identities of the other players. Our algorithm computesan e-approximate Nash equilibrium of an n-player 2-strategyanonymous game in time @math , which significantly improves uponthe running time @math required by the algorithm ofDaskalakis & Papadimitriou, 2007. The improved running time isbased on a new structural understanding of approximate Nashequilibria: We show that, for any e, there exists ane-approximate Nash equilibrium in which either onlyO(1 e 3) players randomize, or all players who randomizeuse the same mixed strategy. To show this result we employ toolsfrom the literature on Stein’s Method. Coalitional games allow subsets (coalitions) of players to cooperate to receive a collective payoff. This payoff is then distributed “fairly” among the members of that coalition according to some division scheme. Various solution concepts have been proposed as reasonable schemes for generating fair allocations. The Shapley value is one classic solution concept: player i’s share is precisely equal to i’s expected marginal contribution if the players join the coalition one at a time, in a uniformly random order. In this paper, we consider the class of supermodular games (sometimes called convex games), and give a fully polynomial-time randomized approximation scheme (FPRAS) to compute the Shapley value to within a (1 ±e) factor in monotone supermodular games. We show that this result is tight in several senses: no deterministic algorithm can approximate Shapley value as well, no randomized algorithm can do better, and both monotonicity and supermodularity are required for the existence of an efficient (1 ±e)-approximation algorithm. We also argue that, relative to supermodularity, monotonicity is a mild assumption, and we discuss how to transform supermodular games to be monotonic.