Voting by sequential elimination with few voters

1 Introduction

The communication burden on the agents in collective decision making is often an obstacle to implementing otherwise good voting rules, perhaps even more than computational complexity: while individuals agree to wait a few hours before knowing the outcome of a collective decision mechanism, they will probably not wish to spend a significant amount of time and energy reporting their preferences, especially in low-stake decision contexts, like choosing a collective item to buy, a place for a group dinner, or a film to watch together. In such contexts, the number of alternatives may be high, while the number of agents can be small: it is reasonable, for instance, to consider a group of four individuals choosing a restaurant out of a dozen. The type of problem we have in mind is the design of mechanisms that could be implemented on smartphone applications, and used by agents quickly and with a very low cognitive effort.

A number of works, which we review below, addressed the issue of designing low-communication protocols for computing the exact or approximate outcome of common voting rules. We follow a different path, by designing new rules that are specifically tailored for coming with low communication protocols. The family of rules we study in this paper concerns contexts where the number of candidates is larger (possibly much larger) than the number of voters, and works by having, at each step, a designated agent eliminating one of the remaining alternatives, until only one alternative remains. We believe that individuals would easily use such rules in

Yann Chevaleyre

LIPN - Univ. Paris-Nord, France yann.chevaleyre@lipn.univ-paris13.fr

J´erˆome Lang

CNRS, U. Paris-Dauphine, PSL, France lang@lamsade.dauphine.fr

low-stake contexts, where simplicity and rapidity of choice matters more than fairness and optimality; as a matter of fact, such rules have been observed in real-life settings by some of us. Although this paper focuses on this precise context, our rules belong to a much larger set, where the number of voters and alternatives can be arbitrary small or large. 1

Related work can be decomposed into three groups (for a good overview of communication issues in voting see Boutilier and Rosenschein [2015]):

Class 1: Defining low-communication protocols for computing voting rules. The communication complexity of voting rules was initiated by Conitzer and Sandholm [2005]: the goal is to identify, for a given rule, lower and upper bounds on the worst-case number of bits to be exchanged so that the outcome can be determined; the upper bound comes with concrete protocols. A different set of results, based on query complexity, identifies the worst-case minimal number of queries to determine the winner of some tournament solution, where a query consists in asking whether some edge exists in the majority graph [Balasubramanian et al., 1997; Procaccia, 2008; Dey, 2017]. Finally, Kalech et al. [2011] study an interactive protocol where at each round, each voter gives her k-th best alternative; the protocol ends when there is enough information to determine the true winner.

Class 2: Defining low-communication protocols for approximating a voting rule. Service and Adams [2012] study the communication complexity of determining approximate winners for rules based on scores (where approximation is relative to the ratio between the score of the outcome and the score of the true winner). Queries in their protocols generally consist in asking voters whether the rank of a candidate lies in a given interval or not. Another series of work that can be located in Class 2 are top-k approximations of voting rules: voters report only their top k alternatives, and a winner is computed from this partial information [Dery et al., 2014; Filmus and Oren, 2014; Lu and Boutilier, 2011].

Class 3: Designing new rules based on low-communication protocols. 2 Goel and Lee [2012] define a randomized urnbased voting rule where at each stage, a triple of voters (i1, i2, i3) is selected randomly; each of them gives her preferred alternative xij , and votes between the other two. If there is a three-way tie, the three voters disappear from the election, otherwise the losing voters are replaced with "copies" of the winning voter. The process is iterated until there remains only one voter (which is guaranteed to eventually occur for a reason we will not explain here). The rule has a low average communication complexity and, when applied to a Euclidean single-peaked profile, achieves a good approximation of the Condorcet winner with high probability. With the random pairs rule [Hansen, 2016], each voter is presented a small number of randomly chosen pairs of alternatives and chooses between them; the alternative winning most pairwise contests is declared the winner. Although the rule can violate Pareto-efficiency and even unanimity, such paradoxes are rare in practice; and the required communication is low. Gross et al. (2017) define a low-communication randomized rule: voters are selected randomly and asked to report their preferred alternative; as soon as there is an alternative named by two voters, it is declared the winner. The worst-case communication complexity O(mlogm) is the same as for our rules, and the principle definitely has some similarity with ours. However, their mechanism is based only on top-ranked alternatives, while ours uses information "inside" the voters' rankings; related to that, their mechanism is not applicable to settings with few voters, because of the risk that no alternative is top-ranked more than once.

