Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPAC Learnability of Approximate Nash Equilibrium in Bimatrix Games
161
0
0.0
(
0
)
Added by
Zhijian Duan
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Computing Nash equilibrium in bimatrix games is PPAD-hard, and many works have focused on the approximate solutions. When games are generated from a fixed unknown distribution, learning a Nash predictor via data-driven approaches can be preferable. In this paper, we study the learnability of approximate Nash equilibrium in bimatrix games. We prove that Lipschitz function class is agnostic Probably Approximately Correct (PAC) learnable with respect to Nash approximation loss. Additionally, to demonstrate the advantages of learning a Nash predictor, we develop a model that can efficiently approximate solutions for games under the same distribution. We show by experiments that the solutions from our Nash predictor can serve as effective initializing points for other Nash solvers.
rate research
Read More
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%$.
We investigate the problem of equilibrium computation for large $n$-player games. Large games have a Lipschitz-type property that no single players utility is greatly affected by any other individual players actions. In this paper, we mostly focus on the case where any change of strategy by a player causes other players payoffs to change by at most $frac{1}{n}$. We study algorithms having query access to the games payoff function, aiming to find $epsilon$-Nash equilibria. We seek algorithms that obtain $epsilon$ as small as possible, in time polynomial in $n$. Our main result is a randomised algorithm that achieves $epsilon$ approaching $frac{1}{8}$ for 2-strategy games in a {em completely uncoupled} setting, where each player observes her own payoff to a query, and adjusts her behaviour independently of other players payoffs/actions. $O(log n)$ rounds/queries are required. We also show how to obtain a slight improvement over $frac{1}{8}$, by introducing a small amount of communication between the players. Finally, we give extension of our results to large games with more than two strategies per player, and alternative largeness parameters.
We present a direct reduction from k-player games to 2-player games that preserves approximate Nash equilibrium. Previously, the computational equivalence of computing approximate Nash equilibrium in k-player and 2-player games was established via an indirect reduction. This included a sequence of works defining the complexity class PPAD, identifying complete problems for this class, showing that computing approximate Nash equilibrium for k-player games is in PPAD, and reducing a PPAD-complete problem to computing approximate Nash equilibrium for 2-player games. Our direct reduction makes no use of the concept of PPAD, thus eliminating some of the difficulties involved in following the known indirect reduction.
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.
Computing a Nash equilibrium (NE) is a central task in computer science. An NE is a particularly appropriate solution concept for two-agent settings because coalitional deviations are not an issue. However, even in this case, finding an NE is PPAD-complete. In this paper, we combine path following algorithms with local search techniques to design new algorithms for finding exact and approximate NEs. We show that our algorithms largely outperform the state of the art and that almost all the known benchmark game classes are easily solvable or approximable (except for the GAMUT CovariantGameRand class).
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
