# approval_with_runoff__542ed434.pdf

Approval with Runoff

Th eo Delemazure1 , J erˆome Lang1 , Jean-Franc ois Laslier2 and M. Remzi Sanver1

1CNRS, Universit e Paris-Dauphine, Universit e PSL, LAMSADE 2CNRS, Paris School of Economics, Universit e PSL theo.delemazure@dauphine.eu, [jerome.lang, remzi.sanver]@lamsade.dauphine.fr, jean-francois.laslier@ens.fr

We deﬁne a family of runoff rules that work as follows: voters cast approval ballots over candidates; two ﬁnalists are selected; and the winner is decided by majority. With approval-type ballots, there are various ways to select the ﬁnalists. We leverage known approval-based committee rules and study the obtained runoff rules from an axiomatic point of view. Then we analyze the outcome of these rules on single-peaked proﬁles, and on real data.

1 Introduction

Plurality with runoff (also known as runoff voting) is a widely used single-winner voting rule, in fact the most common rule for presidential elections throughout the world1. But the social choice literature has pointed out that plurality with runoff suffers from so many drawbacks that we may wonder why it is used at all: it is highly sensitive to cloning, fails monotonicity, reinforcement, participation, Condorcet-consistency, and is very easy to manipulate. In particular, its high sensitivity to cloning has a number of derived effects before the vote (at the level of the determination of candidates) and at voting time (with massive strategic voting of a speciﬁc kind, called useful voting2). Perhaps the main reason why it is so widely used after all is related to the fact that runoff voting is not used as a one-shot voting rule but as two-round protocol: voters are called to urns for the ﬁrst round, the results are made public, and then some amount of time passes (typically one or two weeks), and in between the two rounds, many things happen. In most variants, only two candidates are selected for the runoff. The others candidates may negotiate their support to one of the two contenders, leading to adjustments in the platforms proposed in the second round. The TV debates that take place between the two ﬁnalists at that point in time are considered as the most important moment in the whole campaign, and many voters may, during this period, review their decision to participate or not to the second vote. For all

1See https://en.wikipedia.org/wiki/Two-round system. 2As an example, in the 2022 French presidential election, voter from various left-wing parties voted for the left-wing candidate maximizing the chances to run on the second round (Jean-Luc M elenchon), even if he was not their preferred candidate.

these reasons, the existence of two rounds of vote separate in time is considered to be crucial for the voters information. Are the informational beneﬁts of a runoff protocol enough to overcome its numerous theoretical drawbacks? There can be diverse opinions about this. However, instead of answering this question, we may ask another one: is it possible to keep the nice beneﬁt of the two-round protocol without having to bear all the drawbacks of Plurality at the ﬁrst round? Clearly, if the answer to this question is positive, the format of the ballots at ﬁrst round must no longer be uninominal. Several possibilities exist: ordinal ballots, cardinal ballots, or more simply, approval ballots. Approval ballots have several advantages; to start with, they are simple and easy to express. In this paper we explore this possibility seriously. We deﬁne an approval-with-runoff election as a two-round protocol:

1. First round: voters cast approval ballots, from which the two ﬁnalists are selected.

2. Second round: voters cast votes for one of the two ﬁnalists, and the majority winner wins the overall election.3

Formally, we deﬁne approval-with-runoff as a voting rule, with a one-shot input, and study its properties in a similar way as we would study the properties of plurality with runoff. Then two major questions arise:

1. what should the input of the rule consist of?

2. which rule should be used to determine the two ﬁnalists?

For question 1, the answer becomes clear once we remark that we need the approval data for computing the ﬁnalists, and the pairwise comparisons between candidates for computing the ﬁnal winner. Of course, we will not need all comparisons between arbitrary pairs of candidates; but just as plurality with runoff, seen as a voting rule, takes full rankings as input although most of this information will not be asked, here too, we need more information in the input than we will ask voters, and the normative properties of the rule will be evaluated with respect to this (mostly private) information. Now,

3The present paper is concerned with single-winner elections. Approval voting with a runoff is effectively used in several cantons in Switzerland for committee elections. The precise rules vary from one canton to the other so that the second round is sometimes almost unused, as in the canton of Zurich ([Laslier and Van der Straeten, 2016], [Van der Straeten et al., 2018]).

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