1 For instance, in a context with less alternatives than voters, the designated agent can veto an alternative, and an aternative is eliminated once it obtains a given number of vetos; or else, the designated agent can support an alternative, and the winner is declared once an alternative obtains enough support. Although we have these extensions in mind, we won't discuss them again in the paper.

The paper is organized as follows. In Section 2 we define two families of sequential elimination rules. In the first one, the rules are resolute but non-anonymous, as the elimination sequence is fixed. In the second one, the rules are randomized and anonymous: an elimination pattern is fixed, with virtual voters being placeholders, and actual voters are assigned to placeholders with a uniformprobability. In Section 3 we conduct an axiomatic study of our rules: they are shown to satisfy Pareto-efficiency, monotonicity, and a weakening of independence of losing alternatives. While the set of satisfied properties may seem light, we emphasize that their communication complexity is extremely low. In Section 4 we compare different elimination sequences according to the expected Borda score of the outcome, where profiles follow the impartial culture distribution. While we do not have a closed-form formula for identifying the best sequence in the general case, we are able to do it for a family of sequences that are especially interesting and convenient: non-interleaved sequences, in which the occurrences of each agent in the sequence are contiguous. In Section 5 we study the performance of elimination-based rules on randomly generated data. In Section 6 we suggest further research directions.

2 Elimination-based Voting Rules

Let N = {1, . . . , n} be a set of voters and C = {c1, . . . , cm} a set of candidates. A n-voter preference profile over C is a collection of votes V = (V1, . . . , Vn) where each Vi is a linear order over C. L(C) is the set of all linears orders over C. ∆(C) is the set of all probability distributions over C. For c ∈ C, r(c, Vi) denotes the rank of c in Vi (from 1 for the best candidate to m for the worst one). The Borda score of c for V is SB(c, V ) = ∑ni=1 m- r(c, Vi). Also, we define the contribution of voter Vi to the Borda score of c as SB(c, Vi) = m- r(c, Vi). A resolute voting rule is a function from L(C)n to C. A randomized voting rule is a function from L(C)n to ∆(C). The Borda rule is the resolute rule that outputs the candidate maximizing SB(., V ) (using a predefined priority relation over C in case of a tie).

2 In some sense, class 2 can be interpreted as a subset of class 3, if we see the approximations of voting rules as voting rules per se.

An elimination sequence for n voters and m candidates is a sequence π = (π(1), . . . , π(m- 1)) in N m-1 . Given π, the deterministic sequential elimination rule (SER) Fπ is defined recursively as follows: for each profile V ,

1. C(0) = C;
2. For each i = 1, . . . ,m-1, C(i) = C(i-1)\{last(C(i1), Vπ(i))}, where last(C(i - 1), Vπ(i)) is the least preferred candidate in C(i - 1) according to Vπ(i).
3. Output the single element in C(m).

Example 1 Let n = 3, m = 5, V = (abcde, edcba, debca) and π = (1, 2, 3, 1). Then C(1) = {a, b, c, d} since 1 eliminates e, C(2) = {b, c, d} since 2 eliminates a, C(3) = {b, d} since 3 eliminates c, and finally, C(4) = {b} and Fπ(V ) = b.

Given an elimination sequence π and a permutation σ on N, the randomized SER ˆ Fπ induced by the pattern π outputs each candidate c with probability 1 n! |{σ | Fσ◦π(V ) = c}|. Intuitively, the indices in π are not actual voters but placeholders; the randomly chosen permutation σ then assigns actual voters to placeholders.

