Strategyproof Randomized Social Choice for Restricted Sets of Utility Functions

1 Introduction

When a group of agents wants to find a joint decision in a structured way, they can choose from a multitude of different voting rules. However, it is not clear which rule is the best one as each one has its benefits. This problem lies at the core of social choice theory which draws increased attention by computer scientists because it can be used to reason about computational multi-agent systems (see, e.g., [Chevaleyre et al., 2007; Brandt et al., 2013; Brandt et al., 2016b; Endriss, 2017]). A fundamental requirement for voting rules is strategyproofness, i.e., agents should not be able to benefit by lying about their preferences. In a seminal result, Gibbard [1973] and Satterthwaite [1975] have shown that every deterministic strategyproof voting rule is dictatorial if there are at least three different outcomes possible.

Randomization allows to escape this impossibility the-

(SDSs). These functions aggregate the preferences of agents to lotteries over alternatives which determine for every alternative its winning chances. The final winner is then decided by chance according to these probabilities. While this model allows to circumvent many impossibilities, it is not straightforward how to define strategyproofness because the voters' preferences over lotteries are unclear. Maybe the most prominent approach is to assume that voters use cardinal utility functions on the alternatives to compare lotteries with respect to their expected utilities. However, voters still report ordinal preference relations to the SDS and hence, strategyproofness is defined by quantifying over utility functions: an SDS is strategyproof if voting honestly maximizes the expected utility for every voter and every utility function that is consistent with his true preferences. This strategyproofness notion, often called SD-strategyproofness, has been analyzed by Gibbard [1977] and Barber`a [1979] who prove that all SD-strategyproof SDSs are indecisive because they almost always randomize over multiple alternatives. Even more, Benoˆıt [2002] has shown that SD-strategyproofness is incompatible with the basic democratic idea that an alternative should be the winner of an election if an absolute majority of the voters report it as their best alternative.

While it is unfortunate that SD-strategyproofness does not allow for decisive SDSs, this strategyproofness notion seems also too demanding for because in many applications not all utility functions are plausible. For instance, when a representative body votes about budget proposals, it seems reasonable that similar proposals have similar utilities. Thus, we might neglect utility functions with a large gap between such options when discussing strategyproofness. This observation leads to the new notion of U-strategyproofness which requires that truth telling only maximizes the expected utility of a voter if his utility function is in the set U. Note that Ustrategyproofness does not forbid utility functions u ̸∈ U, but voters with such utility functions might be able to manipulate.

U-strategyproofness allows for a more detailed analysis than SD-strategyproofness because we can analyze the exact set of utility functions U for which an SDS is Ustrategyproof. Conversely, we can also formulate strong impossibility results based on U-strategyproofness for severely restricted sets U and thus, we can pinpoint the source of manipulability far more detailed than with other strategyproofness notions. Hence, U-strategyproofness offers both the possibility of positive results by finding U-strategyproof SDSs for large sets U, and of strong impossibility results by using only a small number of utility functions. Furthermore, information about U-strategyproofness can also be valuable in practice: if the social planner can roughly guess the utility functions of the voters, he might be able to choose an SDS preventing manipulations. Even if the social planner does not have such insights, he might opt for an SDS that is Ustrategyproof for a large set U as such an SDS is immune to manipulations frommost voters.

Other than introducing U-strategyproofness, we use this new notion to investigate the trade-off between strategyproofness and decisiveness. On the positive side, we show that there are U-strategyproof SDSs that assign an alternative probability 1 whenever all but k > 0 voters agree that it is the best option if the utility functions in U value the best alternative much more than the other alternatives. Moreover, we prove for rank-based SDSs that this gap in the utility functions is required to be strategyproof and that it must increase in k. On the other hand, we show that Condorcet-consistency is incompatible with U-strategyproofness if the set U satisfies minimal symmetry conditions between preference relations and there are m ≥ 4 alternatives. If there are only three alternatives and an odd number of voters, the Condorcet rule is characterized by U-strategyproofness for the set U of all equi-distant utility functions and Condorcet-consistency. The proofs of these theorems and of all propositions are omitted because of space limitations.

