Seminar:Quantifying the efficiency of congestion games; March 21st, 2013 at 11:00
Speaker: Martin Gairing, researcher at University of Liverpool , Liverpool, U.K
Abstract: During the last decade, the quantification of the inefficiency of game-theoretic equilibria has been a popular and successful line of research. The two most widely adopted measures for this inefficiency are the Price of Anarchy (PoA) and the Price of Stability (PoS). In this talk I will summarise recent results on the PoA and PoS in congestion games. Such games provide us with a fairly general model for the non-cooperative sharing of resources.
Both concepts compare the social cost in a Nash equilibrium to the optimum social cost that could be achieved via central control. The PoA is pessimistic and considers the worst-case such Nash equilibrium, while the PoS is optimistic and considers the best-case Nash equilibrium. Therefore, the PoA can be used as an absolute worst-case guarantee in a scenario where we have no control over equilibrium selection. On the other hand, the PoS gives an estimate of what is the best we can hope for in a Nash equilibrium; for example, if a trusted mediator suggests this solution to them.