Complexity of Elections: Young and Dodgson Voting Systems

Title: Complexity of Elections: Young and Dodgson Voting Systems

Abstract: This research study investigates the complexity of determining the winner and ranking in Young and Dodgson voting systems. It presents results that show that both problems are complete for PNP/bardbl, a class of problems solvable in polynomial time by parallel access to an NP oracle. The study also explores a homogeneous variant of Dodgson elections proposed by Fishburn and demonstrates that the winner and ranking problems can be solved efficiently by a linear program.

Research Question: How complex is it to determine the winner and ranking in Young and Dodgson voting systems?

Methodology: The study uses reduction techniques and integer linear programming to prove the complexity of the problems. It builds on previous research by Bartholdi, Tovey, and Trick, Hemaspaandra, Hemaspaandra, and Rothe, and Spakowski and Vogel.

Results: The research shows that both the winner and ranking problem for Young elections are complete for PNP/bardbl. It also demonstrates that the winner and ranking problem for Fishburn's homogeneous Dodgson elections can be solved efficiently by a linear program.

Implications: These results contribute to the understanding of the computational complexity of voting systems and may have implications for the design and analysis of voting protocols. They also provide insights into the conditions under which society's aggregate choice can be rational and consistent.

Link to Article: https://arxiv.org/abs/0112021v1 Authors: arXiv ID: 0112021v1