Incentives in Social Decision Schemes with Pairwise Comparison Preferences

1 Introduction

Incentives constitute a central aspect when designing mechanisms for multiple agents: mechanisms should incentivize agents to participate and to act truthfully [Nisan et al., 2007; Shoham and Leyton-Brown, 2009; Brandt et al., 2016]. However, for many applications, guaranteeing these propertiesusually called participation and strategyproofness-is a notoriously difficult task. This is particularly true for collective decision making, which studies the aggregation of preferences of multiple voters into a group decision, because strong impossibility theorems show that these axioms are in variance with other elementary properties [Gibbard, 1973; Satterthwaite, 1975; Moulin, 1988]. For instance, the GibbardSatterthwaite theorem shows that every strategyproof voting rule is either dictatorial or imposing, and Moulin's No-Show paradox demonstrates that all Condorcet-consistent voting rules violate participation. A natural escape route in light of these negative results is to allow for randomization in the output of the voting rule. Rather than returning a single winner, a social decision scheme (SDS) selects a lottery over the alternatives and the winner is eventually drawn at random according to the given probabilities.

In order to study properties such as efficiency, strategyproofness, and participation for SDSs, preferences over alternatives are typically lifted to preferences over lotteries using the notion of stochastic dominance (SD), i.e., one lottery is preferred to another lottery if the expected utility of the former exceeds that of the latter for every utility representation consistent with the voter's preferences over alternatives [Gibbard, 1977; Bogomolnaia and Moulin, 2001; Brandl et al., 2018]. When demanding SD-efficiency, SDstrategyproofness, and anonymity, the only SDS that does the job is uniform random dictatorship (RD), which selects a voter uniformly at random and then returns his favorite alternative [Gibbard, 1977]. Moreover, RD satisfies strict SDparticipation, which means that voters are strictly better off participating (unless their top choice already receives probability 1). Unsurprisingly, RD has some severe shortcomings. It is often criticized for its inability to compromise: if all voters agree on a second best alternative but disagree on the best one, the uniform random dictatorship will not choose the common second best option. Furthermore, it cannot be extended to weak preferences without giving up SD-strategyproofness or SD-efficiency [Brandl et al., 2016b]. On top of these criticisms, the representation of preferences over lotteries via expected utility functions has come under scrutiny [Allais, 1953; Kahneman and Tversky, 1979; Anand, 2009].

As an alternative to traditional expected utility representations, some authors have proposed to postulate that one lottery is preferred to another if the former is more likely to return a preferred outcome [Blyth, 1972; Packard, 1982; Blavatskyy, 2006]. The resulting preference extension is known as pairwise comparison (PC) and represents a special case of Fishburn's skew-symmetric bilinear utility functions [Fishburn, 1982]. Brandl et al. [2019] have shown that the No-Show paradox can be circumvented using PC preferences. Moreover, Brandl and Brandt [2020] proved that PC preferences constitute the only domain of preferences within a rather broad class of preferences over lotteries that allow for preference aggregation that satisfies independence of irrelevant alternatives and efficiency, thus avoiding Arrow's impossibility.

In both cases, the resulting SDS is the set of maximal lotteries (ML), which was proposed by Fishburn [1984b] and has recently attracted significant attention [Brandl et al., 2016a; Brandl et al., 2022; Hoang, 2017].

It is known that PC-efficiency is stronger than SDefficiency and violated by RD. PC-strategyproofness and strict PC-participation, on the other hand, are weaker than their SD counterparts. ML satisfies Condorcet-consistency, PC-efficiency, and PC-participation [Aziz et al., 2018; Brandl et al., 2019]. Furthermore, it is PC-strategyproof in preference profiles that admit a Condorcet winner [Hoang, 2017; Brandl et al., 2022]. These encouraging results lead to the natural question of whether there are attractive SDSs that satisfy PC -strategyproofness or strict PC -participation. We address this question by proving the following theorems, all of which settle open problems raised by Brandt [2017]:

• There is no Condorcet-consistent SDS that satisfies PCstrategyproofness.
• There is no anonymous and neutral SDS that satisfies PC -efficiency and PC -strategyproofness.
• There is no anonymous and neutral SDS that satisfies PC -efficiency and strict PC -participation.

