Quality-bounded solutions for finite Bayesian Stackelberg games: scaling up
Quality-bounded solutions for finite Bayesian Stackelberg games: scaling up
复制标题
DOI：
10.5555/2034396.2034411
复制
发表时间：
2011-05
期刊：
影响因子：
--
通讯作者：
Manish Jain;Christopher Kiekintveld;Milind Tambe
中科院分区：
文献类型：
--
作者：
Manish Jain;Christopher Kiekintveld;Milind Tambe
已知解决具有有限追随者（对手）类型的一般贝叶斯Stackelberg博弈的最快算法已经在洛杉矶国际机场直接实际使用了3年以上；目前，一种解决这些问题的算法（尽管不是贝叶斯算法）也被美国联邦空警服务局（US Federal air marshals Service）用于在国际航班的有限航段安排空警。这些算法找到最优的随机安全调度，分配有限的安全资源来保护目标。随着我们扩展到更大的领域，包括联邦空警覆盖的全部航班，开发更新的算法至关重要，这些算法可以大大超出当前最先进的贝叶斯Stackelberg解算器的限制。本文提出了一种基于层次分解和追随者类型空间上的分支定界搜索的新方法，该方法可应用于不同的Stackelberg博弈解算。我们将这种技术应用于不同的解算器，结果是：(i)一种名为HBGS的新精确算法，它比之前最著名的一般Stackelberg游戏的Bayesian解算器快几个数量级；（ii）一种新的精确算法，称为HBSA，它将已知最快的安全博弈求解器扩展到贝叶斯情况；（iii）与这些新算法相比，HBGS和HBSA的近似版本显示出显著的改进，而实际解决方案质量仅牺牲1- 2%。
The fastest known algorithm for solving General Bayesian Stackelberg games with a finite set of follower (adversary) types have seen direct practical use at the LAX airport for over 3 years; and currently, an (albeit non-Bayesian) algorithm for solving these games is also being used for scheduling air marshals on limited sectors of international flights by the US Federal Air Marshals Service. These algorithms find optimal randomized security schedules to allocate limited security resources to protect targets. As we scale up to larger domains, including the full set of flights covered by the Federal Air Marshals, it is critical to develop newer algorithms that scale-up significantly beyond the limits of the current state-of-the-art of Bayesian Stackelberg solvers. In this paper, we present a novel technique based on a hierarchical decomposition and branch and bound search over the follower type space, which may be applied to different Stackelberg game solvers. We have applied this technique to different solvers, resulting in: (i) A new exact algorithm called HBGS that is orders of magnitude faster than the best known previous Bayesian solver for general Stackelberg games; (ii) A new exact algorithm called HBSA which extends the fastest known previous security game solver towards the Bayesian case; and (iii) Approximation versions of HBGS and HBSA that show significant improvements over these newer algorithms with only 1--2% sacrifice in the practical solution quality.