Empirical distribution of equilibrium play and its testing application

DOI10.1287/MOOR.2016.0794MaRDI QIDQ2976138zbMATH OpenOpenAlexFDO

Authors Yakov Babichenko, Siddharth Barman, Ron Peretz

Publication date 13 April 2017

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

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

zbMATH Keywords

approximate Nash equilibriumhypothesis testingsampling method

Mathematics Subject Classification ID

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

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$.

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

Cites work

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

Cited in

(10)

• Learning convex partitions and computing game-theoretic equilibria from best response queries
• Multilinear games
• Communication complexity of correlated equilibrium with small support
• Approximating the existential theory of the reals
• Approximating the existential theory of the reals
• 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
• Smooth Nash equilibria: algorithms and complexity
• A polynomial-time algorithm for 1/3-approximate Nash equilibria in bimatrix games
• A computer-aided approach for approximate Nash equilibria

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)