Refine
Year of publication
- 2014 (4) (remove)
Document Type
- ZIB-Report (3)
- In Proceedings (1)
Language
- English (4)
Is part of the Bibliography
- no (4)
Keywords
- Game Theory (1)
- Kalman Filter (1)
- Mixed Integer Programming (1)
- Optimal Design (1)
- Price of Anarchy (1)
- Security Games (1)
- Semidefinite programming (1)
- Stackelberg Equilibrium (1)
Institute
Network Spot Checking Games: Theory and Application to Toll Enforcing in Transportation Networks
(2014)
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.
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.
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.
We consider a stationary discrete-time linear process that can be observed by a finite number of sensors.
The experimental design for the observations consists of an allocation of available resources to these sensors.
We formalize the problem of selecting a design that maximizes the information matrix of the steady-state of the Kalman filter,
with respect to a standard optimality criterion, such as $D-$ or $A-$optimality.
This problem generalizes the optimal experimental design problem for a linear regression model with a finite design space and uncorrelated errors.
Finally, we show that under natural assumptions, a steady-state optimal design can be computed by semidefinite programming.