Computing approximate Nash equilibria

Abstract

The problem of finding equilibria in non-cooperative games and understanding their properties is a central problem in modern game theory. After John Nash proved that every finite game has at least one equilibrium (so-called Nash equilibrium), the natural question arose whether we can compute one efficiently. After several years of extensive research, we now know that the problem of finding a Nash equilibrium is PPAD-complete even for two-player normal-form games, making the task of finding approximate Nash equilibria one of the central questions in the area of equilibrium computation. In this thesis our main goal is a new study of the complexity of various variants of the approximate Nash equilibrium. Specifically, we study algorithms for additive approximate Nash equilibria in bimatrix and multi-player games. Then, we study algorithms for relative approximate Nash equilibria in multi-player games. Furthermore, we study algorithms for optimal approximate Nash equilibria in bimatrix games and finally we study the communication complexity of additive approximate Nash equilibria in bimatrix games.

Το πρόβλημα εύρεσης σημείων ισορροπίας σε μη συνεργατικά παίγνια και η κατανόηση των ιδιοτήτων τους είναι ένα κεντρικό πρόβλημα στη μοντέρνα θεωρία παιγνίων. Αφότου ο Νας απέδειξε ότι κάθε πεπερασμένο παίγνιο έχει τουλάχιστον ένα σημείο ισορροπίας (σημείο ισορροπίας κατά Νας), μία φυσική ερώτηση είναι αν μπορούμε να τα υπολογίσουμε αποδοτικά. Μετά από πολλά χρόνια εντατικής έρευνας, ξερουμέ τώρα ότι το πρόβλημα εύρεσης ενός σημείου ισορροπίας κατά Νας είναι PPAD-πλήρης ακόμα και για παίγνια κανονικής μορφής δύο παικτών, κάνοντας την διαδικασία εύρεσης προσεγγιστικών σημείων ισορροπίας κατά Νας μία από τις κεντρικές ερωτήσεις στον υπολογισμό σημείων ισορροπίας. Σε αυτή την εργασία ο κύριος στόχος μας είναι μία νέα μελέτη στην πολυπλοκότητα διαφόρων παραλλαγών των προσεγγιστικών σημείων ισορροπίας κατά Νας. Συγκεκριμένα μελετάμε αλγόριθμους για προσθετικά προσεγγιστικά σημεία κατά Νας σε παίγνια δύο και πολλαπλών παικτών. Μετά μελετάμε αλγόριθμους για πολλαπλασιαστικά προσεγγιστικά σημεία ισορροπίας κατά Νας σε παίγνια πολλαπλών παικτών. Επιπλέον, μελετάμε αλγόριθμους για βέλτιστα προσεγγιστικά σημεία ισορροπίας κατά Νας σε παίγνια δύο παικτών και τέλος μελετάμε την πολυπλοκότητα επικοινωνίας για προσθετικά προσεγγιστικά σημεία ισορροπίας κατά Νας σε παίγνια δύο παικτών.