2 RelatedWork

To our knowledge, we are the first authors who explicitly investigate U-strategyproofness. Nevertheless, ideas similar to U-strategyproofness have been used before. For instance, Sen [2011] and Mennle and Seuken [2021] define strategyproofness by considering restricted sets of utility functions and thus, their works can be interpreted as first results on U-strategyproofness. Moreover, in set-valued social choice (where the outcome of an election is a non-empty set of alternatives instead of a lottery) preferences over sets of alternatives are often derived from utility functions. For instance, Duggan and Schwartz [2000] and Benoˆıt [2002] employ this approach to motivate their strategyproofness notions. The relationship between these results and U-strategyproofness is discussed in more detail in Section 4.

There are also various results on other strategyproofness notions in randomized social choice (see, e.g., [Gibbard, 1977; Hoang, 2017; Aziz et al., 2018; Brandl et al., 2018]), many of which are surveyed by Brandt [2017]. These results either prove the incompatibility of strategyproofness with other axioms or characterize specific SDSs. Our results differ from previous ones as we investigate a different question: instead of asking whether an SDS is strategyproof according to some definition, we ask for which utility functions it is strategyproof.

Moreover, strategyproofness is often considered for restricted domains of preference profiles (see, e.g., [Ehlers et al., 2002; Bogomolnaia et al., 2005; Chatterji and Zeng, 2018]). For instance, Bogomolnaia et al. [2005] discuss an attractive SD-strategyproof SDS for dichotomous preferences. U-strategyproofness can be interpreted similarly, but we focus on utility functions instead of preference profiles: Ustrategyproof SDSs are immune to manipulations if we only allow utility functions in U.

Another field related to U-strategyproofness is cardinal social choice, where the input of social decision schemes consists of the utility functions of the voters. If we allow all utility functions as input, every strategyproof cardinal SDS is, under mild additional assumptions, a variant of a random dictatorship (see, e.g., [Hylland, 1980; Dutta et al., 2007; Nandeibam, 2013]). As noted by Dutta et al. [2007], these negative results break down if the domain of cardinal SDSs is restricted, but this setting is not well understood. Our results provide insights in this problem because every Ustrategyproof SDS can be interpreted as a cardinal SDS that is strategyproof on the domain U.

Finally, note that our model assumptions are quite similar to those used in the analysis of the distortion of SDSs (see, e.g., [Procaccia and Rosenschein, 2006; Gross et al., 2017; Abramowitz et al., 2019]). Just as these authors, we assume that voters only report ordinal preferences but use utility functions to evaluate the quality of a lottery. Whereas distortion focuses on the welfare of SDSs, we investigate their resistance to strategic behavior of voters.

3 Preliminaries

Let N = {1, . . . , n} be a finite set of voters and let A be a set containing m alternatives. A preference relation is an antisymmetric, transitive, complete, and reflexive binary relation on A and Ri denotes the preference relation of voter i. We compactly represent preference relations as comma-separated lists. Let R denote the set of all preference relations on A. A preference profile R is an n-tuple containing the preference of every voter i ∈ N, i.e., R ∈ Rn . When writing preference profiles, we indicate the corresponding voter directly before the preference relation to clarify which voter submits which preference relation. For example, 1 : a, b, c indicates that voter 1 reports that he prefers a to b to c.

In this paper, we discuss social decision schemes (SDSs), which are functions that map preference profiles to lotteries on A. A lottery p is a function from the set of alternatives A to the interval [0, 1] such that ∑x∈A p(x) = 1. Let ∆(A) denote the set of all lotteries on A. Formally, a social decision scheme is a function f : Rn → ∆(A) and we denote with f(R, x) the probability assigned to x by the lottery f(R).

