Empirical distribution of equilibrium play and its testing application

DOI10.1287/MOOR.2016.0794zbMATH Open1360.91009arXiv1310.7654OpenAlexW1941744740MaRDI QIDQ2976138FDOQ2976138

Authors: Yakov Babichenko, Siddharth Barman, Ron Peretz 

Publication date: 13 April 2017

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Abstract: We show that in any $n$-player $m$-action normal-form game, we can obtain an approximate equilibrium by sampling any mixed-action equilibrium a small number of times. We study three types of equilibria: Nash, correlated and coarse correlated. For each one of them we obtain upper and lower bounds on the number of samples required for the empirical distribution over the sampled action profiles to form an approximate equilibrium with probability close to one. These bounds imply that using a small number of samples we can test whether or not players are playing according to an approximate equilibrium, even in games where $n$ and $m$ are large. In addition, our results substantially improve previously known upper bounds on the support size of approximate equilibria in games with many players. In particular, for all the three types of equilibria we show the existence of approximate equilibrium with support size polylogarithmic in $n$ and $m$, whereas the previously best-known upper bounds were polynomial in $n$.

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

Recommendations

• Approximate Nash Equilibria for Multi-player Games
• On Nash-equilibria of approximation-stable games
• Query complexity of approximate nash equilibria
• Query complexity of approximate Nash equilibria
• Simple search methods for finding a Nash equilibrium

zbMATH Keywords

hypothesis testingsampling methodapproximate Nash equilibrium

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Approximation algorithms (68W25) (n)-person games, (n>2) (91A06)

Cites Work

• Non-cooperative games
• Title not available (Why is that?)
• Probability Inequalities for Sums of Bounded Random Variables
• Testing closeness of discrete distributions
• Subjectivity and correlation in randomized strategies
• Title not available (Why is that?)
• Existence of sparsely supported correlated equilibria
• On sparse approximations to randomized strategies and convex combinations
• Asymptotic approximations for the distributions of multinomial goodness- of-fit statistics
• On testing expansion in bounded-degree graphs
• Approximate Nash Equilibria for Multi-player Games
• Sensor Network Gossiping or How to Break the Broadcast Lower Bound

Cited In (7)

• A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
• A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
• Approximating the existential theory of the reals
• Learning convex partitions and computing game-theoretic equilibria from best response queries
• Communication complexity of correlated equilibrium with small support
• Approximating the existential theory of the reals
• Multilinear games

This page was built for publication: Empirical distribution of equilibrium play and its testing application

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