Example 1 (continued) Let us apply the randomized pattern π = (1, 2, 3, 1) to P . Here are the six possible permutations together with the associated winner: 123 ↦→ 123 : b; 123 ↦→ 132 : c; 123 ↦→ 213 : d; 123 ↦→ 231 : d; 123 ↦→ 312 : d; 123 ↦→ 321 : d. Henceforth, ˆ Fπ(P) = 〈b : 16 , c : 16 , d : 23 〉.

It is worth noticing that if π = (1, . . . , 1) then ˆ Fπ coincides with random dictatorship.

There are two ways of viewing ˆ Fπ, yielding two ways of computing the winner. In the offline view, voters report their preferences without knowing which permutation σ will be chosen; in the online view, the permutation σ is randomly chosen first, and voters then proceed to the elimination protocol as in the resolute case. Not only the offline computation of ˆ Fπ requires a complete elicitation of the preferences, but it is also hard, as the following result shows.

Proposition 1 Suppose m > n, and let π = (1, 2, . . . , n, n, n . . .). Checking if a candidate w has a non-zero probability of winning with ˆ Fπ is NP-complete.

Proof sketch. Hardness is proven by the following reduction from 3SAT. Let x1, . . . , xp be the propositional variables, and let c1, . . . , cq the clauses, with ci = li,1 ∨ li,2 ∨ li,3, where each li,j ∈ {x1 . . . xp, ¯x1 . . . ¯xp} is a literal. The reduction is as follows. We build m = 3p + 3q + 3 candidates:

{xi, ¯xi, zi | 1 ≤ i ≤ p}∪{yi, ¯ yi, ci | 1 ≤ i ≤ q}∪{a, b,w}. We build a profile with n = 2p + 3q + 1 voters. Because we are only concerned about the winning probability of w, in each vote Vi, the order of the candidates ranked above w does not matter, so we specify only the order of candidates below w. For each vote Vi, let below(Vi,w) be the projection of Vi on candidates ranked below w in Vi. For example, below (ebdwfa, w) = fa. The profile V is built as follows:

• For each variable xj, we have two voters Vxj and V¯xj such that below(Vxj , w) = xjzj and below(V¯xj , w) = ¯xjzj .
• For each clause ci = li,1 ∨ li,2 ∨ li,3, we have three voters Vi,1, Vi,2, Vi,3 such that below(Vi,j,w) = cili,jy′i yi for j ∈ {1, 2, 3}.
• We have a last voter Vlast such that below(Vlast,w) = x1¯x1 . . . xp¯xpba.

The picking sequence is π = (1, 2, . . . n, n, . . . n). w has a non-zero winning probability if and only if there exists a permutation σ applied to π such that during the m- 1 first picking steps, all candidates except w are removed. We can verify that the set of clauses is satisfiable if and only if w has a non-zero winning probability. □

This hardness result has little practical impact: the winner can still be computed efficiently by using the online protocol.

We say that i appears in π if there is a k such that π(k) = i. Let nv(π) be the number of voters who appear in π. An elimination sequence π is non-interleaved if and only if for each i ∈ N, either i does not appear in π or there are two indices start(i) and end(i) such that for all 0 ≤ k ≤ m1, π(k) = i if and only if start(i) ≤ k ≤ end(i). Given a non-interleaved sequence π, let ρ be the function yielding the j-th voter participating in the sequence. The signature of an non-interleaved sequence is the vector ˜π = (end(ρ(i)) - start(ρ(i)) + 1) | i = 1, . . . , nv(π)). Elimination sequences where voters appear in increasing order are monotonic. For instance, with m = 7 and n = 4, π = (1, 1, 1, 1, 2, 3) is monotonic and yields the signature ˜π = (4, 1, 1). Without loss of generality, a non-interleaved pattern sequence for a randomized SER can be assumed to be monotonic. Random dictatorship corresponds to the pattern sequence (1, . . . , 1) with signature ˜π = (m - 1).

