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

这笔赠款的总主题是将理论计算机科学的工具和力量应用于选举制度的研究(即，一轮社会选择制度--从一系列投入中得出决定的方法)。我们将以一种远远超越提名人和其他许多人对特定选举制度中胜利者语言复杂性的分析的方式来进行研究；相反，我们的核心重点是以下两个主题：(A)了解选举制度复杂性的原因和来源，以及(B)提供规避这种复杂性的方法。关于(A)项，要了解目前在各种被认为具有公平性质的特定选举制度中发现的高度复杂程度的原因而不是什么，我们将研究公平在多大程度上内在地要求高度复杂。也就是说，我们将得到以下形式的定理：任何满足下面的公平公理的系统都会有一个赢家计算问题，这个问题对于下面的复杂性类来说是困难的。这部分研究的目标是为哪些类型的公平财产征收天生就被排除，哪些类型的公平财产征收不被排除--这些信息在选举(决策)制度的设计和选择中非常有用。也就是说，就像Arrow的不可能性定理[Arr63]明确指出，一些自然的公平/美好属性集合完全排除了具有这些属性的系统的存在，我们希望使用不存在而是(更苛刻的可管理性标准)作为指导，来指导哪些属性集合可以实现，哪些不能实现。(我们还将通过研究选举制度所涉及的中央计分函数的复杂性，确定对语言的标准简化是否掩盖了对选举复杂性的洞察，我们还将研究操纵选举制度的复杂性及其对操纵的抵抗力。)关于(B)，我们探讨的核心想法将是：由于真正的选举通常有少量的候选人，对于复杂的选举制度(具体的选举制度和广泛的选举制度)，当被视为候选人人数的参数时，它们的复杂性是什么；以及高复杂性的选举制度背后的计分函数能否很好地逼近，或者能否证明它们不能；在非正式的日常实践中，能否用启发式方法很好地攻击它们？更广泛的影响这项建议涉及广泛的影响，包括信息传播、国际合作、与非授予博士学位的学校的合作、丰富当地社区、培训学生和博士后，以及为理论界提供服务。在整个提案中更详细地概述了这些活动：在项目的更广泛的影响部分。描述，在前工作部分的人力资源和对社区的服务部分，在传记的协同活动部分。素描，以及在毕业典礼上。学生理由预算理由的一部分。另一个更广泛的影响是通过研究本身。这项研究最重要的目标是确定选举公平/友好条件的哪些组合天生会/不会导致计算复杂性。这个目标是非常自然的，因为它试图确定哪些类型的选举制度公平目标不会撞上复杂性理论限制的墙(基本上，类似于阿罗的不可能定理，但不是通过数学上的不可能，而是通过计算的限制来强制执行)。至于这项研究的其他部分，权力公平的研究将研究哪些分配算法放大或缩小社会中小投票团的权力；操纵研究将寻求了解是什么使系统易于评估但同时难以操纵；对看似计算复杂的系统的固定参数复杂性的研究将寻求资助，即使这样的系统在合理的候选人数量上也是可行的。(关于ECS/ASE/NHS，查看计划征集中对它们的详细描述，显然这三个都深受公平和有效地根据不同实体的偏好做出决定的问题的重要性的影响。英国国民健康保险制度还得到了操纵和控制研究的支持。技术重点DMC得到决策的支持，这是DMC重点领域描述的明确部分。)

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