A game theoretic approach to graph problems
| dc.contributor.author | Böhme, Thomas | |
| dc.contributor.author | Schreyer, Jens | |
| dc.contributor.editor | Erfurth, Christian | |
| dc.contributor.editor | Eichler, Gerald | |
| dc.contributor.editor | Schau, Volkmar | |
| dc.date.accessioned | 2019-02-20T10:21:04Z | |
| dc.date.available | 2019-02-20T10:21:04Z | |
| dc.date.issued | 2009 | |
| dc.description.abstract | 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. | en |
| dc.identifier.isbn | 978-3-88579-242-9 | |
| dc.identifier.pissn | 1617-5468 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/20422 | |
| dc.language.iso | en | |
| dc.publisher | Gesellschaft für Informatik e.V. | |
| dc.relation.ispartof | 9th International Conference On Innovative Internet Community Systems I2CS 2020 | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Proceedings, Volume P-148 | |
| dc.title | A game theoretic approach to graph problems | en |
| dc.type | Text/Conference Paper | |
| gi.citation.endPage | 156 | |
| gi.citation.publisherPlace | Bonn | |
| gi.citation.startPage | 149 | |
| gi.conference.date | June 15-17, 2009 | |
| gi.conference.location | Jena | |
| gi.conference.sessiontitle | Regular Research Papers |
Dateien
Originalbündel
1 - 1 von 1