Regret minimization algorithms for the follower's behavior identification in leadership games

We study for the first time, to the best of our knowledge, 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 inspired by security domains, showing that our algorithms dramatically outperform the online learning algorithms available in the state of the art.

In questo lavoro studiamo per la prima volta un leadership game, nel quale un agente, agendo da Leader, affronta un altro agente, che agisce da Follower, il cui comportamento non è conosciuto a priori dal leader, ma fa parte di un insieme di possibili profili comportamentali. La motivazione principale è che nelle applicazioni reali l'assunzione comunemente fatta in Teoria dei giochi, ovvero che l'avversario sia completamente razionale, si verifica raramente ed ogni assunzione specifica, se sbagliata, può portare a una perdita significativa per il leader. La domanda che ci poniamo è se e come il leader possa apprendere il profilo comportamentale di un follower nei leadership games. Questo è per sua natura un problema di online identification: infatti il leader cerca di identificare il profilo comportamentale del follower per sfruttare al meglio la potenziale non-razionalità dell'avversario, minimizzando al contempo il regret dovuto all'iniziale mancanza di informazione. Proponiamo due algoritmi basati su diversi approcci e forniamo una analisi del regret. Inoltre, valutiamo sperimentalmente lo pseudo-regret degli algoritmi in leadership game concreti, ispirati da contesti di sicurezza, mostrando che i nostri algoritmi superano drasticamente gli algoritmi disponibili nello stato dell'arte.