All three theorems hold for strict preferences and require m ≥ 4 alternatives; we show that they turn into possibilities when m ≤ 3 by constructing two new SDSs. The second theorem strengthens Theorem 5 by Aziz et al. [2018], which requires weak preferences. Our theorems demonstrate that efficiency, strategyproofness, and strict participation-which are satisfied by RD if we extend preferences using SD-are not compatible for PC preferences. Hence, there is no equivalent of random dictatorships for PC preferences. This also means that-unlike with Arrow's impossibility and the NoShow paradox-PC preferences do not help to circumvent the Gibbard-Satterthwaite theorem. As a consequence, we face a tradeoff between efficiency and incentive-compatibility, which implies that no SDS can combine the advantages of ML and RD when using PC to compare lotteries. Hence, among the known SDSs, RD is the most attractive one when aiming for incentive-compatibility and ML when aiming for efficiency (and other properties such as Condorcet-consistency).

2 The Model

Let A = {a1, . . . , am} be a finite set of m alternatives and N = {1, 2, 3, . . . } an infinite set of voters. We denote by F(N) the set of all finite and non-empty subsets of N. Intuitively, N is the set of all potential voters, whereas N ∈ F(N) is a concrete electorate. Given an electorate N ∈ F(N), every voter i ∈ N has a preference relation ≻i, which is a complete, transitive, and anti-symmetric binary relation on A. In particular, we do not allow for ties (which only makes our results stronger). We write preference relations as comma-separated lists and denote the set of all preference relations by R. A preference profile R on an electorate N ∈ F(N) contains a preference relation ≻i for every voter i ∈ N, i.e., R ∈ RN . When writing preference profiles, we use sets before preference relations to indicate the voters who report the same preference relation. To this end, we define [j . . . k] = {i ∈ N : j ≤ i ≤ k} and note that [j . . . k] = ∅ if j > k. For instance, [1 . . . 3]: a, b, c means that voters 1, 2, and 3 prefer a to b to c. We omit the brackets for singleton sets. Given a preference profile R ∈ RN , the majority margin between two alternatives x, y ∈ A is gR(x, y) = |{i ∈ N : x ≻i y}| - |{i ∈ N : y ≻i x}|, i.e., the majority margin indicates how many more voters prefer x to y than vice versa. Furthermore, we define nR(x) as the number of voters who prefer alternative x the most in the profile R. Next, we denote by R-i = (≻1, . . . ,≻i-1,≻i+1, . . . ,≻n) the profile derived from R ∈ RN by removing voter i ∈ N. Finally, RF(N) is the set of all possible preference profiles.

In this paper, we study social decision schemes (SDSs), which map preference profiles to lotteries over the alternatives. A lottery p is a probability distribution over the alternatives, i.e., a function p : A → [0, 1] such that p(x) ≥ 0 for all x ∈ A and ∑x∈A p(x) = 1. The set of all lotteries on A is denoted by ∆(A). Then, an SDS f formally is a function of type f : RF(N) → ∆(A). We define f(R, x) as the probability assigned to x by f(R) and extend this notion to sets X ⊆ A by f (R, X) = ∑x∈X f (R, x).

2.1 Fairness and Decisiveness

Next, we formalize desirable properties of SDSs. Two basic fairness notions are anonymity and neutrality, which require that voters and alternatives are treated equally, respectively. Formally, an SDS f is anonymous if f(π(R)) = f(R) for all electorates N ∈ F(N), preference profiles R ∈ RN , and permutations π : N → N. Here, R′ = π(R) is defined by ≻′i = ≻π(i) for all i ∈ N. Analogously, neutrality requires of an SDS f that f(π(R)) = π(f(R)) for all electorates N ∈ F(N), preference profiles R ∈ RN , and permutations π : A → A. This time, R′ = π(R) is the profile such that for all i ∈ N and x, y ∈ A, π(x) ≻′i π(y) if and only if x ≻i y. Another fairness condition is cancellation, which demands that the outcome does not change if two voters with inverse preferences join the electorate. Hence, an SDS f satisfies cancellation if f(R) = f(R′ ) for all preference profiles R,R′ ∈ RF(N) such that R′ is derived fromR by adding two voters with inverse preferences.

