论政治运动的资源配置

让G表示候选人A通过选举的事件，即G<==>Pjwj{SAj>SBj}>Pjwj{SBj>SAj}。因为我们对每个州的投票结果使用连续分布，所以平局事件的概率为零。然而，候选人的选举人票之间可能存在平局的非零概率（当票数为偶数，且有一部分州的选举人票加起来占该国选举人票的一半时）。在这种情况下，通过投掷一枚公平的硬币打破平局；我们在G的给定定义中省略了这一点，以减少符号，尽管我们在计算中考虑了这一点。候选者面临的优化问题是：maxx∈nP（G）（12）maxy∈n1-P（G）（13）莫拉莱斯、塞巴斯蒂安和色雷斯、查尔斯：政治竞选的资源分配14篇提交给POMS的文章；为了计算P（G），我们使用了类似于Kaplan和Barnett（2003）和Rigdon等人（2009）的递归过程。设Pi为候选人A赢得州i的概率，Tk为候选人A从州1到州k获得的选举人票数的rv。递推式为asP（Tk=t）=（1）-pk）P（Tk-1=t）+pkP（Tk-1=t-（工作）K∈{2，…，N}P（T=T）=（1）-p） 1{t=0}+p{t=w}。（14） 设M:=PNi=1wi，即选举人总票数。然后，候选人A当选的概率由P（G）=PMt=dMeP（TN=t）给出（如果M是偶数，则P（TN=M）必须乘以一半）。至于候选人A在状态i（pi）中获胜的概率，这可以计算为分布β（k（αi+xi），k（βi+yi））的cdf的补码，评估值为0.5（见引理1）。

注意，对于极限游戏→0时，每个状态的伯努利参数可以以闭合形式计算为pi=（αi+xi）/（αi+xi+βi+yi）。我们首先探索在纯策略中寻求平衡，然后在混合策略中寻求平衡。定义3。EC下纯策略的平衡是一对效应向量（x*, Y*) ∈确保每个向量x*和y*是表达式（12）和（13）中给出的各候选最大化问题的最优解。4.1。MS和ECIt之间的关系值得注意的是，在某些情况下，MS和ECelection系统下的游戏之间存在一些等价关系。以下定理陈述了其中两个等价物：定理4。如果选举人票数与选民人数成正比，那么以下两个游戏是相同的：oMS，候选人在没有弃权的情况下最大化预期票数，即γ=0候选人最大化预期选举人票数的选举委员会。证据见附录L。尽管更自然的是，候选人要最大限度地提高获胜的可能性，而不是在选举委员会获得的选举人票的数量；事实上，一个几乎没有胜算的政党可能更倾向于将后一个目标作为一种损害控制战略，而牺牲了获胜的机会。定理5。如果选举人票数与选民人数成正比，那么接下来的两个游戏在k的限制下是相等的→0，即两种情况下的玩家效用在概率上趋同：oMS，候选人在没有弃权的情况下最大化获胜概率，即γ=0。莫拉莱斯、塞巴斯蒂安和色雷斯、查尔斯：政治活动的资源分配提交给POMS；第15号手稿oEC，候选人将获胜概率最大化。证据见附录M。