requiring pairwise comparisons between all pairs of candidates just means that we need each voter s ranking of candidates, and requiring her approval set means that this ranking comes with a threshold that separates approved candidates from disapproved candidates. This data structure is called an approval-preference (AP) proﬁle [Brams and Sanver, 2009]. Notice that, with respect to the points mentioned in the introduction, the framework that we use does not allow taking into account the evolution of voters and candidates in between the two rounds. We leave these problems to further research and, in this paper as it is often the case in social choice theory, we concentrate on the counting of sincere ballots cast by a ﬁxed electorate. For question 2, things are more complex because there is not a unique way to select two candidates from approval ballots. The general setting in which we select k candidates (here, k = 2) from an approval proﬁle is called an approval-based committee rule (ABC rule); a recent and extensive survey is in [Lackner and Skowron, 2020], and we have now a series of results that tell us which properties these various rules satisfy and for which contexts they are suitable for. Most importantly, the choice of the rule used for the ﬁrst round has strong implications about the very nature of the two-stage rule, both from a normative point of view and from a political science point of view: should we send to the second round the most two approved candidates? Or should we offer the voters two candidates that are diverse enough? Should we pay attention to proportionality issues? Should we guarantee the most approved candidate is among the two ﬁnalists? Our primary aim is to deﬁne approval with runoff not just as one rule but as a family of rules, and to explore the reasons that may guide us towards the choice of one of the rules in the family. The paper is organized as follows. We start by related work (Section 2). We deﬁne the family of Approval-based Runoff rules (Section 3) together with a selection of meaningful rules. We study these rules form an axiomatic point of view (Section 4). We analyse the outcome of these rules on one-dimensional Euclidean proﬁles (Section 5), and move on to applying the rules on real data (Section 6). We conclude in Section 7.

2 Related Work

Approval with Runoff (in its most straightforward version, see Section 3.2) was ﬁrst introduced in [Sanver, 2010] and compared to other rules based on approval-preference proﬁles. Green-Armytage and Tideman [2020] consider plurality with runoff together with eight other runoff rules for selecting the ﬁnalists, with varying input formats (ordinal, approval, numerical), including Approval with Runoff. Voters are supposed to vote sincerely and, for Approval voting, to approve a candidate if and only if the utility they give to this candidate is larger than the average utility of all candidates running. They evaluate these rules along four numerical criteria (expected utility of winner, of the runoff loser, representativeness, resistance to strategy); numerical results come both from using real data and from simulations. Among other conclusions, plurality with runoff scores particularly bad, and approval with runoff, slightly better, although it is beaten by plurality with runoff on

two criteria: representativeness and resistance to strategy. A runoff can also be seen as an extreme case of shortlisting (with at most two selected candidates). Using approval for shortlisting candidates was studied recently in [Lackner and Maly, 2021]; a crucial difference with runoff rules is that shortlisting does not impose constraints on the number of selected candidates, which leads to very different rules. ABC rules have received enormous attention these last ten years: see [Lackner and Skowron, 2020] for a review. They are clustered in several groups according to the objective of the selection: excellence (select the individually best k candidates), proportional representation (ensure that each coherent group of voters is represented in the selection, proportionally to its size), or diversity (output a diverse set of candidates, avoid similar candidates in the selection). Which of these three clusters of rules suits the selection of runoff candidates better is not clear at this point; our paper aims at answering (at least partly) this question. Deﬁning voting rules that take as input approval-preference proﬁles has been initiated in [Brams and Sanver, 2009], who propose and study two such rules (preference approval voting and fallback voting) that have been studied in a number of subsequent works, from the point of view of axiomatization, computation, resistance to strategic behaviour; as far as we know, they have not been studied in the context of runoffs.

3 Approval with Runoff: A Family of Rules