A natural desideratum in randomized social choice is decisiveness: randomization should be avoided whenever possible. For instance, Condorcet-consistency formalizes this idea. We say an alternative x is a Condorcet winner in a profile R if gR(x, y) > 0 for all y ∈ A \ {x}. Then, Condorcetconsistency requires of an SDS f that the Condorcet winner is chosen with probability 1 whenever it exists, i.e., f(R, x) = 1 for all preference profiles R ∈ RF(N) with Condorcet winner x. A weaker decisiveness condition is the absolute winner property. An absolute winner is an alternative x that is top-ranked by more than half of the voters in R ∈ RN , i.e., nR(x) > |N| 2 . Then, the absolute winner property requires that f(R, x) = 1 for all profiles R ∈ RF(N) with absolute winner x. Since absolute winners are also Condorcet winners, Condorcet-consistency implies the absolute winner property.

2.2 PC and SD Preferences

We assume that the voters' preferences over alternatives are lifted to preferences over lotteries via the pairwise comparison

(PC) extension (see, e.g., [Aziz et al., 2015; Aziz et al., 2018; Brandt, 2017; Brandl and Brandt, 2020]). According to this notion, a voter prefers lottery p to lottery q if the probability that p returns a better outcome than q is at least as large as the probability that q returns a better outcome than p, i.e.,

The relation ≿PC i is known to be complete but intransitive. An appealing interpretation of PC preferences is ex ante regret minimization, i.e., given two lotteries, a voter prefers the one which is less likely to result in ex post regret. Despite the simple definition, PC preferences are quite difficult to work with and even simple notions such as PC-efficiency are little understood [Aziz et al., 2015].

Another well-known way to compare lotteries is stochastic dominance (SD) (e.g., [Gibbard, 1977; Brandl et al., 2018]):

It follows from a result by Fishburn [1984a] that p ≿SD i q implies p ≿PC i q for all preference relations ≻i and all lotteries p and q (see also [Aziz et al., 2015]). In other words, the SD relation is a subrelation of the PC relation. For both X ∈ {PC, SD}, we say a voter strictly X-prefers p to q, denoted by p ≻Xi q, if p ≿Xi q and not q ≿Xi p. Note that p ≻SD i q implies p ≻PC i q.

2.3 Efficiency and Incentives

We can now define efficiency, strategyproofness, and participation. All of these axioms can be defined for both SD and PC; we thus define the concepts for X ∈ {PC, SD}. First, we discuss efficiency, which requires that no lottery is unanimously preferred to the lottery chosen by the SDS. To formalize this, we say a lottery p X-dominates another lottery q in a profile R ∈ RN if p ≿Xi q for all voters i ∈ N and p ≻Xi∗ q for some voter i∗ ∈ N. Conversely, a lottery p is X-efficient in R if it is not X-dominated, and an SDS f is X-efficient if f(R) is X-efficient for all preference profiles R ∈ RF(N) . Both PC-efficiency and SD-efficiency imply ex post efficiency. For introducing this concept, we say an alternative x Pareto-dominates another alternative y in a profile R ∈ RN if x ≻i y for all voters i ∈ N. 1 Then, ex post efficiency requires that f (R, x) = 0 for all profiles R ∈ RF(N) and alternatives x ∈ A that are Pareto-dominated in R.

Next, we introduce strategyproofness, which demands that no voter can benefit by lying about his true preferences. Formally, an SDS f is X-strategyproof if f(R) ≿Xi f(R′ ) for all electorates N ∈ F(N), voters i ∈ N, and preference profiles R,R′ ∈ RN with R-i = R′-i . 2 Conversely, an SDS is X-manipulable if it is not X-strategyproof. Since strategyproofness does not require a variable electorate, we usually specify the electorates for which an SDS is strategyproof or manipulable. Similarly to strategyproofness, participation requires that voters should not be able to benefit by abstaining from the election. Hence, an SDS f satisfies X-participation if f(R) ≿Xi f(R-i) for all electorates N ∈ F(N), voters i ∈ N, and preference profiles R ∈ RN . In this paper, we are interested in strict X-participation introduced by Brandl et al. [2015], which demands of an SDS f that, for all N ∈ F(N), i ∈ N, and R ∈ RN , it holds that f(R) ≿Xi f(R-i) and, moreover, f(R) ≻Xi f(R-i) if there is a lottery p with p ≻Xi f(R-i). That is, if possible, a voter strictly benefits from voting compared to abstaining.

1 Recall that ties in ≻i are not allowed.

2 Another version is to require that f(R′ ) ̸≻Xi f(R); these two versions coincide for PC because the PC extension is complete.

