Σε αυτή τη διπλωματική εργασία μελετάμε το πρόβλημα εύρεσης ενός Nash σημείου ισορροπίας για παίγνια δύο παικτών. Παρουσιάζεται ο αλγόριθμος Lemke - Howson, η πολυπλοκότητα του αλγορίθμου καθώς και η κλάση πολυπλοκότητας PPAD, όπου και αποδεικνύεται ότι το πρόβλημα εύρεσης ενός Nash σημείου ισορροπίας είναι πλήρες για την κλάση αυτή. Αναλυτικότερα, στο πρώτο κεφάλαιο γίνεται μία σύντομη ιστορική αναδρομή της θεωρίας παιγνίων, παρουσιάζονται κάποιες βασικές έννοιες και προτείνονται κάποιες καταστάσεις ως λύσεις ενός παιγνίου, με κύρια αυτή του Nash σημείου ισορροπίας. Το δεύτερο κεφάλαιο ασχολείται με τα παίγνια δύο παικτών ή παίνγια διπίνακα. Αρχικά ορίζονται τα στοιχεία που συνιστούν το παίγνιο, δηλαδή οι παίκτες, οι στρατηγικές τους, η βέλτιστη απόκριση και το Νash σημείο ισορροπίας και παρουσιάζονται με τη βοήθεια ενός παραδείγματος. Στη συνέχεια, ορίζονται τα πολύεδρα και τα πολύτοπα βέλτιστης απόκρισης με βάση τους πίνακες κερδών των δύο παικτών, που αποτελούν και βάση του αλγορίθμου Lemke - Howson. Στο τρίτο κεφάλαιο παρουσιάζεται αναλυτικά ο αλγόριθμος Lemkle - Howson στη γεωμετρική και στην αριθμητική του μορφή και εφαρμόζεται για ένα συγκεκριμένο παίγνιο. Η γεωμετρική εφαρμογή γίνεται με τη βοήθεια των πολυτόπων βέλτιστης απόκρισης και η αριθμητική μέσω του ακέραιου pivoting, που είναι μια παραλλαγή της μεθόδου simplex. Στο τέταρτο κεφάλαιο μελετάται μία κατηγορία παιγνίων όπου ο αλγόριθμος δεν είναι αποδοτικός. Για την κατασκευή των παιγνίων της κατηγορίας αυτής χρειάζεται πρώτα να δούμε τα κυκλικά πολύτοπα και να παρουσίασουμε κάποιες ιδιότητές τους. Στη συνέχεια αποδεικνύεται ότι ο αλγόριθμος απαιτεί εκθετικό χρόνο μέχρι να καταλήξει σε ένα Nash σημείο ισορροπίας του παιγνίου, σε σχέση με το μέγεθος του παιγνίου. Στο πέμπτο κεφάλαιο παρουσιάζεται μία αναγωγή του προβλήματος της εύρεσης ενός Nash σημείου ισορροπίας ενός παιγνίου δύο παικτών σε αυτό του πλήρους ταιριάσματος ενός γραφήματος, όπου και πάλι χρησιμοποιούμε ιδιότητες των πολυτόπων βέλτιστης απόκρισης καθώς και των δεικτοδοτημένων συμβολοσειρών Gale. Το έκτο και τελευταίο κεφάλαιο ασχολούμαστε με την κλάση πολυπλοκότητας PPAD. Αρχικά, ορίζουμε την κλάση και δίνουμε το πλήρες πρόβλημα οδηγό για την κλάση αυτη, το END OF LINE. Στη συνέχεια, δίνουμε μια διαισθητική αναγωγή του παραπάνω προβλήματος στο πρόβλημα SPERNER και έπειτα του SPERNER στο πρόβλημα BROUWER που πρόκειται για μία διακριτοποιημένη και απλόποιημένη εκδοχή της εύρεσης ενός σταθερού σημείου μίας συνάρτησης f. H τελευταία αναγωγή είναι αυτή του BROUWER στο 2NASH, δηλαδή την εύρεση ενός Nash σημείου ισορροπίας σε ένα παίγνιο δύο παικτών. Με αυτό τον τρόπο αποδεικνύεται ότι το 2NASH είναι PPAD πλήρες και δεν υπάρχει πολυωνυμικός αλγόριθμος για το πρόβλημα αυτό εκτός και αν P = PPAD. Στο τέλος της εργασίας υπάρχουν δύο παραρτήματα, όπου στο πρώτο παρουσιάζονται τα μονοπάτια που κατασκευάζει ο αλγόριθμος Lemke - Howson και κάποιες ιδιότητες αυτού και στο δεύτερο παράρτημα παρουσιάζεται ένα παράδειγμα κατασκευής ενός παιγνίου όπου ο αλγόριθμος δεν είναι αποδοτικός, παρατίθεται ο κώδικας σε MATLAB για την παραγωγή των παιγνίων της κλάσης αυτής και παρουσιάζονται τα μήκη των μονοπατιών που κατασκευάζει ο αλγόριθμος παίγνια της κλάσης. / In this thesis we study the problem of finding a Nash equilibrium for bimatrix games. We describe Lemke - Howson algorithm and its complexity. Also we study the PPAD complexity class and we give the reduction which shows that the problem of finding a Nash equilibrium (NASH) is PPAD complete even for bimatrix games. In section 1, we give a short history view of game theory and some essential notions about games, players and game solutions such as Nash equilibrium. In section 2, we define bimatrix games: each player's strategies, payoffs, mixed strategies, best response, Nash equilibria and we demonstrate all of them with an example. After that, we present best response polyhedra and best response polyhedra in which the Lemke - Howson algorithm is based. In section 3, we discribe in detail Lemke - Howson algorithm intuitively, by mones on best response polytopes, and arithmetically, by integer pivoting, which is a variant of simplex method. In section 4, is described a class of games where Lemke - Howson needs exponetial time to find a Nash equilibrium. For the construction of the games we use cyclic polytopes and the Gale evenness condition and their properties. We show in detail the Lemke - Howson paths and we compute their lengths for each dropped label. In section 5, we give a reduction from Perfect Matching to Nash equilibrium for a special case of games and we show that at these games a Nash equilibrium can be computed in polynomial time. In the final section we study the complexity class PPAD. First of all, we define formally the class and we give the first complete problem for this class, END OF LINE. After that, we reduce END OF LINE to SPERNER and SPERNER to BROUWER which is a simplified, discretized version of finding a fixed point for a continuous function f . Finally, we give in detail the reduction from BROUWER to 2NASH and we show that 2NASH is PPAD-complete which means that there is no polynomial time algorithm for 2NASH unless P = PPAD. At the end there are two appendices: At the first one we demonstrate the LH paths and at the second we give the source code in MATLAB for the construction of payoff tables for the LH worst case.

