We study a class of two-player zero-sum Colonel Blotto games in which, after allocating soldiers across battlefields, players engage in (possibly distinct) normal-form games on each battlefield. Per-battlefield payoffs are parameterized by the soldier allocations. This generalizes the classical Blotto setting, where outcomes depend only on relative soldier allocations. We consider both discrete and continuous allocation models and examine two types of aggregate objectives: linear aggregation and worst-case battlefield value. For each setting, we analyze the existence and computability of Nash equilibrium. The general problem is not convex-concave, which limits the applicability of standard convex optimization techniques. However, we show that in several settings it is possible to reformulate the strategy space in a way where convex-concave structure is recovered. We evaluate the proposed methods on synthetic and real-world instances inspired by security applications, suggesting that our approaches scale well in practice.


翻译:我们研究了一类双人零和布洛托上校博弈,其中玩家在将士兵分配到各个战场后,在每个战场上参与(可能不同的)标准形式博弈。每个战场的收益由士兵分配参数化。这推广了经典的布洛托博弈设定,其中结果仅取决于相对士兵分配。我们考虑了离散和连续分配模型,并考察了两种类型的聚合目标:线性聚合和最坏情况战场价值。针对每种设定,我们分析了纳什均衡的存在性与可计算性。该一般问题不具备凸凹性,这限制了标准凸优化技术的适用性。然而,我们证明在多种设定下,可以通过重构策略空间来恢复凸凹结构。我们在受安全应用启发的合成和真实世界实例上评估了所提出的方法,结果表明我们的方法在实践中具有良好的可扩展性。

0
下载
关闭预览

相关内容

专知会员服务
21+阅读 · 2021年8月9日
专知会员服务
17+阅读 · 2021年8月6日
专知会员服务
42+阅读 · 2021年1月18日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
半监督多任务学习:Semisupervised Multitask Learning
我爱读PAMI
18+阅读 · 2018年4月29日
读论文Discriminative Deep Metric Learning for Face and KV
统计学习与视觉计算组
12+阅读 · 2018年4月6日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
46+阅读 · 2015年12月31日
国家自然科学基金
6+阅读 · 2014年12月31日
国家自然科学基金
5+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
Arxiv
0+阅读 · 11月22日
VIP会员
相关VIP内容
专知会员服务
21+阅读 · 2021年8月9日
专知会员服务
17+阅读 · 2021年8月6日
专知会员服务
42+阅读 · 2021年1月18日
相关资讯
相关基金
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
46+阅读 · 2015年12月31日
国家自然科学基金
6+阅读 · 2014年12月31日
国家自然科学基金
5+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员