Well Supported Approximate Equilibria in Bimatrix Games
| 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.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.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| heal.identifier.primary | DOI 10.1007/s00453-008-9227-6 | - |
| heal.journalName | Algorithmica | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 2010 | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | journalArticle | - |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.type.en | Journal article | en |
Files
License bundle
1 - 1 of 1
Loading...
- Name:
- license.txt
- Size:
- 1.74 KB
- Format:
- Item-specific license agreed upon to submission
- Description: