This project will broaden and advance the understanding of voting systems starting with the view that these systems are methods of aggregating agent preferences to select a set of winners. The project will classify voting systems by extracting the source of complexity in elections?ideally via dichotomy results completely characterizing which systems are complex, and which are easy, for the key electoral questions such as control, winnership, bribery, and manipulation. The project will broaden the range of models for election results of this sort, and in particular will extend existing polynomial-time algorithms as far as possible into incomplete information models.
This work is closely allied with issues of interest in social choice, economics, political science, mathematics, and operations research. Elections are used extensively by humans and in (electronic) multi-agent systems, and so protecting such systems against manipulation is of compelling importance to both computer science and society. The development of complex control mechanisms uses complexity in a positive way, namely, using complexity to make difficult the task of would-be electoral manipulators and controllers.
