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），为了了解目前在各种特定选举制度中发现的高复杂性水平的原因，而不是其公平性类型属性被认为是良好的，我们将研究其程度公平本质上需要高度复杂性。也就是说，我们将获得以下形式的定理： 任何满足以下公平公理的系统都将存在对于以下复杂性类别来说很难的获胜者计算问题。这部分研究的目标是资助哪些类型的公平财产集合本质上是被排除的，哪些类型不是——在选举（决策）系统的设计和选择中非常有用的信息。也就是说，正如阿罗不可能定理 [Arr63] 明确指出，一些自然的公平/善良属性集合完全排除了具有这些属性的系统的存在，我们希望不使用存在性，而使用（更严格的标准）可处理性作为指导哪些财产收藏可以实现，哪些不能实现。 （我们还将通过研究选举系统中涉及的中心评分函数的复杂性，确定语言的标准简化是否模糊了对选举复杂性的洞察，我们还将研究操纵选举系统的复杂性及其对操纵的抵抗力.)关于(b)，探讨的核心思想是：由于真正的选举通常只有少数候选人，对于复杂的选举系统（包括特定的系统和广泛的系统），从角度来看它们的复杂性是多少由候选人数量参数化；高度复杂的选举系统的评分函数能否被很好地近似，或者能否证明它们不能；在非正式的日常实践中，他们能否受到启发式方法的有效攻击？ 更广泛的影响 该提案涉及更广泛的影响，包括信息传播、国际合作、与非博士学位授予学校的合作、丰富当地社区、培训学生和博士后，以及为理论界服务。这些活动在整个提案中进行了更详细的概述：在项目的更广泛影响部分。描述，在前期工作部分的人力资源和社区服务部分，在 Biog 的协同活动部分。素描，并在研究生中。学生理由是预算理由的一部分。另一个更广泛的影响是通过研究本身。该研究最重要的目标是确定哪些选举公平/友善条件的组合本质上会/不会引起计算复杂性。这个目标是非常自然的，因为它试图确定哪些类型的选举制度公平目标不会撞上复杂性理论限制的墙（基本上，类似于阿罗不可能定理，但不是通过数学不可能性而是通过计算的局限性）。至于研究的其他部分，权力公平的研究将研究分配算法放大或缩小社会内小投票区块权力的问题；对操纵的研究将寻求了解是什么使系统易于评估但同时难以操纵；对看似计算复杂的系统的固定参数复杂性的研究将寻求资助，即使这样的系统在“合理”数量的候选人上也是可行的。（关于 ECS/ASE/NHS，请查看项目征集中对它们的详细描述）很明显，这三个因素都深受基于 NHS 偏好的公平和有效决策的重要性的影响，并且还得到了操纵和控制研究的支持。经过决策，这是 DMC 重点领域描述的明确部分。）