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

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

英文标题：
《Impossibility Theorems and the Universal Algebraic Toolkit》
---
作者：
Mario Szegedy and Yixin Xu
---
最新提交年份：
2015
---
英文摘要：
  We elucidate a close connection between the Theory of Judgment Aggregation (more generally, Evaluation Aggregation), and a relatively young but rapidly growing field of universal algebra, that was primarily developed to investigate constraint satisfaction problems. Our connection yields a full classification of non-binary evaluations into possibility and impossibility domains both under the idempotent and the supportive conditions. Prior to the current result E. Dokow and R. Holzman nearly classified non-binary evaluations in the supportive case, by combinatorial means. The algebraic approach gives us new insights to the easier binary case as well, which had been fully classified by the above authors. Our algebraic view lets us put forth a suggestion about a strengthening of the Non-dictatorship criterion, that helps us avoid \"outliers\" like the affine subspace. Finally, we give upper bounds on the complexity of computing if a domain is impossible or not (to our best knowledge no finite time bounds were given earlier).
---
中文摘要：
我们阐明了判断聚合理论（更一般地说，评估聚合）与一个相对年轻但发展迅速的普适代数领域之间的密切联系，该领域主要是为了研究约束满足问题而开发的。在幂等元和支持条件下，我们的联系将非二元求值分为可能域和不可能域。在目前的结果之前，E.Dokow和R.Holzman几乎通过组合方法将支持性案例中的非二元评估进行了分类。代数方法也为我们提供了对更简单的二元情况的新见解，这已被上述作者完全分类。我们的代数观点让我们提出了一个关于加强非独裁标准的建议，这有助于我们避免像仿射子空间这样的“异常值”。最后，我们给出了计算复杂度的上界，如果一个域是不可能的（据我们所知，之前没有给出有限时间界限）。
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computational Complexity        计算复杂度
分类描述：Covers models of computation, complexity classes, structural complexity, complexity tradeoffs, upper and lower bounds. Roughly includes material in ACM Subject Classes F.1 (computation by abstract devices), F.2.3 (tradeoffs among complexity measures), and F.4.3 (formal languages), although some material in formal languages may be more appropriate for Logic in Computer Science. Some material in F.2.1 and F.2.2, may also be appropriate here, but is more likely to have Data Structures and Algorithms as the primary subject area.
涵盖计算模型，复杂度类别，结构复杂度，复杂度折衷，上限和下限。大致包括ACM学科类F.1（抽象设备的计算）、F.2.3（复杂性度量之间的权衡）和F.4.3（形式语言）中的材料，尽管形式语言中的一些材料可能更适合于计算机科学中的逻辑。在F.2.1和F.2.2中的一些材料可能也适用于这里，但更有可能以数据结构和算法作为主要主题领域。
--
一级分类：Computer Science        计算机科学
二级分类：Logic in Computer Science        计算机科学中的逻辑
分类描述：Covers all aspects of logic in computer science, including finite model theory, logics of programs, modal logic, and program verification. Programming language semantics should have Programming Languages as the primary subject area. Roughly includes material in ACM Subject Classes D.2.4, F.3.1, F.4.0, F.4.1, and F.4.2; some material in F.4.3 (formal languages) may also be appropriate here, although Computational Complexity is typically the more appropriate subject area.
涵盖计算机科学中逻辑的所有方面，包括有限模型理论，程序逻辑，模态逻辑和程序验证。程序设计语言语义学应该把程序设计语言作为主要的学科领域。大致包括ACM学科类D.2.4、F.3.1、F.4.0、F.4.1和F.4.2中的材料；F.4.3（形式语言）中的一些材料在这里也可能是合适的，尽管计算复杂性通常是更合适的主题领域。
--
一级分类：Mathematics        数学
二级分类：Combinatorics        组合学
分类描述：Discrete mathematics, graph theory, enumeration, combinatorial optimization, Ramsey theory, combinatorial game theory
离散数学，图论，计数，组合优化，拉姆齐理论，组合对策论
--
一级分类：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的别名。经济学，包括微观和宏观经济学、国际经济学、企业理论、劳动经济学和其他金融以外的经济专题
--

---
PDF下载：
--> Impossibility_Theorems_and_the_Universal_Algebraic_Toolkit.pdf (432.59 KB)

2022-5-8 07:24:34 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：工具箱 可能性 Quantitative Optimization Verification

