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