# The Shortest Path Game: Complexity and Algorithms

Andreas Darmann, Ulrich Pferschy, Joachim Schauer

► To cite this version:

Andreas Darmann, Ulrich Pferschy, Joachim Schauer. The Shortest Path Game: Complexity and Algorithms. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.39-53, 10.1007/978-3-662-44602-7_4 . hal-01402026

HAL Id: hal-01402026

https://inria.hal.science/hal-01402026

Submitted on 24 Nov 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Shortest Path Game:
Complexity and Algorithms *

Andreas Darmann<fnref n="1" />, Ulrich Pferschy<fnref n="2" />, and Joachim Schauer<fnref n="2" />

**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.

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

# 1 Introduction

We are given a directed graph $G = (V, A)$ with vertex set $V$ and arc set $A$ with positive costs $c(u, v)$ for each arc $(u, v) \in A$ and two designated vertices $s, t \in V$. The aim of **SHORTEST PATH GAME** is to find a directed path from $s$ to $t$ in the following setting: The game is played by two players (or agents) $A$ and $B$ who start in $s$ and always move together along arcs of the graph. In each

<footnote n="1">¹ University of Graz, Institute of Public Economics, Universitaetsstr. 15,
8010 Graz, Austria, andreas.darmann@uni-graz.at</footnote>

<footnote n="2">² University of Graz, Department of Statistics and Operations Research,
Universitaetsstr. 15, 8010 Graz, Austria,
{pferschy, joachim.schauer}@uni-graz.at</footnote>

<footnote>* Ulrich Pferschy and Joachim Schauer were supported by the Austrian Science Fund (FWF): [P 23829-N13]. Andreas Darmann was supported by the Austrian Science Fund (FWF): [P 23724-G11]. We would like to thank Christian Klamler (University of Graz) for fruitful discussions and valuable comments.</footnote>
vertex the players take turns to select the next vertex to be visited among all
neighboring vertices of the current vertex with player A taking the first decision
in s. The player deciding in the current vertex also has to pay the cost of the
chosen arc. Each player wants to minimize the total arc costs it has to pay. The
game continues until the players reach the destination vertex t. Later, we will
also consider the same problem on an undirected graph G = (V, E) with edge
set E which is quite different in several aspects.

To avoid that the players get stuck at some point, we restrict the players in every
decision to choose an arc (or edge, in the undirected case) which still permits a
feasible path from the current vertex to the destination t.

(R1) No player can select an arc which does not permit a path to vertex t.

In classical game theory the above scenario can be seen as a finite game in
extensive form. All feasible decisions for the players can be represented in a
game tree, where each node corresponds to the decision of a certain player in a
vertex of the graph G.

The standard procedure to determine equilibria in a game tree is backward in-
duction (see [Osborne, 2004, ch. 5]). This means that for each node in the game
tree, whose child nodes are all leaves, the associated player can reach a decision
by simply choosing the best of all child nodes w.r.t. their allocated total cost, i.e.
the cost of the corresponding path in G attributed to the current player. Then
these leaf nodes can be deleted and the pair of costs of the chosen leaf is moved
to its parent node. In this way, we can move upwards in the game tree towards
the root and settle all decisions along the way.

This backward induction procedure implies a strategy for each player, i.e. a rule
specifying for each node of the game tree associated with this player which arc to
select in the corresponding vertex of G. Always choose the arc according to the re-
sult of backward induction. Such a strategy for both players is a Nash equilibrium
and also a so-called subgame perfect equilibrium (a slightly stronger property),
since the decisions made in the underlying backward induction procedure are
also optimal for every subtree.<fnref n="3" />

The outcome, if both players follow this strategy, is a unique path from *s* to *t* in *G* corresponding to the unique subgame perfect equilibrium (SPE) which we will call **spe-path**. A **spe-path** for **SHORTEST PATH GAME** is the particular solution in the game tree with minimal cost for both selfish players under the assumption that they have complete and perfect information of the game and know that the opponent will also strive for its own selfish optimal value.

<footnote n="3">³ In order to guarantee a unique solution of such a game and thus a specific subgame perfect Nash equilibrium, we have to define a tie-breaking rule. We will use the “optimistic case”, where in case of indifference a player chooses the option with lowest possible cost for the other player. If both players have the same cost, the corresponding paths in the graph are completely equivalent. Assigning arbitrary but fixed numbers to each vertex in the beginning, e.g. 1, . . . , n, we choose the path to a vertex with lowest vertex number.</footnote>