Voting in parallel universes

28^th April 2015, 13:00 Ashton Lecture Theater
Prof. Stephane Airiau
LAMSADE
University of Paris-Dauphine
France

Abstract

Some voting rules involve some tie-breaking in the course of an multi-stage process (this is notably the case for STV). For these rules, some authors have argued that there exists a version where ties are broken when they appear, and a 'parallel universe' where all ways of breaking ties at intermediate stages are considered (and, if necessary, ties are broken at the very end). A general framework for these rules had been discussed in (Freeman et al., 15), based on so-called 'computation trees'. Here we propose an alternative general framework, where each 'possible universe' corresponds to a priority ranking over candidates. We show that many other rules fall in this family (such as Banks and Top Cycle). We also consider two other classes of rules: stochastic rules, where the winning probability of a candidate is the ratio of tie-breaking orders for which it wins, and an 'argmax rule' that elects the candidates max- imizing this winning probability. We discuss several properties of these rules and discuss some complexity issues as well as simulation results.