A note on proofs of existence of Nash equilibria in finite strategic games,of two players

Known general proofs of Nash’s Theorem (about the existence of Nash Equilibria (NEa) in finite strategic games) rely on the use of a fixed point theorem (e.g. Brouwer’s or Kakutani’s). While it seems that there is no general way of proving the existence of Nash equilibria without the use of a fixed point theorem, there do however exist some (not so common in the CS literature) proofs that seem to indicate alternative proof paths, for games of two players. This note discusses two such proofs.     

Equilibria of graphical games with symmetries

We study graphical games where the payoff function of each player satisfies one of four types of symmetry in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in general for all four types. Using a characterization of games with pure equilibria in terms of even cycles in the neighborhood graph, as well as a connection to a generalized satisfiability problem, we identify tractable subclasses of the games satisfying the most restrictive type of symmetry. Hardness for a different subclass leads us to identify a satisfiability problem that remains NP-hard in the presence of a matching, a result that may be of independent interest. Finally, games with symmetries of two of the four types are shown to possess a symmetric mixed equilibrium which can be computed in polynomial time. We thus obtain a natural class of games where the pure equilibrium problem is computationally harder than the mixed equilibrium problem, unless P=NP.     

How hard is it to find extreme Nash equilibria in network congestion games?

We study the complexity of finding extreme pure Nash equilibria in symmetric (unweighted) network congestion games. In our context best and worst equilibria are those with minimum respectively maximum makespan. On series–parallel graphs a worst Nash equilibrium can be found by a Greedy approach while finding a best equilibrium is NP-hard. For a fixed number of users we give a pseudo-polynomial algorithm to find the best equilibrium in series–parallel networks. For general network topologies also finding a worst equilibrium is NP-hard.     

Symmetries and the complexity of pure Nash equilibrium

Strategic games may exhibit symmetries in a variety of ways. A characteristic feature, enabling the compact representation of games even when the number of players is unbounded, is that players cannot, or need not, distinguish between the other players. We investigate the computational complexity of pure Nash equilibria in four classes of symmetric games obtained by considering two additional properties: identical payoff functions for all players and the ability to distinguish oneself from the other players. In contrast to other types of succinctly representable multi-player games, the pure equilibrium problem is tractable in all four classes when only a constant number of actions is available to each player. Identical payoff functions make the difference between TC⁰-completeness and membership in AC⁰, while a growing number of actions renders the equilibrium problem NP-hard for three of the classes and PLS-hard for the most restricted class for which the existence of a pure equilibrium is guaranteed. Our results also extend to larger classes of threshold symmetric games where players are unable to determine the exact number of players playing a certain action.     

Equilibria,fixed points,and complexity classes

Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; market equilibria; computing optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysing basic stochastic models for evolution like branching processes and for language like stochastic context-free grammars; and models that incorporate the basic primitives of probability and recursion like recursive Markov chains. It is not known whether these problems can be solved in polynomial time. There are certain common computational principles underlying different types of equilibria, which are captured by the complexity classes PLS, PPAD, and FIXP. Representative complete problems for these classes are, respectively, pure Nash equilibria in games where they are guaranteed to exist, (mixed) Nash equilibria in two-player normal form games, and (mixed) Nash equilibria in normal form games with three (or more) players. This paper reviews the underlying computational principles and the corresponding classes.     

On the Complexity of Pareto-Optimal Nash and Strong Equilibria

We consider the computational complexity of coalitional solution concepts in scenarios related to load balancing such as anonymous and congestion games. In congestion games, Pareto-optimal Nash and strong equilibria, which are resilient to coalitional deviations, have recently been shown to yield significantly smaller inefficiency. Unfortunately, we show that several problems regarding existence, recognition, and computation of these concepts are hard, even in seemingly special classes of games. In anonymous games with constant number of strategies, we can efficiently recognize a state as Pareto-optimal Nash or strong equilibrium, but deciding existence for a game remains hard. In the case of player-specific singleton congestion games, we show that recognition and computation of both concepts can be done efficiently. In addition, in these games there are always short sequences of coalitional improvement moves to Pareto-optimal Nash and strong equilibria that can be computed efficiently.     

When Can Limited Randomness Be Used in Repeated Games?

The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies. However, in practice, humans are known to be bad at generating random-like sequences, and true random bits may be unavailable. Even if the players have access to enough random bits for a single instance of the game their randomness might be insufficient if the game is played many times. In this work, we ask whether randomness is necessary for equilibria to exist in finitely repeated games. We show that for a large class of games containing arbitrary two-player zero-sum games, approximate Nash equilibria of the n-stage repeated version of the game exist if and only if both players have Ω(n) random bits. In contrast, we show that there exists a class of games for which no equilibrium exists in pure strategies, yet the n-stage repeated version of the game has an exact Nash equilibrium in which each player uses only a constant number of random bits. When the players are assumed to be computationally bounded, if cryptographic pseudorandom generators (or, equivalently, one-way functions) exist, then the players can base their strategies on “random-like” sequences derived from only a small number of truly random bits. We show that, in contrast, in repeated two-player zero-sum games, if pseudorandom generators do not exist, then Ω(n) random bits remain necessary for equilibria to exist.     

