{'fraction_non_alphanumeric': 0.044933160845191895, 'fraction_numerical': 0.007761966364812419, 'mean_word_length': 4.142054693274205, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion

The metric distortion framework posits that n voters and m candidates are jointly embedded in a metric space such that voters rank candidates that are closer to them higher. A voting rule's purpose is to pick a candidate with minimum total distance to the voters, given only the rankings, but not the actual distances. As a result, in the worst case, each deterministic rule picks a candidate whose total distance is at least three times larger than that of an optimal one, i.e., has distortion at least 3. A recent breakthrough result showed that achieving this bound of 3 is possible; however, the proof is non-constructive, and the voting rule itself is a complicated exhaustive search. Our main result is an extremely simple voting rule, called Plurality Veto, which achieves the same optimal distortion of 3. Each candidate starts with a score equal to his number of first-place votes. These scores are then gradually decreased via an n-round veto process in which a candidate drops out when his score reaches zero. One after the other, voters decrement the score of their bottom choice among the standing candidates, and the last standing candidate wins. We give a one-paragraph proof that this voting rule achieves distortion 3. This rule is also immensely practical, and it only makes two queries to each voter, so it has low communication overhead. We also generalize Plurality Veto into a class of randomized voting rules in the following way: Plurality veto is run only for k<n rounds; then, a candidate is chosen with probability proportional to his residual score. This general rule interpolates between Random Dictatorship (for k=0) and Plurality Veto (for k=n-1), and k controls the variance of the output. We show that for all k, this rule has distortion at most 3.


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 [29]. 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 [11]. An important contribution due to Anshelevich et al. [2] (see also the journal version [3] and recent surveys [5,4]) 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.) The metric distortion framework has proved to be a fruitful analysis tool. In their initial work, Anshelevich et al. [2] 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. [18] who gave a lower bound of 5; Kempe [21] strengthened the lower bound to Ω( √ m). The first improvement over the upper bound of 5 was due to Munagala and Wang [24], 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. [17], 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. [17] over the prior work of Munagala and Wang [24] and Kempe [21]. 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 first-place 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 voters, 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(log m) 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, multiround 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 [24] and Kempe [21] had shown that if G(c) has a perfect matching, then c has distortion at most 3. The key contribution of Gkatzelis et al. [17] was to show that such a candidate c always exists. In fact, they proved a generalization, called the Ranking-Matching 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 k th round of PLURALITYVETO, which we refer to as k-ROUNDPLURALITYVETO. When k = 0, this more general rule specializes to the well-known 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 [1]. 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) [17]. Also, since k controls the variance of the output, at a high level, this result relates to the work of Fain et al. [14] 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 [9,10,26,27]. Boutilier and Rosenschein [8], Anshelevich et al. [2] 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 [9,10,26,27], the focus was on (positive) utilities, and no additional assumptions (such as metric costs) were placed on the utilities.
The role of randomization in reducing distortion has been studied in several prior papers. The fact that randomized voting rules can achieve expected distortion lower than 3 (the known lower bound for deterministic voting rules) was first shown by Anshelevich and Postl [1], who showed that RANDOMDICTATORSHIP achieves expected distortion 3 − 2 n . A slightly improved distortion of 3 − 2 m was achieved in [20] by randomizing between RANDOMDICTATORSHIP and PROPORTIONALTOSQUARES. This upper bound is best possible among rules that only have access to each candidate's plurality score [19] -in fact, Gross et al. [19] prove a more general lower bound, which establishes that when each voter only communicates her top k < n/2 candidates, every randomized voting rule has distortion at least 3 − 2 ⌊n/k⌋ . A lower bound of 2 on the distortion of any randomized voting rule is straightforward, and it had been conjectured that this bound may be achievable by some randomized voting rule. This conjecture was recently disproved in [12], which established a lower bound of 2.0261 for m = 3 candidates and 2.1126 as the number of candidates m → ∞. Whether any randomized voting rule can achieve expected disortion 3 − Ω(1) for arbitrary m remains an intriguing open question.
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 the study of communication in social choice rules (e.g., [8,13]), and more specifically to studies of the tradeoff between communication and metric distortion. The recent papers [14,20] establish related lower bounds: Fain et al. [14] 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 [20] proves a slightly more general and stronger 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. [14] 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.
Several other recent works have studied the tradeoff between communication and distortion. Mandal et al. [22] study tradeoffs between communication and distortion in the utilitarian model, i.e., without any metric constraints. They also assume that voters actually know their utilities. In this model, they obtain upper and lower bounds on the achievable distortion under communication complexity constraints. Pierczyński and Skowron [25] consider the distortion (and a modified notion of distortion) for approval-based voting (which has reduced communication), in which voters approve all candidates within a certain distance of themselves. They show that under certain parameter settings, for a carefully chosen radius, approvalbased voting achieves constant distortion in their sense. Bentert and Skowron [6] consider the approximate implementation of score-based voting rules using low communication. In particular, their techniques in Section 3.2 show that constant distortion 5 + o(1) can be achieved when the number of voters is large, by asking each voter to compare two uniformly random candidates.

