Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion

1 Introduction

Voting is a fundamental process for reaching consensus and plays a vital role in democracies, organizations and businesses. Even honeybees use a type of voting to decide among potential nest sites; each bee casts a numerical vote indicating the intensity of its preferences, and the site with the highest score wins [Seeley, 2010]. Quantifying preference intensity is not so easy for complicated problems that humans face; thus, the predominant approach is to elicit, from each voter, a preference ranking over candidates. This creates a need for a voting rule that determines the winner from these preferences. Numerous rules have been proposed over the years, with no consensus on a "best" rule.

A key contribution of computer science in this regard has been viewing the ranking of a voter as a proxy for the latent cost she 1 incurs if some candidate wins. Then, an optimal candidate can be defined as one minimizing the total cost, and vote aggregation can be interpreted as an optimization problem with missing information. Due to the missing information, a voting rule can be thought of as an approximation algorithm, whose worst-case performance is referred to as its distortion in this setting.

Without any structures on the costs, not much can be achieved in terms of distortion [Caragiannis et al., 2017]. An important contribution due to Anshelevich et al. [2015] (see also the journal version [Anshelevich et al., 2018] and recent surveys [Anshelevich et al., 2021b; Anshelevich et al., 2021a]) was to assume that the n voters and m candidates are jointly embedded in a metric space, and voters rank candidates by increasing distance. 2 This viewpoint is motivated by observing that each candidate exhibits a standpoint on various issues that voters care about, and each voter also has a standpoint on these issues that is presumably reflected on her ballot. One would then expect that voters rank candidates whose standpoints are "closer" to theirs higher. Note that voting rules do not have access to this space; the only available information is the rankings, which serve as an ordinal proxy for the (cardinal) distances. The worst-case approximation specifically for metric costs is called metric distortion. (Formal definitions of all concepts are given in Section 2.)

1 For ease of presentation, we use female pronouns for voters and male pronouns for candidates throughout.

2 This assumption generalizes the classic notion of single-peaked preferences [Black, 1948; Moulin, 1980].

The metric distortion framework has proved to be a fruitful analysis tool. In their initial work, Anshelevich et al. [2015] established a lower bound of 3 on the distortion of any deterministic voting rule, and showed that the Copeland rule nearly matches the lower bound by achieving distortion 5. Several subsequent papers worked towards closing this gap. Initially, the Ranked Pairs rule was conjectured to achieve distortion 3. This was disproved by Goel et al. [2017] who gave a lower bound of 5; Kempe [2020a] strengthened the lower bound to Ω(√m). The first improvement over the upper bound of 5 was due to Munagala and Wang [2019], who achieved distortion 2 + √5 ≈ 4.23 using a novel asymmetric variant of the Copeland rule. The distortion-3 conjecture was recently resolved in a breakthrough result by Gkatzelis et al. [2020], using a novel voting rule called PLURALITYMATCHING.

One of the main drawbacks of PLURALITYMATCHING is that it is unusually complex for a voting rule in the conventional sense. The winner is selected based on perfect matchings in certain bipartite graphs, which we will discuss shortly. Due to the complex nature of the voting rule, it is not even obvious that there always exists a winner in PLURALITYMATCHING; indeed, this existence proof was the main contribution of Gkatzelis et al. [2020] over the prior work of Munagala and Wang [2019] and Kempe [2020a]. The rule is also almost certainly too technical to be understood by the general public.

Our main contribution is an extremely simple voting rule, called PLURALITYVETO, which achieves the same optimal metric distortion of 3.

Under PLURALITYVETO, each candidate starts with a score equal to his plurality score, i.e., the number of firstplace votes he receives. These scores are then gradually decreased; when the score of a candidate reaches zero, he is eliminated. Voters are processed one by one in an arbitrary order: when it is the turn of a voter, she decrements the score of her bottom choice among uneliminated candidates. Since the initial scores add up to the number of voters, all of the candidates will be eliminated at the end. The last eliminated candidate wins. Notice that this rule does not even require access to the voters' full rankings. Aside from the top choices, it only requires from each voter her bottom choice among uneliminated candidates. Thus, when implemented via sequential queries to users, PLURALITYVETO also has low communication overhead. We summarize our main result as follows. (A formal presentation and proof are given in Section 3.)

