Optimization Online


On the shortest path game

Andreas Darmann (andreas.darmann***at***uni-graz.at)
Ulrich Pferschy (pferschy***at***uni-graz.at)
Joachim Schauer (joachim.schauer***at***uni-graz.at)

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 optimal 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 can be determined by backward induction in the game tree of the associated finite game in extensive form. We show that finding such an optimal 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 even 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.

Keywords: shortest path problem, game theory, computational complexity, cactus graph

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Other Topics (Game Theory )


Download: [PDF]

Entry Submitted: 06/17/2014
Entry Accepted: 06/19/2014
Entry Last Modified: 09/19/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society