Observation 1 The deterministic communication complexity of any resolute elimination rule is in O(mlog(m)).

Indeed, at each step i, voter π(i) just has to indicate the candidate she wants to eliminate, which gives (m - 1)⌈log(m)⌉ as an immediate upper bound. The exact upper bound is in fact less than that: ∑mj=2 ⌈log(j)⌉, because the voter m - j + 1 has to indicate a candidate among the j remaining candidates. This bound is for the set of all sequences; for specific sequences the communication complexity may be lower, especially for non-interleaved sequences. For instance, for the non-interleaved sequence with the signature (4, 2), the first voter needs to communicate ⌈log (74)⌉ = 6 bits, and the second voter ⌈log (32)⌉ = 2 bits: 8 bits in total, whereas ∑mj=2 ⌈log(j)⌉ = 14. The minimum is of course obtained for dictatorship.

We now prove that for some sequences, the lower bound matches the upper bound. Consider the family of sequences πsimple = (1, . . . , m - 1) with n = m - 1:

Proposition 2 The communication complexity of Fπsimple is in Ω(m log m).

Proof. Let S(C) be the set of permutations of C. Consider the set of profiles F = {V σ | σ ∈ S(C)}, where V σ = (V σ 1 , . . . , V σ n ), and V σ i is a vote that ranks xσ(i) in the last position and xm in the second last position (the rest of the vote does not matter). We claim that F is a fooling set for Fπ, that is, for each V, V ′ ∈ F, (a) F(V ) = F(V ′ ), and (b) there is a mixture (VI, V ′-I ) of V and V ′ (coinciding with V on I and with V ′ on N \ I) such that Fπ(VI , V ′-I ) ̸= F(V ). We first verify that for every σ ∈ S(C) we have Fπ(V σ ) = xm: indeed, at each step i = 1, . . . ,m- 1, voter i eliminates her least alternative xσ(i), and the remaining one is xm. Now, we claim that if V σ and V τ are two distinct profiles in F, then there is a mixture V ′ of V σ and V τ such that Fπ(V ′ ) ̸= xm. Indeed, if σ ̸= τ then there exist i, j such that i ̸= j and σ(i) = τ(j). Let V ′ = (V σ 1 , . . . , V σ j-1 , V τ j , V σ j+1 , . . . , V σ n ). Because V ′ i and V ′ j are equal and rank xi last and xm second last, the first one whose turn comes will eliminate xi, and the second one will eliminate xm; thus, Fπ(V ′ ) ̸= xm. Therefore, F is a fooling set for Fπ, and since its cardinality is (m - 1)!, the communication complexity of Fπ is in Ω(log(m-1)!), i.e, in Ω(mlogm). □

For randomized SERs with the online view, the communication complexity is exactly the same, if we do not count the communication bits sent by the random number generator to communicate to each agent her role in the sequence - otherwise we have to add O(n log(n)) bits.

3 Axiomatic Properties

We now show that sequential elimination rules enjoy some of the most desirable properties of voting rules.

Clearly, any SER (whether resolute or randomized) is neutral: it treats all candidates symmetrically. No resolute SER is anonymous: it does not treat voters symmetrically; however, any randomized SER is ex-ante anonymous: voters are symmetrical before their assignment to placeholders.

Now, consider Pareto-efficiency: a resolute rule is Paretoefficient if it always elects a Pareto-optimal candidate, where x is Pareto-optimal if no y ̸= x is preferred to x by all voters. A randomized rule ˆ F is ex-post Pareto-efficient if for any V , the support of ˆ F (V ) contains only Pareto-optimal candidates.

Observation 2 A candidate x is Pareto-optimal in profile V if and only if there exists a sequence π such that Fπ(V ) = x.

Proof. Left to right: the sequence π is constructed by choosing at each step a voter who does not rank x last among the remaining candidates. If it was not possible at some step other than the final step, then x would be ranked last in all votes, and thus would be Pareto-dominated. Right to left: if x is Pareto-dominated by y, then whatever π, y will never be eliminated before x, therefore Fπ(V ) ̸= x. □