Contribution 1. PLURALITYVETO has the optimal metric distortion of 3 and can be implemented to require each voter to communicate only O(logm) bits to the voting rule.

A candidate with a strict majority of first-place votes wins under PLURALITYVETO, regardless of the order in which voters are processed. Thus, one can think of the elimination process (or, as we call it, multi-round veto) as a runoff stage. This makes our rule conceptually simple as well; it is just plurality voting followed by multi-round veto. In this respect, it resembles instant runoff voting, which is used in national elections in several countries. As in instant runoff voting, PLURALITYVETO can be used by eliciting from each voter her full ranking, so that the runoff stage can be run instantly. Alternatively, it can be arranged as a two-stage election in which voters first cast a vote for their top choice, and in the following stage, each voter cancels the vote of another voter.

PLURALITYMATCHING and its analysis are based on domination graphs, a family of bipartite graphs G(c) (one per candidate c) between voters and voters defined in Section 2. Munagala and Wang [2019] and Kempe [2020a] had shown that if G(c) has a perfect matching, then c has distortion at most 3. The key contribution of Gkatzelis et al. [2020] was to show that such a candidate c always exists. In fact, they proved a generalization, called the RankingMatching Lemma, which shows the existence of a graph with a weighted perfect bipartite matching in a more general class of bipartite graphs. We also give (in Section 4) a constructive one-paragraph proof of this more general Ranking-Matching Lemma, using a variant FRACTIONALVETO of PLURALITYVETO which decreases weights fractionally, rather than integrally, in each step.

Finally, we generalize PLURALITYVETO to a class of randomized voting rules that choose a candidate with probability proportional to his residual score at the kth round of PLURALITYVETO, which we refer to as k-ROUNDPLURALITYVETO. When k = 0, this more general rule specializes to the wellknown rule RANDOMDICTATORSHIP, which chooses the top choice of a uniformly random voter. Hence, randomizing the outcome proportional to the scores achieves distortion 3-2/n when k = 0, as shown in [Anshelevich and Postl, 2016]. In Section 5, we show that k-ROUNDPLURALITYVETO in fact achieves distortion at most 3 for all k. In that way, it interpolates between RANDOMDICTATORSHIP (for k = 0) and PLURALITYVETO (for k = n- 1), and the parameter k controls the variance of the output, but does not affect the distortion. The intuition behind this is that PLURALITYVETO repeatedly decreases scores for "extreme" candidates, and thus is likely to end up with central ones. We elaborate on this intuition in the context of Peer Selection in Section 6.

Contribution 2. k-ROUNDPLURALITYVETO has expected metric distortion at most 3 for any number of rounds k.

This upper bound is almost tight, since any rule that can only elect candidates who are the top choice of at least one voter must have distortion at least 3 - o(1) [Gkatzelis et al., 2020]. Also, since k controls the variance of the output, at a high level, this result relates to the work of Fain et al. [2019] who are not only interested in the expected distortion of rules, but also in the expected squared distortion, essentially forcing randomized rules to have lower variance in their distortion.

Other Related Work. The utilitarian analysis of voting rules through the lens of approximation algorithms was first suggested in [Boutilier et al., 2015; Caragiannis and Procaccia, 2011; Procaccia, 2010; Procaccia and Rosenschein, 2006]. Boutilier and Rosenschein; Anshelevich et al. [2016; 2015] were the first to clearly articulate the tension between the objective of maximizing utility (or minimizing cost) and the available information, which is only ordinal; they also termed the resulting gap distortion. In the earlier work, such as [Boutilier et al., 2015; Caragiannis and Procaccia, 2011; Procaccia, 2010; Procaccia and Rosenschein, 2006], the focus was on (positive) utilities, and no additional assumptions (such as metric costs) were placed on the utilities.

