P148 - I2CS 2009: 9th International Conference on Innovative Internet Community Systems

Auflistung nach:

1 - 1 von 1

Konferenzbeitrag
A game theoretic approach to graph problems
(9th International Conference On Innovative Internet Community Systems I2CS 2020, 2009) Böhme, Thomas; Schreyer, Jens
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.