Polynomial algorithms for approximating Nash equilibria of bimatrix games
Φόρτωση...
Ημερομηνία
Συγγραφείς
Kontogiannis, S. C.
Panagopoulou, P. N.
Spirakis, P. G.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Theoretical Computer Science
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
We focus on the problem of computing an epsilon-Nash equilibrium of a bimatrix game, when epsilon is an absolute constant. We present a simple algorithm for Computing a 3/4-Nash equilibrium for any bimatrix game in strongly polynomial time and we next show 4 how to extend this algorithm so as to obtain a (potentially stronger) parameterized approximation. Namely, we present an algorithm that computes a 2+lambda/4-Nash equilibrium, where lambda is the minimum, among all Nash equilibria, expected payoff of either player. The suggested algorithm runs in time polynomial in the number of strategies available to the players. (C) 2009 Elsevier B.V. All rights reserved.
Περιγραφή
Λέξεις-κλειδιά
bimatrix game, approximate nash equilibrium, points
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής