Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/11040Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Kontogiannis, S. C. | en |
| dc.contributor.author | Spirakis, P. G. | en |
| dc.date.accessioned | 2015-11-24T17:02:19Z | - |
| dc.date.available | 2015-11-24T17:02:19Z | - |
| dc.identifier.issn | 0178-4617 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/11040 | - |
| dc.rights | Default Licence | - |
| dc.subject | bimatrix games | en |
| dc.subject | well supported approximate nash equilibria | en |
| dc.subject | nash equilibria | en |
| dc.subject | algorithms | en |
| dc.subject | hard | en |
| dc.title | Well Supported Approximate Equilibria in Bimatrix Games | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | DOI 10.1007/s00453-008-9227-6 | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2010 | - |
| heal.abstract | 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. | en |
| heal.journalName | Algorithmica | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Kontogiannis-2010-Well Supported Appro.pdf | 416.52 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