Recall that PLURALITYVETO only requires very limited communication from each voter, albeit in an n-round sequential algorithm. In this way, our work relates generally to studies of the tradeoff between communication and metric distortion. The recent papers [Fain et al., 2019; Kempe, 2020b] establish related lower bounds: Fain et al. [2019] show that any voting rule that only obtains the top k = O(1) candidates of each voter must have squared distortion Ω(m), in particular implying a bound of Ω(m) for the distortion of deterministic rules. Kempe [2020b] proves a lower bound of Ω(m/k) on the distortion of any deterministic voting rule that only obtains the candidates ranked by each voter in a set K of size k = |K| of positions. Our voting rule avoids these lower bounds by obtaining the bottom candidate from a specified set for each voter; thus, for different voters, the candidates in different positions are queried.

Using randomization, communication can be drastically reduced even compared to our voting rule. Fain et al. [2019] present a RANDOMREFEREE mechanism: the mechanism asks two randomly chosen voters for their top choices, and then has a third voter choose between the two proposed candidates. This mechanism, which only requires access to the top choices of two voters plus one bit, achieves not only constant expected distortion, but constant expected squared distortion.

2 Preliminaries

Throughout, we use bold face for vectors, and denote the ith component of a vector x by xi. Given a set S, let ∆(S) denote the probability simplex over S, i.e., the set of non-negative weight vectors over S that add up to 1.

An election is a tuple E = (V,C,≻V ) consisting of a set of n voters V , a set of m candidates C and a ranked-choice profile ≻V = (≻v)v∈V ; here, ≻v is the ranking of voter v, i.e., a total order over C. We say that voter v ranks candidate c higher than candidate c′ if c ≻v c′ . We also use c ≽v c′ when c ≻v c′ or c = c′ , in which case we say that v ranks c weakly higher than c′ .

A voting rule f is an algorithm that returns a candidate f(≻V ) ∈ C given a ranked-choice profile ≻V . We refer to f(≻V ) as the winner of the election E using the voting rule f, or just as the winner of f if E is clear from the context. For the most part, we will consider deterministic voting rules; in Section 5, we will also study randomized voting rules.

We refer to the candidate ranked highest by voter v as the top choice of v, and denote him by top(v). The candidate ranked lowest by voter v is likewise referred to as the bottom choice of v. We use plu(c) to denote the plurality score of candidate c, i.e., the number of voters whose top choice is c.

2.1 Metric Distortion

A metric over a set S is a function d : S × S → R≥0 which satisfies the following conditions for all a, b, c ∈ S: (1) Positive Definiteness: d(a, b) = 0 if and only 3 if a = b;

3 Our proofs do not require the "only if" condition, so technically, all our results hold for pseudo-metrics, not just metrics.

(2) Symmetry: d(a, b) = d(b, a); (3) Triangle inequality: d(a, b) + d(b, c) ≥ d(a, c).

Given an election E = (V, C,≻V ), we say that a metric d over 4 V ∪ C is consistent with the ranking ≻v of voter v if d(v, c) ≤ d(v, c′ ) for all c, c′ ∈ C such that c ≻v c′ . We say that d is consistent with the ranked-choice profile ≻V if it is consistent with the ranking ≻v for all voters v ∈ V . We use D(≻V ) to denote the domain of metrics consistent with ≻V .

The (utilitarian) social cost of a candidate c with respect to a metric d is defined as the candidate's sum of distances to all voters: cost(c, d) = ∑v∈V d(v, c). A candidate c∗d is optimal with respect to the metric d if c∗d ∈ argminc∈C cost(c, d). The distortion of a voting rule f, denoted by dist(f), is the largest possible ratio between the cost of the winner of f and that of an optimal candidate c∗d , with respect to the worst possible metric d ∈ D(≻V ). That is,

2.2 Domination Graphs