Random Bimatrix Games Are Asymptotically Easy to Solve (A Simple Proof)

We focus on the problem of computing approximate Nash equilibria and well-supported approximate Nash equilibria in random bimatrix games, where each player’s payoffs are bounded and independent random variables, not necessarily identically distributed, but with almost common expectations. We show that the completely mixed uniform strategy profile, i.e., the combination of mixed strategies (one per player) where each player plays with equal probability each one of her available pure strategies, is with high probability a $\sqrt{\frac{\ln n}{n}}$ -Nash equilibrium and a $\sqrt{\frac{3\ln n}{n}}$ -well supported Nash equilibrium, where n is the number of pure strategies available to each player. This asserts that the completely mixed, uniform strategy profile is an almost Nash equilibrium for random bimatrix games, since it is, with high probability, an ?-well-supported Nash equilibrium where ? tends to zero as n tends to infinity.     

Strategic Multiway Cut and Multicut Games

We consider cut games where players want to cut themselves off from different parts of a network. These games arise when players want to secure themselves from areas of potential infection. For the game-theoretic version of Multiway Cut, we prove that the price of stability is 1, i.e., there exists a Nash equilibrium as good as the centralized optimum. For the game-theoretic version of Multicut, we show that there exists a 2-approximate equilibrium as good as the centralized optimum. We also give poly-time algorithms for finding exact and approximate equilibria in these games.     

A game-theoretic and dynamical-systems analysis of selection methods in coevolution

We use evolutionary game theory (EGT) to investigate the dynamics and equilibria of selection methods in coevolutionary algorithms. The canonical selection method used in EGT is equivalent to the standard "fitness-proportional" selection method used in evolutionary algorithms. All attractors of the EGT dynamic are Nash equilibria; we focus on simple symmetric variable-sum games that have polymorphic Nash-equilibrium attractors. Against the dynamics of proportional selection, we contrast the behaviors of truncation selection, (/spl mu/,/spl lambda/),(/spl mu/+/spl lambda/), linear ranking, Boltzmann, and tournament selection. Except for Boltzmann selection, each of the methods we test unconditionally fail to achieve polymorphic Nash equilibrium. Instead, we find point attractors that lack game-theoretic justification, cyclic dynamics, or chaos. Boltzmann selection converges onto polymorphic Nash equilibrium only when selection pressure is sufficiently low; otherwise, we obtain attracting limit-cycles or chaos. Coevolutionary algorithms are often used to search for solutions (e.g., Nash equilibria) of games of strategy; our results show that many selection methods are inappropriate for finding polymorphic Nash solutions to variable-sum games. Another application of coevolution is to model other systems; our results emphasize the degree to which the model's behavior is sensitive to implementation details regarding selection-details that we might not otherwise believe to be critical.     

On the variational equilibrium as a refinement of the generalized Nash equilibrium

We are concerned with a class of games in which the players’ strategy sets are coupled by a shared constraint. A widely employed solution concept for such generalized Nash games is the generalized Nash equilibrium (GNE). The variational equilibrium (VE) (Facchinei & Kanzow, 2007) is a specific kind of GNE characterized by the solution of the variational inequality formed from the common constraint and the mapping of the gradients of player objectives. Our contribution is a theory that provides sufficient conditions for ensuring that the existence of a GNE implies the existence of a VE; in such an instance, the VE is said to be a refinement of the GNE. For certain games, these conditions are shown to be necessary. This theory rests on a result showing the equality of the Brouwer degree of two suitably defined functions, whose zeros are the GNE and VE, respectively. This theory has a natural extension to the primal–dual space of strategies and Lagrange multipliers corresponding to the shared constraint. Our results unify some known results pertaining to such equilibria and provide mathematical substantiation for ideas that were known to be appealing to economic intuition.     

一类定量微分对策理论中最优策略的算法及其收敛性

本文利用不动点原理讨论了一类定量微分对策理论中最优策略的计算方法问题.首先构 造出了一种迭代方法,然后利用不动点原理分析了该迭代法的收敛性.本文给出的方法还可 用于一类Nash微分对策的Nash策略的分散计算方法.     

Comparing the notions of optimality in CP-nets,strategic games and soft constraints

The notion of optimality naturally arises in many areas of applied mathematics and computer science concerned with decision making. Here we consider this notion in the context of three formalisms used for different purposes in reasoning about multi-agent systems: strategic games, CP-nets, and soft constraints. To relate the notions of optimality in these formalisms we introduce a natural qualitative modification of the notion of a strategic game. We show then that the optimal outcomes of a CP-net are exactly the Nash equilibria of such games. This allows us to use the techniques of game theory to search for optimal outcomes of CP-nets and vice-versa, to use techniques developed for CP-nets to search for Nash equilibria of the considered games. Then, we relate the notion of optimality used in the area of soft constraints to that used in a generalization of strategic games, called graphical games. In particular we prove that for a natural class of soft constraints that includes weighted constraints every optimal solution is both a Nash equilibrium and Pareto efficient joint strategy. For a natural mapping in the other direction we show that Pareto efficient joint strategies coincide with the optimal solutions of soft constraints.      