Since p ≻SD i q implies p ≻PC i q and p ≿SD i q implies p ≿PC i q, the concepts of SD-efficiency, SDstrategyproofness, and SD-participation are related to the analogous concepts for PC: PC-efficiency entails SD-efficiency, whereas SD-strategyproofness and strict SD-participation are stronger than the corresponding notions for PC [Brandt, 2017]. See Figure 1 for an overview of these axioms.

2.4 RandomDictatorship andMaximal Lotteries

The following two important SDSs help to put our results into perspective: the uniform random dictatorship (RD) and maximal lotteries (ML). These SDSs are well-known and all subsequent claims are taken from the survey by Brandt [2017]. The uniform random dictatorship (RD) assigns probabilities proportional to nR(x), i.e., RD(R, x) = nR(x) ∑y∈A nR(y) for every alternative x ∈ A and preference profile R ∈ RF(N) . RD is known to satisfy SD-strategyproofness, strict SDparticipation, and SD-efficiency. Even more, when additionally imposing anonymity, it is the only SDS that satisfies these axioms. Since SD-strategyproofness and strict SDparticipation imply the corresponding concepts for PC , RD satisfies our incentive axioms also if we extend preferences using PC . However, RD fails PC -efficiency and Condorcetconsistency, as can be seen in the following profile.

For this profile, RD(R, x) = 13 for all x ∈ A, but a is the Condorcet winner and the lottery that puts probability 1 on a PC -dominates RD(R).

In order to define ML, let ML(R) = {p ∈ ∆(A) : ∑x,y∈A p(x)q(y)gR(x, y) ≥ 0 for all q ∈ ∆(A)} be the set of maximal lotteries for profile R. ML(R) is non-empty by the minimax theorem and almost always a singleton. For all our claims about ML, it does not matter how ties are broken and any maximal lottery can be returned for a profile that admits multiple maximal lotteries. ML satisfies PC -efficiency, PC-participation, and Condorcet-consistency. However, ML fails PC-strategyproofness and strict PC-participation. The former can be seen by considering the following profiles.

The unique maximal lotteries in R and R′ , respectively, are p and q with p(a) = q(c) = 35 and p(b) = p(c) = q(a) = q(b) = 15 . Since ≻i = ≻′i for all i ∈ {1, 2, 3, 5} and q ≻PC 4 p, voter 4 can PC-manipulate by deviating from R to R′ . This raises the question of whether there is an SDS that unifies the advantages of ML and RD. As we show, this is not the case.

3 Results

We are now ready to present our results. The results for PCstrategyproofness are given in Section 3.1 while those for strict PC-participation are given in Section 3.2. Due to space restrictions, we defer most proofs to the full version of this paper [Brandt et al., 2022] and discuss proof sketches instead.

3.1 PC-strategyproofness

In this section, we show that every Condorcet-consistent and every anonymous, neutral, and PC-efficient SDS is PC-manipulable when there are m ≥ 4 alternatives. These results show that no SDS simultaneously satisfies PC-strategyproofness and the desirable properties of maximal lotteries. Moreover, since PC-strategyproofness is weaker than SD-strategyproofness, the incompatibility of PCstrategyproofness and Condorcet-consistency is a strengthening of the well-known impossibility of Condorcet-consistent and SD-strategyproof SDSs. Perhaps more surprising is the impossibility involving PC-efficiency: while anonymity, neutrality, SD-strategyproofness, and SD-efficiency characterize the uniform random dictatorship, the axioms become incompatible when moving from SD to PC . Since both impossibilities require m ≥ 4 alternatives, we also show that they turn into possibilities if m ≤ 3.

We start by discussing the impossibility of Condorcetconsistent and strategyproof SDSs.

Theorem 1. Every Condorcet-consistent SDS is PCmanipulable if |N| ≥ 5 is odd and m ≥ 4.

Proof. Assume for contradiction that there is a Condorcetconsistent and PC-strategyproof SDS f for m ≥ 4 alternatives. Subsequently, we focus on the electorate N = {1, . . . , 5} because we can generalize the result to any larger electorate with an odd number of voters by adding pairs of voters with inverse preferences. These voters do not change the Condorcet winner and hence will not affect our analysis.

As the first step, consider the profiles R1 to R4 . The ∗ symbol is a placeholder for all missing alternatives.

