连续Blotto的部分解

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《A Partial Solution to Continuous Blotto》
---
作者：
Kostyantyn Mazur
---
最新提交年份：
2017
---
英文摘要：
  This paper analyzes the structure of mixed-strategy equilibria for Colonel Blotto games, where the outcome on each battlefield is a polynomial function of the difference between the two players\' allocations. This paper severely reduces the set of strategies that needs to be searched to find a Nash equilibrium. It finds that there exists a Nash equilibrium where both players\' mixed strategies are discrete distributions, and it places an upper bound on the number of points in the supports of these discrete distributions.
---
中文摘要：
本文分析了Blotto上校博弈混合策略均衡的结构，其中每个战场上的结果是两个博弈方分配差异的多项式函数。本文严重减少了需要搜索以找到纳什均衡的策略集。研究发现，当两个参与者的混合策略都是离散分布时，存在一个纳什均衡，并且在这些离散分布的支持点上设置了一个上界。
---
分类信息：

一级分类：Quantitative Finance        数量金融学
二级分类：Economics        经济学
分类描述：q-fin.EC is an alias for econ.GN. Economics, including micro and macro economics, international economics, theory of the firm, labor economics, and other economic topics outside finance
q-fin.ec是econ.gn的别名。经济学，包括微观和宏观经济学、国际经济学、企业理论、劳动经济学和其他金融以外的经济专题
--
一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Mathematics        数学
二级分类：General Topology        一般拓扑
分类描述：Continuum theory, point-set topology, spaces with algebraic structure, foundations, dimension theory, local and global properties
连续统理论，点集拓扑，代数结构空间，基础，维数理论，局部和全局性质
--

---
PDF下载：
--> A_Partial_Solution_to_Continuous_Blotto.pdf (386.94 KB)

2022-6-1 01:06:01 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Lott Ott distribution Quantitative Environments

连续BlottoKostyantyn Mazur的部分解*2022年3月4日摘要本文分析了ColonelBlotto游戏的混合策略均衡结构，其中每个战场上的结果是两个玩家分配差异的多项式函数。本文总结了需要搜索的一组策略，以找到纳什均衡。研究发现，当两个参与者的混合策略都是离散分布时，存在一个纳什均衡，并且在这些离散分布的支持下，给出了点数的上界。*克斯特亚·恩坦·马祖，纽约州布罗科林Metrotech中心6号，新约尔克大学坦顿工程学院；电子邮件：km1883@nyu.eduI感谢Laurent Mathevet博士（纽约大学经济系）和Edward Miller博士（纽约大学坦顿工程学院数学系）对本论文的贡献。内容1简介42模型93主要结果104方法104.1坝址的对称化。114.2预期付款作为零售产品。114.3降维。124.4凸面外壳。155扩展175.1减少组件数量。175.1.1 R度。175.1.2删除奇数坐标。175.1.3删除第0个坐标。195.1.4扩展Carath'eodory定理。205.1.5总影响。215.2其他可能的扩展。

226结论227附录1：引理238附录2：计算491简介Blotto上校是一款双人游戏，其原型版本是两名上校在多条战线上展开战斗。例如，在经济背景下，上校可能是两个在多个地理区域同时竞争的公司，或者两个寻求“赢得”尽可能多的地方的政治候选人。每个上校只有固定数量的兵种（或资源）可以分配到各条战线上，任何一个上校在一条战线上分配更多的兵力都将赢得这条战线。两位上校都希望赢得尽可能多的战线。如果一位上校知道另一位上校如何安排部队，那么这位上校只需安排一名士兵就可以赢得除一条战线以外的所有战线。因此，每个上校都必须采取混合战略；也就是说，随机决定如何安排部队。当然，正是从哪个分布决定了Randomly的纯策略。本文研究了两个战场上的Blotto，其中战场上的结果持续取决于该战场上的分配优势，而迄今为止，这一领域几乎没有受到重视。这样做的动机是，一名士兵的人数超过对手并不能保证驱逐。再有一名士兵是一种优势，但战斗可能还是会走另一条路。优势越大，获胜的可能性越大。因此，将获胜概率设为两个兵力的连续函数是合理的（而不是经典的Blotto游戏中使用的函数：分配较大的玩家为1，其他玩家为0）。目标是最大化赢得的战场数量的预期价值。由于预期是一个线性函数，每个战场的获胜概率可以用预期的获胜战场数来重新解释。