This observation leads to the following Proposition.

Proposition 3 For any π, Fπ is Pareto-efficient and ˆ Fπ is expost Pareto efficient.

All rules Fπ and ˆ Fπ satisfy unanimity: if there is a unanimously preferred candidate, then she is elected (with probability 1 for randomized rules). We now consider monotonicity. An x-improvement of a profile V is a profile V ′ identical to V except for one vote V ′ i , for which x moves one position upward, everything else being unchanged. A resolute rule F is monotonic if for any V with F(V ) = x, and any ximprovement V ′ of V , F(V ′ ) = x. A randomized rule ˆ F is monotonic if with the same assumptions as above, the probability that x wins cannot decrease when changing V into V ′ .

Proof. For the resolute case, this is because if some candidate y is eliminated for V , then for V ′ it must be eliminated either at the same stage as in V or before. The application of this result to all permutations σ yields the result for ˆ Fπ. □

We also mention an interesting property, which is a relaxation of Kelly's independence of losing alternatives [Kelly, 1978]. Let up(x, Vi) = {y | y ≻Vi x} and down(x, Vi) = {y | x ≻Vi y}. Given two votes Vi and V ′ i , we write Vi ∼x V ′ i if up(V ′ i , x) = up(V ′ i , x) and for each y, z ∈ down(Vi, x) we have y ≻Vi z if and only if y ≻V ′ i z. Then, all rules Fπ satisfy independence of reshuffling above the winner: for all profiles V , V ′ such that Vi ∼Fπ(V ) V ′ i for every i = 1, . . . , n, we have Fπ(V ′ ) = Fπ(V ). What makes this property interesting is that it is rather strong, as very few common rules satisfy it (one of the few exceptions being Antiplurality - a.k.a Veto).

For lack of space, we only briefly discuss properties that are not satisfied, or satisfied only in specific cases. We summarize all results without proof: (1) if n ≥ 3 and m ≥ 2, then no SER is Condorcet-consistent; (2) a resolute (resp. randomized) SER is strategyproof if and only if it is a dictatorship (resp. random dictatorship); (3) A family of randomized SERs, defined for any number of voters and candidates, satisfies SD-participation [Brandl et al., 2015] if and only if it is a random dictatorship for any number of voters and candidates.

4 Borda-optimal Non-interleaved Elimination Sequences

Communication complexity is obviously not the only criterion we may use to choose an elimination sequence (as it would lead us to choose random dictatorship). A way of evaluating the quality of an elimination sequence can be its proximity to a known voting rule, and here we choose the Borda rule. Although this is not the only possible choice, still, it is an natural point to start with, since the Borda score has a clear social welfare interpretation that goes beyond seeing Borda as a voting rule (see e.g. d'Aspremont and Gevers [2002]).

For the sake of simplicity, in this section we restrict to noninterleaved elimination sequences. Such a restriction is often natural and desirable: for example, in an online voting setting, voters might want to connect only once to the voting website.

A sequence π will be evaluated by the expected Borda score of the winner Fπ(V ), where profile V is drawn from a uniform random distribution. We write IC(n,m) the uniform distribution (often called Impartial Culture, or IC) over profiles of n voters and m candidates. First, we estimate the value of EV∼IC(n,m) [SB (Fπ(V ), V )] for a given π. Then, we search for the sequence yielding the best Borda approximation, i.e. maximizing this expected Borda score.

Because we work with IC, all non-interleaved elimination sequences sharing the same signature ˜π yield the same expected Borda score. Therefore, without loss of generality, we restrict our study to monotonic elimination sequences. The following proposition gives us a closed formula to compute the expected Borda score, given a non-interleaved elimination sequence.

Proposition 5 Assume the profile V is drawn from IC(n,m). Let π be a monotonic non-interleaved elimination sequence. Let li = m + 1 - ∑ij=1 ˜π(j) for i = 1, . . . n and l0 = m+ 1. Then, the expected contribution of voter Vi to the Borda score of the winner, as well as the total expected Borda score of the winner are:

Proof. We focus on voter i. If c wins, the contribution of i to its total Borda score is SB(c, Vi). Let ki be the number of candidates remaining before i's turn: ki = m- ∑i-1 j=1 ˜π(j). Let X(1) . . .X(ki) be the Borda scores with respect to i of each of these ki remaining candidates, sorted by increasing scores (so m - X(ki) is the rank of i's preferred candidate among all candidates still available). Because Vi is drawn from IC, the set {X(1), . . . ,X(ki)} is uniformly distributed among all ki-subsets over {0, . . . ,m - 1}. Clearly, i will remove the ˜π(i) candidates yielding the lowest Borda scores SB(., Vi). These Borda scores are X(1) . . .X(˜π(i)). Also, the final winner will be uniformly distributed among the remaining candidates (because of IC). So the expected Borda score of the final winner will be Ej∼{˜π(ki)+1,...,ki} [X(j) ].

