Events Calendar

Teamcore Seminar: Dr. Guillaume Sagnol (Zuse-Institute Berlin) - On the price of spite in Spot-checking games

Speaker: Dr. Guillaume Sagnol, Zuse-Institute Berlin

Talk Title: On the price of spite in Spot-checking games

Series: CS Colloquium

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 edges to be controlled.
Although SC games are not zero-sum, we show that a (mixed) 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 price of spite, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. That is, the inspector chooses the most harmful strategy for his opponents (because it is easy to compute) rather than the best strategy for himself. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways.

Biography: Dr. Guillaume Sagnol is a post-doc fellow at Zuse-Institute Berlin and has been a member of this institute since 2010. He holds an engineering degree and a PhD from the French grande école "Mines Paristech". Prior to joining the ZIB he was working as a PhD student in a joint team between INRIA Saclay and Ecole Polytechnique.

His research interests lie in the areas of approximation algorithms for hard combinatorial problems, game theory, and conic programming. In particular, he has developed new SDP and SOCP formulations for the computation of "optimal experimental designs", an area at the interface of statistics and optimization. He he now working on several applied optimization projects, like the optimization of toll enforcement on German motorways, or scheduling problems in surgery planning.

Host: Teamcore

Location: Charles Lee Powell Hall (PHE) - 223

Audiences: Everyone Is Invited

Contact: Assistant to CS chair