Communication complexity of approximate Nash equilibria

DOI10.1016/j.geb.2020.07.005zbMath1497.91015arXiv1608.06580OpenAlexW3046976141MaRDI QIDQ2155907

Yakov Babichenko, Aviad Rubinstein

Publication date: 15 July 2022

Published in: Games and Economic Behavior, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1608.06580

zbMATH Keywords

convergence ratecommunication complexityapproximate Nash equilibriauncoupled dynamicsconvergence rate of uncoupled dynamics

Mathematics Subject Classification ID

Noncooperative games (91A10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Rationality and learning in game theory (91A26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Equilibrium refinements (91A11)

Related Items

Deterministic Communication vs. Partition Number ⋮ The communication complexity of graphical games on grid graphs ⋮ Learning convex partitions and computing game-theoretic equilibria from best response queries ⋮ Query-to-Communication Lifting for BPP ⋮ Unnamed Item ⋮ Distributed methods for computing approximate equilibria ⋮ Unnamed Item ⋮ On the existence of Pareto efficient and envy-free allocations ⋮ The complexity of the parity argument with potential ⋮ Deciphering chaos in evolutionary games ⋮ Adventures in monotone complexity and TFNP ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Optimally Deceiving a Learning Leader in Stackelberg Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completely uncoupled dynamics and Nash equilibria
• Distributed methods for computing approximate equilibria
• Stochastic uncoupled dynamics and Nash equilibrium
• Exponential lower bounds for finding Brouwer fixed points
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
• Learning by trial and error
• Regret-based continuous-time dynamics.
• The query complexity of correlated equilibria
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Separation of the monotone NC hierarchy
• Simple complexity from imitation games
• Polynomial-time computation of exact correlated equilibrium in compact games
• Global Nash convergence of Foster and Young's regret testing
• On the communication complexity of approximate Nash equilibria
• Non-cooperative games
• Can Almost Everybody be Almost Happy?
• Simple Adaptive Strategies
• Rational Learning Leads to Nash Equilibrium
• Settling the complexity of computing two-player Nash equilibria
• Smoothed analysis of algorithms
• On the Computational Power of Demand Queries
• Monotone circuits for matching require linear depth
• Inapproximability of Nash Equilibrium
• Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
• The Complexity of Computing a Nash Equilibrium
• The communication complexity of local search
• Query complexity of approximate nash equilibria
• Computing correlated equilibria in multi-player games