Note that b is the Condorcet winner in R2 , a in R3 , and d in R4 . Thus, Condorcet-consistency entails that f(R2 , b) = f(R3 , a) = f(R4 , d) = 1. In contrast, there is no Condorcet winner in R1 and we use PC-strategyproofness to derive f(R1 ). For instance, this axiom postulates that ∑x,y∈A:x≻23 y f(R2 , x)f(R1 , y) ≥ ∑x,y∈A:x≻23 y f(R1 , x)f(R2 , y) as voter 3 can PCmanipulate by deviating from R2 to R1 otherwise. By substituting f(R2 , b) = 1 and f(R2 , x) = 0 for x ∈ A \ {b}, we thus derive that

Analogously, PC-strategyproofness between R1 and R3 and between R1 and R4 entails the following inequalities because voter 4 needs to PC-prefer f(R3 ) to f(R1 ) and voter 3 needs to PC-prefer f(R1 ) to f(R4 ).

Chaining the inequalities together, we get f(R1 ,A \ {a, d}) ≤ f(R1 , a) ≤ f(R1 ,A \ {a, b}) ≤ f(R1 , b), so f(R1 ,A \ {a, b, d}) = 0. Simplifying (1), (2), and (3) then results in f(R1 , a) ≤ f(R1 , d) ≤ f(R1 , b) ≤ f(R1 , a), so f(R1 , a) = f(R1 , b) = f(R1 , d) = 13 .

Next, we analyze the profiles R5 to R8 .

Just as for the profiles R1 to R4 , there is no Condorcet winner in R5 , whereas b is the Condorcet winner in R6 , a in R7 , and c in R8 . Consequently, Condorcet-consistency requires that f(R6 , b) = f(R7 , a) = f(R8 , c) = 1. Next, we use PC-strategyproofness to derive f(R5 ). In particular, we infer the following inequalities as voter 5 needs to PC-prefer f(R5 ) to f(R6 ), voter 4 needs to PC-prefer f(R7 ) to f(R5 ), and voter 2 needs to PC-prefer f(R8 ) to f(R5 ).

Analogous computations as for R1 now show that f(R5 , a) = f(R5 , b) = f(R5 , c) = 1 3 . Finally, note that R1 and R5 only differ in the preferences of voter 2. This means that voter 2 can PC -manipulate by deviating from R5 to R1 since he PC-prefers f(R1 ) to f(R5 ). Hence, f fails PCstrategyproofness, which contradicts our assumptions.

It is open whether Theorem 1 also holds if |N| is even.

Next, we turn the focus to our second impossibility result: every anonymous and neutral SDS that satisfies PC -efficiency is PC-manipulable. For proving this theorem, we first show that every SDS that satisfies the absolute winner property and PC-efficiency is PC-manipulable.

Lemma 1. Every PC-efficient SDS that satisfies the absolute winner property is PC-manipulable if |N| ≥ 3, |N| ̸∈ {4, 6}, and m ≥ 4.

Proof sketch. Assume for contradiction that there are an SDS f and an electorate N ∈ F(N) that satisfy the requirements of the lemma. In this sketch, we focus on m = 4 alternatives as we can extend the construction to more alternatives by adding Pareto-dominated ones. Moreover, we suppose that n = |N| is odd; the argument for even n is similar but more involved. Now, consider the profiles R and R′ shown below.

The goal is to show that f(R, a) = f(R, b) = f(R, c) = 13 and f(R′ , a) = f(R′ , c) = f(R′ , d) = 13 . Then, voter n+1 2 can PC-manipulate by deviating from R′ to R because he PC-prefers f(R) to f(R′ ). We proceed in three steps to derive the lottery f(R): first, we use the absolute winner property and PC -strategyproofness to show that f(R, c) > 0. Next, we infer from PC-efficiency that f(R, d) = 0. Finally, we repeatedly apply PC-strategyproofness and the absolute winner property to prove that f(R, a) ≥ f(R, c) ≥ f(R, b) ≥ f(R, a), which implies that f(R, x) = 13 for x ∈ {a, b, c}. An analogous argument can be used to derive f(R′ ).

Note that Lemma 1 is a rather strong impossibility itself. Next, we use it to prove that every anonymous, neutral, and PC-efficient SDS is PC-manipulable.

Theorem 2. Every anonymous and neutral SDS that satisfies PC-efficiency is PC-manipulable if |N| ≥ 3, |N| ̸∈ {4, 6}, and m ≥ 4.

