On the communication complexity of approximate Nash equilibria
From MaRDI portal
Publication:2442839
DOI10.1016/j.geb.2014.01.009zbMath1290.91017arXiv1302.3793OpenAlexW2059732663MaRDI QIDQ2442839
Paul W. Goldberg, Arnoud Pastink
Publication date: 1 April 2014
Published in: Games and Economic Behavior, Algorithmic Game Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1302.3793
Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) 2-person games (91A05) Signaling and communication in game theory (91A28) Approximation algorithms (68W25)
Related Items
Communication complexity of approximate Nash equilibria, A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games, High-Dimensional Nash Equilibria Problems and Tensors Applications, Distributed Methods for Computing Approximate Equilibria, Unnamed Item, Distributed methods for computing approximate equilibria, On the existence of Pareto efficient and envy-free allocations, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
Cites Work
- Unnamed Item
- Unnamed Item
- Approximate well-supported Nash equilibria below two-thirds
- On the approximation performance of fictitious play in finite games
- A new polynomial-time algorithm for linear programming
- Stochastic uncoupled dynamics and Nash equilibrium
- How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
- Well supported approximate equilibria in bimatrix games
- A note on approximate Nash equilibria
- Calibrated learning and correlated equilibrium
- Non-cooperative games
- On Learning Algorithms for Nash Equilibria
- Settling the complexity of computing two-player Nash equilibria
- A Simple Adaptive Procedure Leading to Correlated Equilibrium
- Communication Complexity
- The Complexity of Computing a Nash Equilibrium
- Probability Inequalities for Sums of Bounded Random Variables
