On the communication complexity of approximate Nash equilibria

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

zbMATH Keywords

efficient algorithmsmixed strategyapproximate equilibriatwo player

Mathematics Subject Classification ID

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 (9)

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

This page was built for publication: On the communication complexity of approximate Nash equilibria