Konferenzbeitrag
A game theoretic approach to graph problems
Lade...
Volltext URI
Dokumententyp
Text/Conference Paper
Dateien
Zusatzinformation
Datum
2009
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik e.V.
Zusammenfassung
We investigate some well known graph theoretic problems from a game theoretic point of view. To coloring and matching problems we associate binary payoff games where the players are the vertices of the graph. Solutions to the graph problems correspond to action profiles of the game, where all players get payoff 1. We show, that there exist rules for the choice of action in the repeated play of these games, that converge to the solution of the graph problems. Although the convergence is slow, this shows, that the problems can be solved with almost no information on the underlying graph.