大型选举打成平手的可能性有多大？

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

摘要翻译：
在社会选择、博弈论、政治学和公共选择等许多学科中，理解选举被打成平手的可能性是一个经典的话题。尽管有大量的文献和普遍认为联系是罕见的，但除了I.I.D.下几个简单的位置评分规则之外，人们对大型选举中联系有多罕见知之甚少。对选票的均匀分配，被称为社会选择中的公正文化(IC)。特别是，在Marchant于2001年明确提出在IC下建立k-way联系的可能性作为一个悬而未决的问题后，进展甚微。在一个比I.I.D.更普遍和更现实的模型下，我们给出了一个关于广泛的普遍研究的投票规则的开放问题的渐近回答。模型（特别是IC）--夏的平滑社会选择框架，受斯皮尔曼和滕的平滑复杂性分析的启发。在位置计分规则、基于边序的规则和基于多轮计分的淘汰规则下，我们证明了关于平分的光滑似然性的二分定理，这些规则包括常见的投票规则，如复数规则、Borda规则、veto规则、maximin规则、Copeland规则、排序对规则、Schulze规则、STV规则和Coombs规则作为特例。我们还在Preflib上对合成数据和真实世界秩数据进行了实验，对理论结果进行了补充。我们的主要技术工具是关于泊松多项式变量在多面体中的光滑似然性的改进的二分刻划，这是通过探索多面体的V-表示和矩阵表示之间的相互作用而证明的，可能是独立的兴趣。
---
英文标题：
《How Likely Are Large Elections Tied?》
---
作者：
Lirong Xia
---
最新提交年份：
2021
---
分类信息：

一级分类：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系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Economics        经济学
二级分类：Theoretical Economics        理论经济学
分类描述：Includes theoretical contributions to Contract Theory, Decision Theory, Game Theory, General Equilibrium, Growth, Learning and Evolution, Macroeconomics, Market and Mechanism Design, and Social Choice.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--
一级分类：Mathematics        数学
二级分类：Statistics Theory        统计理论
分类描述：Applied, computational and theoretical statistics: e.g. statistical inference, regression, time series, multivariate analysis, data analysis, Markov chain Monte Carlo, design of experiments, case studies
应用统计、计算统计和理论统计：例如统计推断、回归、时间序列、多元分析、数据分析、马尔可夫链蒙特卡罗、实验设计、案例研究
--
一级分类：Statistics        统计学
二级分类：Statistics Theory        统计理论
分类描述：stat.TH is an alias for math.ST. Asymptotics, Bayesian Inference, Decision Theory, Estimation, Foundations, Inference, Testing.
Stat.Th是Math.St的别名。渐近，贝叶斯推论，决策理论，估计，基础，推论，检验。
--

---
英文摘要：
  Understanding the likelihood for an election to be tied is a classical topic in many disciplines including social choice, game theory, political science, and public choice. Despite a large body of literature and the common belief that ties are rare, little is known about how rare ties are in large elections except for a few simple positional scoring rules under the i.i.d. uniform distribution over the votes, known as the Impartial Culture (IC) in social choice. In particular, little progress was made after Marchant explicitly posed the likelihood of k-way ties under IC as an open question in 2001.   We give an asymptotic answer to the open question for a wide range of commonly studied voting rules under a model that is much more general and realistic than i.i.d. models (especially IC) -- the smoothed social choice framework by Xia that was inspired by the celebrated smoothed complexity analysis by Spielman and Teng. We prove dichotomy theorems on the smoothed likelihood of ties under positional scoring rules, edge-order-based rules, and some multi-round score-based elimination rules, which include commonly studied voting rules such as plurality, Borda, veto, maximin, Copeland, ranked pairs, Schulze, STV, and Coombs as special cases. We also complement the theoretical results by experiments on synthetic data and real-world rank data on Preflib. Our main technical tool is an improved dichotomous characterization on the smoothed likelihood for a Poisson multinomial variable to be in a polyhedron, which is proved by exploring the interplay between the V-representation and the matrix representation of polyhedra and might be of independent interest.
---
PDF下载：
--> English_Paper.pdf (2.09 MB)

2022-4-19 18:57:58 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：可能性 Presentation distribution Environments Multivariate

