Proceedings Abstracts of the Twenty-Third International Joint Conference on Artificial Intelligence

Defender (Mis)Coordination in Security Games / 220
Albert Xin Jiang, Ariel D. Procaccia, Yundi Qian, Nisarg Shah, Milind Tambe

We study security games with multiple defenders. To achieve maximum security, defenders must perfectly synchronize their randomized allocations of resources. However, in real-life scenarios (such as protection of the port of Boston) this is not the case. Our goal is to quantify the loss incurred by miscoordination between defenders, both theoretically and empirically. We introduce two notions that capture this loss under different assumptions: the price of miscoordination, and the price of sequential commitment. Generally speaking, our theoretical bounds indicate that the loss may be extremely high in the worst case, while our simulations establish a smaller yet significant loss in practice.