Optimal Rates for Feasible Payoff Set Estimation in Games

Annalisa Barbara, Riccardo Poiani, Martino Bernasconi, Andrea Celli
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:6580-6629, 2026.

Abstract

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

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-barbara26a, title = {Optimal Rates for Feasible Payoff Set Estimation in Games}, author = {Barbara, Annalisa and Poiani, Riccardo and Bernasconi, Martino and Celli, Andrea}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {6580--6629}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/barbara26a/barbara26a.pdf}, url = {https://proceedings.mlr.press/v306/barbara26a.html}, abstract = {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 $\epsilon$ 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.} }
Endnote
%0 Conference Paper %T Optimal Rates for Feasible Payoff Set Estimation in Games %A Annalisa Barbara %A Riccardo Poiani %A Martino Bernasconi %A Andrea Celli %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-barbara26a %I PMLR %P 6580--6629 %U https://proceedings.mlr.press/v306/barbara26a.html %V 306 %X 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 $\epsilon$ 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.
APA
Barbara, A., Poiani, R., Bernasconi, M. & Celli, A.. (2026). Optimal Rates for Feasible Payoff Set Estimation in Games. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:6580-6629 Available from https://proceedings.mlr.press/v306/barbara26a.html.

Related Material