Leadership games: multiple followers, multiple leaders, and perfection

Over the last years algorithmic game theory has received growing interest in AI, as it allows to tackle complex real-world scenarios involving multiple artificial agents engaged in a competitive interaction. These settings call for rational agents endowed with the capability of reasoning strategically, i.e., taking into account not only how their actions affect the external environment, but also their impact on the behavior of other agents. This is achieved by exploiting ideas from game theory, and, in particular, equilibrium concepts that prescribe the agents how to behave strategically. Thus, the challenge faced by the researchers working in algorithmic game theory is to design scalable computational tools that enable the adoption of such equilibrium notions in real-world problems. In this thesis, we study the computational properties of a specific game-theoretic model known as the Stackelberg paradigm. In a Stackelberg game, there are some players who act as leaders with the ability to commit to a strategy beforehand, whereas the other players are followers who decide how to play after observing the commitment. Recently, Stackelberg games and the corresponding Stackelberg equilibria have received considerable attention from the algorithmic game theory community, since they have been successfully applied in many real-world settings, such as, e.g., in the security domain, toll-setting problems, and network routing. Nevertheless, the majority of the computational works on Stackelberg games study the case in which there is one leader and one follower, focusing, in most of the cases, on instances enjoying very specific structures, such as security games. A comprehensive study of general Stackelberg games with (possibly) multiple leaders and followers is still lacking. In this thesis, we make substantial steps towards filling this gap. In particular, in the first part of the work, we address the largely unexplored problem of computing Stackelberg equilibria in games with a single leader and multiple followers, focusing on the case in which the latter play a Nash equilibrium after observing the leader's commitment. We analyze different classes of games, from general normal-form Stackelberg games to games with a compact representation, namely, Stackelberg polymatrix and congestion games. Then, in the second part of the thesis, we study Stackelberg games with multiple leaders, proposing a new way to apply the Stackelberg paradigm in such settings. Our idea is to let the leaders decide whether they want to participate in the commitment or defect from it by becoming followers. This is orchestrated by a suitably defined agreement protocol, which allows us to introduce interesting properties for the commitments. Finally, in the last part of the thesis, we focus on Stackelberg games with a sequential structure, addressing, for the first time in such setting, the problem of equilibrium refinement. This problem has been widely investigated for the Nash equilibrium, as it is well-known that refinements can amend some of its weaknesses, such as sub-optimality off the equilibrium path. In this work, we show that such issues also arise in Stackelberg settings, and, thus, we introduce and study Stackelberg equilibrium refinements based on the idea of trembling-hand perfection so as to solve them.

Negli ultimi anni la teoria dei giochi algoritmica ha ricevuto un interesse sempre maggiore in Intelligenza Artificiale, in quanto ha permesso di affrontare problemi reali dove più agenti artificiali interagiscono in competizione. Questi scenari necessitano di agenti razionali in grado di compiere ragionamenti strategici, tenendo in considerazione non solo come le loro azioni influenzano l’ambiente esterno, ma anche il loro impatto sul comportamento degli altri agenti. Questo obbiettivo è raggiunto con l’ausilio della teoria dei giochi, in particolar dei concetti di equilibrio che definiscono il comportamento strategico degli agenti. La sfida affrontata dai ricercatori in teoria dei giochi algoritmica è come progettare algoritmi scalabili, così da abilitare l’uso di queste nozioni di equilibrio in problemi reali. In questa tesi, si studiano le proprietà computazionali di uno specifico modello della teoria dei giochi, noto come il paradigma di Stackelberg. In un gioco Stackelberg, alcuni giocatori agiscono da leader con l’abilità di annunciare la loro strategia prima degli altri, i quali svolgono il ruolo di follower, decidendo come giocare una volta osservata la strategia del leader. Recentemente, I giochi Stackelberg e i loro corrispondenti equilibri Stackelberg hanno ricevuto una attenzione considerevole da parte della comunità scientifica, in quanto sono stati applicati in molti scenari reali, come, ad esempio, sicurezza fisica o informatica, scelta dei pedaggi, e instradamento di pacchetti su Internet. Nonostante questo, la maggioranza degli studi computazionali sui giochi Stackelberg sono ristretti al caso specifico in cui vi è un solo leader e un solo follower, ponendo l’attenzione su istanze con strutture specifiche, come i cosiddetti security games. Un’analisi comprensiva dei giochi Stackelberg con molteplici leader e follower non è ancora stata svolta. Questa tesi compie un passo importante verso questa analisi. In particolare, nella prima parte, si studia il problema di calcolare un equilibrio Stackelberg in giochi con un solo leader e molteplici follower, nel caso in cui quest’ultimi giocano un equilibrio di Nash dopo aver osservato la strategia del leader. Si analizzano diverse classi di gioco, dai generali giochi Stackelberg in forma normale fino ad arrivare ai giochi con una rappresentazione compatta, come i giochi polymatrix e giochi a congestione. Nella seconda parte, si studiano giochi Stackelberg con molteplici leader, proponendo un nuovo approccio al paradigma Stackelberg. L’idea è quella di permettere ai leader di scegliere se partecipare all’annuncio di una strategia congiunta, oppure rifiutare diventando follower. Questo processo viene gestito da un protocollo di accordo appositamente definito, il quale permette di individuare interessanti proprietà degli equilibri. Infine, nella terza e ultima parte, si studiano giochi Stackelberg con una struttura sequenziale, affrontando per la prima volta il problema del raffinamento degli equilibri Stackelberg. Questo problema è già stato largamente studiato per il caso dell’equilibrio di Nash, in quanto è noto che i raffinamenti possono risolvere alcuni dei suoi problemi, come la subottimalità fuori dal percorso di equilibrio. In questa tesi, si mostra prima che questi problemi possono insorgere anche nei giochi Stackelberg, e successivamente si propone un raffinamento dell’equilibrio di Stackelberg basato sull’idea di perfezione.