Network spot-checking games: Theory and application to toll enforcing in transportation networks
- 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.
Verfasserangaben: | Ralf BorndörferORCiD, Julia Buwaya, Guillaume Sagnol, Elmar Swarat |
---|---|
Dokumentart: | Artikel |
Titel des übergeordneten Werkes (Englisch): | Networks |
Band: | 65 |
Erste Seite: | 312 |
Letzte Seite: | 328 |
Verlag: | Wiley Periodicals, Inc. |
Jahr der Erstveröffentlichung: | 2015 |
Preprint: | urn:nbn:de:0297-zib-47139 |
DOI: | https://doi.org/10.1002/net.21596 |