Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Practical and Efficient Approximations of Nash Equilibria for Win-Lose Games Based on Graph Spectra
verfasst von : Haralampos Tsaknakis, Paul G. Spirakis
Erschienen in: Internet and Network Economics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
It is shown here that the problem of computing a Nash equilibrium for two-person games can be polynomially reduced to an indefinite quadratic programming problem involving the spectrum of the adjacency matrix of a strongly connected directed graph on
n
vertices, where
n
is the total number of players’ strategies. Based on that, a new method is presented for computing approximate equilibria and it is shown that its complexity is a function of the average spectral energy of the underlying graph. The implications of the strong connectedness properties on the energy and on the complexity of the method is discussed and certain classes of graphs are described for which the method is a polynomial time approximation scheme (PTAS). The worst case complexity is bounded by a subexponential function in the total number of strategies
n
and a comparison is made with a previously reported method with subexponential complexity.