Security Games: Quasi-Regular Sequences, and a New Version of TSP
[joint work with Leonard J. Schulman and Omer Tamuz (SODA 2018) and with Mark Klein (submitted)]
In security games, a defender commits to a mixed strategy for protecting a set of n targets of values v_i; an attacker, knowing the defender's strategy, chooses which target to attack and for how long. We study a natural version in which the attacker's utility grows linearly with the time he spends at the target, but drops to 0 if he is caught. The defender's goal is to minimize the...
Read more about David Kempe: Security Games: Quasi-Regular Sequences, and a New Version of TSP