@article{BorndoerferBuwayaSagnoletal., author = {Bornd{\"o}rfer, Ralf and Buwaya, Julia and Sagnol, Guillaume and Swarat, Elmar}, title = {Network spot-checking games: Theory and application to toll enforcing in transportation networks}, series = {Networks}, volume = {65}, journal = {Networks}, publisher = {Wiley Periodicals, Inc.}, doi = {10.1002/net.21596}, pages = {312 -- 328}, abstract = {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.}, language = {en} } @misc{BorndoerferBuwayaSagnoletal., author = {Bornd{\"o}rfer, Ralf and Buwaya, Julia and Sagnol, Guillaume and Swarat, Elmar}, title = {Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach}, issn = {1438-0064}, doi = {/10.1016/j.endm.2013.05.100}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17401}, abstract = {We present a game-theoretic approach to optimize the strategies of toll enforcement on a motorway network. In contrast to previous approaches, we consider a network with an arbitrary topology, and we handle the fact that users may choose their Origin-Destination path; in particular they may take a detour to avoid sections with a high control rate. We show that a Nash equilibrium can be computed with an LP (although the game is not zero-sum), and we give a MIP for the computation of a Stackelberg equilibrium. Experimental results based on an application to the enforcement of a truck toll on German motorways are presented.}, language = {en} }