Domination graphs offer a conceptually simple approach for giving an upper bound of 3 on the distortion of a voting rule. Given an election E = (V, C,≻V ), the domination graph of a candidate c ∈ C is the bipartite graph GE (c) = (V, V, Ec) where (v, v′ ) ∈ Ec if and only if c ≽v top(v′ ). The main use of these graphs is via the following lemma, due to [Munagala and Wang, 2019; Kempe, 2020a; Gkatzelis et al., 2020].

Lemma 1. Let f be a voting rule such that for every election E = (V,C,≻V ), the domination graph GE (f(≻V )) has a perfect matching. Then, f has distortion 3.

Throughout the remainder of the paper, we assume that an election E = (V,C,≻V ) is given, and we drop E from notation when it is clear from the context.

3 Optimal Distortion via PLURALITYVETO

We now introduce PLURALITYVETO formally and show that it has distortion 3. PLURALITYVETO requires very limited ordinal information; it only requires one each of the following two types of queries to every voter.

• A top query to a voter v simply returns top(v).
• A bottom-among query to a voter v regarding a subset of candidates A returns the bottom choice of v among candidates in A, denoted by bottomA(v).

Notice that both can of course be easily derived when each voter's full ranking ≻v is known.

PLURALITYVETO assigns an initial score of plu(c) to each candidate c; doing so only requires making a top query to each voter. These scores are then gradually decreased; when the score of a candidate c reaches zero, we say that c is eliminated. Voters are processed one by one in an arbitrary order; this order can be fixed beforehand, or be adaptive and based on voters' preferences. When a voter v is processed, she decrements the score of her bottom choice among the notyet-eliminated candidates; the bottom choice can be found by making a bottom-among query to v. The winner is the last eliminated candidate. Pseudo-code is given as Algorithm 1.

4 We only care about the distances between voters and candidates, so d can be defined as a function d : V × C → R≥0 instead of on V ∪C. The triangle inequality can then be written as 0 ≤ d(v, c) ≤ d(v, c′ )+d(v′ , c′ )+d(v′ , c) for all v, v′ ∈ V and for all c, c′ ∈ C.

Algorithm 1 PLURALITYVETO

• Input: An election E = (V, C,≻V ) Output: A winning candidate c ∈ C 1: initialize score(c) = plu(c) for each c ∈ C 2: let (v1, . . . , vn) be an arbitrary ordering of V 3: for i = 1, 2, . . . , n do 4: Ai = {c ∈ C : score(c) > 0} 5: ci = bottomAi (vi) 6: decrement score(ci) by 1 7: return cn

Theorem 1. The distortion of PLURALITYVETO is 3.

Proof. We show that G(cn) has a perfect matching, which proves that PLURALITYVETO has distortion 3 by Lemma 1. Initially, the scores of candidates add up to n, and in each of the n iterations, a positive score is decremented by 1. Thus, the score of each candidate must be 0 at the end. This implies that, for each candidate c, there are plu(c) distinct voters vi such that ci = c. In other words, for each voter vi, we can define a unique voter v′i such that top(v′i ) = bottomAi (vi). This means that vi ranks any candidate in Ai weakly higher than top(v′i ). Since score(cn) does not get to 0 until the end, note that cn ∈ Ai for all i. Hence, each voter vi ranks cn weakly higher than top(v′i ), i.e., (vi, v′i ) ∈ Ecn . Thereby, we have shown that G(cn) has a perfect matching.

Algorithm 1 is not only quite natural; it also requires only O(logm) bits of information from each voter vi, namely, top(vi) and bottomAi (vi). However, implementing the rule with these two queries comes with a trade-off: voters need to wait for possibly n rounds after reporting their top choice.

4 A Simple Proof of the Ranking-Matching Lemma via FRACTIONALVETO

