TY - THES A1 - Buwaya, Julia T1 - Optimizing control in a transportation network when users may choose their OD-path N2 - This thesis represents a game-theoretic investigation of the allocation of inspectors in a transportation network, comparing Nash and Stackelberg equilibrium strategies to a strategy in which inspections are conducted proportionally to the traffic volume. It contains specifications for the integration of space and time dependencies and extensive experimental tests for the application on the transportation network of German motorways using real data. Main results are that - although the formulated spot-checking game is not zero-sum - we are able to compute a Nash equilibrium using linear programming and secondly, that experimental results yield that a Nash equilibrium strategy represents a good trade-off for the Stackelberg equilibrium strategy between efficiency of controls and computation time. KW - Optimization KW - Transportation Network KW - Game Theory KW - Stackelberg Equilibrium KW - Mixed Integer Programming KW - Security Game KW - Linear Programming KW - Nash Equilibrium Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42330 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Buwaya, Julia A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - Network Spot Checking Games: Theory and Application to Toll Enforcing in Transportation Networks N2 - 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. T3 - ZIB-Report - 14-07 KW - Game Theory KW - Stackelberg Equilibrium KW - Security Games KW - Mixed Integer Programming KW - Price of Anarchy Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-47139 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Buwaya, Julia A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach N2 - 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. T3 - ZIB-Report - 12-47 KW - Stackelberg Equilibrium KW - Game Theory KW - Mixed Integer Programming Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17401 SN - 1438-0064 ER -