3.1 The Model Let C = {c1, . . . , cm} be a set of m candidates and V = {v1, . . . , vn} a set of n voters. An approval proﬁle is a collection of approval ballots V = A1, . . . , An with Ai C for all i. An ordinal preference proﬁle is a collection of rankings = 1, . . . , n , where i is the preference ranking of voter i over C. An approval-preference proﬁle is a collection of pairs P = (A1, 1), . . . (An, n) where VP = A1, . . . , An is an approval proﬁle and = 1, . . . , n an ordinal preference proﬁle. We also note P = (VP , ). Throughout the paper, we assume ballot consistency: voter vi has a threshold in her ranking i such that every candidate above the threshold is approved and every candidate below is not; formally, a i b holds for all a Ai and b Ai. Ballot consistency allows us to use the following notation [Brams and Sanver, 2009]: x1x2 . . . xj|xj+1 . . . xm represents ( i, Ai) with i= x1 . . . xm and Ai = {x1, . . . , xj}. 4 Given an ordinal preference proﬁle , maj( , {a, b}) is deﬁned as the set of winners of the majority vote between a and b (which is a singleton except in the case of a tie). We now deﬁne the family of approval-based runoff (AVR) rules. The idea is that we use the approval ballots in the ﬁrst round to select two ﬁnalists, and the second round consists in a majority vote between the two candidates. Let F be an (irresolute) approval-based 2-committee rule, i.e. a function that takes as input an approval proﬁle and returns a nonempty set of pairs of candidates. Then, F R is the (irresolute) AVR

4Ballot consistency does not necessarily hold if voters are strategic and cast insincere approval ballots. Most results in the paper still hold without assuming ballot consistency.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

rule such that we conduct the majority rule on every pair of ﬁnalists selected by F. Formally:

F R(V, ) = [

{x,y} F (V ) maj( , {x, y})

For an approval proﬁle V we denote SV (c) = |{i|c Ai}| the approval score of a candidate c C. By extension, the approval score of a set of candidates J C is the number of approval ballots that contains all candidates from the set J, SV (J) = |{i|J Ai}|. For simplicity, we write sets on a simpler form, e.g. SV (abc) instead of SV ({a, b, c}). We call approval winners the candidates that maximize SV , that is the winners of standard (single-winner) approval voting.

3.2 Rules We now deﬁne some ABC rules. Because we need them only for k = 2, we only deﬁne them for this case. (See for instance [Lackner and Skowron, 2020] for a general presentation.) Multi-Winner Approval Voting (MAV):

MAV (V ) = arg max x1,x2 C SV (x1) + SV (x2)

Some rules discount the satisfaction of voters who are already satisﬁed by one of the two ﬁnalists. This is the case of these two rules: Proportional Approval Voting (PAV):

PAV (V ) = arg max x1,x2 C SV (x1) + SV (x2) 1

Approval Chamberlin Courant (CCAV):

CCAV (V ) = arg max x1,x2 C SV (x1) + SV (x2) SV (x1x2)

These rules select the pairs of candidates {x1, x2} maximizing SV (x1)+SV (x2) αSV (x1x2) for some α [0, 1]. This α is equal to 0 for MAV, to 1/2 for PAV and to 1 for CCAV. We call these rules α-AV rules. There also exists sequential versions of these rules. In these sequential versions, the ﬁrst ﬁnalist is always an approval winner. Sequential Proportional Approval Voting (S-PAV): The rule chooses the pairs {x1, x2} such that x1 maximizes SV (x1) and x2 maximizes SV (x2) 1

2SV (x1x2). Sequential Approval Chamberlin Courant (S-CCAV): The rule chooses the pairs {x1, x2} such that x1 maximizes SV (x1), and x2 maximizes SV (x2) SV (x1x2). Note that sequential MAV would be equivalent to standard MAV. For these sequential rules, the ﬁrst ﬁnalist is an approval winner x1, and the second ﬁnalist maximizes the value SV (x2) αSV (x1x2) for some α [0, 1]. We call these rules α-seq AV rules. A rule that almost falls into this family is: Enestr om Phragmen (Ene Phr) : The rule chooses the pairs {x1, x2} such that x1 maximizes SV (x1) and x2 maximizes SV (x2) min(1, Q SV (x1))SV (x1x2) for some quota Q [0, n].

Here α = min(1, Q SV (x1)) and depends on the score of the ﬁrst ﬁnalist. The quota is usually the Droop quota Q = n/(k + 1) = n/3 or the Hare quota Q = n/k = n/2.

Sequential Phragmen (S-Phr): The rule chooses the pairs {x1, x2} such that x1 maximizes SV (x1) and x2 minimizes

1 + SV (x1,x2)

SV (x1) SV (x2)

Example 1. Let V = (2 a, 6 ab, 4 abc, 4 cd, 1 d), i.e., two ballots {a}, six {a, b} etc. With MAV, the selected ﬁnalists are {a, b}; with PAV and S-PAV, {a, c}; with CCAV and S-CCAV, {a, d}. For Ene Phr, the ﬁnalists are {a, c} for both Droop and Hare Quota, as every α-AV and α-seq AV rule with α [1/3, 3/4]. {a, c} are also the ﬁnalists for S-Phr.

We also need the rule that returns all pairs of candidates: Trivial Approval Voting (TRIV): TRIV (V ) = {{x, x } | x, x C, x = x }

Note that the trivial approval rule with runoff is actually not completely trivial: it outputs all candidates except the Condorcet loser whenever there is one. In addition to classic properties of ABC rules (see [Lackner and Skowron, 2021]) we add this one:

Deﬁnition 1. A rule F is said to be favorite-consistent if every winning committee contains an approval winner, i.e. for all winning committee W F(V ), we have W arg maxc C SV (c) = .

In our context, this property is important because it is hard for voters to accept a voting rule in which the approval winner may not be a ﬁnalist. Among the voting rules considered here, it is clear that only sequential rules satisfy this property (MAV, S-PAV, S-CCAV, Ene Phr and S-Phr).

4 Axiomatic Analysis

In this section, we study the properties of AVR rules. As usual, a rule F R is anonymous if it is invariant by any permutation of the voters, and neutral if for any permutation of the candidates π and every proﬁle P, F R(π(P)) = π(F R(P)) We will use the following unanimity condition, that is a strengthening of strict Pareto, adapted to the approvalpreference case. We say that candidate a unanimously preference-approval dominates candidate b if

1. for every voter vi, a i b

2. for some voter vi, a Ai and b Ai Together with ballot consistency, it implies that every voter who approves b also approve a, and at least one voter who approves a does not approve b. For simplicity we refer to this condition as our Pareto condition, and say that a dominates b when a unanimously preference-approval dominates b.

Deﬁnition 2. An AVR rule F R is Pareto-efﬁcient if for all approval-preference proﬁle P in which there exists a, b C such that a dominates b, we have b F R(P).

A i-deviation of a proﬁle P is a proﬁle P such that for all j = i, Aj = A j and j= j. We deﬁne weak strategyproofness as the impossibility for a voter to deviate from a proﬁle where she does not approve any winning candidate to one where she approves at least one winning candidate.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

MAVR S-PAVR S-Phr R Ene Phr R S-CCAVR PAVR CCAVR

Pareto-efﬁcient

Monotonic Weakly Clone-proof

Table 1: AVR rules and their properties

Deﬁnition 3. An AVR rule F R is weakly strategy-proof if for every proﬁle P, there is no i-deviation P of P such that F R(P) Ai = 0 and F R(P ) Ai 1.

It is hard to get strategyproofness in ABC voting, as it is incompatible with proportionality [Peters, 2021]. For AVR rules, this is no better: weak strategyproofness is incompatible with Pareto-efﬁciency. Among the rules deﬁned in Section 3.2, the only strategyproof rule is TRIVR.

Theorem 1. No AVR rule is weakly strategy-proof and Paretoefﬁcient.

Proof. Assume F R is Pareto-efﬁcient and weakly strategyproof. Let P = (V, ) = (10 abc|, ab|c, a|bc, c|ab) that is, V contains 10 approval ballots {a, b, c}, one {a, b} etc., and contains 12 rankings a b c and one c a b. a dominates b in P, and maj( , {b, c}) = b. By Paretoefﬁciency, b / F R(P) and thus {b, c} F(V ). Let P = (V , ) = (10 abc|, a|bc, a|bc, c|ab). In P , a dominates b and maj( , {b, c}) = b, so {c, b} F(V ). Let P = (V , ) = {10 cba|, a|cb, a|cb, c|ab}. In P , c dominates b and maj( , {a, b}) = b, therefore {a, b} F(V ). Because V = V , F(V ) = F(V ) = {a, c}. Assume {a, b} F(V ). Let P = (V , ) = (10 cab|, a|bc, a|bc, c|ab) and a deviation P = (V, ) = (10 cab|, ab|c, a|bc, c|ab), where a voter who used to approve {a} now approves {a, b}. We know F(V ) = {a, c} so F R(P ) = maj( , {a, c}) = c, and a F R(P) because {a, b} F(V ). Therefore, this is a successful manipulation, which contradicts strategy-proofness. Thus, {a, b} / F(V ) and F(V ) = {a, c}. Let P = (V , ) = (10 bca|, ab|c, a|bc, bc|a). In P , b dominates c and maj( , {a, c}) = c. Therefore, {a, c} / F(V ). Assume that {b, c} F(V ). Let b P = (V, b ) = (10 acb|, ab|c, a|bc, c|ba) and b P = (V , b ) = (10 acb|, ab|c, a|bc, cb|a) a deviation where the last voter now approves {b, c}. We have F R( b P) = maj(b , {a, c}) = a. However, if we assume {b, c} F(V ), then c F R( b P ) because maj(b , {b, c}) = c. Therefore, the deviating voter makes c win. This contradicts strategy-proofness, therefore, {b, c} / F(V ) and F(V ) = {a, b}. Finally, let P = (V , ) = (10 cab|, ab|c, a|bc, cb|a) and the deviation P = (V, ) = (10 cab|, ab|c, a|bc, c|ba), where the voter approving {b, c} now approves {c}. We have F R( P ) = maj( , {a, b}) = a and F R( P) = maj( , {a, c}) = c. This deviation is a manipulation. This contradicts strategyproofness, and proves the theorem.

This set of properties is minimal: TRIVR is weakly strategyproof but not Pareto-efﬁcient, MAVR is Pareto-efﬁcient but not weakly strategyproof.

We now focus on monotonicity. Given a proﬁle P = (V, ) and a C, a proﬁle P = (V , ) = P is an a-improvement of P if for some i N we have

1. A i = Ai {a} or A i = Ai 2. For all x, y with y = a, if x i y then x i y

3. For all j = i, A j = Aj and j= j

Deﬁnition 4. An AVR rule F R is monotonic if for every a F R(P) and for every a-improvement P of P, we have a F R(P ).

MAVR satisﬁes both monotonicity and Pareto-efﬁciency.5 All omitted proofs, including this one, are in the long version of the paper [Delemazure et al., 2022]. Finally, we focus on clone-proofness. Informally, this property means that adding a clone of a candidate does not change signiﬁcantly the outcome of the election. Formally, let a C, and a proﬁle P = (V , ) over C = C {a }. P is an a-cloning extension of P = (V, ) if

1. For every vi and x, y C, x A i if and only if x Ai, and x i y if and only if x i y

2. For every vi, a A i if and only if a Ai 3. For every vi and x {a, a }, a i x if and only if a i x

Deﬁnition 5. An AVR rule F R is clone-proof if for any proﬁle P, candidate a C, and an a-cloning extension P of P, the two following conditions hold:

1. For every c = a, c F R(P) if and only if c F R(P )

2. a F R(P) if and only if F R(P ) {a, a } 1

MAVR is not clone-proof. Let P = (a|b, ba|, ba|); MAVR(P) = {b}. P = (aa |b, baa |, baa |) is an a-cloning extension of P and yet MAVR(P ) = {a}. P can be used to prove that CCAVR and S-CCAVR are not clone-proof either: CCAVR(P) = S-CCAV(P) = {b}; P = (V , ) = (aa |b, baa |, baa |) is an a-cloning extension of P; and yet CCAV(V ) = S-CCAV(V ) = {(b, a), (b, a ), (a, a )}, so CCAVR(P ) = S-CCAVR(P ) contains a. Among the rules considered in Section 3.2, none is cloneproof. However, there exist AVR clone-proof rules: such a rule is deﬁned by the ABC rule that selects the pairs of candidates maximizing f(x1, x2) = SV (x1) + SV (x2) 2SV (x1x2). However, this rule is not Pareto-efﬁcient. More generally, clone-proofness and Pareto-efﬁciency are incompatible:

5This is not the only rule satisfying these two properties. This is also the case for F R, where F returns all pairs of candidates {a, b} such that either (i) neither a nor b is Pareto-dominated in V or (ii) a is the only candidate that dominates b in V .

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

0.0 0.2 0.4 0.6 0.8 1.0 0.0

distance to center

Position of the second ﬁnalist for different values of d

d = 0.1 d = 0.25 d = 0.33 d = 0.5 S-PAV

(a) Triangular distribution (Exact solution)

0.0 0.2 0.4 0.6 0.8 1.0 0.0

distance to center

Position of the second ﬁnalist for different values of d

d = 0.1 d = 0.25 d = 0.33 d = 0.5 S-PAV

(b) Gaussian distribution (Empirical solution)

Figure 1: Position of the second ﬁnalist for α-seq AV rules for various values of the approval radius d and with α [0, 1]. The position corresponds to the distance to the center of the distribution (which is also the position of the ﬁrst ﬁnalist)

Theorem 2. No AVR rule is clone-proof and Pareto-efﬁcient.

We now deﬁne a weaker version of clone-proofness, with a domain restriction that eliminates pathological proﬁles:

Deﬁnition 6. An AVR rule F R is weakly clone-proof if it is clone-proof on every proﬁle P such that no candidate c C is approved in every non-empty ballot: for every c C, there exists a voter vi such that Ai = and c Ai.

CCAVR and S-CCAVR are weakly clone-proof.6 Unfortunately, we have the following impossibility:

Theorem 3. No AVR rule is monotonic, weakly clone-proof and neutral.

Proof. Assume F R is monotonic, weakly clone-proof and neutral. Let P = (V, ) = (10 cab|, a|bc, b|ca, c|ab). By neutrality, assume wlog {a, b} F(V ), so a F R(P). P = (V , ) = (10 cab|, a|bc, ba|c, c|ab) is an a-improvement of P. By monotonicity, a F R(P ). Because maj( , {a, c}) = c, this implies {a, b} F(V ). Let P = (V , ) = (10 cba|, a|bc, ba|c, c|ab) and P = (V , ) = (10 cba|, ab|c, ab|c, c|ab) a bimprovement of P . Since V = V we have {a, b} F(V ), and b F R(P ). By monotonicity, b F R(P ). Since maj( , {b, c}) = c, we have {a, b} F(V ). Now consider b P = (b V , b ) = (10 ca|, a|c, a|c, c|a). We have F R( b P) = {c}. If we clone a into another candidate a , we can deﬁne the a-cloning extension b P = (b V , b ) = (10 ca a|, aa |c, aa |c, c|aa ). By weak clone-proofness, neither a nor a is in F R( b P ), so {a, a } / F(b V ). However, if π is the permutation that exchanges a and b, we have π(b V ) = V . By neutrality, F(π(b V )) = F(V ). There is a contradiction, because {a, b} F(V ) and {a, b} / F(π(b V )). This concludes the proof.

This set of properties is minimal: MAVR is monotonic and neutral; CCAVR is weakly clone-proof and neutral; a rule

6Recall that they are not Pareto-efﬁcient. A rule weakly cloneproof and Pareto-efﬁcient is F R, where F selects the CCAV ﬁnalists, and uses MAV as a tie-breaking if there are several pairs of ﬁnalists.

with a constant pair of ﬁnalists is weakly clone-proof and monotonic. On the positive side, some AVR rules satisfy one of the two properties, cf. Theorem 4. In contrast, plurality with runoff is neither monotonic or weakly clone-proof.

Theorem 4. Table 1 gives properties of the different AVR rules (a rule satisﬁes a property if and only if there is a ).

5 Statistical Analysis with One-Dimensional Euclidean Preferences

We now want to explore the spectrum between rules that select the most popular candidates, typically MAV, and rules that favour diversity in the set of ﬁnalists, typically CCAV and S-CCAV or, to a lesser extent, PAV and S-PAV. In this section we focus on one-dimensional Euclidean preferences: we assume that there is a function φ : V C R such that c i c if |φ(c) φ(vi)| < |φ(c ) φ(vi)|. We also assume that there exists d > 0 such that every voter vi approves all candidates c such that |φ(c) φ(vi)| < d. Given a distribution of voters, we want to know in which position a candidate can maximize his score with α-seq AV rules. Godziszewski et al [2021] studied the location of the winners of ABC rules with a 2D-euclidean model.

5.1 Triangular Distribution

We ﬁrst assume that the distribution of voters follows the following triangular density function f: all voters and candidates are located on [ 1, 1], and for all x [ 1, 1], f(x) = 1 |x|. Let us consider α-seq AV rules, for α [0, 1]: for all pairs of ﬁnalists, one ﬁnalist x1 is an approval winner and the other ﬁnalist x2 maximizes SV (x2) αSV (x1x2). Recall that α = 0 leads to MAV and α = 1 to S-CCAV. The ﬁrst ﬁnalist will always be the closest to the middle point of the interval (here 0). It can be shown that the position in which the second ﬁnalist will get the maximum score for speciﬁc α and d is

2 α if α 2d 1 + d 2d

α if 2d α 2d 1 d 2d if α > 2d 1 d

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Rule MAV CCAV S-CCAV PAV S-PAV S-Phr 2017-Strasbourg Lib/Left Lib/Left Lib/ Left Lib/Left Lib/Left Lib/ Left 2017-Grenoble Soc/Lib Soc/Cons Soc/Cons Lib/Left Lib/Soc Cons/ Soc 2017-HSC Lib/Left Lib/Left Lib/ Left Lib/Left Lib/Left Lib/ Left 2017-Crolles Lib/Left Lib/Nat Lib/ Nat Lib/Left Lib/Left Lib/ Left Best-Poster-A #1/#2 #1/#6 #1/#6 #1/#4 #1/#4 #1/#4 Best-Poster-B #1/#2 #1/#2 #1/#2 #1/#2 #1/#2 #1/#2

Table 2: Finalists with different ABC rules on several datasets

0.0 0.2 0.4 0.6 0.8 1.0

Finalists in Grenoble

(Socialist, Conservative) (Liberal, Left) (Liberal, Socialist) PAV

(a) α-AV rules

0.0 0.2 0.4 0.6 0.8 1.0 0

Second ﬁnalist in Grenoble (Socialist is ﬁrst)

Liberal Conservative Left Nationalist S-PAV

(b) α-seq AV rules

Figure 2: Scores of pairs of candidates with α-AV and α-seq AV rules on the Grenoble dataset of the 2017 French presidential election.

This optimal distance to the ﬁrst ﬁnalist is depicted on Figure 1a, which clearly shows that for rules close to MAV, the second ﬁnalist is quite centrist, and the closer we are to S-CCAV, the more extreme is the second ﬁnalist. Also, α-seq AV rules starts to be equivalent to S-CCAV before α = 1 when d < 1

5.2 Gaussian Distribution Now, we assume that we have a Gaussian distribution of voters, with center 0 and standard deviation 1/2. We used simulations on synthetic data. We sampled 20, 000 voters and 1, 000 candidates. Again, every voter approves candidates at distance d. For each d and α we compute the two ﬁnalists and observed their positions on the line. The ﬁrst selected ﬁnalist is always the closest to the center. Figure 1b shows the distance between the two ﬁnalists for α-seq AV rules with α [0, 1] and various d. We observe that Figure 1b is very similar to Figure 1a.

6 Experiments Finally, we want to compare the different rules on real data. We used approval ballot datasets from different sources: Datasets from several cities conducted during the 2017 French presidential election [Bouveret et al., 2019] each with around 1000 voters, and the 11 candidates running. Two datasets of a poster competition held at the San Sebastian Summer School on Computational Social Choice7 (17 candidates, around 60 voters per dataset). After a debiasing step (for the presidential election datasets), we ran the different rules presented in Section 3.2. Table 2 summarizes the ﬁnalists obtained for each dataset and each rule. For some datasets, the choice of the rule has a strong

7Available on www.preﬂib.org

impact on the ﬁnalists, which suggests that the choice of the ABC rule should be made with care. We can also look at the evolution of the ﬁnalists with α-AV and α-seq AV rules when α varies from 0 to 1. This gives us a spectrum of rules from MAV to (S-)CCAV and we can see how the results evolve between the extremes. For MAV, the ﬁnalists are the two candidates from the strongest group, and for CCAV, they are from two very different groups. Figure 2a depicts the evolution of the pair of ﬁnalists for α-AV rules for the 2017-Grenoble Dataset. We can see that the pairs of ﬁnalists change twice and involve 4 different candidates (Liberal, Left, Socialist and Conservative). As no candidate appears in all three pairs, the ﬁnal winner will differ for at least two rules. Figure 2b depicts the evolution of the α-seq AV score of candidates for second ﬁnalist spot in the 2017-Grenoble dataset. The approval winner is the Socialist candidate; the second ﬁnalist is either the Liberal or the Conservative.

7 Conclusion Our main message is that approval with runoff is not one rule but a family of rules, parameterized by the ABC rule chosen for determining the ﬁnalists. Our axiomatic and experimental results in Sections 4, 5 and 6 show that this choice makes a big difference. If such rules have to be used in political elections, the choice of the ABC rule will be crucial, and is far from easy, but our results already give some useful elements. An important question is, will citizens understand and accept such rules especially in comparison with plurality with runoff and standard (single-winner) approval voting? Will there be a difference in voting behaviour under AVR rules between citizens used to runoff voting in their country and those who are not?

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Acknowledgements

This work was funded in part by the French government under management of Agence Nationale de la Recherche as part of the Investissements d avenir program, reference ANR-19P3IA-0001 (PRAIRIE 3IA Institute).

References [Bouveret et al., 2019] Sylvain Bouveret, Renaud Blanch, Antoinette Baujard, Franc ois Durand, Herrade Igersheim, J erˆome Lang, Annick Laruelle, Jean-Franc ois Laslier, Isabelle Lebon, and Vincent Merlin. Voter Autrement 2017 for the French Presidential Election. Technical Report, HAL halshs-02379941, November 2019. [Brams and Sanver, 2009] Steven J. Brams and M. Remzi Sanver. Voting systems that combine approval and preference. In The Mathematics of Preference, Choice and Order, Studies in Choice and Welfare, pages 215 237. Springer, 2009. [Delemazure et al., 2022] Th eo Delemazure, J erˆome Lang, Jean-Franc ois Laslier, and M. Remzi Sanver. Approval with runoff. Co RR, abs/2203.02343, 2022. [Godziszewski et al., 2021] Michał T. Godziszewski, Paweł Batko, Piotr Skowron, and Piotr Faliszewski. An analysis of approval-based committee rules for 2d-euclidean elections. Proceedings of the AAAI Conference on Artiﬁcial Intelligence, 35(6):5448 5455, May 2021. [Green-Armytage and Tideman, 2020] James Green Armytage and T. Nicolaus Tideman. Selecting the runoff pair. Public Choice, 182(1):119 137, 2020. [Lackner and Maly, 2021] Martin Lackner and Jan Maly. Approval-based shortlisting. In AAMAS, pages 737 745. ACM, 2021. [Lackner and Skowron, 2020] Martin Lackner and Piotr Skowron. Approval-based committee voting: Axioms, algorithms, and applications. Co RR, abs/2007.01795, 2020. [Lackner and Skowron, 2021] Martin Lackner and Piotr Skowron. Consistent approval-based multi-winner rules. J. Econ. Theory, 192:105173, 2021. [Laslier and Van der Straeten, 2016] Jean-Franc ois Laslier and Karine Van der Straeten. Strategic voting in multiwinners elections with approval balloting: a theory for large electorates. Social Choice and Welfare, 47(3):559 587, 2016. [Peters, 2021] Dominik Peters. Proportionality and strategyproofness in multiwinner elections. Co RR, abs/2104.08594, 2021. [Sanver, 2010] M. Remzi Sanver. Approval as an intrinsic part of preference. In Handbook on Approval Voting, pages 469 481. Springer, 04 2010. [Van der Straeten et al., 2018] Karine Van der Straeten, Romain Lachat, and Jean-Franc ois Laslier. Strategic voting in multi-winner elections with approval balloting: An application to the 2011 regional government election in Zurich. In Laura B. Stephenson, John H. Aldrich, and Andr e Blais,

editors, The Many Faces of Strategic Voting. Tactical Behavior in Electoral Systems Around the World, pages 178 202. The University of Michigan Press, 2018.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)