São analisados nesta dissertação problemas em teoria dos jogos, com enfoque no efeito que perturbações acarretam em jogos. A análise suavizada (smoothed analysis) é utilizada para tal análise, e dois tipos de jogos são o foco principal desta dissertação, jogos bimatrizes e o problema de atribuição de tráfego (Traffic Assignment Problem.) O algoritmo de Lemke-Howson é um método utilizado amplamente para computar um equilíbrio Nash de jogos bimatrizes. Esse problema é PPAD-completo (Polynomial Parity Arguments on Directed graphs), e existem instâncias em que um tempo exponencial é necessário para terminar o algoritmo. Mesmo utilizando análise suavizada, esse problema permanece exponencial. Entretanto, nenhum estudo experimental foi realizado para demonstrar na prática como o algoritmo se comporta em casos com perturbação. Esta dissertação demonstra como as instâncias de pior caso conhecidas atualmente podem ser geradas e mostra que a performance do algoritmo nestas instâncias, quando perturbações são aplicadas, difere do comportamento esperado provado pela teoria. O Problema de Atribuição de Tráfego modela situações em uma rede viária onde usuários necessitam viajar de um nodo origem a um nodo destino. Esse problema pode ser modelado como um jogo, usando teoria dos jogos, onde um equilíbrio Nash acontece quando os usuários se comportam de forma egoísta. O custo total ótimo corresponde ao melhor fluxo de um ponto de vista global. Nesta dissertação, uma nova medida de perturbação é apresentada, o Preço da Anarquia Suavizado (Smoothed Price of Anarchy), baseada na análise suavizada de algoritmos, com o fim de analisar os efeitos da perturbação no Preço da Anarquia. Usando esta medida, são estudados os efeitos que perturbações têm no Preço da Anarquia para instâncias reais e teóricas para o Problema de Atribuição de Tráfego. É demonstrado que o Preço da Anarquia Suavizado se mantém na mesma ordem do Preço da Anarquia sem perturbações para funções de latência polinomiais. Finalmente, são estudadas instâncias de benchmark em relação à perturbação. / This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses 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 verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin 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, which we call 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.

