2015/07/21 by Arne Recknagel, Recknagel, Arne, Tarek R. Besold +1
Computer Science · Economics, Econometrics and Finance · #Advanced Algebra and Logic #Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #Distributed #FOS: Computer and information sciences #Game Theory and Voting Systems #H.4.2 #I.2.11 #I.2.3 #I.2.8 #Logic, Reasoning, and Knowledge #Multiagent Systems (cs.MA) #Parallel #and Cluster Computing (cs.DC) #cs.AI #cs.DC #cs.GT #cs.MA
paper · pdf · doi:10.48550/arxiv.1507.05875
Additional references; partially rewritten text for improved readability; minor corrections of typos/language issues etc
openalex publication_date 2015/07/21 · arxiv created 2016/08/09 · arxiv updated 2016/08/10 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
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. One of the voting procedures most 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 on 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 reducing the problem size.