Preliminaries
Throughout, we use bold face for vectors, and denote the i th component of a vector x by x i . 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.

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 Given an election E = (V, C, ≻ V ), we say that a metric d over 4 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: 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, .

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 The main use of these graphs is via the following lemma, due to [24,21,17].

Lemma 1. Let f be a voting rule such that for every election
) 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.

Optimal Distortion via PLURALITYVETO
We now introduce PLURALITYVETO 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 bottom A (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 not-yet-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.

Algorithm 1 PLURALITYVETO
Input: An election E = (V, C, ≻ V ) Output: A winning candidate c ∈ C  Proof. We show that G(c n ) 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 v i such that c i = c. In other words, for each voter v i , we can define a unique voter v This means that v i ranks any candidate in A i weakly higher than top(v ′ i ). Since score(c n ) does not get to 0 until the end, note that c n ∈ A i for all i. Hence, each voter v i ranks c n weakly higher than top(v ′ i ), i.e., (v i , v ′ i ) ∈ E cn . Thereby, we have shown that G(c n ) has a perfect matching.
Algorithm 1 is not only quite natural; it also requires only O(log m) bits of information from each voter v i , namely, top(v i ) and bottom A i (v i ). 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.
Note that our proof of Theorem 1 also implies that there is always a candidate whose domination graph has a perfect matching. Indeed, all attempts to resolve the optimal metric distortion conjecture, in one way or another, boiled down to proving the existence of such a candidate. This was done in [17] by giving a stronger existence result, called the ranking-matching lemma. Our rule, as stated so far, does not require this stronger lemma, but in the next section, we show that a simple generalization also implies the general ranking-matching lemma.

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 [17] 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 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 (p uni , q plu )-domination graph has a fractional perfect matching; here, p uni v = 1/n for all v ∈ V and q plu 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 G E p,q (c) has a fractional perfect matching. Gkatzelis et al. [17] 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. This makes the proof somewhat harder to grasp.
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 p uni and q plu , FRACTIONALVETO specializes to PLURALITYVETO.

Algorithm 2 FRACTIONALVETO
Input: An election E = (V, C, ≻ V ) along with weight vectors p ∈ ∆(V ) and q ∈ ∆(C) Output: A candidate c ∈ C whose (p, q)-domination graph has a fractional perfect matching let v be such a voter 5: 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 any weight vectors p ∈ ∆(V ) and q ∈ ∆(C), FRACTIONALVETO returns a candidate c ∈ C whose (p, q)-domination graph G E p,q (c) has a fractional perfect matching.
Proof. We begin by observing that the while loop (lines [3][4][5][6][7][8][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 G p,q ( c) has a fractional perfect matching w.
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 = bottom A (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 G p,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 p v and q c . 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 G p,q ( c).

A Class of 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 [1]. 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 RANDOMDICTATOR-SHIP 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 w c . 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 w c · 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.
To phrase our generalized voting rule precisely, we observe that a candidate c wins under RANDOM-DICTATORSHIP with probability proportional to his plurality score plu(c). When the score of candidate c i is decremented at the i th iteration of PLURALITYVETO, suppose that we rule out voter v ′ i , as defined in the proof of Theorem 1. Since top(v ′ i ) = c i , the current score of candidate c i 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. The algorithm is formally given as Algorithm 3.

Algorithm 3 k-ROUNDPLURALITYVETO
Input: An election E = (V, C, ≻ V ) Output: A winner distribution w ∈ ∆(C) 1: initialize score(c) = plu(c) for each c ∈ C 2: let (v 1 , . . . , v n ) be an arbitrary ordering of V 3: for i = 1, 2, . . . , k do 4: decrement score(c i ) by 1 7: return w c = score(c)/(n − k) for all c ∈ C Our main result in this section is that k-ROUNDPLURALITYVETO has distortion at most 3 for any k. Our proof is based on a generalization of the flow technique from [21] to randomized voting rules. It is encapsulated in Lemma 2 below; this lemma is a straightforward generalization of Lemma 3.1 from [21]. As in that paper, the proof is somewhat technical and long; thus, it is given in the appendix.
The key concept, adopted from [21], is the following flow network. Given an election E, let H E = (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 -For every candidate c and any pair v = v ′ of distinct voters, there is a (bi-directed) sideways edge An illustration of a flow network is given in Fig. 1.
For a winner distribution 5 w ∈ ∆(C) and a candidate c * , a (w, c * )-flow on H E is a circulation g (i.e., non-negative and conserving flow unless specified otherwise) in which -For each candidate c and voter v, exactly w c 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, The cost of g is cost(g) = max v∈V cost v (g). An illustration of flows and their costs is given in Fig. 2.
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, with the following property: For every election E = (V, C, ≻ V ) and any candidate c * ∈ C, on the flow network H E , there is a (w, c * )-flow g such that Preference edges are shown in black, while sideways edges are shown in red. For legibility, we have omitted preference edges that could be replaced by a path of two or more other preference edges, e.g., the edge from We are now ready to give the proof of Theorem 3.
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 ) = bottom A i (v i ) for all i in the execution of PLURALITYVETO, i.e., without stopping early. Define V k = {v 1 , . . . , v k } and 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 / ∈ A k , no flow originates at any nodes (v, c) for c / ∈ A k .

First, consider a voter
voter v i ranks all candidates in A k weakly higher than bottom A i (v i ). Therefore, g can route all the flow originating at nodes . This one unit of flow is next routed to ) 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 v i ∈ V k . Fix a candidate c ∈ A k . Because score(c)/(n − k) units of flow originate at each node (v i , c) for v i ∈ V k , and there are |V k | = 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 (v i , c) (for v i ∈ V k ) 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 (v i , c) with c ∈ A k , 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 V k , the unit sent is by the first case above; for voters in V ′ k , the unit received is by the first case. For voters in V k , the unit sent is by the second case; for voters in V ′ k , the unit received is by the second case. Finally, each voter v i absorbs the one received unit of flow at (v i , c * ). This proves that cost(g) = 3, completing the proof.

Conclusion and Future Work
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 of PLURALITYVETO, called FRACTIONALVETO, to prove the Ranking-Matching Lemma of Gkatzelis et al. [17], 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, including the standard axiomatic voting rule properties. 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 PLURALITY-MATCHING by Gkatzelis et al. [17]. Second, if the metric space is α-decisive (i.e., for each voter, the ratio between her distance to her top-ranked and second-ranked candidate is at most α [1]) 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 v i 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 v i+1 is always one whose first-place vote was canceled by v i . In addition, the vote of v 1 is always canceled, so the winner is the top choice of v n . 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 v 1 , then somev = v n wins. If the process is run starting from v 1 =v, the winner must be some other candidateṽ =v, becausev 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 R D . 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 A k (who are not yet eliminated after k rounds) contains no voter fromĀ k . 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 (although of course the process can be fully simulated if each voter's full ranking is known). In describing the sequential process, we assumed that all queries are answered truthfully. While no non-trivial voting rule can be truthful in general [16,28], truthfulness can be achieved in restricted settings [15]. 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?