例如，57%的获胜概率意味着0.57个战场的预期价值。这种解释更加有用，因为它也可以适应不同程度的胜利。毕竟，并非所有的战斗都是一方或另一方的明确胜利。从函数中减去0.5也是合理的，因此战场上的积极结果代表预期的胜利（积极结果越大，胜利的可能性越大），而消极结果则相应地代表预期的失败。因此，0.57个战场的预期结果变成了0.07个战场的预期结果，比该战场上的平均结果要好。这种减法效应将常数和博弈转化为零和博弈。这个预期结果可以写为战场上分配差异的函数，这个函数可以称为结果函数。如果两个玩家拥有相同的资源，那么，至少如果结果函数是一个奇数函数，那么这个游戏将有一个简单的解决方案：两个玩家都可以玩任何策略，结果将为零。一个战场上的任何收益将由另一个战场上同等大小的损失来补偿。因此，有必要在游戏中引入一些不公平，要么让结果函数不奇怪，要么让一个玩家在资源上占优势。该pa per的模型可适应两种方法。众所周知，这样的博弈有一个纳什均衡；Glicksberg定理[7]保证了这一点。

本文证明，如果结果函数是多项式的，则不仅存在纳什均衡，而且存在一个双方仅从少量纯策略中选择的纳什均衡。实际上，准确地找到平衡是一件困难的事情。这种类型的游戏可以模拟两个公司同时在两个市场上竞争，其中一个公司恰好更大。如果（例如）一个政党在一个地区的席位数量与该政党在该地区的投票比例成正比，那么它还可以模拟两个政党在两个地区的竞争（通过花费竞选资金），而这是经典的损益表无法做到的。它还可以模拟赢家通吃的规则，因为仅仅花费超过对手并不能保证赢得一个地区。确实，精确的结果函数不太可能是多项式，但可以通过几个点用多项式拟合。多项式经过的点数越多，结果越接近纳什均衡，但评估博弈就越困难。在零和博弈中，纳什均衡代表了两个博弈方的完美策略，即每个博弈方的策略（如果在均衡中进行）保证该博弈方至少获得均衡结果。这两个组合的保证排除了任何一个球员寻求更好结果的可能性，因为对手的均衡策略使得无论球员做什么都不可能。在某种程度上，（零和）ColonelBlotto g ame正确地反映了经济竞争，纳什均衡为双方提供了完美的策略。不，主要是，对于一系列连续的期权，纳什均衡看起来像是一个连续的分布，所有这些一起构成了一个有限维空间。

本文表明，一类特殊的连续Blotto博弈是例外，它具有纳什均衡，而纳什均衡只能通过搜索策略的有限维空间来获得，每个策略都有一个简单的f形式。本文使用的一般方法是混合策略集的一系列约简和变换，这些策略表示为概率密度函数。首先，任何一个玩家的纯策略都只由一个数字表示，x代表玩家1，y代表玩家2。（如果有资源优势，让玩家1成为具有资源优势的玩家。）基于这个数字的支付函数矩阵（称为E）有很多行和列（玩家1选择行，玩家2选择列）。然而，在很多列（或行）中，只有N+1（其中N是函数结果的阶数）是线性独立的，本质上是因为这些列是x中至多N阶的多项式，是纯策略的参与者1的选择。这意味着E将所有函数的空间映射到一个有限维空间。因此，只有一个（N+1）维函数空间g（玩家2策略的概率密度函数），其中Eg是不同的。因此，如果g是另一个函数，则Eg=Eg。但是，如果f是参与者1混合策略的概率密度函数（对于参与者2也是如此），则预期结果为fTEg。如果Eg=Eg，那么fTEg=fTEg不考虑f是什么，因此玩家2的每个策略f都相当于（N+1）维空间中的一个g。如果这两名球员对位，这也同样有效。换句话说，存在一个（N+1）维的等价策略类空间（对于任何一个玩家），其中相同等价类中的任何两个策略都是payoff等价的。每个等价类都可以描述为（N+1）维向量。

这是足球运动员的遗憾。此外，将策略的概率密度函数化简为策略等价类的向量的函数可以是线性的。因此，它保留了凸组合。因此，所有等价类的向量都是纯策略等价类向量的凸组合。（N+1）维空间中形成曲线的纯策略的等价类。然而，Carath'eodory定理指出，（N+1）-维空间中点的每个凸组合可以描述为大多数N+2点的凸组合。这意味着，包含任何策略的每个等价类都包含一个仅由无数（最多N+2）个纯策略的凸组合，或者，等效地，包含at代表转置，并且这种乘法应该被解释为伪矩阵乘法，用一个整数代替求和。凸组合是具有非负权重的加权平均；这里，权重是混合策略的概率密度函数。最多N+2个分量的离散分布。

