Distributed Methods for Computing Approximate Equilibria

DOI10.1007/978-3-662-54110-4_2MaRDI QIDQ2959815zbMATH OpenOpenAlexFDO

Authors Argyrios Deligkas, Michail Fasoulakis, John Fearnley, Marcin Jurdziński, Rahul Savani, Artur Czumaj

Publication date 10 February 2017

Published in Web and Internet Economics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.03315, http://wrap.warwick.ac.uk/103481/1/WRAP-distributed-methods-computing-approximate-Czumaj-2018.pdf

zbMATH Keywords

approximate Nash equilibriabimatrix games

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) 2-person games (91A05)

Abstract: We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same time (for example, by solving a single LP that combines the two players payoffs), our algorithm first solves two independent LPs, each of which is derived from one of the two payoff matrices, and then compute approximate Nash equilibria using only limited communication between the players. Our method has several applications for improved bounds for efficient computations of approximate Nash equilibria in bimatrix games. First, it yields a best polynomial-time algorithm for computing emph{approximate well-supported Nash equilibria (WSNE)}, which guarantees to find a 0.6528-WSNE in polynomial time. Furthermore, since our algorithm solves the two LPs separately, it can be used to improve upon the best known algorithms in the limited communication setting: the algorithm can be implemented to obtain a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and finds a 0.6528-WSNE. The algorithm can also be carried out to beat the best known bound in the query complexity setting, requiring $O(nlogn)$ payoff queries to compute a 0.6528-WSNE. Finally, our approach can also be adapted to provide the best known communication efficient algorithm for computing emph{approximate Nash equilibria}: it uses poly-logarithmic communication to find a 0.382-approximate Nash equilibrium.

Recommendations

• Distributed methods for computing approximate equilibria
• Distributed algorithms for the computation of noncooperative equilibria
• A distributed algorithm for solving mixed equilibrium problems
• Approximations in Distributed Optimization
• Distributed Computation of Equilibria in Misspecified Convex Stochastic Nash Games
• Distributed Computation of Nash Equilibria in Linear-Quadratic Stochastic Differential Games
• On the convergence to Nash equilibrium in problems of distributed computing
• Distributed computation of Pareto solutions in n-player games
• Distributed Nash Equilibrium Seeking by a Consensus Based Approach
• Distributed computation of equilibria in monotone Nash games via iterative regularization techniques

Cites work

• A note on approximate Nash equilibria
• An optimization approach for approximate Nash equilibria
• Approximate well-supported Nash equilibria in symmetric bimatrix games
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
• Learning equilibria of games via payoff queries
• New algorithms for approximate Nash equilibria in bimatrix games
• Non-cooperative games
• Settling the complexity of computing two-player Nash equilibria
• The complexity of computing a Nash equilibrium
• Well supported approximate equilibria in bimatrix games

Cited in

(16)

• New algorithms for approximate Nash equilibria in bimatrix games
• Distributed algorithms for the computation of noncooperative equilibria
• Inapproximability results for constrained approximate Nash equilibria
• A distributed algorithm to obtain repeated games equilibria with discounting
• Convergence to equilibria in distributed, selfish reallocation processes with weighted tasks
• Inapproximability results for approximate Nash equilibria
• An optimization approach for approximate Nash equilibria
• On distributed dynamic programming
• Communication complexity of correlated equilibrium with small support
• Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
• A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
• Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
• Distributed methods for computing approximate equilibria
• Automating approximation analysis for Nash equilibria algorithms in two-player games
• On the optimal mixing problem of approximate Nash equilibria in bimatrix games
• On the optimal mixing problem of approximate Nash equilibria in bimatrix games

This page was built for publication: Distributed Methods for Computing Approximate Equilibria

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959815)