Towards Efficiently Implementing Dodgson’s Formally Intractable Voting Rule

Abstract

Conflict of interest is the permanent companion of any population of agents (computational or biological). For that reason, the ability to compromise is of paramount importance, making voting a key element of societal mechanisms. A voting procedure often discussed in the literature and, due to its intuitiveness, also conceptually quite appealing is Charles Dodgson’s scoring rule, basically using the respective closeness to being a Condorcet winner for evaluating competing alternatives. In this paper, we offer insights into the practical limits of algorithms computing the exact Dodgson scores from a number of votes. While the problem itself is theoretically intractable, this work proposes and analyses five different solutions which try distinct approaches to practically solve the issue in an effective manner. Additionally, three of the discussed procedures can be run in parallel which has the potential of drastically improving computational performance on the problem.