大型选举打成平手的可能性有多大？夏立荣，伦斯勒理工学院，特洛伊，纽约12180，美国，XialiRong@gmail.comabstract，理解选举打成平手的可能性是包括社会选择、博弈论、政治学和公共选择在内的许多学科的经典话题。这个问题不仅作为概率论和统计学中的一个基本问题而重要，而且因为它在许多其他重要问题中扮演着关键的角色，如投票的优柔寡断、策略投票、投票的隐私、投票权、选民投票率等。尽管有大量的文献和人们普遍认为联系是罕见的，但除了I.I.D.下的几个简单的位置评分规则之外，人们对联系在大型选举中有多罕见知之甚少。在社会选择中被称为公正文化(IC)。特别是Marchant在2001年明确提出了IC下K-路联系的似然性作为一个开放问题[38]之后，我们对这个开放问题给出了一个更普遍和更现实的模型，称为平滑的社会选择框架[66]，该模型受著名的平滑复杂性分析Spielmanand Teng[59]的启发，为广泛的普遍研究的投票规则提供了一个渐近的答案。在位置计分规则、基于边序的规则和基于多轮计分的淘汰规则下，我们证明了关于平分的光滑似然性的二分定理，这些规则包括常见的投票规则，如复数规则、Borda规则、veto规则、maximin规则、Copeland规则、排序对规则、Schulze规则、STV规则和Coombs规则作为特例。本文还通过对合成数据和真实秩数据的实验，对文献[41]中的理论结果进行了补充。我们的维护工具是通过探索多面体的V-表示和矩阵表示之间的相互作用，改进了泊松多项式变量在多面体中的平滑似然性的刻画，并且可能具有独立的利益。1引言假设两个备选方案（候选人）a和b之间的总统选举即将举行，并且有n个代理人（选民）。每个智能体独立投票给概率为0.5的备选方案，投票数多的备选方案获胜。选举以平局告终的可能性有多大？如果有两个以上的备选方案，代理对备选方案进行排名，并使用基于排名的投票规则来选择获胜者，该怎么办？如果分布不是独立的和同分布的（I.I.D.）在社会选择、博弈论、政治学和公共选择等多个学科中，理解两党选举的可能性是一个重要而经典的话题，不仅因为它是概率论和统计学中的一个基本问题，而且因为它在许多重要问题中发挥着关键作用。例如，在投票的犹豫不决[27]、战略投票[26，56]、投票的隐私[35]等情况下，联系是不可取的。另一方面，在投票权[3]、选民投票率[19，55]等情况下，联系是可取的。虽然两个选择的联系的可能性是众所周知的[3，5]，但除了几个简单的规则之外，我们并不知道有三个或更多选择的选举的数学分析是不可靠的。以往的研究主要集中在三个维度上：（1）选举中使用的投票规则；（2）选举结果的不确定性，用平局的票数来衡量；（3）产生选票的统计模型。更多讨论见1.1节。尽管有这些问题，下面的问题基本上仍然悬而未决。在现实模型下，大型选举有多大可能打成平手？具体来说，Marchant[38]提出了在I.I.D.下，超越某些位置计分规则的打成平手的可能性。均匀分配被称为社会选择中的公平文化，在2001年成为一个开放的问题，但此后我们并没有看到任何进展。

