Network theory: Il prezzo dell'anarchia ​

The aim of this thesis is to analyze the concept of “Price of Anarchy”, introduced by Christos Papadimitriou and Elias Koutsoupias in 1998, and studied by Tim Roughgarden and Eva Tardos from the following year. This theory estimates the loss of efficiency of a system, that degrades due to a selfish behavior of its agents, who cause a deviation from the optimal solution of the problems. The question this thesis wants to answer is: How bad is this deviation? (or better: What is the price of anarchy?). In the second chapter we analyze two models: nonatomic model, in which we suppose there are infinite rational agents that control a negligible amount of traffic, and atomic model in which we consider a single agent who routes an amount of traffic no longer negligible. In both models we will explain the way to compute the loss of efficiency and the bounds of the Price of Anarchy. In the third chapter we will introduce a particular class of strategic finite games, called Potential Games (games that admit a potential function). Adapting the definition of Price of Anarchy for this class of strategic games, lastly, in the fourth chapter we will discuss a specific Potential Game, called Global Connection Game, where players no longer route traffic on an already existing network, but they create it, trying to minimize the edge's construction costs. Even in this case we will find the way to quantify the loss of efficiency of the selfish behavior and to bound the Price of Anarchy. ​

Scopo di questa tesi è quello di analizzare il concetto di “Prezzo dell'Anarchia”, introdotto nel 1998 da Christos Papadimitriou e Elias Koutsoupias e studiato a fondo da Tim Roughgarden ed Eva Tardos a partire dall'anno successivo. Tale teoria, misura quanto l'efficienza di un sistema, degrada a causa di un comportamento egoistico dei suoi agenti. In generale, gli utenti egoisti causano una certa deviazione nella soluzione ottimale ai problemi. Questa tesi quindi, pone la domanda: quanto può essere grave questa deviazione? O meglio: qual è il prezzo dell'anarchia? Nel secondo capitolo analizzeremo due modelli: quello nonatomico, in cui supponiamo ci siano infiniti agenti razionali che controllano una quantità di traffico trascurabile e quello atomico in cui consideriamo un singolo utente che instrada una quantità di traffico non più trascurabile. In entrambi i modelli illustreremo la procedura per calcolare la perdita di efficienza e calcoleremo quindi i limiti del Prezzo dell'Anarchia. Nel terzo capitolo introdurremo una classe particolare di giochi strategici finiti, chiamati Potential Games, cioè giochi che ammettono una “funzione potenziale”. Adattando la definizione di Prezzo dell'Anarchia per questo tipo di giochi strategici, infine, nel capitolo 4 discuteremo uno specifico Potential Game chiamato Global Connection Game, dove i giocatori non instradano più traffico su una rete già esistente, ma la creano cercando di minimizzare i costi di costruzione degli archi. Anche in questo caso troveremo il modo per quantificare la perdita di efficienza del comportamento egoistico e limitare il Prezzo dell'Anarchia. ​