Optimal Rates for Feasible Payoff Set Estimation in Games
This work establishes learning-theoretic foundations for set-valued payoff inference, enabling counterfactual analysis and mechanism design in applications like auctions, pricing, and security games, though it is incremental in providing optimal rates for an existing problem.
The paper tackles the problem of estimating the full set of payoff functions consistent with observed equilibrium play in games, without prior knowledge of the game or equilibrium, and provides the first minimax-optimal rates for this estimation in terms of precision on the Hausdorff metric, applicable to exact and approximate equilibria in zero-sum and general-sum games.
We study a setting in which two players play a (possibly approximate) Nash equilibrium of a bimatrix game, while a learner observes only their actions and has no knowledge of the equilibrium or the underlying game. A natural question is whether the learner can rationalize the observed behavior by inferring the players' payoff functions. Rather than producing a single payoff estimate, inverse game theory aims to identify the entire set of payoffs consistent with observed behavior, enabling downstream use in, e.g., counterfactual analysis and mechanism design across applications like auctions, pricing, and security games. We focus on the problem of estimating the set of feasible payoffs with high probability and up to precision $ε$ on the Hausdorff metric. We provide the first minimax-optimal rates for both exact and approximate equilibrium play, in zero-sum as well as general-sum games. Our results provide learning-theoretic foundations for set-valued payoff inference in multi-agent environments.