Our proof of Theorem 1 implied that there always exists a candidate whose domination graph has a perfect matching. The Ranking-Matching Lemma in [Gkatzelis et al., 2020] is a stronger existence result based on an extension of domination graphs in which nodes have arbitrary weights. Given an election E = (V, C, ≻V ) and weight vectors p ∈ ∆(V ) and q ∈ ∆(C), the (p, q)-domination graph of a candidate ˜c ∈ C is the bipartite graph GEp,q (˜c) = (V,C,E˜c, p, q); the edge (v, c) ∈ E˜c if and only if ˜c ≽v c. A fractional perfect matching of GEp,q (˜c) is a weight function w : E˜c → R≥0 such that ∑c∈C:(v,c)∈E˜ c w(v, c) = pv for each voter v and ∑v∈V :(v,c)∈E˜ c w(v, c) = qc for each candidate c. That is, the total weight of edges incident to each node must be equal to the weight of the node.

A candidate's domination graph has a perfect matching if and only if his (puni , qplu )-domination graph has a fractional perfect matching; here, puni v = 1/n for all v ∈ V and qplu c = plu(c)/n for all c ∈ C. The Ranking-Matching Lemma gives a stronger existence guarantee by asserting that, for any election E and any p ∈ ∆(V ) and q ∈ ∆(C), there is a candidate c ∈ C whose (p, q)-domination graph GEp,q (c) has a fractional perfect matching. Gkatzelis et al. [2020] give a proof by minimal counterexample for this lemma; thus, their proof is non-constructive. Moreover, it contains elaborate details for defining a minimal counterexample and intricate arguments involving smaller elections where some voters and candidates are removed.

We provide a much simpler and constructive proof of the Ranking-Matching Lemma. We generalize PLURALITYVETO in a way that allows any p ∈ ∆(V ) and q ∈ ∆(C) to be given as input. We refer to this voting rule as FRACTIONALVETO, and give the pseudo-code as Algorithm 2. Notice that for the special case with weights puni and qplu , FRACTIONALVETO specializes to PLURALITYVETO.

Algorithm 2 FRACTIONALVETO

Input: An election E = (V, C, ≻V ) along with normalized weight vectors p ∈ ∆(V ) and q ∈ ∆(C)

Output: A candidate c ∈ C whose (p, q)-domination graph has a fractional perfect matching

• 1: initialize weight(v) = pv for each v ∈ V
• 2: initialize weight(c) = qc for each c ∈ C
• 3: while there is a v ∈ V with weight(v) > 0 do
• 4: let v be such a voter
• 5: A = {c ∈ C : weight(c) > 0}
• 6: c = bottomA(v)
• 7: ϵ = min {weight(v), weight(c)}
• 8: decrement weight(v) by ϵ
• 9: decrement weight(c) by ϵ
• 10: return c (i.e., the last candidate whose weight is decremented)

Theorem 2. Given any election E = (V, C, ≻V ), and weight vectors p ∈ ∆(V ) and q ∈ ∆(C), FRACTIONALVETO returns a candidate c ∈ C whose (p, q)-domination graph GEp,q (c) has a fractional perfect matching.

Proof. We begin by observing that the while loop (lines 3-9) terminates in at most n+m iterations since in each iteration, the weight of either a voter v or a candidate c reaches 0. Next, we show that if a candidate, say ˜c, wins, then Gp,q(˜c) has a fractional perfect matching w : E˜c → R≥0.

First, note that, since ˜c is the last candidate whose weight is decremented, ˜c ∈ A for all iterations. Let us now consider an arbitrary iteration of FRACTIONALVETO in which a voter v is chosen. By definition, v ranks any candidate in A weakly higher than the candidate c = bottomA(v); in particular, v ranks ˜c weakly higher than c, i.e., (v, c) ∈ E˜c. Let w assign a weight of ϵ to the edge (v, c), i.e., w(v, c) = ϵ. We now show that w is a fractional perfect matching of Gp,q(˜c).

For each edge (v, c) ∈ E˜c to which w assigns positive weight, there exists an iteration where the weights of both v and c are decremented by w(v, c). Hence, the total weight of edges incident to each voter and candidate is equal to how much their weight is decremented until the end. All we need to show is that the weight of each voter v and candidate c reaches 0 at the end as they are initialized, respectively, to pv and qc. The total weights of voters and candidates are initially the same, and they stay so after each iteration since only a single voter's and candidate's weights are decremented, and by the same amount. Therefore, when the weight of each voter reaches 0, so does each candidate's. Thus, we have shown that w is a fractional perfect matching of Gp,q(˜c).

