Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 8 von 8
Zurück zur Trefferliste

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.
Metadaten
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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.