不可能性定理与泛代数工具Kitmario Szegedy和Yixin Xu罗格斯大学计算机科学系。罗格斯大学。教育部，2018年11月10日摘要我们阐明了判断聚合理论（更一般地说，评估聚合）与一个相对年轻但增长迅速的普适代数领域之间的密切联系，该领域主要用于研究约束满足问题。我们的联系产生了一个完整的非二元评估分类，分为可能性域和不可能性域，无论是在有效条件还是支持条件下。在当前结果之前，E.Dokow和R.Holzmanner通过组合方法对支持性案例中的非二元评估进行了分类。代数方法也为我们提供了对更简单的二元情况的新见解，这已经被上述作者完全分类。我们的代数观点让我们提出了一个关于加强非独裁标准的建议，这有助于我们避免像a ffine子空间这样的“异常值”。最后，我们给出了计算复杂度的上界，如果一个域不可能或不可能（据我们所知，之前没有给出确切的时间界限）。关键词：判断聚合、话语困境、康多塞悖论、阿罗不可能理论、社会选择理论、独裁、兼容操作、约束满足问题、二分法、，多态性1简介判断聚合的目标是研究“将多个逻辑连接命题上的单个判断集聚合为集体判断集”的函数的存在与否[LP02]。

阿罗的不可能性定理可以在判断聚合框架中进行解释，这是一个有力的例子，表明即使在简单的情况下，我们也无法有意义地将个人观点聚合为社会观点。Elad Dokow和Ron Holzman[DH10a，DH10b]研究了判断聚合的一个优雅概括，我们在他们的评价聚合标题后称之为判断聚合。假设J是一组确定的问题，D是一组确定的可能立场/意见（如“是”、“否”等）。在不失去普遍性的情况下，我们假设j=[m]={1，…，m}。评估（v，…，vm）∈ DMD将D中的一个位置分配给每个j∈ [m] 。二元情况whenD={0，1}受到了特别关注[Wil75，RF86，DH10a]。我们的基本目标是领域X 在可行性评估中，这些评估（即意见组合）允许选民选择。例1。假设在谋杀案审判期间，陪审团成员必须就两个问题进行投票：1。嫌疑人有一把刀；2.嫌疑人是凶手；在每个问题上采取“是”或“否”的立场。每个成员都必须在这两个问题上采取立场，但陪审团同意，立场组合（1:否，2:是）不应有效：既不能作为个人投票，也不能作为集合投票。因此X={（不，不），（是，不），（是，是）}。聚合器。当一个社会的n个成员对所有m个问题采取立场时，每个成员的意见来自X，我们得到一个文件向量（X（1），x（n））∈ Xn。我们的目标是设计一个函数f:Xn→ 将文件向量转换为X的单个元素的函数。这种函数称为聚合器。我们将考虑的聚合器必须满足三个条件，这三个条件直接来自Arrow的著名条件，他在研究偏好列表聚合的特殊情况时确定了这三个条件。在我们描述它们之前，我们注意到x（i）=（x（i）。

，x（i）m）∈ 对于i=1，··，n，是向量本身：x（i）jis是jthissue上的位置。因此，文件是向量的向量。f的输出是一个以Dm为单位的向量，表示m个问题上的聚合位置。后一个向量也必须属于X。第一个也是关键的条件是，每个问题都应该独立于其他问题进行聚合（也称为逐点聚合或逐问题聚合）：逐问题聚合（IIA）：有函数fj:Dn→ D（1）≤ J≤ m） 这样，外汇（x（1），x（n））∈ Xn:f（x（1），x（n））=Fx（1），x（n）, . . . , 调频x（1）米，x（n）m通过picturex（1）·x（1）m可以很好地可视化IIA属性∈ 十、x（n）··x（n）m∈ 十、↓f···↓fmx··xm∈ X上面我们汇总了列j（其中j∈ [m] 是功能fj的问题）。f takesXnto X的条件相当于，如果每一行都属于X，那么聚合行也属于X。组件聚合函数应该协同工作以实现这一点。我们采用了E.Dokow和R.Holzman[DH10a，DH10b]提出的术语“逐项汇总”，在这种广义背景下，它比常用的“无关替代品的独立性”表达更适合，其好处是首字母缩写保持不变。IIA分解的唯一性。f:Xn的表示→ X as（f，…，fm）显然不是唯一的，例如，当D包含任何元素时，这些元素在任何X中都不是构成元素∈ X.为了避免FJ的非唯一性，我们定义了j=prjX={uj|（u，…，um）∈ 十} 。如果我们定义fjon Dnjin而不是Dn，很容易看出fjbecomes是独一无二的。在本文中，我们将假设这一点。接下来，我们将描述Arrow对聚合器f:Xn施加的另外两个条件（除了IIA）→ 幂等性（或一致性）：f（X，…，X）=X每X∈ 引理1。