在社会选择理论中，IC一直是超普适选择，但它也被广泛批评为不切实际[34]。事实上，在IC下，这个问题已经具有很大的挑战性，如下面的例子1所示。考虑在Borda规则下，对于3个备选方案和n个代理，三向联系的概率。Bordais是一种位置评分规则，它根据每个备选方案的等级对其进行评分。在Borda下，eachagent使用替代方案的线性顺序来表示他/她的偏好，排名第i的替代方案获得M-I分。获胜者是总点数最大的备选方案。例1。设A={1,2,3}表示备选方案集。对于A上的每一个线性阶R,letxr表示一个随机变量，该变量表示投票数为R的代理的数目，当它们的投票数是均匀随机产生的（即IC）。例如，X表示1-2-3的倍数。然后，给出了Borda W.R.T.下3向联系的概率。IC可以用下列线性方程组成立的概率来表示，其中（1）备选方案1和2是并列的状态，(2)备选方案2和3是并列的状态，(3)备选方案1和3是并列的状态。2X+2X+X+X=2X+2X+X+X=2X+2X+X+X(2)2X+2X+X+X=2X+2X+X+X=2X+2X+X+X=2X+2X+X+X(3)精确界定并列似然的方法来自两种统计相关性。fiefrst类型由x的各分量之间的相关性组成。也就是说，对于任何线性阶R和W的配对，XRand XWare都是统计相关的。第二类包括方程之间的相互关系，以及更一般的不等式，正如我们将在本文研究的一般问题中看到的那样。例如，虽然在例1中（1）和（2）意味着(3)，这很简单，但不清楚（1）和（2）之间存在多大的相关性。现有的渐近工具，如多元中心极限定理和Berry-Esseen型定理[6,61,16,17,54]（又称Lyapunov型界）都含有O(n-0.5)或更高的误差界，这些误差界太粗，与本文将要证明的下界不匹配。由于不平等、其他投票规则、其他替代方案的数量、其他K和非I.I.D,这个问题变得更加具有挑战性。投票上的分配。模型。我们在平滑的社会选择框架[66]下讨论了联系的可能性，该框架受著名的平滑复杂性分析[59]的启发。我们认为，该框架比广泛研究的I.I.D.更加普遍和现实。模型，特别是IC。在该框架中，智能体的“地面真相”偏好可以被任意关联并被对手选择，然后添加独立噪声形成其投票。从数学上讲，对手为每个主体j选择一个分布πj，这个分布πj是在所有线性阶上分布的集合π，在这个集合π下研究各种感兴趣事件的概率，例如Condorcet悖论和公理的满足[66]。我们的贡献。本文采用文献[66]中的统计模型，构造并研究了联系的平滑似然。给定一个（不定的）投票规则r,2≤k≤m,n,n个agents,最大敌手的目标是通过选择~π=(π,...,πn)εn来最大化k-路关系的似然性，以ftiemaxπ(r,k,n）表示。形式上，ftiemaxπ(r，k，n),sup~π∈nprpπ~π(r(P)=k)(4)类似地，最小敌手的目标是使k-路关系的似然最小化，其结果如下:ftieminπ(r，k，n),inf~π∈nprpπ~π(r(P)=k)(5)我们把ftiemaxπ(r，k，n)（分别，ftieminπ(r，k，n))称为关系的最大（分别，min)平滑似然。当π由单一分布π组成时，ftiemaxπ(r，k，n)和ftieminπ(r，k，n)相互重合，成为I.I.D下的联系似然。分布π。特别地，当π={πuni}，其中πuni是均匀分布时，ftiemaxπ(r，k，n)和ftieminπ(r，k，n)成为Ic下关系的经典分析。

