ITR - (ECS+ASE+NHS) - (dmc): Richer Understanding of the Complexity of Election Systems

ITR - (ECS ASE NHS) - (dmc)：对选举系统复杂性的更深入了解

• 批准号: 0426761
• 负责人: Lane Hemaspaandra
• 金额: --
• 依托单位: University of Rochester
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0426761&HistoricalAwards=false
• 关键词: ITR; ECS+ASE+NHS; dmc; Richer; Understanding

The overall theme of this grant is to bring the tools and power of theoretical computer science to bear on the study of electoral systems (i.e., one-round social choice systems-ways of so reaching a decision from a collection of inputs). We will do so in a way that jumps far beyond the analyses of language-complexity-of-winner in specific electoral systems research done by the proposer and many others; rather, our core focus is on the following two themes: (a) understanding the reasons for and sources of complexity in electoral systems, and (b) providing ways of circumventing such complexity.Let us speak of each of these two related themes in turn. Regarding (a), to get at not the what but the why of the high complexity levels that by now have been found in various specific electoral systems that are considered nice in terms of their fairness-type properties, we will study the extent to which fairness inherently requires high complexity. That is, we will obtain theorems of the form: Any system satisfying the following fairness axioms will have a winner-computation problem that is hard for the following complexity class. The goal of this part of the research is to fund what types of fairness property collections are inherently precluded, and what types are not-information that is very useful in the design and choice of electoral (decision) systems. That is, just as Arrow's Impossibility Theorem [Arr63] made clear that some natural fairness/niceness property collections outright preclude the existence of systems having those properties, we wish to use not existence but (the more demanding standard of) tractability as a guide to what property collections can and cannot be achieved. (We also will, via studying the complexity of the central score functions involved in electoral systems, determine whether the standard simplification to languages has obscured insights into electoral complexity, and we will also study the complexity of manipulating electoral systems, and their resistance to manipulation.)Regarding (b), the core ideas explored will be: Since real elections typically have small numbers of candidates, for complex electoral systems (both specific ones and broad classes of systems), what is their complexity when viewed as parameterized by the number of candidates; and can the scoring functions underlying electoral systems having high complexity be well-approximated, or can it be proven that they cannot; and in informal everyday practice can they be well-attacked with heuristic methods?Broader Impacts This proposal involves a wide range of broader impacts, including information dissemination, international collaboration, collaboration with a non-PhD-granting school, enrichment of local community, training of students and post-docs, and service to the theory community. These activities are outlined in more detail throughout the proposal: in the Broader Impacts part of the Proj. Description, in the Human Resources and Service to the Community parts of the Prior Work section, in the Synergistic Activities part of the Biog. Sketch, and in the Grad. Student Justification part of the Budget Justification. Another broader impact is via the research itself. The research's most important goal is to determine which combinations of electoral fairness/niceness conditions inherently do/don't induce computational complexity. This goal is exceedingly natural, as it seeks to identify what types of electoral-system fairness goals don't crash into the wall of complexity-theoretic limitations (basically, an analog of Arrow's Impossibility Theorem, yet enforced not by mathematical impossibility but rather by the limitations of computation). As to other parts of the research, the study of power-fairness will research the issue of which apportionment algorithms amplify or shrink the power of small voting blocks within a society; the study of manipulation will seek to learn what makes a system easy to evaluate yet simultaneously hard to manipulate; the study of fixed-parameter complexity of seemingly computationally complex systems will seek to fund when even such systems can be feasible on \reasonable" numbers of candidates. (Regarding ECS/ASE/NHS, looking at the detailed descriptions of them in the program solicitation, it is clear that all three are deeply affected by the importance of the issue of coming fairly and efficiently to decisions based on the preferences of separate entities. NHS is additionally supported by the studies of manipulation and control. And the Technical Focus dmc is supported by decision-making, which is an explicit part of the description of the dmc focus area.)

这项资助的总体主题是将理论计算机科学的工具和力量应用于选举系统的研究（即，一轮社会选择系统——从一系列输入中做出决定的方法）。我们将以一种远远超越由提议者和其他许多人在特定选举制度研究中对获胜者的语言复杂性的分析的方式来进行研究；相反，我们的核心重点是以下两个主题：(a)了解选举制度复杂性的原因和来源，以及(b)提供规避这种复杂性的方法。让我们依次谈谈这两个相关的主题。关于(a)，为了了解目前在各种被认为具有公平性质的特定选举制度中发现的高度复杂性的原因而不是“是什么”，我们将研究公平本质上需要高度复杂性的程度。即，我们将得到如下形式的定理：任何满足以下公平性公理的系统将存在一个赢家计算问题，该问题对于以下复杂性类来说是困难的。这部分研究的目标是资助哪些类型的公平财产收集本质上是被排除在外的，哪些类型是不被排除在外的——这些信息在选举（决策）系统的设计和选择中非常有用。也就是说，正如阿罗的不可能性定理（arar63）明确指出的那样，一些自然的公平/美好属性集合完全排除了具有这些属性的系统的存在，我们希望使用可追溯性（更苛刻的标准）而不是存在性来指导属性集合可以实现和不能实现。（我们还将通过研究选举系统中涉及的中心分数函数的复杂性，确定对语言的标准简化是否掩盖了对选举复杂性的洞察，我们还将研究操纵选举系统的复杂性，以及它们对操纵的抵抗能力。）关于(b)，探讨的核心思想将是：由于真正的选举通常只有少数候选人，对于复杂的选举制度（具体的和广泛的制度），当以候选人数量作为参数时，它们的复杂性是什么？具有高度复杂性的选举系统的得分函数是否可以很好地近似，或者是否可以证明它们不能很好地近似；在非正式的日常实践中，启发式方法能很好地攻击它们吗？更广泛的影响这项建议涉及范围广泛的影响，包括信息传播、国际合作、与非博士学位授予学校的合作、丰富当地社区、培训学生和博士后，以及为理论界提供服务。这些活动在整个提案中有更详细的概述：在项目的“更广泛的影响”部分。描述，在前期工作部分的人力资源和社区服务部分，在个人简介的协同活动部分。素描，并在Grad。预算论证的学生论证部分。另一个更广泛的影响是通过研究本身。该研究最重要的目标是确定选举公平性/良好性条件的哪些组合固有地会/不会引起计算复杂性。这个目标是非常自然的，因为它试图确定哪种类型的选举系统公平目标不会撞到复杂性理论限制的墙上（基本上，类似于阿罗的不可能定理，但不是通过数学上的不可能，而是通过计算的限制来执行）。在其他部分的研究中，权力公平的研究将研究分配算法在社会中放大或缩小小投票区块的权力的问题；对操纵的研究将寻求了解是什么使一个系统易于评估，同时又难以操纵；对看似计算复杂的系统的固定参数复杂性的研究将寻求资助，即使这样的系统在“合理”的候选数量上也是可行的。(关于ECS/ASE/NHS，看看项目征集中对它们的详细描述，很明显，这三者都深受基于不同实体偏好的公平和有效决策问题的重要性的影响。NHS还得到了操纵和控制研究的支持。技术焦点dmc是由决策支持的，这是dmc重点领域描述的明确部分。