The Price of Spite in Spot-checking games

Please always quote using this URN: urn:nbn:de:0297-zib-52775
  • 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. 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

  • Export Bibtex
Metadaten
Author:Guillaume Sagnol, Ralf Borndörfer, Thomas Schlechte, Elmar Swarat
Document Type:ZIB-Report
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx)
91-XX GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES
Date of first Publication:2014/10/15
Series (Serial Number):ZIB-Report (14-38)
ISSN:1438-0064
Published in:Appeared in: 7th International Symposium on Algorithmic Game Theory (SAGT'2014), as a brief announcement
DOI:http://dx.doi.org/10.1007/978-3-662-44803-8

$Rev: 13581 $