Computational Aspects of Uncertainty Profiles and Angel-Daemon Games

We analyze the complexity of equilibria problems for a class of strategic zero-sum games, called angel-daemon games. Those games were introduced to asses the performance of the execution of a web orchestration on a moderate faulty or under stress environment. Angel-daemon games are a natural example of zero-sum games whose representation is naturally succinct. We show that the problems of deciding the existence of a pure Nash equilibrium or of a dominant strategy for a given player are ${\Sigma}^{p}_{2}$ -complete. Furthermore, computing the value of an angel-daemon game is EXP-complete. Thus, our results match the already known classification of the corresponding problems for the generic families of succinctly represented games with exponential number of actions.     

Weakly-Acyclic (Internet) Routing Games

Weakly-acyclic games—a superclass of potential games—capture distributed environments where simple, globally-asynchronous interactions between strategic agents are guaranteed to converge to an equilibrium. We explore the class of routing games introduced in Fabrikant and Papadimitriou (The Complexity of Game Dynamics: BGP Oscillations, Sink Equilibria, and Beyond, pp. 844–853, 2008) and in Levin et al. (Interdomain Routing and Games, pp. 57–66, 2008), which models important aspects of routing on the Internet. We show that, in interesting contexts, such routing games are weakly acyclic and, moreover, that pure Nash equilibria in such games can be found in a computationally efficient manner.     

Computing Equilibria in Discounted 2 × 2 Supergames

This article examines the subgame perfect pure strategy equilibrium paths and payoff sets of discounted supergames with perfect monitoring. The main contribution is to provide methods for computing and tools for analyzing the equilibrium paths and payoffs in repeated games. We introduce the concept of a first-action feasible path, which simplifies the computation of equilibria. These paths can be composed into a directed multigraph, which is a useful representation for the equilibrium paths. We examine how the payoffs, discount factors and the properties of the multigraph affect the possible payoffs, their Hausdorff dimension, and the complexity of the equilibrium paths. The computational methods are applied to the 12 symmetric strictly ordinal 2 × 2 games. We find that these games can be classified into three groups based on the complexity of the equilibrium paths.     

Concurrent imitation dynamics in congestion games

Imitating successful behavior is a natural and frequently applied approach when facing complex decision problems. In this paper, we design protocols for distributed latency minimization in atomic congestion games based on imitation. We propose to study concurrent dynamics that emerge when each agent samples another agent and possibly imitates this agent’s strategy if the anticipated latency gain is sufficiently large. Our focus is on convergence properties. We show convergence in a monotonic fashion to stable states, in which none of the agents can improve their latency by imitating others. As our main result, we show rapid convergence to approximate equilibria, in which only a small fraction of agents sustains a latency significantly above or below average. Imitation dynamics behave like an FPTAS, and the convergence time depends only logarithmically on the number of agents. Imitation processes cannot discover unused strategies, and strategies may become extinct with non-zero probability. For singleton games we show that the probability of this event occurring is negligible. Additionally, we prove that the social cost of a stable state reached by our dynamics is not much worse than an optimal state in singleton games with linear latency functions. We concentrate on the case of symmetric network congestion games, but our results do not use the network structure and continue to hold accordingly for general symmetric games. They even apply to asymmetric games when agents sample within the set of agents with the same strategy space. Finally, we discuss how the protocol can be extended such that, in the long run, dynamics converge to a pure Nash equilibrium.     

Abstracting Nash equilibria of supermodular games

Supermodular games are a well known class of noncooperative games which find significant applications in a variety of models, especially in operations research and economic applications. Supermodular games always have Nash equilibria which are characterized as fixed points of multivalued functions on complete lattices. Abstract interpretation is here applied to set up an approximation framework for Nash equilibria of supermodular games. This is achieved by extending the theory of abstract interpretation in order to cope with approximations of multivalued functions and by providing some methods for abstracting supermodular games, thus obtaining approximate Nash equilibria which are shown to be correct within the abstract interpretation framework.     

Equilibria problems on games: Complexity versus succinctness

We study the computational complexity of problems involving equilibria in strategic games and in perfect information extensive games when the number of players is large. We consider, among others, the problems of deciding the existence of a pure Nash equilibrium in strategic games or deciding the existence of a pure Nash or a subgame perfect Nash equilibrium with a given payoff in finite perfect information extensive games. We address the fundamental question of how can we represent a game with a large number of players? We propose three ways of representing a game with different degrees of succinctness for the components of the game. For perfect information extensive games we show that when the number of moves of each player is large and the input game is represented succinctly these problems are PSPACE-complete. In contraposition, when the game is described explicitly by means of its associated tree all these problems are decidable in polynomial time. For strategic games we show that the complexity of deciding the existence of a pure Nash equilibrium depends on the succinctness of the game representation and then on the size of the action sets. In particular we show that it is NP-complete, when the number of players is large and the number of actions for each player is constant, and that the problem is -complete when the number of players is a constant and the size of the action sets is exponential in the size of the game representation. Again when the game is described explicitly the problem is decidable in polynomial time.