Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLogarithmic Query Complexity for Approximate Nash Computation in Large Games
394
0
0.0
(
0
)
Added by
Francisco Javier Marmolejo-Coss\\'io
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
This paper shows the existence of $mathcal{O}(frac{1}{n^gamma})$-Nash equilibria in $n$-player noncooperative aggregative games where the players cost functions depend only on their own action and the average of all the players actions, and is lower semicontinuous in the former while $gamma$-H{o}lder continuous in the latter. Neither the action sets nor the cost functions need to be convex. For an important class of aggregative games which includes congestion games with $gamma$ being 1, a proximal best-reply algorithm is used to construct an $mathcal{O}(frac{1}{n})$-Nash equilibria with at most $mathcal{O}(n^3)$ iterations. These results are applied in a numerical example of demand-side management of the electricity system. The asymptotic performance of the algorithm is illustrated when $n$ tends to infinity.
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.
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 explore the complexity of nucleolus computation in b-matching games on bipartite graphs. We show that computing the nucleolus of a simple b-matching game is NP-hard even on bipartite graphs of maximum degree 7. We complement this with partial positive results in the special case where b values are bounded by 2. In particular, we describe an efficient algorithm when a constant number of vertices satisfy b(v) = 2 as well as an efficient algorithm for computing the non-simple b-matching nucleolus when b = 2.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
