Publicado em: 23/02/2012

Dissertação de Mestrado em Fundamentos da Computação

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
INSTITUTO DE INFORMÁTICA
PROGRAMA DE POS-GRADUAÇÃO EM COMPUTAÇÃO
———————————————————
DEFESA DE DISSERTAÇÃO DE MESTRADO

Aluno: Félix Carvalho Rodrigues
Orientadora: Profa. Dra. Luciana Salete Buriol

Título: Smoothed Analysis in Nash Equilibria and the Price of Anarchy
Linha de Pesquisa: Fundamentos da Computação

Data: 28/02/2012
Hora: 14h30
Local: Auditório José Mauro Volkmer de Castilho, Prédio 43424 – Instituto de Informática

Banca Examinadora:
Profa. Dra. Ana Lúcia Cetertich Bazzan (UFRGS)
Prof. Dr. Aristidis Anagnostopoulos (SU-Rome)
Prof. Dr. Carlos Hoppen (UFRGS)
Prof. Dr. Guido Schäfer (CWI – Amsterdam)

Presidente da Banca: Profa. Dra. Luciana Salete Buriol

Abstract:
This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focus on two kind of games, bimatrix games and the traffic assignment problem. The Lemke-Howson algorithm is a widely used algorithm to compute a Nash equilibrium of a bimatrix game. This problem is PPAD-complete (Polynomial Parity Arguments on Directed graphs), and there exists an instance which takes exponential time (with any starting pivot.) It has been proven that even with a smoothed analysis it is still exponential. However, no experimental study has been done to demonstrate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and show that the performance of the algorithm on these instances, when perturbed, differ from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from a source to a destination. It can be modeled as a game using game theory, with a Nash equilibrium happening when users behave selfishly and an optimal social welfare being the best possible flow from a global perspective. We provide a new measure, the Smoothed Price of Anarchy, based on the smoothed analysis of algorithms in order to analyze the effects of perturbation on the Price of Anarchy. Using this measure, we analyze the effects that perturbation has on the Price of Anarchy for real and theoretical instances for the Traffic Assignment Problem. We demonstrate that the Smoothed Price of Anarchy remains in the same order as the original Price of Anarchy for polynomial latency functions. Finally, we study benchmark instances in relation to perturbation.

Keywords: Algorithmic Game Theory, Smoothed Analysis, Lemke-Howson Algorithm, Bimatrix Games, Frank-Wolfe Algorithm, Network Games, Traffic Assignment Problem, Price of Anarchy.