无论任何纳什均衡策略位于何处，其等价类都包含一个具有这种离散分布类型的策略，该策略与纳什均衡策略等价（因此也是一个Na-sh均衡策略）。找到Blotto g ames的纳什均衡是许多论文的主题，每一篇论文的任务都是涵盖条件的特定变化，第一篇提出问题的是Borel，在[5]（翻译成英文为[6]）。变化的因素包括参与者的目标（最大化预期价值或赢得多数票的可能性），分配是可以离散地还是连续地变化，战场的数量，每个上校可以使用的部队数量（以及一个上校是否比另一个上校多的部队），FRONT的相关值（其中AIM将使赢得的总价值最大化）、博弈是否为零和，甚至资源约束的性质。其中包括温斯坦（20）、哈特（10）、格罗斯（Gross）和瓦格纳（Wagner）的（9）、罗伯森（Roberson）和克瓦索夫（Kvasov）的（17）、霍塔拉（Hortala Vallve）和洛伦特（Llorente Saguer）的（11）、施瓦茨（Schwartz）、卢瓦索（Loiseau）和萨斯特里（Sastry）的（18）、托马斯（Thomas）的（19）、科文诺克（Kovenock）和R oberson的（12）、麦克唐纳（Macdonell）和马斯特罗纳尔迪。Macdonell和Mastronardi的论文与该论文的结果相似，因为它也有两个资源不平等的战场，以及一组始终包含离散分布的纳什均衡。本文探讨了Blotto的另一个维度，其结果取决于胜利的程度。即使是这种形式的污点也被探索过，尽管没有传统的赢/输污点那么多。不幸的是，这些论文只搜索纯策略，如果没有，使用这些论文的方法可以得出的唯一结论就是：“不存在纯策略纳什均衡”。

Blackett的[4]就是一个例子，它只有一个存在纯战略平衡的必要条件。Blackett允许任何结果函数。Golman和Page的[8]有一个单参数的结果函数族，并允许多个领域和小领域结果之间的依赖关系，但Golman和Page发现，在他们研究的大多数案例中，纯战略均衡并没有特克斯特。Os’orio的[16]确实成功地找到了一个纯策略纳什均衡，但该论文仅限于一类狭窄的结果函数。这篇论文是对纯策略搜索的补充，因为它充分说明了需要考虑的策略是多么“不纯”。文献[15]探讨了m of Blotto的混合策略均衡，但该论文将其结果函数限制在一个有限的参数集。根据混合策略，离散分布混合策略的一个组成部分是以正概率发挥作用的纯策略之一。Bellman[3]的凸优化方法在这里不适用，因为其假设（根据本文的语言）在所有战场上，结果函数在玩家1的分配中是凹下的，在玩家2的分配中是凹上的。当结果函数是分配差异的函数（如这里所示）时，这种假设几乎总是不正确的。然而，Beale和Heselden方法的更简单版本【1】，也是Behnezhad、Dehghani、Derakhshan、HajiAghayi和Seddighin算法的更简单版本【2】，适用于此处。玩家1获取一个整数L（L越大，近似值越高，但计算所需的时间越长），并将两个玩家的可能分配视为是否需要N+aL的整数倍。

然后，玩家1将每种策略的概率视为变量，为支付添加一个额外的变量，并建立不等式，以反映概率必须为非负且总和为1，并且对任何一个玩家2的策略的预期支付不低于支付变量。玩家1试图最大化受这些不平等影响的支付风险，并使用线性规划模型来实现这一点。这是当L上升时可能产生越来越复杂的平衡策略的缺点，这里证明了在多项式结果函数的情况下，这是不必要的。由于知道存在离散分布的纳什均衡策略，且分量数量有上界，因此更容易通过分析或数值方法搜索纳什均衡。实现这一点的一种可能的方法是，根据组成部分的数量，以及使用“边缘”策略（如果有的话）作为组成部分，对每个参与者可能的混合策略进行分组。然后，在每一组中，玩家控制的参数是：哪些纯策略是组件，以及玩组件的所有概率中的一个。