Stopping games on finite directed graphs

10^th March 2020, 13:00 SCTH-LT1
Janos Flesch
Maastricht University

Abstract

We consider a special class of stochastic ganes, which are played on finite directed graphs. In such a game, each vertex of a directed graph is controlled by one of the two players. The game starts in a given vertex. The player who controls this vertex has two options: he can terminate the game, or he can choose one of the outgoing arcs. In the former case, the game ends. In the latter case, the play moves to the vertex at the end of the chosen arc, and the controlling player of this vertex has two options: he can can terminate the game, or he can choose one of the outgoing arcs. This is repeated until a player decides to terminate the game. The payoff of each player only depends on the vertex where the game is terminated. If no player ever terminates the game, each player receives payoff 0.

We show that these games admit a subgame-perfect ?-equilibrium, for any ?>0. Here, ? is an error-term. A subgame-perfect ?-equilibrium is thus a strategy profile in which no player can gain more than ? by a unilateral deviation, in any subgame. The proof of this existence result is constructive, and is based on a recursive algorithm that outputs a subgame-perfect ?-equilibrium, for any ?>0, after a finite number of steps. This result generalizes several earlier existence results. As an additional feature, the constructed strategy profile is robust to discounting in the sense that the very same strategy profile is also a subgame-perfect ?-equilibrium when the payoffs are discounted, provided that the discount factor is sufficiently high (the players are patient).