IIA聚合器f=（f，…，fm）是幂等的当且仅当在泛代数意义下每个FJI都是幂等的，即。 1.≤ J≤ M U∈ Dj:fj（u，…，u）=uNon独裁：聚合器f:Xn→ 如果有一个1，那么X就是独裁≤ K≤ n使得forevery（x（1），x（n））∈ 我们有f（x（1），x（n））=x（k）。否则，f引理2的非独裁条件成立。IIA聚合器f=（f，…，fm）是独裁当且仅当存在1≤ K≤ M使得每个FJI都是在普遍代数意义下的KTH坐标上的投影： 1.≤ J≤ M U联合国∈ Dj:fj（u，…，un）=UK定义1（不可能性/可能性域）。我们称之为X 关于IIA+幂等性+非独裁条件的Dma可能性域（箭头后），如果对于某些n≥ 2存在满足上述三个条件的算术数为n的X的聚合函数f。OtherwiseX是一个不可能的领域。在本文中，我们完全刻画了关于IIA+幂等+非独裁的不可能域，以及当幂等被支持性取代时的不可能域：f:Xn→ 如果每X（1），x（n）∈ Xnand每1≤ J≤ 我们有f（x（1），x（n））j∈ {x（1）j，…，x（n）j}。引理3。IIA聚合器f=（f，…，fm）是支持的当且仅当每个FJI在普遍代数意义上是保守的： 1.≤ J≤ M U联合国∈ Dj:fj（美国，…，联合国）∈ {u，…，un}支持性意味着幂等性，但反之亦然。在我们的结果之前，我们在[DH10a]中获得了IIA+幂等+非独裁下所有不可能二元域的完整特征。

他们将工作扩展到了非二元情况，但只获得了部分特征，并且仅在IIA+支持+非独裁条件下。在我们的描述中，我们利用了D.Geiger[Gei68]发现的Galois联系。盖革的性质定理允许我们用小工具的存在来描述聚合器的不存在性——存在的逻辑表达式是由X和一些非常基本的关系创建的，比如赋值或一元关系。（在文献中，小工具有时也称为连接查询。）定理8和定理17给出了我们的主要结果。我们的主要贡献不是任何新技术，而是指出了迄今为止尚未探索的非常广泛的联系。简单只对新连接有利。基于代数观点，我们还可以加强非独裁条件，以排除专家认为的异常值（如线性子空间）的可能性。我们在这里使用的理论越来越为计算机科学家所熟悉，因为它提供了一个强大的机制来解决著名的费德和瓦迪[FV98]关于约束满意度问题（CSP）的二分法猜想。希望这种联系能让研究人员利用CSP研究所创造的大量材料来证明不可能性定理。2背景E.Dokow和R.Holzman在[DH10a，DH10b]中提出了引言中描述的优雅的一般组合框架，作为本论文的基础。我们将其命名为“综合评估”，以其标题命名。在他们的两个突破性成果中，他们在对不可能域进行分类方面取得了决定性的进展，即那些我们无法从中总结观点的X。特别是，他们彻底解决了二元问题。为了解释他们的结果，我们需要一些定义。定义2。

如果| prjX |对每1大于1，我们称X为非退化的≤ J≤ m、 由于退化发生的问题可以简单地聚合起来，在不丧失普遍性的情况下，我们可以假设X是非退化的。定义3（块度图和MIPE）。域X的块性图 {0，1}在顶点集V=[m]×{0，1}上有一个有向图：有一条来自（k，σ）的有向边∈ Vto（`，ρ）∈ 其中k6=`当且仅当存在：（i.）子集S [m] 这样k，`∈ S和（ii）a（部分）评估美国→ {0，1}uk=σ，u`=¨ρ，因此在x中没有任何完整赋值x的扩展，但如果我们定义u的任何位，则得到的部分赋值将扩展到x的某个元素。上述部分赋值u称为MIPE（最小不可行部分赋值）。定义4（完全堵塞）。域X {0，1}mH是完全阻塞条件，当且仅当阻塞图是强连通的。Nehring和Puppe[NP02]的结果导致[DH10a]。当单调性条件被添加到通常的条件中时，他们已经获得了二进制不可能域的完整分类。如果在任何情况下，对于每个问题j，如果投票人决定将他/她在该问题上的立场转换为当前的聚合立场，那么聚合器被称为单调的。定理4（Nehring和Puppe[NP02]）。非退化X 关于IIA+幂等性+单调性+非独裁性，{0，1}是一个不可能域，当且仅当X是完全锁定的。E.Dokow和R.Holzman：定理5（E.Dokow，R.Holzman[DH10a]）最终证明了没有单调性条件的二元计算的完整特征。让X {0，1}m，非退化。

