Approval with Runoff

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 world 1 . 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 specific kind, called "useful" voting 2 ). 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 first 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 finalists 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 these reasons, the existence of two rounds of vote separate in time is considered to be crucial for the voters' information.

1 See https://en.wikipedia.org/wiki/Two-round system.

2 As 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.

Are the informational benefits 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 benefit of the two-round protocol without having to bear all the drawbacks of Plurality at the first round?

Clearly, if the answer to this question is positive, the format of the ballots at first 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 define an approval-with-runoff election as a two-round protocol:

1. First round: voters cast approval ballots, fromwhich the two finalists are selected.
2. Second round: voters cast votes for one of the two finalists, and the majority winner wins the overall election. 3

Formally, we define 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 finalists?

For question 1, the answer becomes clear once we remark that we need the approval data for computing the finalists, and the pairwise comparisons between candidates for computing the final 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, 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) profile [Brams and Sanver, 2009].

3 The 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]).

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 fixed 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 profile 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 first 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 finalists?

Our primary aim is to define 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 define 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 profiles (Section 5), and move on to applying the rules on real data (Section 6). We conclude in Section 7.

2 RelatedWork

Approval with Runoff (in its most straightforward version, see Section 3.2) was first introduced in [Sanver, 2010] and compared to other rules based on approval-preference profiles. Green-Armytage and Tideman [2020] consider plurality with runoff together with eight other runoff rules for selecting the finalists, 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.

Defining voting rules that take as input approval-preference profiles 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 profile is a collection of approval ballots V = 〈A1, . . . ,An〉 with Ai ⊆ C for all i. An ordinal preference profile is a collection of rankings ≻= 〈≻1, . . . ,≻n〉, where ≻i is the preference ranking of voter i over C. An approval-preference profile is a collection of pairs P = 〈(A1,≻1), . . . (An,≻n)〉 where VP = 〈A1, . . . , An〉 is an approval profile and ≻= 〈≻1, . . . , ≻n〉 an ordinal preference profile. 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 profile ≻, maj(≻, {a, b}) is defined 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 define the family of approval-based runoff (AVR) rules. The idea is that we use the approval ballots in the first round to select two finalists, 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 profile and returns a nonempty set of pairs of candidates. Then, F R is the (irresolute) AVR

4 Ballot 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.

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

For an approval profile 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 define some ABC rules. Because we need them only for k = 2, we only define them for this case. (See for instance [Lackner and Skowron, 2020] for a general presentation.)

Multi-Winner Approval Voting (MAV):

Some rules discount the satisfaction of voters who are already satisfied by one of the two finalists. This is the case of these two rules:

Proportional Approval Voting (PAV):