当k接近零时，极限情况会在每个州产生一个“U”形密度函数，导致选民之间产生高度相关的结果，其中所有人要么支持一个候选人，要么支持另一个候选人。这种情况在现实中不太可能出现。4.2. 计算纯策略中的均衡我们采用梯度下降-上升法，如第3.2.1节中使用的方法，但现在将P（G）作为零和博弈的目标函数。在这种情况下，Payoff函数的导数可以写成xiP（G）=PjpjP（G）pj十一=皮普（G）圆周率西辛斯pjxi=0表示i6=j。圆周率xi是β分布的互补cdf在xi上的导数。让我们嘲笑候选人A赢得第一州选举人票的事件，让Gcibe成为这一事件的补充。全概率定律意味着P（G）=P（G | Gi）pi+P（G | Gci）（1）-pi），对piresults进行导数piP（G）=P（G | Gi）-P（G | Gci）。P（G | Gi）和P（G | Gci）可以使用与方程式（14）中引入的相同的递归计算，但当条件事件为Gior GCIRespective时，将ITHState的结果划分为获胜（pi=1）或失败（pi=0）。然后我们开始xiP（G）=（P（G | Gi）-P（G | Gci））kE[ln（SAiSAi+SBi）1{SAi≥SBi}]+piθ（k（αi+xi），k（βi+yi））,（15） 式中θ（a，b）：=ψ（a+b）-ψ（a）和ψ是digamma函数。与候选B类似。因此，我们可以使用第3.2.1节中描述的相同程序，尤其是命题2和算法1的使用。通过数值计算，我们发现梯度下降-上升法收敛到一个点，至少在数值上，该点似乎是一个平衡点或局部纳什平衡点。特别是，参数k（控制可变性）似乎在这方面起着关键作用。低的k值会导致均衡的存在，而高的k值会导致局部纳什均衡。