那么X是关于IIA+幂等性+非独裁的一个可能性域，当且仅当X是全锁的且不是一个有效子空间。Dokow和Holzman在通用D[DH10b]方面也取得了重大进展。在近特征化中，他们对非二进制谓词使用了总阻塞性的推广，这与二进制概念相似但更复杂，我们将定义推迟到第10.1节（定义17）。我们还需要定义关系X的一个条件，这在宇宙代数文献中被称为2-可分解性。对于[DH10b]中的同一概念，我们采用了这个术语，而不是“非多重约束”表达式。定义5。对于D上的m元关系X和1≤ k<`≤ m、 让prk，`X={（uk，u`）|（u，…，嗯）∈ 十} 。如果对于任何元组X=（X，…，xm），关系X称为2-可分解的∈ DMWEX∈ X当且仅当（xk，X`）∈ prk，`X代表所有1≤ k<`≤ m、 备注1。巧合的是，在[DH10b]中也出现了“2-可分解”的表达，但含义截然不同。定理6（E.Dokow，R.Holzman[DH10b]）。让X Dm，非退化和非二进制（有一个1≤ J≤ 我认为| prjX |>2）。如果X完全被阻止且不可2-分解（见定义5），那么X是关于IIA+支持性+非独裁的不可能域。定理7（E.Dokow，R.Holzman[DH10b]）。让X 马克。如果X是非退化的，并且不是完全封闭的，那么X是关于IIA+支持性+非独裁的可能性域。3.我们的研究结果尽管多科和霍尔茨曼取得了令人印象深刻的进步，但仍有一些重要问题有待解决：1。当| D |>3时，完成支持性案例的描述。（在[DH10b]中，|D |=3的情况得到解决。）2.

用幂等条件解决| D |>2的情况。我们从代数理论中得到启发，并将其与[DH10b]的思想结合起来，得到了非二元情形的完整特征，以及支持性和幂等性条件。定理8。让X Dm，非退化和非二元。如果X完全被阻止，那么X是关于IIA+支持性（幂等）+非独裁的可能性域，当且仅当不存在支持性（幂等）非独裁IIA聚合器，且最多有三个（| D |）投票者。描述（据我们所知，这是第一次）允许算法确定ifX是关于支持（幂等）条件的不可能域。小工具。事实证明，我们可以用一组小工具的双重方式来描述不可能域。我们的新描述为不可能提供了证据，但在投票理论的背景下还没有被更早地了解。Gadget（或连接查询）是在本地翻译实例（逐项）时用于减少约束满足问题的表达式。它们是存在量化的从句组合，其中每个从句都是一种关系。这种解释中的关系被视为不一定是布尔变量上的布尔值函数。gadget的语法是：R（~x）=~y:S（~x，~y）∧ . . . ∧ Sk（~x，~y）（每个Siin效应只取决于~x，~y的子集）它们的目的是表达给定关系集合中的新关系。D.Geiger[Gei68]的一个定理建立了一组关系的聚合器的不存在与Γ-gadget（即所有关系都来自Γ或“=”关系）的存在之间的联系。这个定理是P.Jeavons，A.A.Bulatov，A.A.Krokhin，D.A.Cohen，M.提出的约束满足问题代数理论的支柱。

库珀、M.吉森[JCG97、Jea98、JCC98、BJK05]和其他几位研究人员。图1:multi-sorted Not All Equal（NAE）小工具，用于表示x（类型1）和x（类型3）之间的多重排序不等式关系。变量Yan和Yar是存在界的（它们也被设置为常数）。这个小玩意是我们证明阿罗定理的核心。这也是我们的出发点。在通用代数（IIA）中，聚合器被称为多态性。它们与我们介绍的聚合器不同，因为它们是单排序的：f=f=…=调频。阿尔及利亚文献[BJ03，Bul11]也研究了多分类多态性，即FJ可能不同的情况。在处理多排序多态性时，所有关系和小工具也必须是多排序的。在多排序世界中，我们首先必须为每个变量声明一个类型。变量的类型与编程语言中的用途相同：调用函数时，被调用变量的类型必须与函数声明中的类型匹配。本着同样的精神，我们构造（或提供给我们）的每一个多排序的l元关系R都必须有一系列的l（不一定是不同的）类型。我们可以称之为类型声明。类型必须一致：小工具中任何关系出现时涉及的变量类型必须与类型声明匹配。在本文中，我们证明了盖革定理的多排序版本（见第4节）。这使我们能够通过生产一系列的小配件来验证不可能的结果。如果我们想证明XQmjDjis是一个不可能的领域，我们需要为某个“完整”的（多排序）关系集构造X+小工具。在这里，上一个索引中的“+”指的是使用赋值关系的权限（即“x=a”，其中a∈ 除了X之外，我们的小工具中还有Dj（用于类型j变量）。