It is a standard result from order statistics that when drawing a uniform subset of k elements from {1, . . . , m}, and then ordering them increasingly, the expected value of the ith element is i m+1 k+1 (see e.g. Arnold et al. [1992, page 56]). Since our Borda scores are drawn from {0, . . . ,m-1}, we get E [X(i) ] = i m+1 ki+1 - 1. For j ≤ ki, 1 + Ei∼{j,...,ki} [X(i) ] = E [ 1 ki-j+1 ∑ki=j X(i) ] = (j+ki)(ki-j+1)(m+1) 2(ki-j+1)(ki+1) . Finally, 1 + Ej∼{˜π(ki)+1,...,ki} [X(j) ] = (˜π(ki)+1+ki)(ki-˜π(ki))(m+1) 2(k-˜π(ki))(ki+1) = (˜π(ki)+1+ki)(m+1) 2(ki+1) . Replacing ki + 1 by li-1, we get Ej∼{˜π(ki)+1,...,ki} [X(j) ] = (2li-1-li)(m+1) 2li-1 - 1 = m- li li-1 ( m+1 2 ). The result follows. □

Now, we look for an optimal sequence, i.e. maximizing the expected total Borda score. We need to minimize:

with the constraints that l is a non-increasing sequence of integers, l0 = m+ 1 and ln = 2.

4.1 Exact Solution with Real Numbers

To forge the intuition, let us relax the assumptions by allowing the (li) to be real numbers. For 0 < i < n, a partial derivation of E with respect to li leads to li-1 li = li li+1 , hence l must be geometric. We deduce:

.

When the above solution consists of integers, it can be implemented. For example, consider n = 3 and m = 15. Then l = (16, 8, 4, 2). Remarking that the signature ˜π is computed as the differences between consecutive terms in l, we have ˜π = (8, 4, 2). More generally, if there exists some integer k such that m = 2kn - 1, then ˜π(i) = 2(k - 1)kn-i .

If the Borda score is viewed as a measure of social welfare, then among the non-interleaved SERs, the solution above is optimal not only for utilitarian, but also for egalitarian social welfare (ex-ante), since all voters have the same expected utility.

4.2 Properties of the Optimal Sequence

Let us bring back the constraint that (li) are integers (still with monotonic non-interleaved elimination sequences).

Proposition 6 If m-1 ≤ n, then the only optimal sequence has signature ˜π = (1, . . . , 1). If m- 1 ≥ n, then for any optimal sequence, nv(π) = n, i.e. all voters participate.

Proof. Let π be a sequence. Assume that a voter eliminates more than one candidate and that another voter eliminates none. We will then prove that π is not optimal. This immediately implies the two assertions of the proposition.

Let i be the last voter such that ˜π(i) > 1 and k = nv(π)+1 the first non-participating voter. For j = i + 1, . . . , k - 1, we have ˜π(j) = 1. It is easy to check that li = k - i + 1.