直觉上，后一种情况类似于博弈的决定论版本，因为在极端情况下（ofk），纯均衡似乎不可信→ ∞), 支付函数甚至不是连续的。由于纯策略中缺乏均衡，我们探讨了确实存在的混合策略中的均衡。定理6。在EC下，随机博弈的混合策略存在一个均衡。证据证据遵循附录F中给出的相同论点。不幸的是，寻找博弈的混合均衡并不是一项简单的任务。此外，这可能会导致复杂的策略，对相关代理来说可能不实用。因此，我们决定在有限的策略子集中寻找博弈的混合均衡。请注意，莫拉莱斯、塞巴斯蒂安和色雷斯、查尔斯：《政治活动的资源分配》16篇文章提交给POMS；手稿号。由于这是一个零和博弈，如果策略子集是有限的，我们可以通过简单求解一个LP得到一个混合均衡。更准确地说，考虑（n，q）-单纯形晶格（如Scheffe（1958）中介绍的）作为点Dq的集合(n） ：={x∈ Rn|xi≥ 0，Pni=1xi=1，xiq∈ Z+}其中q∈ Z+。后一组表示单纯形的离散化（还请注意，我们只考虑Pixi=1时的策略），其中参数q控制网格的限制，因此该参数的高值导致更精确的集合，见图1。直观地说，（n，q）-simplexlattice代表了玩家的策略，因此每个玩家都有q个不可区分的球，他们必须在n个州之间进行投资。（n，q）-SimpleX晶格中的元素数为n+qn, 不幸的是，它在状态数和参数Q上是指数型的。然而，我们可以想出一种方法，只考虑Dq中的一部分策略(n） 。

然后，为了在混合策略中找到平衡，我们考虑以下迭代过程：1。从两位Dq玩家的策略子集开始(n） 二,。在混合策略中找到平衡点3。在行动空间中探索玩家在纯策略中的最佳反应n、 四,。对于每个玩家在步骤3中的最佳响应，获取单纯形晶格中的顶点，这些顶点生成包含最佳响应的最小凸包。将这些顶点添加到相应的玩家策略集中。如果两个参与者都没有新的策略需要添加，则完成；否则，请转至步骤2。图1 Dq的示例() 对于q=1,2,3,4。为了将后者正式化，考虑策略集TA、TBDq(n） 每一位选手。对于第一步，我们从两个参与者的一小套策略开始。例如，这些可以是n个标准向量EIN，其中在ITH分量中有一个1，在其他地方有一个0，对于i=1，n、 对于第2步，定义混合策略中的均衡，其中参与者有一套明确的策略。定义4。离散策略集Ta和Tb在EC下的混合策略均衡是一对向量（σ*A、 σ*B）∈ |TA |×|TB |以至于σ*A.∈ arg最大σEσ，σ*B[P（G）]和σ*B∈arg maxσEσ*A、 σ[P（G）]。莫拉莱斯、塞巴斯蒂安和色雷斯、查尔斯：政治活动的资源分配提交给POMS；17号手稿如前所述，由于零和博弈结构，这种均衡可以通过解一个LP来找到。让P∈R | TA |×| TB |是第一个参与者的支付矩阵，即Pij=P（G），其中x设置为TA的利润策略，与TB类似，y设置为。我们可以求解以下LPsmaxv，σAvs。t、 烦恼-PTσB≤0eTAσA=1σA≥0，（16）分钟，σ总线。t、 ueA-PTσB≥0eTBσB=1σB≥0，（17）其中ea和eBare向量分别带有| TA |和| TB |个。

详见附录N。对于第3步，我们需要找到玩家在游戏中纯策略的最佳反应甚至是他们对手的混合策略。为了做到这一点，我们对每个参赛者使用梯度下降法，根据参赛者的混合概率，考虑目标导数的期望。因此，候选者A考虑关于σ的期望*B、 而B是关于σ的*A.对于第4步，考虑x∈nas是候选人A（wlog）的最佳回应。我们希望在单纯形晶格中找到凸壳中包含x的点，同时尽可能小（在这个意义上，这些点中没有其他子集也包含凸壳中的x）。回想一下，单纯形晶格的网格元素是由参数q给出的，这意味着Dq中所有点的分量(n） 是1/q的倍数。然后，我们可以从分析中去掉x的分数部分，即1/q的倍数，并保留余数；也就是说，我们可以定义xr:=x-bqxcq∈[0，q）n，其中fl-oor函数适用于每个组件。通过q放大XRB可得到qxr∈[0,1）n.让我们定义m:=Pni=1qxri，然后我们可以陈述以下权利要求：权利要求1.它认为m∈{0,1，…，n-1}.证据见附录O。让Y:={Y∈{0,1}n|Pni=1yi=m}。然后，我们的目标是在Y中找到向量的子集，这样qxrca就可以写成这些向量的凸组合。这导致纳米要从中选择的向量。因此，我们使用以下算法：莫拉莱斯、塞巴斯蒂安和色雷斯、查尔斯：政治竞选资源分配18篇提交给POMS的文章；算法2：寻找包含小数点1的二进制向量：输入y∈[0,1）n，s.t.m=Pni=1yi∈{0, 1, . . .

N-1} 2：设置Z=, w=y3:w=6∈{0，1}ndo4:z=arg minv∈Ykw-vk5:Z=Z∪{z} 6:t=minmini:wi<zinwizi-wio，mini:wi>zin1-女巫-zioo7:w=w+t×（w）-z） 8：结束，9:z=z∪{w} 10:Return Z如果给定一个分数点，算法2将返回一个集合，其中Y方向的向量在其凸包中包含分数点。尤其是在每次迭代中：在第4行中，它会找到Y中距离当前点w最近的点。请注意，第4行中的目标函数可以写成kw-vk=Pjwj+Pjvj- 2Pjvjwj=kwk+m- 2Pj:vj=1wj，在n维线性向量中，w的m个最大分量中有一个最佳值，其他地方为0。关系可以随意中断。在第5行中，我们将z添加到输出集z。在第6行和第7行中，我们从当前点w沿w方向移动-z，直到第一个分量达到0或1（来自不同的前一个值），更新当前点w。这个循环重复，直到当前点是二进制的，在这种情况下，我们停止迭代，并将该点添加到集合z（第9行）。下一个引理说明了算法2的一些性质。引理2。在算法2中，将z（k）表示为在集合z中添加的KTH点，将t（k）表示为在算法2中的KTH运算中标量t的值。（i） 该算法最多在n次迭代中完成，即| Z|≤n、 （ii）算法输入y的凸组合的权重可计算为λk=t（k）1+t（k）Qk-1j=11+t（j）k<| Z |，λ| Z |=Q | Z | j=11+t（j），其中λk>0表示所有k.证明。见附录P。我们可以从引理2中看出，要返回的点的输出是线性的（最多n个）。事实上，在每次迭代中，算法将w的一个分量固定为0或1，在剩余的迭代中保持其值不变。后者是引理2第二个主张的结果。

有趣的是，算法2不仅返回输入点为凸组合的顶点，还通过使用算法的中间计算返回凸组合的权重。算法2]在O（n）中运行。莫拉莱斯、塞巴斯蒂安和色雷斯、查尔斯：政治活动的资源分配提交给POMS；手稿19那么，我们可以使用y=qxrin的算法2，以获得y中最多n个点，并将这些点转换为原始尺度（回想一下，算法2在[0,1]超立方体中工作，与q无关）。更准确地说，如果x∈ nis是其中一个玩家的最佳响应，那么要添加到玩家策略集中的简单格点是Z（x）：={bqxcq+zkq | zk∈ Z（qxr）}（注意基数最多为n），其中我们使用符号Z（qxr）表示算法2的输出，输入y=qxr。图2显示了算法2如何在原始空间中迭代n=3且网格中符合单纯形晶格的点。图2算法2。蓝点是最好的回应不公开。第二个面板的白点代表第一次迭代的z，而黑色部分代表光线w- z、 在第三个面板中，红色的点代表新的点w。新的点z在第四个面板中以红色表示，最后一个点w在第五个面板中以白色表示。最后，可以说，在Dq中没有其他集合的情况下，集合Z中的附加点是最小的(n） ，例如W，它生成x作为凸组合，例如Conv（W）（Conv（Z）。正式证明见附录Q。

总之，下面给出了在单纯形格的子集上作为策略集找到混合平衡点的完整算法。算法3单纯形格子集混合平衡的算法1：输入α，β∈Rn+，k∈R+，w∈Zn+，q∈Z+2：设置TA，TB={ei∈恩，我∈一} ，Pij=P（G | x（I），y（j））（x（i），y（j））∈TA×TB3：而真do:4:（σA，σB）=解（P）5:xBR=arg maxx∈nP（G | x，σB），yBR=arg miny∈nP（G |σA，y）6:If Z（xBR）TAZ和yBRTB:Break7:TA=TA∪Z（xBR），TB=TA∪Z（yBR）8:Update P9:End While10:Return（TA，σA，TB，σB）Morales，Sebasti\'an和Thraves，Charles:Resource Allocation for Political Campaigns提交给POMS的20篇文章；算法3第2行中的策略集用标准向量初始化，并在这些策略对下计算支付矩阵P。第4行通过求解优化问题（17）和（16）来计算混合平衡。第5行和第6行计算连续空间上的每个候选最佳响应n、 在第7行中，我们计算simplexlattice中的离散化向量，以获得最佳响应；如果这些集合Z（xBR）和Z（yBR）已经包含在各自的玩家策略集合（TAB和TB）中，则算法完成。如果不是这样，新的离散化策略将添加到第11行和第12行的玩家策略集中。最后，更新支付矩阵，以包括涉及新策略的成对玩家策略的支付。5.数值结果在本节中，我们展示了在多数票和选举人团投票制度下产生的不同设置下博弈均衡的数值计算。然后，我们分析了两种选举制度的两极分化效应。5.1. 多数制5。1.1.

确定性案例：我们将分析重点放在策略非负面的案例上。无界博弈（即，无非负性约束）的数值结果如附录R所示。表1显示了MS下确定性博弈在由十个区域组成的瞬间的均衡。该地区的投票份额、偏见和弃权参数分别在第2、3-4和5栏中给出。我们观察到，只有前三个地区，即投票份额最大的地区，被两位候选人选中进行投资。把所有地区的结果加起来，我们看到候选人A、候选人B和弃权票分别为30.0%、28.9%和41票。分别为1%。因此，候选人A通过在A和B之间的选举中获得50.9%的选票而获胜。在候选人投资的地区中，从表1可以看出，他们将大部分资源分配到了偏向其竞争者的地区。例如，与候选B相比，候选A在区域1的偏向性较差（即α<β）；因此，在均衡状态下，候选人A最终将68.3%的资源投资于该地区（而候选人B的投资比例为36.4%）。因此，候选人a最终获得的地区1的投票率略高于一半。（见表1最后一列）。与第一个地区相比，第二个地区的偏见和候选投资方向相反。