5 Randomized Voting Rules with Distortion 3

As shown in Theorem 1, PLURALITYVETO has distortion 3. Another voting rule that is well known to have distortion 3 (or 3 - 2/n, to be precise) is RANDOMDICTATORSHIP, which returns the top choice of a voter chosen uniformly at random [Anshelevich and Postl, 2016]. In the same vein, one can view PLURALITYVETO as choosing a voter deterministically and returning that voter's top choice; this voter is referred to as v′n in the proof of Theorem 1. This suggests a more general class of randomized voting rules, interpolating between RANDOMDICTATORSHIP and PLURALITYVETO: carefully rule out k voters, and return the top choice of a uniformly random voter among the remaining n-k voters. In this section, we introduce such a general rule and show that it achieves distortion at most 3 for every choice of k ∈ {0, 1, . . . , n-1}.

A randomized voting rule f is an algorithm which, given a ranked-choice profile ≻V , returns a probability distribution over candidates f(≻V ) ∈ ∆(C). Writing w = f(≻V ), each candidate c is chosen as the winner by f with probability wc. We refer to w as the winner distribution of f. The cost of a winner distribution under a given metric is the expected cost of the winner, i.e., cost(w, d) = ∑c∈C wc · cost(c, d). The distortion of a randomized voting rule is still the ratio of the rule's cost to the cost of the optimum solution. For randomized rules, the current best upper bound is 3 - 2/m [Kempe, 2020b], which is typically slightly better than the distortion of RANDOMDICTATORSHIP. This upper bound is known to be best possible among rules that randomize over only candidates with positive plurality score [Gkatzelis et al., 2020]. It is open whether any randomized voting rule has distortion 3-Ω(1). The current best lower bound is 2.1126, due to Charikar and Ramakrishnan [2022].

A candidate c wins under RANDOMDICTATORSHIP with probability proportional to his plurality score plu(c). When the score of candidate ci is decremented at the ith iteration of PLURALITYVETO, suppose that we rule out voter v′i , as defined in the proof of Theorem 1. Since top(v′i ) = ci, the current score of candidate ci can be viewed as his plurality score with respect to the remaining voters v′i+1 , . . . , v′n . Our generalized voting rule (Algorithm 3) therefore simply runs PLURALITYVETO for only k < n iterations, then chooses a candidate with probability proportional to the residual scores.

Theorem 3. The distortion of k-ROUNDPLURALITYVETO is at most 3 for any number of rounds 0 ≤ k < n.

Our proof is based on a generalization of the flow technique from [Kempe, 2020a] to randomized voting rules. It is

Algorithm 3 k-ROUNDPLURALITYVETO Input: An election E = (V, C,≻V ) Output: Awinner distribution w ∈ ∆(C) 1: initialize score(c) = plu(c) for each c ∈ C 2: let (v1, . . . , vn) be an arbitrary ordering of V 3: for i = 1, 2, . . . , k do 4: Ai = {c ∈ C : score(c) > 0} 5: ci = bottomAi (vi) 6: decrement score(ci) by 1 7: return wc = score(c)/(n-k) for all c ∈ C

encapsulated in Lemma 2 below; this lemma is a straightforward generalization of Lemma 3.1 from [Kempe, 2020a]. As in that paper, the proof is somewhat technical and long; thus, it is deferred to the full version.

The key concept, adopted from [Kempe, 2020a], is the following flow network. Given an election E, let HE = (V ×C, E) be a directed graph with the the following edges:

• For every voter v and any pair of candidates c and c′ such that c ≻v c′ , there is a directed so-called preference edge (v, c) → (v, c′ ) in E.
• For every candidate c and any pair v ̸= v′ of distinct voters, there is a (bi-directed) so-called sideways edge (v, c) ↔ (v′ , c) in E.