Consider the sequence π′ whose signature is identical to ˜π, except that ˜π′ (i) = ˜π(i) - 1 and ˜π′ (k) = 1. Denoting E′ the counterpart of E for sequence π′ , we have: E′ -E = 1 k-i+1+˜π(i) +∑k-i+1 j=3 1 j(j+1) - 13 = 1 k-i+1+˜π(i) - 1 k-i+2 < 0 Hence π′ is strictly better than π. □

In the following, we often use the fact that if m- 1 ≥ n, then all voters participate, hence l is strictly decreasing.

Proposition 7 In an optimal sequence, we have

Proof. For m- 1 ≤ n, this follows from Proposition 6. Assume m- 1 > n. Intuitively, we examine a "discrete partial derivative" of E with respect to li. Let ϵ ∈ {-1,+1} and π′ a sequence whose signature is identical to ˜π, except that ˜π′ (i) = ˜π(i)+ϵ and ˜π′ (i+1) = ˜π(i+1)-ϵ. Comparing E andE′ , by optimality of π, we have li li-1 + li+1 li ≤ li-ϵ li-1 + li+1 li-ϵ . Some basic algebra leads to ϵli+1 ≥ li(ϵli-1) li-1 . Since it is true for ϵ ∈ {-1,+1}, the result follows.

Note that the difference between the lower and upper bounds in Equation (1) is 2li li-1 < 2, hence there are at most two integers in that interval. We will use this fact for our algorithm.

Proposition 8 The signature ˜π of any optimal sequence is non-increasing.

Proof. Since Proposition 6 proves this assertion for m- 1 ≤ n, we assume m- 1 > n. Let i ∈ {1, . . . , n - 1}. Some rewriting of (1) leads to:

Finally, we state (omitting its proof due to lack of space) this last property of optimal non-interleaved sequences.

Proposition 9 The signature ˜π of any optimal sequence is approximately convex, in the sense that:

For example, for n = 4 and m = 7, the optimal sequence is ˜π = (2, 2, 1, 1) (as shown by our algorithm, see below). It is not convex, because ˜π(2) = 2 is strictly greater than the average of its two adjacent terms ˜π(1) = 2 and ˜π(3) = 1. But it is approximately convex. This example shows that in the above inequality, the "error constant" 12 is tight.

4.3 Computing Borda-optimal Sequences for IC

We present the sketch of an algorithm in O(nm) that computes the signature ˜π of an optimal non-interleaved sequence under IC. We will build two tables predecessor and penalty, whose rows are indexed from 0 to n and columns from 2 to m, with the following interpretations. predecessor(i -1, j) = k means that in an optimal sequence, if li = j, then li-1 = k. penalty(i - 1, j) = p means that in an optimal sequence, if li = j, then l1 l0 +. . .+ li li-1 = p. For any j, predecessor(0, j) is initialized tom+1 and penalty(0, j) is initialized to j m+1 . Then, for each i from 1 to n - 1, we establish partial optimal sequences until li+1. To that end, each possible li yields two possible values of li+1 thanks to Proposition 7. Since several values of li can lead to the same value of li+1, only the one with lowest penalty is kept as a valid predecessor of li+1, along with the corresponding penalty. At the end of the algorithm, tables predecessor and penalty are built. We have then ln = 2 and for any i ∈ {1, . . . , n}, li-1 = predecessor(i - 1, li). Finally, ˜π = (l0 - l1, . . . , ln - ln-1).

To conclude this section, we comment on two other ideas of algorithms: 1) explore only the rounded values of the real solution for sequence l (Section 4.1); or 2) use an integer adaptation of a gradient descent algorithm, until all conditions from Equation (1) are met (i.e. until a local optimum is reached, where incrementing or decrementing any li is not profitable). However, consider n = 3 and m = 40. The real optimum is (41.00, 14.98, 5.47, 2.00). But (as our algorithm shows) the integer optimum is (41, 16, 6, 2), which does not consist in rounded values of the real solution: this excludes idea 1. Besides, another sequence, (41, 14, 5, 2), also meets all conditions from Equation (1): it is a local optimum, but not the global one, leaving little hope for idea 2.