Proof sketch. We prove this theorem by showing that the given axioms imply the absolute winner property; then, Lemma 1 implies the impossibility. Consider an arbitrary SDS f that satisfies all given axioms and an electorate N ∈ F(N) with n = |N| ≥ 3. Moreover, we focus on three alternatives because, as in Lemma 1, we can extend the argument to more alternatives by assuming that these are Pareto-dominated. We proceed with a case distinction with respect to the parity of n and, in this sketch, restrict attention to even n. Consider the following profile R.

Anonymity and neutrality require that f(R, b) = f(R, c). Next, PC-efficiency implies that f(R, b) = f(R, c) = 0 and hence f(R, a) = 1. Based on this insight, one can prove that a is chosen with probability 1 whenever the voters i ∈ [1 . . . n2 +1] report it as their best alternative. Due to anonymity and neutrality, this statement is equivalent to the absolute winner property.

Since both Theorems 1 and 2 require m ≥ 4 alternatives, we can still hope for a possibility if m ≤ 3. Indeed, for m = 2, ML satisfies Condorcet-consistency, PC -efficiency, PC-strategyproofness, anonymity, and neutrality. However, as shown in Section 2.4, ML fails PC-strategyproofness if m = 3. Thus, we construct another SDS that satisfies all given axioms. To this end, let CW(R) be the set of Condorcet winners in R, and let WCW(R) = {x ∈ A: gR(x, y) ≥ 0 for all y ∈ A \ {x}} be the set of weak Condorcet winners if CW(R) = ∅, and WCW(R) = ∅ otherwise. Then, define the SDS f 1 as follows.

It is easy to see that f 1 is Condorcet-consistent. The next proposition characterizes f 1 as the only SDS that satisfies cancellation and the axioms of Theorem 2.

Proposition 1. For m = 3, f 1 is the only SDS that satisfies PC-efficiency, PC-strategyproofness, neutrality, anonymity, and cancellation.

Proof sketch. The definition of f 1 immediately implies that this SDS satisfies anonymity, neutrality, and cancellation. Moreover, tedious case distinctions establish that f 1 satisfies PC-strategyproofness and PC-efficiency. For the reverse direction, we show first that every SDS that satisfies all given axioms is Condorcet-consistent. Building on this insight, we use the given axioms to infer the outcomes for all profiles.

Remark 1. Of all the axioms in this section besides cancellation, ML only fails PC -strategyproofness, dictatorships only fail anonymity and Condorcet-consistency, and the uniform random dictatorship only fails PC -efficiency and Condorcetconsistency. This shows that all axioms of Theorem 2 but neutrality are required for the result, and that both axioms are required for Theorem 1. We conjecture that Theorem 2 holds even without neutrality. Proposition 1 shows that m ≥ 4 alternatives are required for both Theorems 1 and 2.

3.2 Strict PC-participation

In this section, we investigate strict PC-participation and prove that this axiom is incompatible with PC -efficiency. This result is rather surprising given that multiple SDSs are known to satisfy SD-efficiency and strict SD-participation [Brandl et al., 2015]. Moreover, our impossibility can be seen as a complement to the work of Brandl et al. [2019] which shows that ML satisfies both PC-participation and PC-efficiency. In particular, our result demonstrates that maximal lotteries satisfy a maximal degree of participation subject to PC-efficiency. Finally, since Theorem 3 requires m ≥ 4 alternatives, we construct an SDS that satisfies all our requirements when m ≤ 3. We first discuss the impossibility theorem.

Theorem 3. No neutral and anonymous SDS satisfies both PC -efficiency and strict PC -participation if m ≥ 4.

Proof. Assume for contradiction that there is a neutral and anonymous SDS f that satisfies both PC-efficiency and strict PC-participation. In what follows, we focus on the case m = 4 because we can generalize our construction to m > 4 by adding m- 4 alternatives at the bottom of all voters' preference rankings. Since these dummy alternatives are Paretodominated by the original alternatives, PC-efficiency requires these alternatives to be assigned probability 0, and thus they will not affect our subsequent analysis.

First, consider the following profile with ten voters.

Observe that d is Pareto-dominated by a, so by PC-efficiency, f(R1 , d) = 0. Moreover, since b and c are symmetric in this profile, neutrality and anonymity imply that f(R1 , b) = f(R1 , c). If f(R1 , b) = f(R1 , c) > 0, then f is not PC-efficient because all voters weakly prefer the degenerate lottery that puts probability 1 on a, with voters 1-6 strictly preferring this lottery. Hence, f(R1 , b) = f(R1 , c) = 0 which means that f(R1 , a) = 1.