For a winner distribution 5 w ∈ ∆(C) and a candidate c∗ , a (w, c∗ )-flow on HE is a circulation g (i.e., non-negative and conserving flow unless specified otherwise) in which

• For each candidate c and voter v, exactly wc units of flow originate at the node (v, c).
• Flow is only absorbed at nodes (v, c∗ ).

The cost of g at voter v is the total amount of flow absorbed at (v, c∗ ), plus the total flow on sideways edges into or out of nodes (v, c), for any candidate c. Formally, costv(g) = ∑e into (v,c∗ ) ge+∑c̸=c∗ ∑v′ ̸=v g(v′ ,c)↔(v,c) where gu↔u′ = gu→u′ +gu′→u. The cost of g is cost(g) = maxv∈V costv(g). The key lemma showing how to use flows to upper-bound the distortion of a voting rule is the following.

Lemma 2. Let f be a randomized voting rule. For every election E = (V, C, ≻V ) and any candidate c∗ ∈ C, suppose that there is a (w, c∗ )-flow g on the flow network HE such that w = f(≻V ) and cost(g) ≤ λ. Then, dist(f) ≤ λ.

Proof of Theorem 3. Fix an arbitrary candidate c∗ ∈ C. We will describe a (w, c∗ )-flow g, and prove that it has cost at most 3. Theorem 3 then follows directly from Lemma 2.

As shown in the proof of Theorem 1, we can sort the voters as v′1 , . . . , v′n such that top(v′i ) = bottomAi (vi) for all i in the execution of PLURALITYVETO, i.e., without stopping early. Define Vk = {v1, . . . , vk} and Vk = {vk+1, . . . , vn}; also V ′ k = {v′1 , . . . , v′k } andV ′k = {v′k+1 , . . . , v′n }.

5 Kempe [2020a] considered only deterministic voting rules; in that case, the distribution w was restricted to have probability 1 for the deterministic winner, and 0 for all other candidates.

In order to obtain a (w, c∗ )-flow, we must route flow such that for each candidate c and each voter v ∈ V , exactly score(c)/(n - k) units of flow originate at the node (v, c). In particular, because score(c) = 0 for candidates c /∈ Ak, no flow originates at any nodes (v, c) for c /∈ Ak.

1. First, consider a voter vi ∈ Vk, so that i ≤ k. Since Ak ⊆ Ai, voter vi ranks all candidates in Ak weakly higher than bottomAi (vi). Therefore, g can route all the flow originating at nodes (vi, c) to (vi, bottomAi (vi)) along preference edges. At that point, there is one unit of flow at (vi, bottomAi (vi)). This one unit of flow is next routed to (v′i , bottomAi (vi)) = (v′i , top(v′i )) using a sideways edge. Finally, since top(v′i ) is by definition the top choice of v′i , the unit can be routed to (v′i , c∗ ) using a preference edge, and is then absorbed.
2. Next, we (jointly) consider all voters vi ∈ Vk. Fix a candidate c ∈ Ak. Because score(c)/(n - k) units of flow originate at each node (vi, c) for vi ∈Vk, and there are |Vk| = n - k such nodes, in total, exactly score(c) units of flow originate at these nodes. On the other hand, score(c) is also the number of distinct voters v′j ∈ V ′k such that top(v′j ) = c. g distributes all the score(c) units of flow from nodes (vi, c) (for vi ∈ Vk) to the score(c) nodes (v′j , c) with top(v′j ) = c, in a way that each voter v′j ∈ V ′k receives one unit of flow. Then, for each voter v′j ∈ V ′k with top(v′j ) = c, the flow g routes the one unit of flow from (v′j , c) to (v′j , c∗ ) using a preference edge; there, it is absorbed. Because flow only originates at nodes (vi, c) with c ∈ Ak, all the flow is in fact routed to an absorbing node in this way.

