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.)

这笔赠款的总体主题是将理论计算机科学的工具和力量带入对选举系统的研究（即SO SO的一轮社会选择系统，从而从一系列的投入中得出决定）。我们将以一种远远超出提议者和许多其他人进行的特定选举系统研究中的语言复杂性分析的方式来做。相反，我们的核心重点是以下两个主题：（a）理解选举系统中复杂性的原因和来源，以及（b）提供这种复杂性的方式。让我们依次谈论这两个相关主题依次。关于（a），要不了解到现在在各种特定的选举系统中发现的高复杂性水平的原因，这些级别从其公平性型特性方面被认为是好的，我们将研究公平固有地需要高复杂性的程度。也就是说，我们将获得形式的定理：满足以下公平公理的任何系统都会有一个赢家的问题，对于以下复杂性类别而言，这很难。这一研究的目的是资助固有排除的公平性财产收集类型，以及哪些类型在选举（决策）系统的设计和选择中非常有用。也就是说，正如Arrow的不可能定理[ARR63]明确表明，某些自然公平/善意的财产收集完全排除了具有这些属性的系统的存在，我们希望使用不存在，而是（更苛刻的易访问标准）作为指导属性可以和无法实现的指导。 （我们还将通过研究选举制度中涉及的中心分数功能的复杂性，确定语言的标准简化是否掩盖了对选举复杂性的见解，我们还将研究操纵选举系统的复杂性及其对操纵的抵抗的复杂性，以及它们对操纵的抵抗力。）关于（b）的核心思想。当将候选人数量视为参数时，它们的复杂性是什么？并且可以很好地证明其具有很高复杂性的选举系统的评分功能是否可以证明它们不能；在非正式的日常练习中，他们是否可以通过启发式方法进行攻击？更广泛的影响，该提案涉及广泛的广泛影响，包括信息传播，国际合作，与非Phd授予学校的合作，当地社区的丰富，培训学生和培训学生和培训后以及对理论社区的服务。在整个建议中，这些活动更详细地概述了：在ProJ的更广泛影响中。描述在人力资源和对先前工作部分社区部分的服务中，在《生物日》的协同活动中。素描和毕业生。学生的理由是预算辩护的一部分。另一个更广泛的影响是通过研究本身。该研究最重要的目标是确定固有的/不引起计算复杂性的选举公平/善良条件的哪些组合。这个目标是非常自然的，因为它试图确定哪些类型的选举系统公平目标不会陷入复杂性理论局限性的墙壁（基本上是对Arrow的不可能定理的类似物，但不是由于数学上的不可能而实现的，而是由于计算的局限性而实现的）。至于研究的其他部分，对电力的研究将研究哪种分配算法扩大或缩小社会中小型投票块的力量的问题；对操纵的研究将寻求学习使系统易于评估但同时难以操纵的原因；看似计算复杂系统的固定参数复杂性的研究甚至在这些系统都可以在合理的“候选人数量上都是可行的（关于ECS/ASE/NHS的数量）。（关于程序招标中对它们的详细描述，这三个都会受到对临时和有效的决定的重要性，从而深深地影响了它们的详细描述。在对操纵和控制的研究和技术重点DMC的支持下，由决策支持，这是DMC焦点区域描述的明确部分。