Next, consider profile R2 , which is obtained by adding

voter 11 with the preference d, a, b, c to R1 . We infer from strict PC -participation that f(R2 , d) > f(R2 , b) + f(R2 , c). Finally, consider profile R3 , which is obtained by adding

voter 12 with the preference d, a, c, b to R2 . Observe that b, c, and d are symmetric in R3 , so by neutrality and anonymity, f(R3 , b) = f(R3 , c) = f(R3 , d). If f(R3 , b) = f(R3 , c) = f(R3 , d) > 0, then f is not PC-efficient because all voters strictly prefer the degenerate lottery that puts probability 1 on a. Hence, f(R3 , b) = f(R3 , c) = f(R3 , d) = 0, which means that f(R3 , a) = 1. Since f(R2 , d) > f(R2 , b) + f(R2 , c), voter 12 has a disincentive to participate in R3 , thereby contradicting the strict PC -participation of f .

Since Theorem 3 requires m ≥ 4, a natural question is whether the impossibility also holds for m ≤ 3. As we demonstrate, the impossibility ceases to hold. If m= 2, it is easy to see that the uniform random dictatorship satisfies all axioms of Theorem 3. For m = 3, however, the uniform random dictatorship fails PC-efficiency (see Section 2.4). In light of this, we construct a new SDS that satisfies all axioms used in Theorem 3. To this end, let B denote the set of alternatives that are never bottom-ranked. Then, the SDS f 2 is defined as follows: return the uniform random dictatorship if |B| ∈ {0, 2}; otherwise, we delete the alternatives x ∈ A \ B that minimize nR(x) (if there is a tie, delete both alternatives) and return the outcome of the uniform random dictatorship for the reduced profile. As the following proposition demonstrates, f 2 indeed satisfies all axioms of Theorem 3 if m = 3.

Proposition 2. For m = 3, f 2 satisfies anonymity, neutrality, PC-efficiency, and strict PC-participation.

Proof sketch. The definition of f 2 immediately implies that this SDS is anonymous and neutral. Next, for proving that f 2 is PC-efficient, we consider the case distinction used in the definition of this SDS: if |B| ∈ {0, 2}, randomizing over the top-ranked alternatives is PC-efficient. On the other hand, if |B| = 1, f 2 is PC-efficient as it ignores one of the top-ranked alternatives. Finally, the strict PC-participation of f 2 follows from a tedious case distinction with respect to B.

Remark 2. Each of PC-efficiency and strict PCparticipation is by itself compatible with anonymity and neutrality, as witnessed by maximal lotteries and the uniform random dictatorship, respectively. Hence, these two axioms are required for Theorem 3. In contrast, we do not know whether anonymity and neutrality are needed for this result. Proposition 2 shows that m ≥ 4 is required.

Remark 3. Strict PC-participation is also incompatible with Condorcet-consistency, i.e., a statement analogous to Theorem 1 holds. This follows from the fact that a single voter cannot always change the Condorcet winner by joining the electorate, even if it is his least preferred outcome. In such cases, Condorcet-consistency implies that the outcome does not change while strict PC-participation requires the opposite.

4 Conclusion

We have studied incentive properties of social decision schemes (SDSs) based on the pairwise comparison (PC) lottery extension, and answered open questions raised by Brandt [2017] by proving three strong impossibilities. In particular, we showed that PC-strategyproofness and strict PC-participation are incompatible with PC-efficiency and Condorcet-consistency (see also Figure 1). We highlight three important aspects and consequences of our results. Firstly, when moving from the standard approach of stochastic dominance (SD) to PC, previously compatible axioms become incompatible. Secondly, our results show that-unlike with other classical impossibilities-PC does not help to circumvent the Gibbard-Satterthwaite theorem. Finally, our impossibilities identify a tradeoff between incentive-compatibility and efficiency. In light of this tradeoff, two SDSs seem particularly appealing: the uniform random dictatorship because it satisfies PC-strategyproofness and strict PC-participation, and maximal lotteries because it satisfies PC-strategyproofness in all profiles that admit a Condorcet winner, Condorcet-consistency, PC-efficiency, and PC-participation.

Acknowledgements

This work was supported by the Deutsche Forschungsgemeinschaft under grants BR 2312/11-2 and BR 2312/12-1, and by an NUS Start-up Grant.