Leadership congestion games

Nowadays, in disciplines such as Artificial Intelligence and Machine Learning problems in which a multitude of agents interact with each other are getting more and more frequent and important. Game Theory provides a complete and rigorous mathematical framework suitable to model this kind of situations. Our goal is to study which are the optimal strategies for the players. Moreover, there is the necessity of build up algorithms able to yield a solution, deriving from the theory, in a polynomial amount of time. Congestion Games are a particular class of game that efficiently describes the interaction among agents when they have to choose some resources into an environment. Our aim is to study the Leadership problem in a Congestion Game, that is characterized by the Leader-Follower Equilibrium solution concept, in which a player, the Leader, plays first and then all the others players, the Followers, plays consequently. This thesis provides theoretical and algorithmic results concerning Leadership Congestion Games, under the assumption that all the players must choose only one resource and the Followers always play a pure strategy. This assumptions allow us to obtain useful results both from the theoretical and the algorithmic point of view. Such games naturally arise when, for example, an administrator of a network, the Leader has to decide her optimal access point before the other users, the Followers. We prove the best strategy of the Leader is playing pure strategies as well and the problem belongs to the FP complexity class. We introduce an Integer Linear Programming (ILP) version of our problem. We also provide polynomial time algorithm to compute the value of the Leader. Furthermore, we also demonstrated that the Leader-Follower equilibrium, under the additional assumption that the costs are the same for all players, is a Nash Equilibrium. Finally, we conclude our work with the relative experiment simulations concerning the performance of the algorithms implementing the ILP formulation.

Oggigiorno, in discipline come l’Intelligenza Artificiale e il Machine Learning, riuscire ad affrontarare problemi nei quali una moltitudine di agenti interagisce tra loro è diventata una questione sempre più frequente e importante. La Teoria dei Giochi fornisce un completo e rigoroso ambiente matematico capace di modellizzare queste situazioni. L’obiettivo che ci poniamo è di studiare quale siano le stratgie ottime per i giocatori. Inoltre, esiste la necessità di costruire algoritmi capaci di fornire una soluzione del problema, derivante dalla teoria, in tempo polinomiale. I Giochi a Congestione sono una classe di giochi che rappresentano efficientemente le interazioni tra agenti quando essi devono scegliere alcune risorse all’interno di un contesto specifico. Il nostro scopo è quello di studiare il problema della Leadeship nei Giochi a Congestione, cercando una soluzione rappresentata da un Equilibrio di tipo Leader-Follower, nel quale un giocatore, detto Leader sceglie una strategia, e gli altri giocatori, chiamati Followers, una volta osservata questa strategia, giocano di conseguenza. Questa tesi presenta risultati teorici e algoritmici riguardanti il problema appena descritto, assumendo che tutti i giocatori scelgano esattamente una risorsa e che i Followers giochino sempre in strategie pure. Queste assuzioni ci permettono di ridurre la complessità del problema e ottenere risultati concreti sia dal punto di vista teorico che algoritmico. Un’applicazione di questi giochi si ha, per esempio, nel caso in cui un amministratore di rete, il Leader, deve decidere quale sia per lui il miglior punto di accesso, prima che gli altri utenti, i Followers, si colleghino. Durante la trattazione viene dimostrato come il Leader abbia sempre convenienza a giocare anch’egli in strategie pure e che il problema appartenga alla classe di complessità FP. Verrà introdotta una versione Integer Linear Programming (ILP) del nostro problema. Verranno introdotti algoritmi originali polinomiali per calcolare il valore del Leader. Inoltre verrà dimostrato, sotto opportune ipotesi, come l’equilibrio Leader-Follower calcolato sia effettivamente anche un Equilibrio di Nash. Concludiamo il nostro lavoro presentando le simulazioni sperimentali per testare le performance di algoritmi che implementano la versione ILP del problema.