Gesellschaft fr Informatik e.V.

Lecture Notes in Informatics

Innovative Internet Community Systems I2CS 2009 P-148, 149-156 (2009).

Gesellschaft für Informatik, Bonn

Copyright © Gesellschaft für Informatik, Bonn


A game theoretic approach to graph problems

Thomas Böhme and Jens Schreyer


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.

Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-242-9

Last changed 24.01.2012 22:05:24