正如文献[66]所讨论的，平滑社会选择框架允许主体的基本真值偏好是任意相关的，而噪声是独立的，这是许多文献如行为科学、经济学、统计学和平滑复杂性分析的标准假设。我们的主要技术结果是在大型选举(n→∞)中，对于至少三个备选方案(m≥3)的给定数目，tiess的平滑似然性的渐近刻画。非正式地，我们的主要结果可以概括为以下几个方面。主要结果：平滑的联系的可能性，非正式地放。在对π的温和假设下，对于许多常见的投票规则r,对于任意m≥3,任意2≤k≤m,任意n∈n,gtiemaxπ(r,k,n）（分别为gtieminπ(r~s,k,n））要么为0,exp(-θ(n)),要么为θ(poly-1(n))。更准确地说，我们证明了整数位置计分规则（包括复数，Borda，veto)的定理3,基于边序的规则（包括maximin，Schulze，排序对，copeland,见第11条）的定理4,以及STV和Coombs的定理5。这些定理的形式陈述还刻画了每个(0、指数或多项式）情形的条件以及多项式情形中的渐近紧界。当联系不可取时，例如在投票的不决定性、策略性投票或隐私的情况下，低的最大平滑似然是好消息。当联系是可取的，例如，在投票权和选民投票率的情况下，一个高的最小平滑可能性是好消息。因此，我们的定理完全刻画了在特定情况下好消息的条件。我们的定理的直接应用回答了Marchant[38]关于许多常见的投票规则的公开问题，如下面表1所总结的。表1：在一些常见的投票规则下k-路关系(2≤k≤m)的概率W.R.T.Ic.forcopelandα，Lα是最小正整数S.t。αlα∈Z.int。波斯。得分（科罗。1）STV和Coombs（道具）6）maximin（道具）3）舒尔茨（道具。4）排列成对（道具。5）如果没有n个Votespore包含k路连接θ(n-k-1)，否则，如果m≥k+5Dlog Ken^a(log klog k)Copelandα(0≤α≤1)（prop.），则θ(n-k-1)下上(Ω(n-k-1)Ω（n-dlog ke)(n-dlog ke)(n-dlog ke)(n-dlog ke)(n-dlog ke)(n-dlog ke）。2）0如果2-n,2 k,和k≥m-1θ(n-k)如果2 n,2 k,和(1)k=m，或(2)k=m-1和α≥，或(3)k=m-1和k≤lα(Lα+1)θn-lα(Lα+1)如果2 n,2 k,k=m-1,α<和k>lα(Lα+1)θ(1)否则（即如果2-k或k≤m-2)，粗略地说，表1揭示了投票规则W.R.T的以下排名。对于每2≤k≤m.{int.pos.scorning,STV,Coombs}≤{maximin,Schulze}≤ranked pairs≤CopelandA紧密相关的问题，它们在IC下的k-路联系的似然性是任意-路联系的似然性，有时称为优柔寡断[38]，即对于任意2≤k≤m.选举承认k-路联系。从表1不难看出，这种似然性是由双向联系的概率支配的，对于表中的所有规则，除了分别被命题5和命题2所覆盖的排列对和Copeland之外，它要么是0要么是θ(√n)。据我们所知，这些结果是新的，除了复数和Borda。对这些观测结果所产生的合成数据进行的实验，而对pre-emib数据进行的实验[41]揭示了一种不同的顺序，即在Borda（1.6%）和Copeland（2.6%）下，联系很少，而在由于技术革新而被否决（31.3%）下，联系很常见。本文中关于平顺似然的证明遵循了这种高层次的思想。我们用类似于例1中的线性不等式系统来建立k-路联系的存在性模型。这样，联系的似然性就变成了随机生成的profile的直方图在由线性不等式表示的多面体H中的似然性，该profile是一个泊松多元变量(PMV)。

然后，我们证明了PMV在H中的一个二分刻划（定理1）,并将定理1（更确切地说，它的推广定理2应用于多个多面体的并）来刻划层的光滑似然。更确切地说，给定n,q∈n和{1,.....,q}上n个分布的向量~π=(π,...,πn),一个（n,q)-PMV用~x~π表示，它表示n个独立随机变量的直方图，它们的分布分别是{π,...,πn}。（pmv在多面体中的定理，非正式地说）。设H表示无多面体，π表示满足一些温和条件的分布集，对于任意n∈n，sup~π∈npr(~x~π∈H)为0,exp(-θ(n)),或θ(poly(n)),而inf~π∈npr(~x~π∈H)为0,exp(-θ(n)),或θ(poly(n)),其界是渐近紧的，该定理的形式陈述也分别刻画了0,指数和多项式情况下的条件。正如在例子1之后评论的那样，我们没有看到通过直接应用现有的渐近工具来证明定理1的方法。我们还认为定理1是一个有用的工具，可以用来研究在[66]中评论的许多社会选择中感兴趣的事件的平滑似然。1.1选举中的相关工作和讨论。例如，正如穆里根和亨特评论的那样，估计联系可能性的重要性已经得到广泛承认：“也许众所周知，公民选举往往不是由一票决定的...对关键投票频率的精确计算有助于我们理解有多少票（如果有的话）可以理性地和工具地投出”[47]。然而，在实践中，联系并不像通常认为的那样罕见，即使在高风险的选举中也是如此，并导致了陷阱和随之而来的选举制度和宪法的修改。例如，在1800年的美国总统选举中，杰伊森和伯尔在ElectoralCollection的选票上打成平手。根据宪法，众议院应该投票，直到候选人赢得多数席位。但在随后的35轮僵持投票中，两位候选人均未获得多数。最终，杰奎森赢得第36次连任，成为总统。这“表明了《宪法》的根本缺陷”。因此，宪法的第十二次修正案被引入，并被修改为“[9]。三种或多种方式的联系。如今，立法者很清楚双向铁杆选举的可能性，并制定了特定的打破铁杆选举的机制来处理这些问题。然而，三个或更多的关系没有得到应有的重视，有时被忽视。例如，2019年《阿拉巴马州法典》第17-12-23条规定：“在所有县或选区的同一首席执行官的最高候选人之间有平局的所有选举中，应由县议会在候选人在场的情况下进行抽签决定”。该代码没有指定当三个或更多的候选人并列时应该采取什么行动。本文中的结果描述了这种情况是多么罕见，以便立法者能够在知情的情况下决定漏洞在实践中是否是一个值得关注的问题，如果是，如何弥补它。平滑分析。关于平滑分析在数学规划、机器学习、数值分析、离散数学、组合优化等方面的应用，有大量的文献，见[59]。平滑分析也被应用于经济学中的各种问题，例如无政府状态的价格[11]和市场均衡[32]。在最近的一篇论文中，Baumeister、Hogrebe和Rothe[4]提出了一个基于Mallows的模型，用于对社会选择的计算方面进行传导平滑分析，并评论说该模型可以用于分析投票悖论和联系，但该论文没有包含技术结果。

[66]独立地提出了对非社会选择的悖论和不可能定理进行平滑分析，刻画了Condorcet投票悖论的平滑似然性和无边可能性定理，并提出了一种新的平衡点打破机制。我们只使用了[66]中的概率模型，从主题上来说，我们的论文是在[66]的基础上建立的，因为我们在通常研究的投票规则下建立并研究了联系的似然性，这是[66]中没有研究的。我们认为，本文的主要技术工具（定理1）是将[66]中引理1推广到任意多面体，每n个整数矩阵和最小敌手。更多的讨论可以在注记后定理1中找到。我们相信定理1是分析社会选择中许多其他问题的平滑似然性的有用工具。例如，[66]中的所有结果都可以立即被定理1所加强。下表总结了前人对本文的研究成果，其主要贡献是对似然性的刻画。论文m k投票规则分布[5]2 2多数两组，I.I.D。在每组内[39][10]2 2多数。W.R.T.一个不确定分布[27]任意m∈n2≤k≤m多一致I.I.D.(IC)[28]32≤k≤m Borda一致I.I.D.(IC)[38]任意m∈N，k=m，I.I.D.一致确定得分规则。更精确地说，Beck[5]研究了在多数规则下（在两个备选方案上）与两组代理人的平局概率，这两组代理人的投票是I.I.D。每组内。Margolis[39]和Chamberlain和Rothschild[10]集中讨论了两种选择的多数规则，其中代理人的偏好是I.I.D.根据随机生成的分布。Gillett[27]研究了在多个W.R.T.下的全向联系（即k=m)的概率。IC用于任意数目的替代和代理。Gillett[28]在m=3W.R.T.的情况下，得到了Borda不确定（两个或多个备选方案被绑定）的一个闭式公式。IC.Marchant[38]考虑了一类计分规则，其中每个agent可以从给定的计分向量集(SVS)中选择一个计分向量，并刻画了在一类计分规则下M-路联系的渐近概率为θ(n1-m)W.R.T.他们的身份证明。在所有SV上均匀分布。此结果可以应用于Borda和批准投票，但不能应用于复数。Marchant[38]也注意到Domb[18]在Borda下得到了m=3的等价公式。正如前面所讨论的，我们论文中所使用的平滑社会选择框架是更普遍的。特别地，我们的定理的推论回答了Marchant提出的开放问题[38]，并根据IC下的铁似然性揭示了对这些规则的排序，如表1所总结的。以前的工作与铁似然性有关。[33]研究了Agent被分成多个组的情况，在每个组中，Agent的投票由公正匿名文化(IAC)模型产生。平滑的社会选择框架与IAC有直接的可比性。前者更普遍，因为代理人的“基本真相”偏好是任意相关的。后者更一般，因为代理人的“噪音”不是独立的。还有一系列关于美国选举团制度下关系的经验性和混合经验性-理论性工作[24,25]。在这种情况下，研究平局的平滑似然关系是今后的工作。平局选举的概率与单个选民投票的概率密切相关，有时称为投票权，这在投票悖论[19]和合作博弈论中权力指数的定义中发挥着重要作用。

