不可能性定理与通用代数工具箱

在这些定义下（k，σ）与XB的块度图中的（`，ρ）有关（二元域的块度图见定义3）。10.2支持性非二元评估首先我们重申定理8的支持部分：定理31。让X Dm，非退化和非二元。如果X完全被阻止，那么X是关于IIA+支持性+非独裁的可能性域，当且仅当X是关于IIA+支持性+非独裁的可能性域≤ 3条件（意味着当我们将自己限制为只有三个参数的聚合器时，除了独裁，我们找不到其他聚合器）。备注3。该定理是一个分类定理，因为它为我们提供了一个算法来确定给定的域X是否是关于IIA+支持性+非独裁的不可能域：只需使用最多三个参数检查所有潜在聚合器。证据“仅当”部分很简单，因为如果X是关于IIA+支持性+非独裁的不可能域，那么X的每个支持性IIA聚合器f=（f，…，fm）都是独裁，而不仅仅是对arity n≤ 3.对于“如果”部分，我们需要E.Dokow和R.Holzman的以下结果：定义18（E.Dokow和R.Holzman[DH10b]）。设f=（f，…，fm）是arity n对X的一个聚合器 马克。对于一个问题j和一对有序的不同位置u，v∈ Djwe翻译fj{u，v}:{u，v}n→ {u，v}到函数Wuvj:{0，1}n→ 0下的{0，1}<-> v、 一,<-> u、 引理32（E.Dokow和R.Holzman[DH10b]，命题1）。如果X完全被阻止，那么所有Wuvj都是相同的。定义19（E.Dokow和R.Holzman[DH10b]）。如果所有的Wuvj（j∈ [m] ，u，v∈ Dj）是关于同一个k.引理33的独裁（E.Dokow和R.Holzman[DH10b]，命题5）。

如果X完全被阻止，f是2独裁，那么f就是独裁。让我们试着把以上两个引理放在一起！完全阻塞是定理中的一个条件，我们想证明它的“如果”部分，所以缺少的是，在定理的条件下，Wuvj不只是简单地相同，而是都是独裁。我们依赖于以下引理，它本质上是[Bul11]中定理2.16的简化版本和Schaefer的二分法定理的多排序版本（见定理28和[Che09]）。引理34。设Γ是D上的一组多排序关系，其类型为集合[t]。如果Γ没有iia+支持+非独裁聚合器，则n≤ 3条件，则对于任何f=（f，··，ft）∈ MPol（Γf），a∈ [t] ，u，v∈ Dawith u 6=v限制fa |{u，v}是一个独裁政权。证据（引理34）假设相反，即Γ不具有IIA+支持性+非独裁聚合器和n≤ 3，但它有一些聚合器f=（f，·ft）∈ MPol（Γf），因此存在∈ [t] 还有u，v∈ Da，u 6=v，其性质是fa |{u，v}不是独裁政权，其中n是f的算术。那么n必须至少是4。让f作为miniman的反例。特别地，任何f=f（x（1），x（i）|{z}i参数，x（i）{z}10电荷量，x（n）），也就是说，当我们识别两个输入时，必须是两个独裁，因为faggrates n- 1.输入。用g表示fa |{u，v}，这可能不是独裁。通过证明g是一个独裁政权，即存在一个k，我们将得出一个矛盾∈ [n] 这样对于任何x，··，xn∈ D、 g（x，··，xn）=xk。由于g变量的任何识别都是通过首先在f中识别这些变量，然后将结果类型=组件限制在二进制集合{u，v}中而产生的，因此我们认为，g变量的任何识别都必须导致独裁。

如果所有这些识别x（i）=x（i）导致一个专政，该专政计划协调i（而不是某些协调6∈ {i，i}），我们通过将{i，i}首先设置为{1，2}，然后设置为{3，4}得到一个矛盾：u=f（u，u |{z}，v，v，…=f（u，u，v，v |{z}，…）=v、 （用那句话）≥ 4.）因此，存在两个坐标，在这两个坐标中，识别相应的变量将产生一个专政函数，该函数投影到其他坐标（即非i，i）。Wlog假设g（x，x |{z}，x，x，···，xn）=x当g（x，x，x，x，···，xn）=x。我们证明了这意味着g（x，x，x，x，···，xn）=x。如果g |x=x是比x大的独裁者，那么设置x=x并让x变化，我们会得到一个矛盾。类似的推理给出了g（x，x，x，x，··，xn）=x。因此，每当x，x，x的值之间存在重复时，g的输出总是x。但是重复总是发生的，因为| D |=2，因此g是一个独裁，一个矛盾。我们现在准备证明定理31的“如果”部分。假设当n≤ 3除了独裁统治（以及其他条件：X不退化，完全被封锁）之外，没有其他支持X的聚合器。考虑一个聚合器f for X with n≥ 4.引理34，对于任何j [m] 对于任何u，v∈ Dj，u 6=v，我们有一个独裁政权。根据引理32，由于X完全被阻塞，所有的Wuvjare都是一样的。引理33则暗示f是一个独裁政权。10.3一般幂等非二元求值法35。对于给定的域X Dm，非退化和非二元，即| D |=D≥ 3，并且完全被阻止，如果X没有任何IIA+幂等+非独裁聚合器，则n≤ 条件，那么X是关于IIA+幂等+非独裁的不可能域。证据

通过矛盾假设X满足引理的条件，并且X是关于IIA+幂等+非独裁的可能域。然后有一个幂等聚合器f=（f，···，fm），它不是独裁政权。根据引理的假设，f有arityn≥ d+1。假设f具有最小的算术性，即不存在具有较小算术性的幂等非独裁聚合器。我们首先表明f是支持的，即。 x（1），··，x（n）∈ 十、 1.≤ J≤ m:fj（x（1）j，··，x（n）j）∈ {x（1）j，··，x（n）j}。如果我们能证明，对于任何固定的x（1），··，x（n）和j，我们有fj（x（1）j，··，x（n）j），我们就完成了∈{x（1）j，··，x（n）j}。我们使用鸽子洞原理。自从≥ d+1，在x（1）j，··，x（n）j中，必须至少有两个相同的元素。为了便于记谱，它们是x（1）jand x（2）j。冲突不会发生在所有输入和js的同一对索引上，但这不会影响我们，因为我们将输入设置为固定。由于碰撞发生在指数1和2，我们将研究n的聚合器-1元素g，我们通过识别f的前两个输入从f中得到。由于g也是X的幂等IIA聚合器，根据我们的最小假设，g必须是一个独裁政权。因此，它也是一个独裁政权，因此是支持它的。特别是，u=gj（x（2）j，··，x（n）j）∈ {x（2）j，··，x（n）j}。但u也是fjt在x（1）j，x（2）j··，x（n）j上的值（因为根据我们的假设x（1）j=x（2）j）。这就证明了f是支持的。然后，因为我们已经找到了X的非独裁支持聚合器（在一定数量的输入上），根据定理31，在三个输入上也必须有一个非独裁支持聚合器。

因为支持聚合器也是幂等的，所以我们与引理的假设相矛盾，即最小的非独裁幂等聚合器位于| D |以上≥ 3.输入。这个引理解决了幂等情形，这是定理8.11算法的剩余部分，当我们试图确定X Dmis是一个不可能域与否关于IIA+幂等性（或支持性）+非独裁，我们可以依赖两种不同类型的刻画定理：通过小工具（定理17）；通过聚合器（定理8）。这两种类型都会产生算法解决方案，我们可以将它们都用作替代方案。11.1根据gadgets的特征化算法正如我们在前面的章节中所看到的，为了确定X是否是关于IIA+幂等性（或支持性）+非独裁的不可能域，我们需要检查某些关系是否可以表示为X+-gadgets（Xf-gadgets）。这在定理17中有说明。因此，任务是解决以下类型的问题：查找Gadget：给定D上的一组Γ关系和D上的一个关系R，确定R是否存在ΓGadget。在多排序版本中，关系位于具有关联域SD的类型集[t]上，Dt。起初，一个障碍似乎是这些小工具可能包含任意数量（未指定）的辅助变量。然而，由于盖格[Geiger[Gei68]、杰文斯[Jea98]和特雷维桑等人[TSSW96]，我们知道，R的最小Γ-小工具中辅助变量的数量在| R |、|D |和|Γ|方面是上界的。上述结果很容易推广到多排序情况。在我们的设置中|Γ|是X+或Xf。后者的大小以m和| D |为上界。

不幸的是，直截了当的实现在| X |，D和m中产生了双指数的运行时间，我们目前还不知道是否可以将其简化为单指数。尽管最坏情况下的计算时间很长，但小工具通常为不可能提供非常经济的证据（参见我们前面的两个具体例子），而且在所有情况下，上述参数中的证据大小都是最重要的。11.2聚合器表征的算法定理8为我们提供了一个完整的不可能域分类，用于任意（二元或非二元）评估。在这里，我们将这些转化为算法。我们假定x是非退化的，但不失一般性。算法。确定X 在IIA+支持性+非独裁条件下，Dmis是一个不可能域：1。检查X是否完全堵塞（参见定义17）。如果X不是完全阻塞的，那么X是一个可访问域。否则：2。对于每个支持的f=（f，…，fm），其中fj:Dj→ Dj，检查f是否聚集了X，这是非独裁。如果我们的搜索返回满足条件的f，那么X是可能域，否则它是不可能域。注：只看n=3而不是n就足够了≤ 3.运行时间由步骤2决定。搜索中的f s数的上限为|D | m·|D |。检查独裁是微不足道的。要检查f是否是X的聚合器，需要poly（|X |，m，| D |）时间。因此我们有：定理36。确定给定域X 关于国际投资协定+支持+非独裁是一个不可能的领域（poly（|X |，m，| D |）、D | m·| D |）。类似地（我们必须用| D |替换3），我们得到：定理37。

确定给定域X 关于IIA+幂等+非独裁的不可能域是O（poly（|X |，m，| D |），D | m | D | D |）。请注意，我们将D视为常数（二进制等），并将上述复杂性视为指数。12度民主虽然非独裁条件代表了民主的最低标准，但有许多功能通过了非独裁测试，但几乎不能被称为民主。例如，考虑一个布尔函数，如果第一个投票人投票为零，则取多数值，否则取一。虽然这不是独裁统治，但第一位选民在选举结果中占据压倒性优势。我们应该认为哪些投票功能是民主的？现实生活中的场景，比如美国选举制度（迭代多数功能），表明多数票并不是唯一可以被视为真正民主的投票。答案并非微不足道。Kalai[Kal02]提出了不同的民主标准，例如匿名性（Sn下不变）或对称性（在[n]上的传递置换群下不变），这些标准介于多数和独裁投票方案之间。在本文中，我们将介绍StrongDem，它具有深刻的代数动机。StrongDem：让f成为X的聚合器 DMN≥ 2满足国际投资协定条件的选民，因此其形式为f=（f，…，fm）。我们说f是StrongDem，如果每1≤ J≤ m、 一,≤ 我≤ n有c，cn∈ dj使得fj（c，…，ci）-1，x，ci+1，cn）不依赖于x∈ 流行音乐播音员我们进一步要求，该属性不仅适用于Dj，而且在我们用任何Dj替换Dj时也适用 使操作f保留（尊重）Dj。

（在替换中，仅当x也来自Dj时，x的独立性才能保持。）三个或更多参数的多数函数在StrongDem中：取任意D D，并将除投票人i投票外的所有投票设定为某些（任意）c∈ D.那么无论投票人采取什么立场，结果都将是c。因为任何StrongDem聚合器都显然是非独裁的，所以我们有了遏制：非独裁 StrongDem 多数投票所有的包容在以下强烈意义上都是严格的：对于上述任何两种情况，我们都可以找到X，它对于较大的类是一个可能域，但对于较小的类是一个不可能域（假定为IIA+幂等）。一个重要的例子是，对于一个X，它允许一个具有非独裁条件的FW，但没有StrongDem投票方案，这就是a ffine子空间。LetD={0，1}，和X={（X，X，X）∈ D | x+x+x=1模2}。当n为奇数时，有一个非独裁投票方案：让fj:（u，…，un）→Pni=1的IMOD 2≤ J≤ 3.很容易看出f=（f，f，f）具有非独裁性质。可以看出，这是X的唯一一种非独裁聚合器，而不是StrongDem。多数、匿名、对称性该方案以完全相同的方式对待所有选民。当所有其他选票都得到适当固定时，一个选民无法改变结果。非独裁，没有一个选民排他性地控制结果。图5：民主条件及其非正式含义StrongDem条件相当于聚合器落入一个经过充分研究的宇宙代数操作类。此类包含“无法计数”的操作。相比之下，具有计数功能的奇偶校验函数对输入非常敏感：当计数仅改变一次时，它们的值会改变七次。

在代数理论的一个影响深远的部分，“无法计数”运算类生成了“避免类型1和类型2”[HM88]同余的代数。最近，这类代数的特征是局部一致性检查算法，这是一个突破[BK09]。StrongDem的概念之所以特别吸引人，是因为当我们看到它的最低限度定义时，它似乎是民主的必要条件，但它也有相应的表述，这些表述足够强大，足以将其视为有效条件。定义20（强韧性）。设D为有限域，u为D的度量值。f:Dn的第i个变量的影响系数，u（f）→ D是Probun+1（f（x）6=f（x）），其中x，x穿过所有仅在第i坐标中不同的随机输入对（un+1对这些对提供了一个自然度量）。最大影响max infu（f）为maxiInfi，u（f）。函数f:Dn→ 如果在D:max infu（fk）上预先测量u，则D具有很强的弹性→ 0当k→ ∞ 其中，fk由合成fk=f（fk）递归定义-1.fk-1).定理38（G.Kun和M.Szegedy[KS09]）。以下是等效的：1。f是StrongDem。2.在[{f}]中有一个很强的弹性操作。13最后的注释和未来的研究我们的翻译产生了进一步令人惊讶的结果。事实证明，森的著名定理[Sen79]有一个从[BP75，JCC98]：定理39中很容易被搁置的推广。如果X {0，1}mis 2-可分解且k为奇数，则k为voters的多数函数是X的IIA聚合器。对于k=odd，反之亦然。从这一点出发，森的原始定理很容易遵循。在这项工作中，我们仅仅开始阐述判断聚合（更一般地说，评估聚合）和泛代数之间的密切关系。这种联系还有其他几个分支：稳健性结果、外部条件。

在后续结果[SX14]中，我们讨论了多数聚合器。14致谢我们要感谢安德烈·A·布拉托夫和罗恩·拉维的富有洞察力的评论。参考文献[Arr50]肯尼斯·J·阿罗。社会福利概念上的困难。《政治经济学杂志》，58（4）：328-346，1950年8月。[BJ03]安德烈·A·布拉托夫和彼得·杰文斯。多排序约束的代数方法。在CP中，第183-198页，2003年。[BJK05]安德烈·A·布拉托夫、彼得·杰文斯和安德烈·A·克罗钦。利用有限代数对约束的复杂性进行分类。暹罗J.计算机。，34(3):720–742, 2005.[BK09]L.巴托和M.科齐克。有界宽度的约束满足问题。《计算机科学基础》，2009年。FOCS\'09。2009年10月，第50届IEEE年会，第595-603页。[BP75]科比。贝克和阿尔登夫。皮克斯利。多项式插值与代数系统的中国剩余定理。Mathematische Zeitschrift，143（2）：165-1741975。安德烈·布拉托夫。保守约束满足问题的复杂性。计算逻辑上的ACMTransactions（TOCL），12（4）：242011。[Che09]陈胡比。逻辑、复杂性和代数的交汇点。计算机。Surv。，2009年12月42（1）：2:1–2:32。Elad Dokow和Ron Holzman。二元计算的聚合。经济理论杂志，145（2）：495-5112010。[DH10b]Elad Dokow和Ron Holzman。非二进制计算的聚合。《非应用数学进展》，45（4）：487-5042010。[FF11]德维尔·法利克和埃胡德·弗里德古特。一个强大的社会选择不可能的代数证明。在FOCS中，第413-422页，2011年。[FV98]T.费德和M.瓦迪。单调一元SNP的计算结构与约束满足：基于数据日志和群论的研究。暹罗肿瘤学杂志，28（1）：57-1041998。[Geiger]D.盖格。函数和谓词的封闭系统。