The Shortest Path Game: Complexity and Algorithms

Abstract : In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (agents/players) move together along the edges of a graph from a given starting vertex to a given destination. The two players take turns in deciding in each vertex which edge to traverse next. The decider in each vertex also has to pay the cost of the chosen edge. We want to determine the path where each player minimizes its costs taking into account that also the other player acts in a selfish and rational way. Such a solution is a subgame perfect equilibrium and can be determined by backward induction in the game tree of the associated finite game in extensive form.We show that finding such a path is PSPACE-complete even for bipartite graphs both for the directed and the undirected version of the game. On the other hand, we can give polynomial time algorithms for directed acyclic graphs and for cactus graphs in the undirected case. The latter is based on a decomposition of the graph into components and their resolution by a number of fairly involved dynamic programming arrays.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.39-53, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_4〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01402026
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 10:47:58
Dernière modification le : jeudi 24 novembre 2016 - 11:14:12
Document(s) archivé(s) le : lundi 20 mars 2017 - 23:57:40

Fichier

978-3-662-44602-7_4_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Andreas Darmann, Ulrich Pferschy, Joachim Schauer. The Shortest Path Game: Complexity and Algorithms. Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.39-53, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_4〉. 〈hal-01402026〉

Partager

Métriques

Consultations de la notice

43

Téléchargements de fichiers

76