The definition of SDSs allows for a huge variety of functions, some of which seem not desirable. Therefore, we introduce axioms to narrow down the set of SDSs. Two basic fairness axioms are anonymity and neutrality, which require that voter and alternatives, respectively, are treated equally. More formally, an SDS f is anonymous if f(R) = f(π(R)) for all profiles R and permutations π : N → N, and neutral if f(R, x) = f(τ(R), τ(x)) for all alternatives x ∈ A, profiles R, and permutations τ : A → A. Another natural axiom is unanimity, which requires of an SDS f that f(R, x) = 1 for all preference profiles R in which all voters agree that x is the best choice. While this axiom is so weak that is often considered indisputable, it is also irrelevant in practice as ballots are usually not unanimous. Therefore, we introduce the stronger notion of k-unanimity: an SDS f is k-unanimous if f(R, x) = 1 whenever n - k or more voters report x as the best alternative. By definition, unanimity is equal to 0-unanimity and note that k-unanimity is only well-defined if k < n2 . A well-known strengthening of kunanimity is Condorcet-consistency. For defining this axiom, let nxy(R) = |{i ∈ N : xRiy}| - |{i ∈ N : yRix}| denote the majority margin between two alternatives x, y ∈ A in the preference profile R. An alternative x is the Condorcet winner in a preference profile R if nxy(R) > 0 for all other alternatives y ∈ A\{x}. Less formally, an alternative x is the Condorcet winner if it is preferred to every other alternative by a majority of the voters. Finally, an SDS f is Condorcetconsistent if f(R, x) = 1 for all profiles R and alternatives x ∈ A such that x is the Condorcet winner in R.

An important class of SDSs are rank-based SDSs. The basic idea of these schemes is that voters assign ranks to the alternatives and that an SDS should only rely on these ranks, but not on which voter assigns which rank to an alternative. For formalizing this concept, we denote with r(Ri, x) = |{y ∈ A: yRix}| the rank of alternative x in voter i's preference relation. Moreover, we define the rank vector r∗ (R, x) as the vector that contains the rank of x with respect to every voter in increasing order, i.e., r∗ (R, x)i ≤ r∗ (R, x)i+1 for all i ∈ {1, . . . , n - 1}, and the rank matrix r∗ (R) as the matrix that contains the rank vectors of all alternative as rows. Finally, we call an SDS f rank-based if it only depends on the rank matrix, i.e., f(R) = f(R′ ) for all preference profiles R, R′ with r∗ (R) = r∗ (R′ ). The set of rank-based SDSs contains many prominent functions such as point scoring rules and anonymous SDSs that only depend on the first-ranked alternatives of the voters.

4 U-Strategyproofness

A central problem in social choice is that of manipulability: voters may lie about their preferences to achieve a better outcome. While the definition of a manipulation is easy if an SDS never randomizes between multiple alternatives, it is not clear how to compare non-degenerate lotteries. A classical approach for this problem is to assume that voters are endowed with utility functions ui : A → R. We impose the constraint that no voter assigns the same utility to two alternatives, i.e., ui(x) ̸= ui(y) for all voters i ∈ N and alternatives x, y ∈ A, to ensure that the ordinal preference relation induced by a utility function is anti-symmetric. We denote with U the set of all such utility functions and say that a utility function u ∈ U is consistent with a preference relation R if u(x) ≥ u(y) iff xRy for all alternatives x, y ∈ A. Finally, each voter i uses his utility function ui to compare lotteries by their expected utilities E[p]ui = ∑x∈A p(x)ui(x), i.e., voter i prefers lottery p weakly to lottery q if E[p]ui ≥ E[q]ui .

