The Price of Spite in Spot-checking games
- 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.
Verfasserangaben: | Guillaume Sagnol, Ralf BorndörferORCiD, Thomas Schlechte, Elmar Swarat |
---|---|
Herausgeber:in: | Ron Lavi |
Dokumentart: | Konferenzbeitrag |
Titel des übergeordneten Werkes (Englisch): | 7th International Symposium on Algorithmic Game Theory (SAGT'2014) |
Band: | 8768 |
Erste Seite: | 293 |
Serie: | Lecture Notes in Computer Science |
Verlag: | Springer |
Jahr der Erstveröffentlichung: | 2014 |
Seitenzahl: | 1 |
Bemerkungen: | Brief Announcement included in Back Matter p. 293 following |
Preprint: | urn:nbn:de:0297-zib-52775 |
DOI: | https://doi.org/10.1007/978-3-662-44803-8 |