Approximability of Symmetric Bimatrix Games and Related Experiments
| dc.contributor.author | Kontogiannis, S | en |
| dc.contributor.author | Spiridakis, P. | en |
| dc.date.accessioned | 2015-11-24T17:02:34Z | |
| dc.date.available | 2015-11-24T17:02:34Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/11070 | |
| dc.rights | Default Licence | - |
| dc.subject | Bimatrix games | en |
| dc.subject | indefinite quadratic optimization | en |
| dc.subject | Nash equilibrium approximation | en |
| dc.subject | symmetrization | en |
| dc.title | Approximability of Symmetric Bimatrix Games and Related Experiments | en |
| heal.abstract | In this work we present a simple quadratic formulation for the problem of computing Nash equilibria in symmetric bimatrix games, inspired by the well-known formulation of Mangasarian and Stone [26]. We exploit our formulation to shed light to the approximability of NE points. First we observe that any KKT point of this formulation (and indeed, any quadratic program) is also a stationary point, and vice versa. We then prove that any KKT point of the proposed formulation (is not necessarily itself, but) indicates a 31? NE point, which is polynomially tractable, given as input the KKT point. We continue by proposing an algorithm for constructing an 31+? NE point for any , in time polynomial in the size of the game and quasi-linear in 1, exploiting Ye s algorithm for approximating KKT points of QPs [34]. This is (to our knowledge) the first polynomial time algorithm that constructs points for symmetric bimatrix games for any ε close to 31. We extend our main result to (asymmetric) win lose games, as well as to games with maximum aggregate payoff either at most 1, or at least 35. To achieve this, we use a generalization of the Brown & von Neumann symmetrization technique [6] to the case of non-zero-sum games, which we prove that is approximation preserving. Finally, we present our experimental analysis of the proposed approximation and other quite interesting approximations for NE points in symmetric bimatrix games. | en |
| heal.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| heal.identifier.primary | 10.1007/978-3-642-20662-7_1 | - |
| heal.journalName | Lecture Notes in Computer Science | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 2011 | - |
| heal.publisher | Springer | en |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | journalArticle | - |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.type.en | Journal article | en |
Αρχεία
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.74 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: