Premium
Network spot‐checking games: Theory and application to toll enforcing in transportation networks
Author(s) -
Borndörfer Ralf,
Buwaya Julia,
Sagnol Guillaume,
Swarat Elmar
Publication year - 2015
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21596
Subject(s) - stackelberg competition , nash equilibrium , computer science , toll , game theory , stochastic game , computation , mathematical optimization , pairwise comparison , integer programming , best response , mathematical economics , repeated game , graph , linear programming , theoretical computer science , mathematics , algorithm , artificial intelligence , genetics , biology
We introduce the class of spot‐checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. In an SC game, the pure strategies of network users correspond to paths in a graph, and the pure strategies of the inspectors are subset of arcs to be controlled. Although SC games are not zero‐sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium (SSE) is more relevant for this problem and we give a mixed integer programming (MIP) formulation for this problem. We show that the computation of such an equilibrium is NP‐hard. More generally, we prove that it is NP‐hard to compute a SSE in a polymatrix game, even if the game is pairwise zero‐sum. Then, we give some bounds on the price of spite , which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we report computational experiments on instances constructed from real data, for an application to the enforcement of a truck toll in Germany. These numerical results show the efficiency of the proposed methods, as well as the quality of the bounds derived in this article. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 312–328 2015