In the flow g described above, for each voter v, exactly one unit is sent out on sideways edges, and one unit is received on sideways edges. For voters in Vk, the unit sent is by the first case above; for voters in V ′ k , the unit received is by the first case. For voters inVk, the unit sent is by the second case; for voters inV ′k, the unit received is by the second case. Finally, each voter vi absorbs the one received unit of flow at (vi, c∗ ). This proves that cost(g) = 3, completing the proof. □

6 Conclusion and FutureWork

We showed that a simple deterministic voting rule, called PLURALITYVETO, achieves the optimal metric distortion of 3; the proof is short and simple. We used a generalization to prove the Ranking-Matching Lemma of Gkatzelis et al. [2020], and we also showed that a class of randomized rules interpolating between RANDOMDICTATORSHIP and PLURALITYVETO all achieve expected distortion at most 3.

PLURALITYVETO is a very natural and potentially practical voting rule, and it would be of interest to understand which other properties it satisfies. One difficulty is that the outcome depends on the order in which the voters are queried in the multi-round veto process. On the other hand, this makes the structure of the set W ⊆ C of potential winners (i.e., candidates who will win for at least one processing order of the voters) an interesting object of study.

Note that W is a subset of candidates whose domination graph has a perfect matching, i.e., potential winners of PLURALITYMATCHING. This has several immediate implications. First, it is possible that for all orderings of voters, the selected candidate fails to be a Condorcet winner, as shown for PLURALITYMATCHING by Gkatzelis et al. [2020]. Second, if the metric space is α-decisive (i.e., for each voter, the ratio between her distance to her top-ranked and secondranked candidate is at most α [Anshelevich and Postl, 2016]) then the distortion bound improves to 2 + α.

Additional insights can be gleaned from the Peer Selection setting, in which the set of voters is the same as the set of candidates, so each voter/candidate ranks herself first; as a result, all such instances are 0-decisive. PLURALITYVETO can be even more easily described in the Peer Selection setting: in each round i, the voter vi eliminates from consideration the remaining candidate furthest from her.

Here, we consider a slight variant of PLURALITYVETO: the order of voters is chosen adaptively, and the next voter vi+1 is always one whose first-place vote was canceled by vi. In addition, the vote of v1 is always canceled, so the winner is the top choice of vn. A proof essentially identical 6 to the one of Theorem 1 shows that this rule returns a candidate whose domination graph has a perfect matching as well. In turn, we can use this insight to prove that there are at least two candidates who can win in Peer Selection, i.e., |W| ≥ 2. First, if the process is run from an arbitrary v1, then some ˆ v = vn wins. If the process is run starting from v1 = ˆ v, the winner must be some other candidate ˜ v ̸= ˆ v, because ˆ v is eliminated in the first step. So there are at least two potential winners.

Peer selection also has interesting properties when the voters/candidates are embedded in Euclidean space RD . Since each voter, on her turn, eliminates the voter furthest from her, the eliminated voter is always located at a corner of the convex hull of all previously uneliminated ones. In this sense, PLURALITYVETO "peels away" extreme candidates one by one 7 : the convex hull of the voters in Ak (who are not yet eliminated after k rounds) contains no voter from ¯ Ak. A natural question is whether the set W of potential winners has the same convexity property, i.e., the convex hull of W contains no voter/candidate from C \ W. 8 If true, this would show that the potential winners are in a sense "cohesive."

Another compelling direction concerns the incentives under PLURALITYVETO. We described it as a sequential process in which voters are queried about their bottom choice one by one. In describing the sequential process, we assumed that all queries are answered truthfully. An interesting direction here is to consider the "Price of Anarchy:" what is the worst distortion of PLURALITYVETO if agents play a subgame perfect equilibrium in the VETO stage instead of truthfully revealing their bottom choice?

6 Because the vote of v1 is always canceled, this rule is not technically a special case of PLURALITYVETO.

7 This behavior also provides some informal intuition for why the final candidate should be close to the geometric median.

8 For the general case (rather than Peer Selection), this is false: for example, if there is one voter and candidate each on the left and right, but only one candidate (with no voters) in the center, then the left and right candidates can win, but not the center one.