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