有大量关于投票游戏的工作，在投票游戏中，一个选民成为关键的概率，相当于其他选民之间的可能性，在分析选民的战略行为中发挥着核心作用。例子包括开创性的工作[1,21,48]，以及最近的工作[49]。不难看出，正如outin所指出的，在多数规则下，两个或多个备选方案的投票权几乎等于在某些打破平局的规则下，少一票的平局选举的概率[29]。对于三个或更多的替代方案，这两个问题密切相关，但在技术上是不一致的，我们留待将来的工作。联系的可能性也与投票规则的可操作性有关[14]--如果一次选举没有联系，那么没有一个单独的代理人能够改变结果，因此没有一个代理人单独激励否决进行操纵投票。我们的结果与文献[53,67,45,65]中关于可操作性的典型案例分析和定量的Gibbard-Satterthwaite定理[23,46]有关，其中投票被假定为I.I.D.联系的可能性也与Butdi和Erent有关[37,64]，更广泛地说，与选举中的贿赂和控制[20]有关。为研究联系增加噪音。我们不知道以前的一项工作描述了这种联系的可能性，就像我们在本文中所做的那样。添加噪音来研究领带的想法并不新鲜。在[60]中对可解决性的认识中，增加了一个额外的投票来打破联系。在[22]中，犹豫不决的投票规则通过将获胜者的联盟置于agiven Profective周围的Profections之下来改变。文献中研究的另一个可解性（例如，参见[58]第4.2节中的公式#1)要求在投票规则W.R.T.下，联系的概率为0。IC，whichis在投票的优柔寡断方面与文学有着密切的联系。由于IC是平滑社会选择框架的一个特例，我们的设置和结果更具一般性，而且我们的结果也刻画了收敛速度。最近有大量关于打破联系的计算方面的工作。[13]提出了多阶段规则的平行宇宙断裂(PUT)，并刻画了STV规则的复杂性。[7]刻划了秩对下PUT的复杂性，研究了秩对的光滑似然性。[40]描述了Baldwin和Coombs等多阶段投票规则下PUT的复杂性。[51，50，2，52]研究了对操纵复杂性的破坏机制。[22]提出一种在广义评分规则下建立联系的一般方法。[62]提出了在STV和排序对下计算PUT的实用AI算法。2初步的基本设置。对于任意q∈N，我们设[q]={1,...,q}。设A=[m]表示m≥3个备选方案的集合。设L(A)表示A上所有线性序的集合。n∈n表示主体的个数。每个代理使用线性顺序来表示他或她的偏好，称为投票。n个代理人投票的向量，用P表示，称为（偏好）亲，有时称为n亲。fractional profection是一个偏好profection P和一个可能非整数且可能负权重的向量~ωP=(ωR:R∈P)∈Rn，用于P中的投票。因此，非分数优先级是具有均匀权重的分数优先级，即~ωp=~1。有时，当上下文清楚或~ωP=~1时，我们会略去权重向量，从而略去权重向量。对于任何一个（分数）po,设Hist(P)∈ZM！≥0表示P的匿名权重，也称为P的直方图，它包含根据P在L(A)中每个线性阶的总权重。（不定的）投票规则r是从一个权重到一个非空的优胜者集的映射。下面我们回顾几个常用的投票规则的定义。整数位置计分规则。