5 Experimental Study

Now we show to which extent sequential elimination rules provide a good Borda score approximation in practice. To this end we have carried out two sets of experiments. In both sets we have considered random instances drawn from five particular cultures: Impartial Culture (IC), Mallows with a dispersion parameter ϕ = 0.1 (M0.1), Mallows with ϕ = 0.5 (M0.5), Single-Peaked Impartial Culture (SPIC), and SinglePeaked with Uniform Peak (SPUP) [Conitzer, 2007].

In the first experiment, the number of voters n varies from 2 to 10 and the number of candidates is 2n+1 - 1. Recall that under IC, optimal non-interleaved sequences in this setting are geometric sequences (Section 4.1). For each (n,m) and each culture, we focused on three different sequences: (i) geometric (e.g. ˜π = (8, 4, 2)), (ii) round-robin (e.g. π = (1, 2, 3, 1, 2, 3, ...)) and (iii) random (single) dictator (e.g. π = (1, 1, 1, ...)). We have computed for each one the mean value of the differential ratio SB(Fπ(V ),V )-min(SB(.,V )) max(SB(.,V ))-min(SB(.,V )) over a sample of 10000 profiles generated for each (n, m) and culture. The results are shown in Figure 1 (the result for M0.1 is not shown but gives an even better approximation ratio than M0.5 for all three sequences).

In the second experiment, the number of voters n varies from 2 to 6 and the number of candidates m from n+1 to 2n. For each (n,m) and each culture, we used an exhaustive search algorithm over the space of all sequences to find the sequence yielding the best expected Borda score (estimated from a sample of 10000 profiles). For all settings, these best sequences, their differential ratios and the standard-deviation of this ratio (both in percentage) are shown in Table 1.

What is remarkable is that the estimated expected value for the differential ratio is almost always over 90% for roundrobin, geometric sequences and the optimal sequence and for all the cultures (IC being the worst), and is even close to 100% for more correlated profiles like the Mallows ones. Thus, although the optimal sequence is interleaved, the best noninterleaved sequence (geometric) performs almost as well. Even if it differs from the optimal sequence, round-robin even gives a better approximation of it than the best noninterleaved sequence. Unsurprisingly, random dictatorship performs quite badly in comparison.

Finally, we tested our approach on the real Sushi dataset from PrefLib [Mattei and Walsh, 2013]. To obtain instances with more candidates than voters, we sampled 10000 profiles of 5 voters from the whole set (in this dataset, m = 10) and as before computed the best sequence according to the average differential ratio. The sequence obtained is (1, 1, 1, 2, 2, 2, 3, 4, 5), and gives a differential ratio of 93.035%, showing that the method may perform well on realistic datasets as well.

6 Conclusion

Sequential elimination rules have a low communication complexity, while enjoying several important properties. We have defined a framework for identifying optimal sequences for a quality measure, the Borda score; a further research direction consists in identifying optimal sequences for other measures. This work is a first study, in a setting with few voters; we plan to investigate similar low-communication rules, consisting of a sequence of steps where a designated voter vetoes or supports an alternative, applicable in different settings. Moreover, a similar family of protocols in fair division, picking sequences, have also been studied under the social welfare point of view [Bouveret and Lang, 2011; Kalinowski et al., 2013; Aziz et al., 2016]. Now, picking sequences can be viewed to some extent as elimination protocols, as each agent, when picking an item, eliminates a set of possible assignments; it is worth exploring this connection further. Finally, as we have seen, this family of voting rules is of course not strategyproof. In this paper, we have left strategical issues aside, but it would be a crucial topic for future research.

Acknowledgements

This research has been supported by the project ANR-14CE24-0007-01 CoCoRICo-CoDec.