São analisados nesta dissertação problemas em teoria dos jogos, com enfoque no efeito que perturbações acarretam em jogos. A análise suavizada (smoothed analysis) é utilizada para tal análise, e dois tipos de jogos são o foco principal desta dissertação, jogos bimatrizes e o problema de atribuição de tráfego (Traffic Assignment Problem.) O algoritmo de Lemke-Howson é um método utilizado amplamente para computar um equilíbrio Nash de jogos bimatrizes. Esse problema é PPAD-completo (Polynomial Parity Arguments on Directed graphs), e existem instâncias em que um tempo exponencial é necessário para terminar o algoritmo. Mesmo utilizando análise suavizada, esse problema permanece exponencial. Entretanto, nenhum estudo experimental foi realizado para demonstrar na prática como o algoritmo se comporta em casos com perturbação. Esta dissertação demonstra como as instâncias de pior caso conhecidas atualmente podem ser geradas e mostra que a performance do algoritmo nestas instâncias, quando perturbações são aplicadas, difere do comportamento esperado provado pela teoria. O Problema de Atribuição de Tráfego modela situações em uma rede viária onde usuários necessitam viajar de um nodo origem a um nodo destino. Esse problema pode ser modelado como um jogo, usando teoria dos jogos, onde um equilíbrio Nash acontece quando os usuários se comportam de forma egoísta. O custo total ótimo corresponde ao melhor fluxo de um ponto de vista global. Nesta dissertação, uma nova medida de perturbação é apresentada, o Preço da Anarquia Suavizado (Smoothed Price of Anarchy), baseada na análise suavizada de algoritmos, com o fim de analisar os efeitos da perturbação no Preço da Anarquia. Usando esta medida, são estudados os efeitos que perturbações têm no Preço da Anarquia para instâncias reais e teóricas para o Problema de Atribuição de Tráfego. É demonstrado que o Preço da Anarquia Suavizado se mantém na mesma ordem do Preço da Anarquia sem perturbações para funções de latência polinomiais. Finalmente, são estudadas instâncias de benchmark em relação à perturbação. / This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses 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 verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin 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, which we call 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.

São analisados nesta dissertação problemas em teoria dos jogos, com enfoque no efeito que perturbações acarretam em jogos. A análise suavizada (smoothed analysis) é utilizada para tal análise, e dois tipos de jogos são o foco principal desta dissertação, jogos bimatrizes e o problema de atribuição de tráfego (Traffic Assignment Problem.) O algoritmo de Lemke-Howson é um método utilizado amplamente para computar um equilíbrio Nash de jogos bimatrizes. Esse problema é PPAD-completo (Polynomial Parity Arguments on Directed graphs), e existem instâncias em que um tempo exponencial é necessário para terminar o algoritmo. Mesmo utilizando análise suavizada, esse problema permanece exponencial. Entretanto, nenhum estudo experimental foi realizado para demonstrar na prática como o algoritmo se comporta em casos com perturbação. Esta dissertação demonstra como as instâncias de pior caso conhecidas atualmente podem ser geradas e mostra que a performance do algoritmo nestas instâncias, quando perturbações são aplicadas, difere do comportamento esperado provado pela teoria. O Problema de Atribuição de Tráfego modela situações em uma rede viária onde usuários necessitam viajar de um nodo origem a um nodo destino. Esse problema pode ser modelado como um jogo, usando teoria dos jogos, onde um equilíbrio Nash acontece quando os usuários se comportam de forma egoísta. O custo total ótimo corresponde ao melhor fluxo de um ponto de vista global. Nesta dissertação, uma nova medida de perturbação é apresentada, o Preço da Anarquia Suavizado (Smoothed Price of Anarchy), baseada na análise suavizada de algoritmos, com o fim de analisar os efeitos da perturbação no Preço da Anarquia. Usando esta medida, são estudados os efeitos que perturbações têm no Preço da Anarquia para instâncias reais e teóricas para o Problema de Atribuição de Tráfego. É demonstrado que o Preço da Anarquia Suavizado se mantém na mesma ordem do Preço da Anarquia sem perturbações para funções de latência polinomiais. Finalmente, são estudadas instâncias de benchmark em relação à perturbação. / This thesis analyzes problems in game theory with respect to perturbation. It uses smoothed analysis to accomplish such task and focuses 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 verify and evaluate in practice how the algorithm behaves in such cases. This thesis shows in detail how the current known worst-case instances are generated and shows that the performance of the algorithm on these instances, when perturbed, differs from the expected behavior proven in theory. The Traffic Assignment Problem models a situation in a road network where users want to travel from an origin 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, which we call 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.