Approval Chamberlin Courant (CCAV):

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 first finalist 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) - 12 SV (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 first finalist is an approval winner x1, and the second finalist maximizes the value SV (x2)-αSV (x1x2) for some α ∈ [0, 1]. We call these rules α-seqAV rules. A rule that almost falls into this family is:

Enestr¨om Phragmen (EnePhr) : 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 first finalist. 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

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 finalists are {a, b}; with PAV and S-PAV, {a, c}; with CCAV and S-CCAV, {a, d}. For EnePhr, the finalists are {a, c} for both Droop and Hare Quota, as every α-AV and α-seqAV rule with α ∈ [1/3, 3/4]. {a, c} are also the finalists for S-Phr.

We also need the rule that returns all pairs of candidates:

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:

Definition 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 finalist. Among the voting rules considered here, it is clear that only sequential rules satisfy this property (MAV, S-PAV, S-CCAV, EnePhr 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 profile 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.

Definition 2. An AVR rule F R is Pareto-efficient if for all approval-preference profile P in which there exists a, b ∈ C such that a dominates b, we have b ̸∈ F R(P).

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

Definition 3. An AVR rule F R is weakly strategy-proof if for every profile 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-efficiency. Among the rules defined in Section 3.2, the only strategyproof rule is TRIVR.

Theorem 1. No AVR rule is weakly strategy-proof and Paretoefficient.

Proof. Assume F R is Pareto-efficient 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 Paretoefficiency, 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 ̂ P = (V, ̂≻) = (10 × acb|, ab|c, a|bc, c|ba) and ̂ P ∗ = (V ∗ , ̂≻) = (10 × acb|, ab|c, a|bc, cb|a) a deviation where the last voter now approves {b, c}. We have F R( ̂ P ) = maj(̂≻, {a, c}) = a. However, if we assume {b, c} ∈ F(V ∗ ), then c ∈ F R( ̂ P ∗ ) because maj(̂≻, {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-efficient, MAVR is Pareto-efficient but not weakly strategyproof.

We now focus on monotonicity. Given a profile P = (V, ≻) and a ∈ C, a profile 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

Definition 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 satisfies both monotonicity and Pareto-efficiency. 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 significantly the outcome of the election. Formally, let a ∈ C, and a profile 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

Definition 5. An AVR rule F R is clone-proof if for any profile 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 defined 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-efficient. More generally, clone-proofness and Pareto-efficiency are incompatible:

5 This 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 .

Position of the second finalist for different values of d

(a) Triangular distribution (Exact solution)

Position of the second finalist for different values of d

(b) Gaussian distribution (Empirical solution)

Figure 1: Position of the second finalist for α-seqAV 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 first finalist)

Theorem 2. No AVR rule is clone-proof and Pareto-efficient.

We now define a weaker version of clone-proofness, with a domain restriction that eliminates pathological profiles:

Definition 6. An AVR rule F R is weakly clone-proof if it is clone-proof on every profile 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 ̂ P = (̂ V , ̂≻) = (10 × ca|, a|c, a|c, c|a). We have F R( ̂ P) = {c}. If we clone a into another candidate a∗ , we can define the a-cloning extension ̂ P ∗ = (̂ V ∗ , ̂≻∗ ) = (10 × ca∗a|, aa∗ |c, aa∗ |c, c|aa∗ ). By weak clone-proofness, neither a nor a∗ is in F R( ̂ P ∗ ), so {a, a∗ } /∈ F(̂ V ∗ ). However, if π is the permutation that exchanges a∗ and b, we have π( ̂ V ∗ ) = V ∗ . By neutrality, F(π(̂ V ∗ )) = F(V ∗ ). There is a contradiction, because {a, b} ∈ F(V ∗ ) and {a, b} /∈ F (π( ̂ 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 with a constant pair of finalists 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.

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

Theorem4. Table 1 gives properties of the different AVR rules (a rule satisfies 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 finalists, 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 α-seqAV rules. Godziszewski et al [2021] studied the location of the winners of ABC rules with a 2D-euclidean model.

5.1 Triangular Distribution

We first 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 α-seqAV rules, for α ∈ [0, 1]: for all pairs of finalists, one finalist x1 is an approval winner and the other finalist x2 maximizes SV (x2)-αSV (x1x2). Recall that α = 0 leads to MAV and α = 1 to S-CCAV. The first finalist 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 finalist will get the maximum score for specific α and d is

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

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 finalists and observed their positions on the line. The first selected finalist is always the closest to the center. Figure 1b shows the distance between the two finalists for α-seqAV 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 Choice 7 (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 finalists obtained for each dataset and each rule. For some datasets, the choice of the rule has a strong impact on the finalists, which suggests that the choice of the ABC rule should be made with care.

7 Available on www.preflib.org

We can also look at the evolution of the finalists with α-AV and α-seqAV 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 finalists 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 finalists for α-AV rules for the 2017-Grenoble Dataset. We can see that the pairs of finalists change twice and involve 4 different candidates (Liberal, Left, Socialist and Conservative). As no candidate appears in all three pairs, the final winner will differ for at least two rules.

Figure 2b depicts the evolution of the α-seqAV score of candidates for second finalist spot in the 2017-Grenoble dataset. The approval winner is the Socialist candidate; the second finalist 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 finalists. 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?

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).