Poster
Learning Optimal Commitment to Overcome Insecurity
Avrim Blum · Nika Haghtalab · Ariel Procaccia

Thu Dec 11th 02:00 -- 06:00 PM @ Level 2, room 210D #None
in Poster Session »

Game-theoretic algorithms for physical security have made an impressive real-world impact. These algorithms compute an optimal strategy for the defender to commit to in a Stackelberg game, where the attacker observes the defender's strategy and best-responds. In order to build the game model, though, the payoffs of potential attackers for various outcomes must be estimated; inaccurate estimates can lead to significant inefficiencies. We design an algorithm that optimizes the defender's strategy with no prior information, by observing the attacker's responses to randomized deployments of resources and learning his priorities. In contrast to previous work, our algorithm requires a number of queries that is polynomial in the representation of the game.

Author Information

Avrim Blum (CMU)
Nika Haghtalab (Carnegie Mellon University)
Ariel Procaccia (Carnegie Mellon University)

More from the Same Authors