Well Supported Approximate Equilibria in Bimatrix Games
Φόρτωση...
Ημερομηνία
Συγγραφείς
Kontogiannis, S. C.
Spirakis, P. G.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Algorithmica
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
In view of the apparent intractability of constructing Nash Equilibria (NE in short) in polynomial time, even for bimatrix games, understanding the limitations of the approximability of the problem is an important challenge. In this work we study the tractability of a notion of approximate equilibria in bimatrix games, called well supported approximate Nash Equilibria (SuppNE in short). Roughly speaking, while the typical notion of approximate NE demands that each player gets a payoff at least an additive term less than the best possible payoff, in a SuppNE each player is assumed to adopt with positive probability only approximate pure best responses to the opponent's strategy. As a first step, we demonstrate the existence of SuppNE with small supports and at the same time good quality. This is a simple corollary of Althofer's Approximation Lemma, and implies a subexponential time algorithm for constructing SuppNE of arbitrary (constant) precision. We then propose algorithms for constructing SuppNE in win lose and normalized bimatrix games (i.e., whose payoff matrices take values from {0,1} and [0,1] respectively). Our methodology for attacking the problem is based on the solvability of zero sum bimatrix games (via its connection to linear programming) and provides a 0.5-SuppNE for win lose games and a 0.667-SuppNE for normalized games. To our knowledge, this paper provides the first polynomial time algorithms constructing epsilon-SuppNE for normalized or win lose bimatrix games, for any nontrivial constant 0a parts per thousand currency sign epsilon < 1, bounded away from 1.
Περιγραφή
Λέξεις-κλειδιά
bimatrix games, well supported approximate nash equilibria, nash equilibria, algorithms, hard
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής