2022/08/12 by Cyrus Cousins, Bhaskar Mishra, Cousins, Cyrus +5
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Bayesian Modeling and Causal Inference #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Simulation Techniques and Applications #Sports Analytics and Performance
paper · pdf · doi:10.48550/arxiv.2208.06400
openalex publication_date 2022/08/12 · openalex created_date 2022/08/16 · openalex updated_date 2026/07/28
Empirical game-theoretic analysis (EGTA) is primarily focused on learning the equilibria of simulation-based games. Recent approaches have tackled this problem by learning a uniform approximation of the game's utilities, and then applying precision-recall theorems: i.e., all equilibria of the true game are approximate equilibria in the estimated game, and vice-versa. In this work, we generalize this approach to all game properties that are well behaved (i.e., Lipschitz continuous in utilities), including regret (which defines Nash and correlated equilibria), adversarial values, and power-mean and Gini social welfare. Further, we introduce a novel algorithm -- progressive sampling with pruning (PSP) -- for learning a uniform approximation and thus any well-behaved property of a game, which prunes strategy profiles once the corresponding players' utilities are well-estimated, and we analyze its data and query complexities in terms of the a priori unknown utility variances. We experiment with our algorithm extensively, showing that 1) the number of queries that PSP saves is highly sensitive to the utility variance distribution, and 2) PSP consistently outperforms theoretical upper bounds, achieving significantly lower query complexities than natural baselines. We conclude with experiments that uncover some of the remaining difficulties with learning properties of simulation-based games, in spite of recent advances in statistical EGTA methodology, including those developed herein.