Regret Minimization Algorithms for the Follower’s Behaviour Identification in Leadership Games

Lorenzo Bisi, Giuseppe De Nittis, Francesco Trov‘ò, Marcello Restelli, Nicola Gatti
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:651-660, 2017.

Abstract

We study for the first time, a leadership game in which one agent, acting as leader, faces another agent, acting as follower, whose behaviour is not known a priori by the leader, being one among a set of possible behavioural profiles. The main motivation is that in real-world applications the common game-theoretical assumption of perfect rationality is rarely met, and any specific assumption on bounded rationality models, if wrong, could lead to a significant loss for the leader. The question we pose is whether and how the leader can learn the behavioural profile of a follower in leadership games. This is a “natural” online identification problem: in fact, the leader aims at identifying the follower’s behavioural profile to exploit at best the potential non-rationality of the opponent, while minimizing the regret due to the initial lack of information. We propose two algorithms based on different approaches and we provide a regret analysis. Furthermore, we experimentally evaluate the pseudo-regret of the algorithms in concrete leadership games, showing that our algorithms outperform the online learning algorithms available in the state of the art.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-bisi17a, title = {Regret Minimization Algorithms for the Follower’s Behaviour Identification in Leadership Games}, author = {Bisi, Lorenzo and De Nittis, Giuseppe and Trov`{\`o}, Francesco and Restelli, Marcello and Gatti, Nicola}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {651--660}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/bisi17a/bisi17a.pdf}, url = {https://proceedings.mlr.press/r15/bisi17a.html}, abstract = {We study for the first time, a leadership game in which one agent, acting as leader, faces another agent, acting as follower, whose behaviour is not known a priori by the leader, being one among a set of possible behavioural profiles. The main motivation is that in real-world applications the common game-theoretical assumption of perfect rationality is rarely met, and any specific assumption on bounded rationality models, if wrong, could lead to a significant loss for the leader. The question we pose is whether and how the leader can learn the behavioural profile of a follower in leadership games. This is a “natural” online identification problem: in fact, the leader aims at identifying the follower’s behavioural profile to exploit at best the potential non-rationality of the opponent, while minimizing the regret due to the initial lack of information. We propose two algorithms based on different approaches and we provide a regret analysis. Furthermore, we experimentally evaluate the pseudo-regret of the algorithms in concrete leadership games, showing that our algorithms outperform the online learning algorithms available in the state of the art.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Regret Minimization Algorithms for the Follower’s Behaviour Identification in Leadership Games %A Lorenzo Bisi %A Giuseppe De Nittis %A Francesco Trov‘ò %A Marcello Restelli %A Nicola Gatti %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-bisi17a %I PMLR %P 651--660 %U https://proceedings.mlr.press/r15/bisi17a.html %V R15 %X We study for the first time, a leadership game in which one agent, acting as leader, faces another agent, acting as follower, whose behaviour is not known a priori by the leader, being one among a set of possible behavioural profiles. The main motivation is that in real-world applications the common game-theoretical assumption of perfect rationality is rarely met, and any specific assumption on bounded rationality models, if wrong, could lead to a significant loss for the leader. The question we pose is whether and how the leader can learn the behavioural profile of a follower in leadership games. This is a “natural” online identification problem: in fact, the leader aims at identifying the follower’s behavioural profile to exploit at best the potential non-rationality of the opponent, while minimizing the regret due to the initial lack of information. We propose two algorithms based on different approaches and we provide a regret analysis. Furthermore, we experimentally evaluate the pseudo-regret of the algorithms in concrete leadership games, showing that our algorithms outperform the online learning algorithms available in the state of the art. %Z Reissued by PMLR on 04 October 2026.
APA
Bisi, L., De Nittis, G., Trov‘ò, F., Restelli, M. & Gatti, N.. (2017). Regret Minimization Algorithms for the Follower’s Behaviour Identification in Leadership Games. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:651-660 Available from https://proceedings.mlr.press/r15/bisi17a.html. Reissued by PMLR on 04 October 2026.

Related Material