Even though we assume the existence of utility functions, voters only report ordinal preferences. Consequently, strategyproofness is often defined by quantifying over utility functions. In particular, Gibbard [1977] employs this approach to define SD-strategyproofness: an SDS f is SD-strategyproof if E[f(R)]ui ≥ E[f(R′ )]ui for all voters i ∈ N, preference profiles R, R′ , and utility functions ui ∈ U such that ui is consistent with Ri and Rj = R′j for all j ∈ N \ {i}. While SD-strategyproofness allows for strong negative results (see, e.g. [Gibbard, 1977; Barber`a, 1979]), it lacks relevance for many practical applications as not all utility functions are plausible. Also, SD-strategyproofness provides often only shallow theoretical insights as it is not possible to pinpoint the source of manipulability.

In order to address these problems, we introduce a new strategyproofness notion by restricting the set of feasible utility functions U beforehand: an SDS f is U-strategyproof if E[f(R)]ui ≥ E[f(R′ )]ui for all voters i ∈ N, preference profiles R, R′ , and utility functions ui ∈ U such that ui is consistent with Ri and Rj = R′j for all j ∈ N \ {i}. Less formally, U-strategyproofness only requires that voters with a utility function in U cannot increase their expected utility by misrepresenting their preferences. Hence, U-strategyproofness is equal to SD-strategyproofness and smaller sets of utility functions result in less demanding strategyproofness notions. Note that U-strategyproofness solves both problems of SDstrategyproofness: we can investigate whether an SDS is manipulable in practice by dismissing implausible utility functions, and we can find the core of impossibility results by determining the minimally required set of utility functions. Next, we discuss an example to illustrate the difference between U-strategyproofness and SD-strategyproofness.

Example 1. Consider the profiles R1 and R2 shown below and let f denote an SDS such that f(R1 , x) = 13 for x ∈ {a, b, c} and f(R2 , b) = 1. Moreover, consider the utility functions u1, u2, and u3 with u1(a) = 2, u1(b) = 1, u1(c) = 0, u2(a) = 3, u2(b) = 1, u2(c) = 0, u3(a) = 3, u3(b) = 2, and u3(c) = 0. These utility functions are only consistent with voter 1's preference relation in R1 , and thus, we can check whether this voter can benefit by deviating to R2 . A quick calculation shows that E[f(R1 )]u1 = 1 = E[f(R2 )]u1 , E[f(R1 )]u2 = 4 3 > 1 = E[f(R2 )]u2 , and E[f(R1 )]u3 = 5 3 < 2 = E[f(R2 )]u3 . Hence, voter 1 can increase his expected utility if his utility function is u3 and thus, f is SD-manipulable. In contrast, voter 1 does not benefit from deviating to R2 if his utility function is u1 or u2. Since the preferences of the other voters are not consistent with u1, u2, and u3, it follows that f is {u1, u2}-strategyproof on these two profiles.

R1 :

1: a, b, c

2: b, c, a

3: c, a, b

R2 :

1: b, a, c

2: b, c, a

3: c, a, b

In our results, we always consider U-strategyproofness for symmetric sets U, i.e., we assume that u ∈ U implies that uπ = u ◦ π ∈ U for every permutation π on A. This formalizes the natural condition that all preference relations should be treated equally. Moreover, the symmetry condition is rather weak since every neutral SDS is U ′ -strategyproof for a symmetric set U ′ if it is U-strategyproof for a set U ̸= ∅.

Proposition 1. If a neutral SDS is U-strategyproof for a set U ̸= ∅, it is U ′ -strategyproof for a symmetric set U ′ with U ⊆ U ′ .

A special case of our symmetry assumption is that U consists of a single utility function u and its renamings, i.e., that U = {u ◦ π : π ∈ Π}, where Π denotes the set of all permutations on A. In this case, we write uΠ-strategyproofness instead of U-strategyproofness. Note that uΠ-strategyproofness associates every preference relation with exactly one utility function, whereas {u}-strategyproofness, i.e., strategyproofness for a single utility function u, only affects a single preference relation. Since the utility of an alternative only depends on its rank for uΠ-strategyproofness, we often write u(k) to denote the utility of the k-th best alternative of a voter. As the next proposition shows, it suffices to consider uΠ-strategyproofness or even {u}-strategyproofness because for every SDS f and every preference relation Ri, the set of utility functions u that are consistent with Ri and for which f is strategyproof is convex.

Proposition 2. For every SDS f and preference relation Ri, the set URi = {u ∈ U : u is consistent with Ri and f is {u}-strategyproof} is convex.

We can use this proposition to show that an SDS is Ustrategyproof for a large set U by proving that it is uΠi - strategyproof for a few utility functions ui ∈ {u1, . . . , ul}. Assuming that u1, . . . , ul are all consistent with a preference relation Ri, it follows then from Proposition 2 that the SDS is ˆuΠ-strategyproof for every utility function ˆu that can be represented as a convex mixture of u1, . . . , ul, which means that it is U-strategyproof for a large set U.

Next, note that U-strategyproofness inherits many attractive properties from SD-strategyproofness: for instance, the convex combination of U-strategyproof SDSs is itself Ustrategyproof, i.e., the set of U-strategyproof SDSs is convex for every set U. As a consequence of this observation, it is often possible to construct an anonymous U-strategyproof SDS based on a non-anonymous U-strategyproof SDS. Another similarity between U-strategyproofness and SDstrategyproofness is that both axioms disincentivize even manipulations from groups of voters with the same preferences.

Finally, observe that U-strategyproofness can be used to transfer results from set-valued social choice to the probabilistic setting. We explain this relation using the impossibility result of Benoˆıt [2002] as example. This theorem states that strategyproofness is incompatible with 1-unanimity for set-valued social choice functions if voters prefer every subset of their best two alternatives to every other set and other in our model negligible conditions are satisfied. For formulating this result for SDSs, we have to compare lotteries only based on their support supp(p) = {x ∈ A: p(x) > 0}. Hence, let ϵf = minx∈A,R∈Rn :f(R,x)>0 f(R, x) denote the smallest non-zero probability assigned to an alternative by the SDS f and note that ϵf is well-defined since SDSs are defined for a fixed set of alternatives and voters. Given this probability, we derive that every voter whose utility function u satisfies u(2) > (1 - ϵf)u(1) + ϵfu(3) prefers every lottery that randomizes only over his best two alternatives to every other lottery. After rearranging this equation, we can formulate Benoˆıt's impossibility as follows.

Proposition 3. No SDS f satisfies both uΠ-strategyproofness and 1-unanimity if u(1)-u(2) < ϵf 1-ϵf (u(2)-u(3)), m ≥ 3, and n ≥ 3.

Note that Proposition 3 highlights the central requirement of Benoˆıt's impossibility theorem: voters must be close to indifferent between their best two alternatives. This refines Benoˆıt's reasoning who justifies his strategyproofness notion with voters who "like his or her two favorite alternatives "much more" than the rest of the alternatives". 1 Based on this approach, we can also formalize other impossibility results from set-valued social choice with U-strategyproofness.

5 Results

In the sequel, we employ U-strategyproofness to analyze the trade-off between strategyproofness and decisiveness. In particular, we investigate two decisiveness axioms: kunanimity and Condorcet-consistency. The first axiom allows for positive results if suitable utility functions are considered, whereas Condorcet-consistency is incompatible with uΠ-strategyproofness for every utility function u ∈ U.

5.1 k-unanimity

A central result of Gibbard [1977], who attributes it to Hugo Sonnenschein, is that the SDS called random dictatorship (henceforth RD) is the only SD-strategyproof SDS that satisfies unanimity and anonymity. This SDS assigns an alternative x in a profile R the probability PL(R,x) n , where PL(R, x) = |{i ∈ N : ∀y ∈ A : xRiy}| denotes the plurality score of alternative x. A common method for executing RD is to choose a voter uniformly at random and to return his most preferred alternative as winner. While RD is one of the most attractive SD-strategyproof SDSs, it violates kunanimity for k > 0. Even more, Benoˆıt [2002] has shown that every SD-strategyproof SDS fails k-unanimity for k > 0.

However, we can define a variant of RD that satisfies both k-unanimity for an arbitrary k ∈ {0, . . . , ⌊ n-1 2 ⌋} and Ustrategyproofness for a large set of utility functions U. Hence, consider the following SDS, which we call k-random dictatorship (abbreviated by RD k ): if at least n - k voters agree that alternative x is the best choice, assign alternative x a probability of 1; otherwise, return the outcome of RD. As we show in Theorem 1, RD k satisfies U-strategyproofness for U = {u ∈ U : u(1) - u(2) ≥ k(u(2) - u(m))}, i.e., if voters have a strong preference for the first alternative, RD k is strategyproof. Unfortunately, the definition of U depends on k, i.e., for large values of k, there must be an extremely large gap between u(1) and u(2). Another variant of RD, which we refer to as OMNI ∗ , solves this problem. This SDS assigns probability 1 to an alternative x if more than half of the voters report x as their best alternative, and otherwise randomizes uniformly among all alternatives that are at least once top-ranked. This SDS is U-strategyproof for U = {u ∈ U : u(1) - u(2) ≥ ∑mi=3 u(2) - u(i)}. While OMNI ∗ satisfies ⌊ n-1 2 ⌋-unanimity for all numbers of voters and alternatives, the condition on U seems only realistic if there are few alternatives.

1 Benoˆıt [2002] also discusses a variant for SDSs in which he uses the minimal non-zero probability assigned to an alternative. However, Benoˆıt only gives an example showing that there is a suitable utility function such that the required preferences over sets extend to preferences over lotteries.

Theorem 1. For every k ∈ {1, . . . , ⌊ n-1 2 ⌋}, RD k satisfies U-strategyproofness for U = {u ∈ U : u(1) - u(2) ≥ k(u(2) - u(m))} and violates {u}-strategyproofness for every utility function u ̸∈ U. Moreover, OMNI ∗ satisfies U-strategyproofness for U = {u ∈ U : u(1) - u(2) ≥ ∑mi=3 u(2)-u(i)} and violates {u}-strategyproofness for every utility function u ̸∈ U.

The constraint on the set U for RD k arises naturally by considering the preference profile in which n - k - 1 voters top-rank the second best alternative of voter i and the remaining k voters top-rank voter i's least preferred alternative. In this situation, voter i can ensure that his second best alternative is chosen with probability 1 by reporting it as his best one. Solving the corresponding inequality required by Ustrategyproofness leads to the bound on U. A similar worstcase analysis can be applied for OMNI ∗ .

While it is positive that k-unanimity and U-strategyproofness can be simultaneously satisfied at all, the bounds on the sets U in Theorem 1 become increasingly worse with large k and m. This raises the question for less demanding bounds on the utility functions. As our next theorem shows, the approach used for defining RD k and OMNI ∗ has not much space for improvement as both SDSs are rank-based.

Theorem 2. There is no rank-based SDS that satisfies uΠstrategyproofness and k-unanimity for 0 < k < n2 if m ≥ 3, n ≥ 3, and u(1) - u(2) < ∑mi=max(3,m-k+1) u(2) - u(i).

The proof of Theorem 2 works by contradiction: we assume that there is a k-unanimous rank-based SDS f that satisfies uΠ-strategyproofness for a utility function u with u(1) - u(2) < ∑mi=max(3,m-k+1) u(2) - u(i). Moreover, let k∗ = min(k,m- 2). Our analysis then starts at a profile R where n - k∗ voters favor a the most, which implies that f(R, a) = 1 due to k-unanimity. The central argument is a rather involved construction that shows that a voter can weaken alternative a from the first rank to the second one without affecting the outcome. By repeatedly applying this construction, we eventually arrive at a profile R′ where only k∗ voters top-rank a and the remaining voters top-rank b, but f(R′ , a) = 1. This is in conflict with k-unanimity as n-k∗ ≥ n-k voters report b as best choice but f(R′ , b) ̸= 1.

Remark 1. A computer-aided approach has shown that there are rather technical SDSs that satisfy k-unanimity and uΠ-strategyproofness for utility functions u with u(1) - u(2) < ∑mi=max(3,m-k+1) u(2) - u(i) if we dismiss rankbasedness and m ≤ 4. Hence, rank-basedness is required for Theorem 2. Moreover, most bounds of the theorem are tight: if m = 2, OMNI ∗ and RD k are even SDstrategyproof, and if n = 2, k-unanimity is not well-defined for k > 0. Furthermore, the condition on the utility functions is almost tight: RD 1 shows that the bound is tight for 1-unanimity, and OMNI ∗ shows that the bound is tight if k ≥ m - 2. Finally, RD k shows that no constraint of the type u(1) - u(2) ≤ ∑mi=m-k+1 u(2) - u(i) + ϵ with ϵ > 0 can result in an impossibility because we can always find a utility function u such that ∑mi=m-k+1 u(2) - u(i) + ϵ ≥ u(1) - u(2) ≥ k(u(2) - u(m)) by making the difference between u(i) and u(m) for i ≥ 3 sufficiently small. Nevertheless, it remains open to find rank-based SDSs that satisfy Ustrategyproofness and k-unanimity for U = {u ∈ U : u(1) - u(2) = ∑mi=m-k+1 u(2) - u(i)} and 2 ≤ k ≤ m - 3.

Remark 2. Theorem 1 and Theorem 2 have an intuitive interpretation: if voters strongly prefer their best alternative, it becomes possible to achieve strategyproofness and decisiveness. This follows as strategyproofness is compatible with kunanimity if there is a sufficiently large gap between u(1) and u(2). In contrast, it is impossible that an SDS satisfies both axioms if voters are close to indifferent between their best two alternatives. For the class of general SDSs, this is shown by Benoˆıt [2002], and for the class of rank-based SDSs, Theorem 2 significantly weakens the requirements on the utility functions.

Remark 3. Figure 1 illustrates the results of this section. For this figure, we assume that there are 5 alternatives and a large number of voters n ≥ 11, and we fix all utilities but u(1). Hence, we can compute the values of u(1) for all SDSs of Theorem 1 such that the considered SDS is uΠstrategyproof. The figure shows that for RD k , the required value of u(1) increases in k and the bound of OMNI ∗ is independent of k. Moreover, the required values of u(1) are quite large compared to u(2) for all SDSs but RD. However, the red area shows the values of u(1) for which Theorem 2 applies and hence, these large values are indeed required. The white area shows that there is a small gap between the positive results in Theorem 1 and the impossibility in Theorem 2.

5.2 Condorcet-consistency

As there are even rank-based SDS that are k-unanimous and U-strategyproof for large sets U, the question arises whether stronger decisiveness notions can be achieved by dismissing rank-basedness. Unfortunately, we find a negative answer to this question by considering Condorcet-consistency.

Theorem 3. There is no Condorcet-consistent SDS that satisfies uΠ-strategyproofness regardless of the utility function u if m ≥ 4, n ≥ 5 and n ̸= 6, n ̸= 8.

The proof of this result works by contradiction and relies on a case distinction on the utility function u. If u(1)-u(2) < u(2)-u(m), the utility of the second best alternative is larger than the average utility, which means that a voter can manipulate by making his second best alternative into the Condorcet winner. If u(1) - u(m - 1) > u(m - 1) - u(m), voters value their second worst alternative less than the uniform lottery. As a consequence, there is a voter who can manipulate by weakening his second worst alternative such that it is no longer the Condorcet winner. Finally, note that these two cases are exhaustive: the strictness of the utility function u entails that u(m - 1) - u(m) < u(1) - u(m - 1) if u(1) - u(2) ≥ u(2) - u(m) and m ≥ 4.

A close inspection of the proof shows that the impossibility also holds if m = 3 unless U only contains equi-distant utility functions, i.e., utility functions with u(1) - u(2) = u(2) - u(3). This raises the question whether there is a U-strategyproof SDS that satisfies Condorcet-consistency in this special case. Indeed, the Condorcet rule (abbreviated by COND), which assigns probability 1 to the Condorcet winner whenever it exists and returns the uniform lottery over all alternatives otherwise, satisfies U-strategyproofness for this set. Even more, the Condorcet rule is uniquely characterized by these axioms if n is odd.

Theorem 4. COND is the only Condorcet-consistent SDS that satisfies U-strategyproofness for U = {u ∈ U : u(1) - u(2) = u(2) - u(3)} if m = 3 and n is odd.

It is easy to show that the Condorcet-rule is Ustrategyproof for U = {u ∈ U : u(1) - u(2) = u(2) - u(3)} if m = 3 because the uniform lottery on all three alternatives has for every voter the expected utility of u(2). Hence, the proof mainly focuses on why no other Condorcet-consistent SDS f satisfies U-strategyproofness for this set U. For this, we show that there is a profile R and a voter i such that voter i's expected utility E[f(R)]u is less than u(2). Moreover, this voter can either make his second best alternative into the Condorcet winner or revert to a preference profile in which each alternative is chosen with a probability of 13 . As both cases yield an expected utility of u(2) for voter i, we have found a contradiction to U-strategyproofness.

Remark 4. The Condorcet rule is also U-strategyproof for the set of equi-distant utility functions if m = 3 and n is even. However, other SDSs satisfy Condorcet-consistency and Ustrategyproofness for even n, too. For instance, the SDS that assigns the Condorcet winner probability 1 whenever it exists and uniformly randomizes among the top-ranked alternatives otherwise satisfies also all required axioms. The proof for this claim relies on the insight that every voter has a utility of at least u(2) in the absence of a Condorcet winner.

Remark 5. Awell-known class of SDSs are tournament solutions which only depend on the majority relation RM = {(x, y) ∈ A2 : nxy(R) ≥ nyx(R)} of the input profile R to compute the outcome. For these SDSs, unanimity and uΠstrategyproofness entail Condorcet-consistency. Thus, there are no unanimous and uΠ-strategyproof tournament solutions, regardless of the utility function u, if m ≥ 4. This is in harsh contrast to results for set-valued social choice, where attractive tournament solutions satisfy various strategyproofness notions (see, e.g., [Brandt et al., 2016a]).

Remark 6. The proof of Theorem 3 also reveals more insights about the compatibility of k-unanimity and uΠstrategyproofness for general SDSs. In particular, the first case shows that no ⌈ n3 ⌉-unanimous SDS can be uΠstrategyproof for a utility function u with u(1) - u(2) < u(2) - u(m) if m ≥ 4 and n ≥ 3.

6 Conclusion and Discussion

We study a new strategyproofness notion called Ustrategyproofness. Whereas the common notion of SDstrategyproofness is derived by quantifying over all utility functions, U-strategyproofness is derived by quantifying only over the utility functions in a specified set U. This new strategyproofness notion arises from practical observations as often not all utility functions are plausible, and also has theoretical advantages because it allows for a much finer analysis than SD-strategyproofness. Furthermore, we analyze the compatibility of U-strategyproofness and decisiveness axioms such as k-unanimity and Condorcet-consistency. In particular, we discuss SDSs that satisfy k-unanimity for any k with 0 < k < n/2 and U-strategyproofness if the set U only contains utility functions u for which u(1)-u(2) is sufficiently large. Moreover, we show for rank-based SDSs that the large gap between u(1) and u(2) is required to be strategyproof and has to increase in k. We also prove that U-strategyproofness is incompatible with Condorcet-consistency if the set U is symmetric and m ≥ 4. This impossibility also holds if m = 3 unless the utility functions in U are equi-distant. In this special case and if n is odd, the Condorcet rule can be characterized by U-strategyproofness and Condorcet-consistency.

Our results have a very intuitive interpretation: strategyproofness is only compatible with decisiveness if each voter has a clear best alternative. Even more, the more decisiveness is required, the stronger voters have to favor their best alternative. This conclusion is highlighted by Theorems 1 and 2 as well as the impossibility of Benoˆıt [2002]. Moreover, it coincides with the informal argument that it is easier to manipulate for a voter who deems many alternatives acceptable as he can just report another acceptable alternative as his best one. Hence, our results show that the main source of manipulability are voters who are close to indifferent between some alternatives.

Acknowledgments

This work was supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/12-1. I thank the anonymous reviewers and Felix Brandt for helpful comments.