一个（整数）位置打分规则的特征是s=(s,...,sm)∈Zm，且s≥s≥···≥sm，且s>sm。对于任何Wikipedia[63]都给Douglas R.Woodall提供了这一认识，但我们不能找到一个形式引用。备选方案a和任意线性阶R∈L(a)，我们设~s(R,a)=si，其中i是a在R中的秩。给定一个带权重~ωP的方案P，位置评分规则R~以最大值pr∈PωR·s(R,a）对所有备选方案a进行排序。例如，Multium使用计分向量(1，0，.，0)，Borda使用计分向量(M-1，M-2，.，0)，而veto使用计分向量(1，.，1，0)。对于任一（分数）方案P和任一对备选方案a、b，设P[a.b]表示P中选票的总权重，其中a优于b。设WMG(P)表示P的加权多数图，它的顶点是A，边上的权A→bis wP(A,b)=P[A b]-P[b A]。有时L(a)上的分布π被看作是一个分数，其中对于每个R∈L(a)，在R上的权重是π(R)。在这种情况下，我们让WMG(π)表示由π表示的分数序列的加权多数图。如果投票规则的获胜者仅依赖于输入序列的WMG，则称其为基于加权多数图（WMG-based）。在本文中，我们考虑以下常见的基于WMG的规则。oCopeland。Copeland规则的参数为0≤α≤1，并预先表示为Copelandα，简称CDα。对于任何分数P，替代方案a在他们的正面竞争中击败的另一个替代方案获得1分，每个平局获得α分。Copelandα选择总分最高的所有备选方案作为获胜者。o马希民。对于每一个备选方案a，它的最小得分被定义为minb∈AWP(a，b)。Maximin用MM表示，它选择所有具有最大最小得分的备选方案作为获胜者。给定一个profireme P，如果存在一种方法以非递增顺序逐个地对WMG(P)中的边进行修改，则备选方案a是排序对（用RP表示）下的赢家。它们的权重（有时会中断联系），除非它创建了一个与以前的firexeDedges的循环，以便在考虑所有边之后，a没有传入的边。这就是所谓的平行宇宙打破平局(PUT)[13]。o舒尔茨。对于WMG中的任何有向路径，它的强度被定义为沿着路径的任何一条边的最小权值。对于任一对备选方案a、b，设S[a,b]是从a到b的所有路径中的最大权重。然后，我们写出a。b当且仅当S[a,b]≥S[b,a]，Schulze[58]证明了这个二元关系的严格形式，用Istransitive表示。Schulze规则，用Sch表示，选择所有备选方案a，使得对于所有其他备选方案b，我们有一个b，多轮基于分数的淘汰(MRSE)规则。本文研究的另一类投票规则在M-1轮中选择获胜者。在每一轮中，使用整数positionalscoring规则对剩余的备选方案进行排序，并从选举中删除一个失败者（具有最小总得分的备选方案）。就像排位对一样，PUT被用来选择获胜者--如果有一种方法可以打破失败者之间的联系，使a在M-1轮后成为剩余的备选方案，那么备选方案a就是获胜者。例如，STV规则在每一轮中使用复数规则，而Coombs规则在每一轮中使用否决规则。我们现在回想平滑社会选择框架中使用的统计模型[66]。第1条（单代理偏好模型[66])。单主体偏好模型用M=(θ,L(A),π)表示，其中θ为参数空间，L(A)为样本空间，π由以θ为索引的分布组成。当存在>0时，M是严格正的，使得π中任意分布下的任意线性阶的概率至少是。

