Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure
Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure
复制标题
子模结构零和博弈中的均衡计算与鲁棒优化
DOI：
10.1609/aaai.v32i1.11455
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Bryan Wilder
中科院分区：
文献类型：
--
作者：
Bryan Wilder
定义了一类具有组合结构的零和对策，其中一方的最佳对策问题是极大化一个次模函数。例如，这个类包括在网络上玩的安全游戏，以及在一组场景的最坏情况下鲁棒优化子模块函数的问题。计算均衡的挑战在于，双方的策略空间都可能是指数级的。因此，以前的算法具有最坏情况下的指数运行时间，并且确实无法在实际情况下扩展。我们给出了一个伪多项式时间算法，该算法为最大化局中人获得了一个保证的（1 - 1/e）^2-近似混合策略。我们的算法只需要访问一个弱化版本的最佳对策预言的最小化的球员，在多项式时间内运行。网络安全游戏和一个强大的预算分配问题的实验结果证实，我们的算法提供了接近最优的解决方案和规模更大的实例比以前可能的。
We define a class of zero-sum games with combinatorial structure, where the best response problem of one player is to maximize a submodular function. For example, this class includes security games played on networks, as well as the problem of robustly optimizing a submodular function over the worst case from a set of scenarios. The challenge in computing equilibria is that both players' strategy spaces can be exponentially large. Accordingly, previous algorithms have worst-case exponential runtime and indeed fail to scale up on practical instances. We provide a pseudopolynomial-time algorithm which obtains a guaranteed (1 - 1/e)^2-approximate mixed strategy for the maximizing player. Our algorithm only requires access to a weakened version of a best response oracle for the minimizing player which runs in polynomial time. Experimental results for network security games and a robust budget allocation problem confirm that our algorithm delivers near-optimal solutions and scales to much larger instances than was previously possible.