Strategizing against Learners in Bayesian Games

Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:5221-5252, 2022.

Abstract

We study repeated two-player games where one of the players, the learner, employs a no-regret learning strategy, while the other, the optimizer, is a rational utility maximizer. We consider general Bayesian games, where the payoffs of both the optimizer and the learner could depend on the type, which is drawn from a publicly known distribution, but revealed privately to the learner. We address the following questions: (a) what is the bare minimum that the optimizer can guarantee to obtain regardless of the no-regret learning algorithm employed by the learner? (b) are there learning algorithms that cap the optimizer payoff at this minimum? (c) can these algorithms be implemented efficiently? While building this theory of optimizer-learner interactions, we define a new combinatorial notion of regret called polytope swap regret, that could be of independent interest in other settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-mansour22a, title = {Strategizing against Learners in Bayesian Games}, author = {Mansour, Yishay and Mohri, Mehryar and Schneider, Jon and Sivan, Balasubramanian}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {5221--5252}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/mansour22a/mansour22a.pdf}, url = {https://proceedings.mlr.press/v178/mansour22a.html}, abstract = {We study repeated two-player games where one of the players, the learner, employs a no-regret learning strategy, while the other, the optimizer, is a rational utility maximizer. We consider general Bayesian games, where the payoffs of both the optimizer and the learner could depend on the type, which is drawn from a publicly known distribution, but revealed privately to the learner. We address the following questions: (a) what is the bare minimum that the optimizer can guarantee to obtain regardless of the no-regret learning algorithm employed by the learner? (b) are there learning algorithms that cap the optimizer payoff at this minimum? (c) can these algorithms be implemented efficiently? While building this theory of optimizer-learner interactions, we define a new combinatorial notion of regret called polytope swap regret, that could be of independent interest in other settings.} }
Endnote
%0 Conference Paper %T Strategizing against Learners in Bayesian Games %A Yishay Mansour %A Mehryar Mohri %A Jon Schneider %A Balasubramanian Sivan %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-mansour22a %I PMLR %P 5221--5252 %U https://proceedings.mlr.press/v178/mansour22a.html %V 178 %X We study repeated two-player games where one of the players, the learner, employs a no-regret learning strategy, while the other, the optimizer, is a rational utility maximizer. We consider general Bayesian games, where the payoffs of both the optimizer and the learner could depend on the type, which is drawn from a publicly known distribution, but revealed privately to the learner. We address the following questions: (a) what is the bare minimum that the optimizer can guarantee to obtain regardless of the no-regret learning algorithm employed by the learner? (b) are there learning algorithms that cap the optimizer payoff at this minimum? (c) can these algorithms be implemented efficiently? While building this theory of optimizer-learner interactions, we define a new combinatorial notion of regret called polytope swap regret, that could be of independent interest in other settings.
APA
Mansour, Y., Mohri, M., Schneider, J. & Sivan, B.. (2022). Strategizing against Learners in Bayesian Games. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:5221-5252 Available from https://proceedings.mlr.press/v178/mansour22a.html.

Related Material