Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Network Spot Checking Games: Theory and Application to Toll Enforcing in Transportation Networks

Please always quote using this URN: urn:nbn:de:0297-zib-47139
  • 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 edges 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 is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways.

Download full text files

Export metadata

Author:Ralf BorndörferORCiD, Julia Buwaya, Guillaume Sagnol, Elmar Swarat
Document Type:ZIB-Report
Tag:Game Theory; Mixed Integer Programming; Price of Anarchy; Security Games; Stackelberg Equilibrium
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx)
Date of first Publication:2014/12/03
Series (Serial Number):ZIB-Report (14-07)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.