如果π(rm中概率单纯形的子集），M是闭的是RM中的一个闭集。例如，在单代理Mallows模型[66，附录中的示例2]中，给定对于任意一个参数，均为中心排序R和色散参数的Mallow分布。对于任意一个参数，均为R和色散参数的Mallos分布，均为中心排序R和色散参数的Mallos分布，均为中心排序R和色散参数的Mallos分布。对于任意W∈L(A)，π(R,2)(W)=πKT(R,W)/z，其中KT(R,W)是R与W之间的Kendall Tau距离，即R与W之间的成对分歧数，z=是thromagation常数。由此可以得到M[,]是严格正的，闭的，并且CH(π)包含在所有排序上的均匀分布，用πuni表示。2（平顺的联系似然）。在给定投票规则r,单主体偏好模型M=(θ,L(a)，π),2≤k≤M,n,n,n的情况下，(k-way)关系的最大（分别,最小）光滑似然关系被定义为（4）中的最大（分别,最小）光滑似然关系（分别为（5）中的最大（分别,最小）光滑似然关系）。3 pmv-in-polydron问题和主要技术定理本文研究的PMV和pmv-in-polydron问题的形式定义3（Poisson multivariate variables（Poisson multivariate variables,pmv-in-polydron问题）。给定[q]上n个分布的任意q，n∈n和任意向量~π，我们设~x~π表示对应于~π的(n，q)-PMV。也就是letY，..n表示[q]上的n个独立随机变量，使得对任意j≤n,yjs分布为πj。对于任意1≤i≤q，~x~π的第i个分量是取值i的yj的个数。给出[q]上的多面体H Rq和分布集合π，我们对上界sup~π∈npr(~x~π∈H)和下界inf~π∈npr(~x~π∈H)感兴趣，前者（分别为后者）是（N,q)-pmv在H中的最大（分别为最小）概率，其中N个变量的分布均取自π。为了给出定理，我们引入了一些符号，并给出了一个例子。已知q∈N，L∈N，L×q整数矩阵A，q维行向量~B和N∈N，我们得到H,H,Hn,Hn,HZnas如下：H,~x∈RQ:A·(~x)>≤~B>,H,~x∈RQ:A·(~x)>≤~>,Hn,N~x∈HTMRQ≥0:~x·~1=no,HZn,HnTMZQ≥0,即H是用A和~B表示的多面体；His是H的特征锥，HN由H中的Lnorm为n的非负向量组成，HZN由HN中的非负整数向量组成。设dim(H)表示H的维数，即Rq包含H的最小线性子空间的维数。在本文中，我们假定分布的集合π是严格正闭的，这是文[66]中所讨论的温和的假设，形式上定义如下。给定任一q∈N，如果对所有i∈[q]，π(i)≥，则[q]上的概率分布π对于某些>0是严格正的。我们说[q]上的一个分布集π对于某个>0是严格正的，如果每个π∈π是严格正的。如果π是RQ中的闭集，则π是闭集。设CH(π)表示π的凸壳，设锥(π)表示π生成的凸锥。例2。图1说明了两个例子，q=2和π={π,π}，其中π=(，)和π=(，)。在这两个例子中，CH(π)是π和π之间的线段，圆锥(π)是haded区域，H是红色区域，His是蓝色区域，H和His的交点是purpleare，HNS是绿色线段。图1(A)和图1(b)之间的一个关键的关系是whetherCH(π)h=(1在图1(A)中是真的，而在图1(A)中不是真的）。还有可能是H*H，如图1(b)所示。！“#$！%&\'()*+\'#，！”-.！%&\'/01234！“+$0567234！%！”-！%89/:！“#$%&\'()\'*+&(*，-./01\'(\'*$2-345/01\'(&2\'*+%&\'*+67%\'()\'*89，:$（；(a)a=-3 41-2和~b=。(b)a=-1 11-20-1和~b=-√0.1。图1:H、H、Hn、CH(π)和锥(π)的两个例子。a在多面体中PMV问题上的高级尝试。

在正式提出定理之前，让我们进行一次发展直觉的高级尝试。以上界sup~π∈πnpr(~x~π∈H)为例，有三种情况:o0情况。显然，如果H不包含任何Lnorm为n的非负整数，它等价于hzn=，则sup~π∈πnpr(~x~π∈H)=0.o为指数情形（图1(a))。假设hzn6=.对于任意由最大敌手选择的~π=(π,...,πn)∈πn，我们有~π·~1=pnj=1πj∈Cone(π)。根据多元中心极限定理，~x~π以高概率“中心”在~π·~1的一个θ(τn)邻域上。因此，如果~π·~1离H为θ(n),则sup~π∈πnpr(~x~π∈H)是指数小的。这种情况发生在CH(π)h=，如图1(a)所示。o多项式情况（图1(b))。否则，我们有CH(π)H6=，如图1(b)所示。在这种情况下，最大敌手可以选择~πππn，使得~π·~1不是锥(π)就是接近锥(π),这意味着sup~πππnpr(~x~π∈H)应该大于指数情况下的sup~πεnpr(~x~π∈H)。然而，并不能立即明确概率是多项式的，因为~π·~1接近锥(π)，而hzn6=，并不能立即暗示~x~π接近于HZn，即使我们假设~x~π接近于HZn中的某些（整数）向量，也不清楚这些向量在~π·~1的θ(√n）邻域内有多“密”，而~x~π是高概率的。事实上，精确地界定多项式情况下的概率是问题中最具挑战性的部分，因为现有的渐近工具由于它们的O(n-0.5)误差项而无法工作。下面的主要技术定理与上面提出的当π接近且严格为正时的直觉一致（见定义5)，多项式情况的答案是θndim(H)-q，它通常比n-0.5小得多。定理1（pmv在多面体中的平滑似然性）。给定[q]上的任一q∈N，任一闭正态和严格正态π，以及任一以整数矩阵A为特征的多面体H,对于任一N∈N，sup~π∈npr~x~π∈H=0,如果Hzn6=和HüCH(π)=ndim(H)-q,否则（即Hzn6=和HüCH(π)6=,如果Hzn=exp(-θ(N)),如果Hzn6=和θndim(H)-q,则inf~π∈npr~x~π∈H=0,如果Hzn=exp(-θ(N)),如果Hzn=θndim(H)-q,则hzn=θndim(H)-q另外（即hzn6=θ和CH(π)H)对定理1的幂的说明。我们认为定理2的主要力量在于它提供了一种系统的方法，将概率分析（pmv多面体问题的渐近紧上下限）减少到最坏情况下的非概率分析，而最坏情况下的非概率分析往往容易验证。特别地，当CH(π)可以用一个向量的凸包表示时，可以用线性规划的方法来验证HüCH(π)=θ和/或CH(π)6。以例2设置中定理1的最部分为例。假定hzn6=.o在图1(a)中，很容易看出hüCH(π)=.因此，在图1(b)中，π~π∈n，pr~x~π∈H≤exp(-θ(n))o我们有HüCH(π)={π}6=，CH(π)6H，dim(H)=2。因此，对于任意su lutly ciently n（对其不难证明hzn6=)，我们有π~π∈n，exp(-θ(n))≤pr~x~π∈H≤θ(n-2-2)=θ(1)注意这两个界是渐近紧的。例如，下界可以由~π={π}n实现，上界可以由~π={π}n实现。作为定理1的inf部分的一个例子，假设图1(b)中π被π=（,）代替，那么CH(π)H,即表示π~π∈πn,pr~x~π∈H≥θ(1)和下界是渐近紧的。对定理1的一般性和局限性进行了说明。我们认为定理1是很一般的，因为它为PMV-内多面体问题提供了一个二分法（更准确地说，是三分法）。二是上下界渐近紧。第三，该定理适用于以整数矩阵A和任意~B为特征的任意H和任意闭严格正π。