We study the equilibrium computation problem for two classical resource allocation games: atomic splittable congestion games and multimarket Cournot oligopolies. For atomic splittable congestion games with singleton strategies and player-specific affine cost functions, we devise the first polynomial time algorithm computing a pure Nash equilibrium. Our algorithm is combinatorial and computes the exact equilibrium assuming rational input. The idea is to compute an equilibrium for an associated integrally-splittable singleton congestion game in which the players can only split their demands in integral multiples of a common packet size. While integral games have been considered in the literature before, no polynomial time algorithm computing an equilibrium was known. Also for this class, we devise the first polynomial time algorithm and use it as a building block for our main algorithm. We then develop a polynomial time computable transformation mapping a multimarket Cournot competition game with firm-specific affine price functions and quadratic costs to an associated atomic splittable congestion game as described above. The transformation preserves equilibria in either games and, thus, leads -- via our first algorithm -- to a polynomial time algorithm computing Cournot equilibria. Finally, our analysis for integrally-splittable games implies new bounds on the difference between real and integral Cournot equilibria. The bounds can be seen as a generalization of the recent bounds for single market oligopolies obtained by Todd [2016].
For the computation of equilibria, Marcotte @cite_30 proposed four numerical algorithms and showed local convergence results. Meunier and Pradeau @cite_10 developed a pivoting-algorithm (similar to Lemkes algorithm) for nonatomic network congestion games with affine player-specific cost functions. Polynomial running time was, however, not shown and seems unlikely to hold. @cite_19 considered nonatomic routing games on parallel links with affine player-specific cost functions. They developed a convex potential function that can be minimized within arbitrary precision in polynomial time. @cite_24 considered general concave games with compact action spaces and investigated algorithms computing an approximate equilibrium. Roughly speaking, they discretized the compact strategy space and use the Lipschitz constants of utility functions to show that only a finite number of representative strategy profiles need to be considered for obtaining an approximate equilibrium (see also @cite_21 for a similar approach). The running time of the algorithm, however, depends on an upper bound of the norm of strategy vectors, thus, implying only a pseudo-polynomial algorithm for our setting.
@cite_30 @cite_21 @cite_24 @cite_19 @cite_10
2030722474 2131967794 2949253038 622918438
We consider the problem of computing a Nash equilibrium in multiple-player games. It is known that there exist games, in which all the equilibria have irrational entries in their probability distributions [19]. This suggests that either we should look for symbolic representations of equilibria or we should focus on computing approximate equilibria. We show that every finite game has an equilibrium such that all the entries in the probability distributions are algebraic numbers and hence can be finitely represented. We also propose an algorithm which computes an approximate equilibrium in the following sense: the strategies output by the algorithm are close with respect to l ∞ -norm to those of an exact Nash equilibrium and also the players have only a negligible incentive to deviate to another strategy. The running time of the algorithm is exponential in the number of strategies and polynomial in the digits of accuracy. We obtain similar results for approximating market equilibria in the neoclassical exchange model under certain assumptions. We consider a nonatomic congestion game on a connected graph, with several classes of players. Each player wants to go from its origin vertex to its destination vertex at the minimum cost and all players of a given class share the same characteristics: cost functions on each arc, and origin-destination pair. Under some mild conditions, it is known that a Nash equilibrium exists, but the computation of an equilibrium in the multiclass case is an open problem for general functions. We consider the specific case where the cost functions are affine and propose an extension of Lemke's algorithm able to solve this problem. At the same time, it provides a constructive proof of the existence of an equilibrium in this case. The complexity of computing pure Nash equilibria in congestion games was recently shown to be PLS-complete. In this paper, we therefore study the complexity of computing approximate equilibria in congestion games. An alpha-approximate equilibrium, for α > 1, is a state of the game in which none of the players can make an α-greedy step, i.e., an unilateral strategy change that decreases the player's cost by a factor of at least α. Our main result shows that finding an α-approximate equilibrium of a given congestion game is sc PLS-complete, for any polynomial-time computable α > 1. Our analysis is based on a gap introducing PLS-reduction from FLIP, i.e., the problem of finding a local optimum of a function encoded by an arbitrary circuit. As this reduction is tight it additionally implies that computing an α-approximate equilibrium reachable from a given initial state by a sequence of α-greedy steps is PSPACE-complete. Our results are in sharp contrast to a recent result showing that every local search problem in PLS admits a fully polynomial time approximation scheme. In addition, we show that there exist congestion games with states such that any sequence of α-greedy steps leading from one of these states to an α-approximate Nash equilibrium has exponential length, even if the delay functions satisfy a bounded-jump condition. This result shows that a recent result about polynomial time convergence for α-greedy steps in congestion games satisfying the bounded-jump condition is restricted to symmetric games only. We study the ability of decentralized, local dynamics in non-cooperative games to rapidly reach an approximate (pure) Nash equilibrium. Our main result states that for symmetric congestion games in which the cost function associated with each resource satisfies a "bounded jump" condition, convergence to an [epsilon]-Nash equilibrium occurs within a number of steps that is polynomial in the number of players and [epsilon]-1. We show moreover that this result holds under a variety of conventions governing the move orders among the players, including the minimal liveness assumption that no player is indefinitely blocked from moving. We also prove that in the generalized setting where players have different "tolerances" [epsilon]i, the number of moves a player makes before equilibrium is reached depends only on his associated [epsilon]i, and not on those of other players. Finally, we show that polynomial time convergence holds even when a constant number of resources have arbitrary cost functions.