On the communication complexity of approximate Nash equilibria
From MaRDI portal
Publication:2442839
DOI10.1016/j.geb.2014.01.009zbMath1290.91017arXiv1302.3793MaRDI 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
68Q25: Analysis of algorithms and problem complexity
91A10: Noncooperative games
91A05: 2-person games
91A28: Signaling and communication in game theory
68W25: Approximation algorithms
Related Items
High-Dimensional Nash Equilibria Problems and Tensors Applications, Unnamed Item, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria, A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games, Distributed methods for computing approximate equilibria, On the existence of Pareto efficient and envy-free allocations, Communication complexity of approximate Nash equilibria, Distributed Methods for Computing Approximate 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