Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBounding the Uncertainty of Graphical Games: The Complexity of Simple Requirements, Pareto and Strong Nash Equilibria
611
0
0.0
(
0
)
Added by
Gianluigi Greco
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We investigate the complexity of bounding the uncertainty of graphical games, and we provide new insight into the intrinsic difficulty of computing Nash equilibria. In particular, we show that, if one adds very simple and natural additional requirements to a graphical game, the existence of Nash equilibria is no longer guaranteed, and computing an equilibrium is an intractable problem. Moreover, if stronger equilibrium conditions are required for the game, we get hardness results for the second level of the polynomial hierarchy. Our results offer a clear picture of the complexity of mixed Nash equilibria in graphical games, and answer some open research questions posed by Conitzer and Sandholm (2003).
rate research
Read More
Graphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They have wide applications ranging from computer science to economics and biology. Yet, even though a players payoff only depends on the actions of their direct neighbors in graphical games, computing the Nash equilibria and making statements about the convergence time of natural local dynamics in particular can be highly challenging. In this work, we present a novel approach for classifying complexity of Nash equilibria in graphical games by establishing a connection to local graph algorithms, a subfield of distributed computing. In particular, we make the observation that the equilibria of graphical games are equivalent to locally verifiable labelings (LVL) in graphs; vertex labelings which are verifiable with a constant-round local algorithm. This connection allows us to derive novel lower bounds on the convergence time to equilibrium of best-response dynamics in graphical games. Since we establish that distributed convergence can sometimes be provably slow, we also introduce and give bounds on an intuitive notion of time-constrained inefficiency of best responses. We exemplify how our results can be used in the implementation of mechanisms that ensure convergence of best responses to a Nash equilibrium. Our results thus also give insight into the convergence of strategy-proof algorithms for graphical games, which is still not well understood.
We prove that computing a Nash equilibrium of a two-player ($n times n$) game with payoffs in $[-1,1]$ is PPAD-hard (under randomized reductions) even in the smoothed analysis setting, smoothing with noise of constant magnitude. This gives a strong negative answer to conjectures of Spielman and Teng [ST06] and Cheng, Deng, and Teng [CDT09]. In contrast to prior work proving PPAD-hardness after smoothing by noise of magnitude $1/operatorname{poly}(n)$ [CDT09], our smoothed complexity result is not proved via hardness of approximation for Nash equilibria. This is by necessity, since Nash equilibria can be approximated to constant error in quasi-polynomial time [LMM03]. Our results therefore separate smoothed complexity and hardness of approximation for Nash equilibria in two-player games. The key ingredient in our reduction is the use of a random zero-sum game as a gadget to produce two-player games which remain hard even after smoothing. Our analysis crucially shows that all Nash equilibria of random zero-sum games are far from pure (with high probability), and that this remains true even after smoothing.
We study the problem of checking for the existence of constrained pure Nash equilibria in a subclass of polymatrix games defined on weighted directed graphs. The payoff of a player is defined as the sum of nonnegative rational weights on incoming edges from players who picked the same strategy augmented by a fixed integer bonus for picking a given strategy. These games capture the idea of coordination within a local neighbourhood in the absence of globally common strategies. We study the decision problem of checking whether a given set of strategy choices for a subset of the players is consistent with some pure Nash equilibrium or, alternatively, with all pure Nash equilibria. We identify the most natural tractable cases and show NP or coNP-completness of these problems already for unweighted DAGs.
Extensive study on the complexity of computing Nash Equilibrium has resulted in the definition of the complexity class PPAD by Papadimitriou cite{Papa2}, Subsequently shown to be PPAD-complete, first by Daskalakis, Goldberg, and Papadimitriou cite{Papa} for $3$ or more and even for the bimatrix case by Chen and Deng cite{Chen}. On the other hand, it is well known that Nash equilibria of games with smooth payoff functions are generally Pareto-inefficient cite{Dubey} In the spirit of Von Neumanns Minimax Theorem and its polynomial-time solvability via Linear Programming, Kalantari cite{Kalantari} has described a multilinear minimax relaxation (MMR) that provides an approximation to a convex combination of expected payoffs in any Nash Equilibrium via LP. In this paper, we study this relaxation for the bimatrix game, solving its corresponding LP formulation and comparing its solution to the solution computed by the Lemke-Howson algorithm. We also give a game theoretic interpretation of MMR for the bimatrix game involving a meta-player. Our relaxation has the following theoretical advantages: (1) It can be computed in polynomial time; (2) For at least one player, the computed MMR payoff is at least as good any Nash Equilibrium payoff; (3) There exists a convex scaling of the payoff matrices giving equal payoffs. Such a solution is a satisfactory compromise. Computationally, we have compared our approach with the state-of-the-art implementation of the Lemke-Howson algorithm cite{Lemke}. We have observed the following advantages: (i) MMR outperformed Lemke-Howson in time complexity; (ii) In about $80%$ of the cases the MMR payoffs for both players are better than any Nash Equilibria; (iii) in the remaining $20%$, while one players payoff is better than any Nash Equilibrium payoff, the other players payoff is only within a relative error of $17%$.
Nearly a decade ago, Azrieli and Shmaya introduced the class of $lambda$-Lipschitz games in which every players payoff function is $lambda$-Lipschitz with respect to the actions of the other players. They showed that such games admit $epsilon$-approximate pure Nash equilibria for certain settings of $epsilon$ and $lambda$. They left open, however, the question of how hard it is to find such an equilibrium. In this work, we develop a query-efficient reduction from more general games to Lipschitz games. We use this reduction to show a query lower bound for any randomized algorithm finding $epsilon$-approximate pure Nash equilibria of $n$-player, binary-action, $lambda$-Lipschitz games that is exponential in $frac{nlambda}{epsilon}$. In addition, we introduce ``Multi-Lipschitz games, a generalization involving player-specific Lipschitz values, and provide a reduction from finding equilibria of these games to finding equilibria of Lipschitz games, showing that the value of interest is the sum of the individual Lipschitz parameters. Finally, we provide an exponential lower bound on the deterministic query complexity of finding $epsilon$-approximate correlated equilibria of $n$-player, $m$-action, $lambda$-Lipschitz games for strong values of $epsilon$, motivating the consideration of explicitly randomized algorithms in the above results. Our proof is arguably simpler than those previously used to show similar results.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
