Introduction
Voting is used to aggregate the preferences of a group of stakeholders over a set of alternatives in order to arrive at a shared group decision [14 , 38 ] . Voting rules frequently operate on a ranking over alternatives provided by each voter, yet voters often have an underlying intensity of preference or utility associated with each alternative. Voters, who may be part of a human society or a digital agent such as a recommender system [1 ] or AI agent, may not even know their exact utility over alternatives; this might arise from uncertain or changing human preferences, lack of alignment between human preferences and AI agent representatives [16 ] , or even noisiness in a communication environment. As a result, ordinal rankings are relied upon to achieve good outcomes from a voting procedure. The quality of such a procedure might be measured in two ways: First, voting rules may be desirable due to the axiomatic properties which they satisfy. Second, voting rules aim to optimize some target function based on voter preferences.
Under the axiomatic perspective, much work studies voting procedures which provably satisfy some set of desirable principles for all possible preferences [38 ] . For instance, a system designer might wish to ensure that a single voter does not have unilateral control over election outcomes (non-dictatorship) or that an alternative who is preferred head-to-head against all other alternatives is always selected (Condorcet consistency). The optimization view, which we focus on in this paper, sees the goal of a voting rule as finding some outcome that maximizes a target function. This may be, for example, a straightforward sum of voter utilities — known as utilitarian welfare. A frequent focus of research is on
worst-case analysis; finding the voting rule which maximizes the worst possible outcome that a voting rule might produce [30 ] .
Recently, the optimization view has been shown effective on axiomatic settings using black-box techniques, i.e., machine learning, to find novel rules that rarely violate axioms, rather than provably satisfying axioms [15 , 25 ] . These approaches show the existence of such rules but are not immediately useful in practice. An optimization approach constrained to a bounded class of rules, such as score based rules, has shown that the axiomatic approach can be cleanly combined with optimization to blend these schools of thought [10 ] .
Contribution. We focus on the optimization task of maximizing a broad class of function over voter utilities: the power mean , which includes special cases such as utilitarian (utility sum), Nash (utility product), and egalitarian (min utility) welfare functions. We find that deterministic positional scoring rules (PSRs) asymptotically maximize welfare and explore how the optimal rule changes based on utility distribution and power mean. These rules are particularly desirable as an optimization target as they are well understood axiomatically [33 , 37 ] , thus blending both schools of voting. This work generalizes and extends prior results for specific instances of the power mean family [3 , 13 ] . Among our results, we introduce a novel description of the rule exactly optimizing Nash social welfare and strengthen previous results on egalitarian welfare. We also show that the best randomized PSR is always a k k k -approval rule and, under a minimal assumption on voter independence, is plurality. These contributions are summarized in Table 1 . Experimental analysis supports these results and finds the optimized positional scoring vector for distributions outside of our theoretical analysis, highlighting open questions for future research and suggesting that the well-known Borda rule may prove to maximize social welfare on certain highly structured preference domains.
Table 1. Average-case welfare maximizing PSRs. Results with no citation are new. We show deterministic rules asymptotically maximize power mean welfare across all social choice functions. *: Apesteguia et al. [3 ] provide non-asymptotic, non-PSRs exactly maximizing welfare. †: With neutrality on alternatives and independence among voters this is plurality.
Related Work
Much of the past work is focused on a worst-case analysis and many papers have explored the optimization of utilitarian social welfare. We find less work that studies other social welfare functions.
Average Case Analysis Several previous works have studied the rule which maximizes utilitarian social welfare and few that study other functions. Weber [36 ] assumes voter utilities are distributed independently and uniformly on an interval and show that Borda asymptotically maximizes utilitarian welfare. Bordley [12 ] and Merrill [26 ] use computer simulation to expand these results to additional utility distributions and voting rules in the utilitarian setting. Borda was shown to be the optimal score vector for expected utilitarian welfare by Apesteguia et al. [3 ] , when utilities are sampled i.i.d. from a uniform distribution for all voters. Under a slightly different model, Boutilier et al. [13 ] also show that expected utilitarian welfare is maximized by a scoring rule based on the order statistics of the underlying utility distribution and, on uniform utilities, is the Borda vector for any number of voters. Later work shows a novel positional scoring rule, binomial voting , approximately maximizes utilitarian welfare [21 ] . Pivato [28 ] shows Borda is highly likely to elect the alternative maximizing social welfare in a given profile, under varying utility distributions. Experimental analysis also shows that on Euclidean preferences, Borda typically results in much higher utilitarian welfare than other voting rules [22 ] .
Worst Case Analysis Early work from Procaccia and Rosenschein [30 ] introduced distortion as a measure of the worst-case quality of voting rules and shows that many deterministic PSRs, such as Borda and Veto, have unbounded distortion. Subsequent work shows that despite poor worst-case welfare, all PSRs can be learned with an efficient number of samples in polynomial time, highlighting the possibility of attempting to learn novel PSRs optimized for a metric of interest, such as expected welfare [31 ] . Boutilier et al. [13 ] show that a randomized rule based on the harmonic score vector ( 1 , 1 / 2 , 1 / 3 , … ) (1,1/2,1/3,\ldots) ( 1 , 1/2 , 1/3 , … ) is near-optimal for utilitarian distortion.
Optimization of Non-Utilitarian SW In addition to their utilitarian result, Apesteguia et al. [3 ] also show that egalitarian and maximax welfare are not optimized by a PSR as social welfare cannot be exactly represented as a summation over per-voter terms. Use of the power mean function as a welfare function in voting was first proposed by Cousins [17 ] who apply a sample-complexity approach to identify possible causes of systemic bias. This is extended to the weighted power mean function by Pardeshi et al. [27 ] who study the PAC-learnability of welfare functions based on their weights. A similar welfare function has also been used in studying fair allocations [8 , 9 ] . The optimization of arbitrary utility functions has been discussed by Armstrong et al. [4 ] and applied to a measure of axiomatic satisfaction [15 ] . Nash-based rules have been studied normatively for allocations [2 ] and voting [5 ] . Aziz et al. [5 ] detail properties of a Nash rule which takes as input voter utilities but do not comment on ordinal rules. Ebadian et al. [18 ] study Nash welfare and show that a rule exists which can always achieve within a Θ ( log m ) \Theta(\log m) Θ ( log m ) approximation to the best welfare.
Model
Following a typical model of voting [38 ] , we have a set of alternatives A = { a 1 , a 2 , … , a m } A=\{a_1,a_2,\ldots,a_m\} A = { a 1 , a 2 , … , a m } and a set of voters V = { v 1 , v 2 , … , v n } V=\{v_1,v_2,\ldots,v_n\} V = { v 1 , v 2 , … , v n } . We assume each voter v i v_i v i draws a utility vector ( u i ( a ) ) a ∈ A (u_i(a))_{a\in A} ( u i ( a ) ) a ∈ A from a distribution D D D over R ≥ 0 m \mathbb{R}_{\ge0}^m R ≥ 0 m , giving a utility function u i : A → R ≥ 0 u_i:A\to\mathbb{R}_{\ge0} u i : A → R ≥ 0 where u i ( a ) u_i(a) u i ( a ) denotes the utility to v i v_i v i if a a a is selected as a winner. The set of utility functions indexed by voter is called a utility profile u \mathbf{u} u .
Each utility function induces a preference order σ \sigma σ over the alternatives A A A , where σ ( a ) \sigma(a) σ ( a ) refers to the rank of a a a in σ \sigma σ and the collection of all preference orders is a preference profile. For a voter v i v_i v i , σ i \sigma_i σ i denotes a strict ordering over A A A such that σ i ( a ) < σ i ( a ′ ) ⟺ u i ( a ) > u i ( a ′ ) \sigma_i(a)<\sigma_i(a')\Longleftrightarrow u_i(a)>u_i(a') σ i ( a ) < σ i ( a ′ ) ⟺ u i ( a ) > u i ( a ′ ) . That is, v i v_i v i prefers a a a over a ′ a' a ′ if, and only if, v i v_i v i receives more utility from the election of a a a than from the election of a ′ a' a ′ . Let σ \boldsymbol{\sigma} σ refer to the preference profile containing all orderings induced by a utility profile u \mathbf{u} u . The sets of all possible utility and preference profiles are denoted, respectively, U \mathbb{U} U and P \mathbb{P} P . We use the term “profile” to refer to both types of profile as contextually appropriate.
We introduce three utility assumptions used throughout.
(A1) Voters draw their utility vectors independently from the same neutral distribution D D D on ( 0 , ∞ ) m (0,\infty)^m ( 0 , ∞ ) m . D D D is unchanged when the alternatives are relabelled and the joint distribution of utility profiles is anonymous and neutral.
(A1†) Each voter’s utilities for the m m m alternatives are i.i.d. draws from a distribution with CDF F F F , shared between all voters.
(A2) No voter assigns equal utility to two alternatives and each ranking σ i \sigma_i σ i is strict.
Under A1 and A2 our model matches the utility assumptions used by Boutilier et al. [13 ] . If we use A1† and A2 we instead get the model of Apesteguia et al. [3 ] . A1 allows utilities over alternatives to be correlated within a single voter’s preference order while under A1† does not. Unless stated otherwise we assume A1 and A2.
Positional Scoring Rules
A social choice function (SCF) f : P → 2 A ∖ ∅ f:\mathbb{P}\to2^A\setminus\varnothing f : P → 2 A ∖ ∅ maps a preference profile to a non-empty set of winning alternatives. An SCF is called resolute if it always returns a single winning alternative [38 ] .
We focus on a special class of SCFs known as positional scoring rules (PSR) which are parameterized by a score vector s = ( s 1 , … , s m ) \mathbf{s}=(s_1,\ldots,s_m) s = ( s 1 , … , s m ) . PSRs assign a score to each alternative based on the number of times it is ranked in each position: S s ( a , σ ) = ∑ σ i ∈ σ s σ i ( a ) S_s(a,\sigma)=\sum_{\sigma_i\in\sigma}s_{\sigma_i(a)} S s ( a , σ ) = ∑ σ i ∈ σ s σ i ( a ) . We assume scores are always non-negative. We consider both deterministic and randomized PSRs. In the deterministic setting winning alternatives are exactly those who receive the maximal score, f s ( σ ) = { a ∈ A ∣ S s ( a , σ ) = max a ′ ∈ A S s ( a ′ , σ ) } f_s(\sigma)=\{a\in A\mid S_s(a,\sigma)=\max_{a'\in A}S_s(a',\sigma)\} f s ( σ ) = { a ∈ A ∣ S s ( a , σ ) = max a ′ ∈ A S s ( a ′ , σ )} . In the randomized setting (denoted f s R f_s^R f s R ), a single winner is chosen with probability directly proportional to their score; Pr [ f s R ( σ ) = a ] = S s ( a , σ ) / ( n s ) \Pr[f_s^R(\sigma)=a]=S_s(a,\sigma)/(ns) Pr [ f s R ( σ ) = a ] = S s ( a , σ ) / ( n s ) , where s ˉ = ∑ j = 1 m s j \bar{s}=\sum_{j=1}^m s_j s ˉ = ∑ j = 1 m s j . Observe that, in the deterministic setting, scoring vectors can be scaled additively and multiplicatively without changing the outcome of the corresponding PSR, and can be scaled multiplicatively in the randomized setting. Any rule we refer to as “unique” is unique only up to these transformations.
We say that a PSR f s f_s f s is feasible if s i ≥ s i + 1 ∀ 1 ≤ i < m s_i\ge s_{i+1}\ \forall\ 1\le i<m s i ≥ s i + 1 ∀ 1 ≤ i < m and s 1 > s m s_1>s_m s 1 > s m . For simplicity we typically denote feasible deterministic PSRs as s = ( 1 , … , 0 ) s=(1,\ldots,0) s = ( 1 , … , 0 ) . In the literature there are a number of classic PSRs that are considered canonical such as Plurality: ( 1 , 0 , … , 0 ) (1,0,\ldots,0) ( 1 , 0 , … , 0 ) ; Veto: ( 1 , 1 , … , 0 ) (1,1,\ldots,0) ( 1 , 1 , … , 0 ) ; Borda: ( m − 1 , m − 2 , … , 0 ) (m-1,m-2,\ldots,0) ( m − 1 , m − 2 , … , 0 ) ; Harmonic [13 ] : s h = ( 1 , 1 / 2 , 1 / 3 , … , 1 / m ) s^h=(1,1/2,1/3,\ldots,1/m) s h = ( 1 , 1/2 , 1/3 , … , 1/ m ) , and Binomial [21 ] : s j b i = ∑ k = j m ( k j ) s_j^{bi}=\sum_{k=j}^m\binom{k}{j} s j bi = ∑ k = j m ( j k ) . All of these PSRs, visualized in Figure 1 , target normative ideas of a correct score for each rank. e.g., Plurality models a winner-take-all mentality, while Borda linearly scales reward for candidates with their rank. We consider only resolute rules here and can transform any non-resolute social choice function into a resolute SCF with a tie-breaking method. Two tie-breaking methods are common: lexicographic, and random [6 , 19 ] . Lexicographic tie-breaking requires an ordering over alternatives and would violate rule neutrality so when ties occur we select a winner uniformly at random.
Figure 1. The canonical score vectors discussed in Section 3.
Social Welfare
A social welfare function (SWF) is a function W : R n × A → R W : \mathbb{R}^{n} \times A \to\mathbb{R} W : R n × A → R which uses the utility each voter would receive from the election of alternative a a a to compute a single numeric value representing the quality of a a a as a social decision. Different SWFs aim to capture different aspects of quality and may be more or less appropriate in varying settings [32 ] . We write W ( { u i ( a ) ∀ i ∈ V } , a ) W(\{u_i(a) \ \forall\ i \in V\}, a) W ({ u i ( a ) ∀ i ∈ V } , a ) and assume that W W W is computable in polynomial time. Due to the range of fairness concerns we focus on a general family of social welfare functions, the power mean, which generalizes existing welfare functions into a single parameterized model [27 ] , defined (slightly abusing notation) as,
W P M ( u , a , p ) = { ( 1 n ∑ i = 1 n u i ( a ) p ) 1 p if p ≠ 0 , ( ∏ i = 1 n u i ( a ) ) 1 n if p = 0. W^{\mathrm{PM}}(\mathbf{u},a,p)=
\begin{cases}
\left(\frac{1}{n}\sum_{i=1}^{n}u_i(a)^p\right)^{\frac{1}{p}} & \text{if } p\ne0,\\
\left(\prod_{i=1}^{n}u_i(a)\right)^{\frac{1}{n}} & \text{if } p=0.
\end{cases} W PM ( u , a , p ) = { ( n 1 ∑ i = 1 n u i ( a ) p ) p 1 ( ∏ i = 1 n u i ( a ) ) n 1 if p = 0 , if p = 0.
Based on the parameter p ∈ [ − ∞ , ∞ ] p \in[-\infty,\infty] p ∈ [ − ∞ , ∞ ] , W P M W^{\mathrm{PM}} W PM can reduce to a number of special cases from the literature [3 , 13 ] . We treat p = ± ∞ p=\pm\infty p = ± ∞ as the min and max functions which are approached in the limit.
( p = 1 ) (p=1) ( p = 1 ) : 1 n ∑ i ∈ V u i ( a ) \frac{1}{n}\sum_{i\in V}u_i(a) n 1 ∑ i ∈ V u i ( a ) measures the mean utility across all voters, i.e., utilitarian social welfare . This can be maximized when a single voter receives a large amount of utility, or when all voters receive increased utility.
( p = 0 ) (p=0) ( p = 0 ) : ∏ i ∈ V u i ( a ) 1 n \prod_{i\in V}u_i(a)^{\frac{1}{n}} ∏ i ∈ V u i ( a ) n 1 measures the geometric mean of all voter’s utility and is maximized when voter utilities are both high and equal . Corresponds directly with Nash welfare .
( p → − ∞ ) (p\to-\infty) ( p → − ∞ ) : min i ∈ V ( u i ( a ) ) \min_{i\in V}(u_i(a)) min i ∈ V ( u i ( a )) is based on only a single voter’s utility, and is maximized when the voter receiving the lowest amount of utility receives as high utility as possible. This is referred to as Egalitarian or Rawlsian social welfare.
( p → ∞ ) (p\to\infty) ( p → ∞ ) : max i ∈ V u i ( a ) \max_{i\in V}u_i(a) max i ∈ V u i ( a ) is also based on a single voter’s utility but is maximized when the voter receiving the most utility receives high utility. This function, referred to as Maximax , largely represents unfairness and is included primarily as a special case of the power mean function.
Social Welfare Optimization
We now discuss our optimization framework. We focus on analyzing average-case social welfare
and study voting rules which maximize this asymptotically. We first introduce assumptions used in our theoretical results.
Assumptions. Let U U U denote a voter’s utility for a fixed alternative (by A1 voter and alternative identity do not matter here). Let U ( 1 ) > U ( 2 ) > ⋯ > U ( m ) U_{(1)}>U_{(2)}>\cdots>U_{(m)} U ( 1 ) > U ( 2 ) > ⋯ > U ( m ) denote voter’s utilities in descending order (strict by A2), so that U ( k ) U_{(k)} U ( k ) is the utility of that voter that voter ranks in position k k k . We use this non-standard notation for order statistics so that U ( i ) U_{(i)} U ( i ) corresponds with the indexing of s i s_i s i in a score vector. For fixed p ∈ R p\in\mathbb{R} p ∈ R , ψ p : ( 0 , ∞ ) → R \psi_p:(0,\infty)\to\mathbb{R} ψ p : ( 0 , ∞ ) → R is the Box-Cox transform,
ψ p ( t ) = { t p − 1 p if p ≠ 0 , log t if p = 0. (1) \psi_p(t)=
\begin{cases}
\frac{t^p-1}{p} & \text{if }p\ne0,\\
\log t & \text{if }p=0.
\end{cases} \tag*{(1)} ψ p ( t ) = { p t p − 1 log t if p = 0 , if p = 0. (1)
which Lemma 1 shows is continuous, strictly increasing, and satisfies ψ p ( W P M ( u , a , p ) ) = 1 n ∑ i ψ p ( u i ( a ) ) \psi_p(W^{\mathrm{PM}}(\mathbf{u},a,p))=\frac{1}{n}\sum_i\psi_p(u_i(a)) ψ p ( W PM ( u , a , p )) = n 1 ∑ i ψ p ( u i ( a )) . Many of our proofs rely on the assumption below which holds for every p p p whenever the support of D D D lies in [ ε , M ] [\varepsilon,M] [ ε , M ] for some 0 < ε < M < ∞ 0<\varepsilon<M<\infty 0 < ε < M < ∞ .
(A3) For fixed p p p , E [ ψ p ( U ) 2 ] < ∞ \mathbb{E}[\psi_p(U)^2]<\infty E [ ψ p ( U ) 2 ] < ∞ and E [ U q ] < ∞ \mathbb{E}[U^q]<\infty E [ U q ] < ∞ for some q > max { 2 , p } q>\max\{2,p\} q > max { 2 , p } .
Definition 1 (Expected Social Welfare). Fix p ∈ R ∪ { ± ∞ } p\in\mathbb{R}\cup\{\pm\infty\} p ∈ R ∪ { ± ∞ } and let u \mathbf{u} u be a random utility profile of n n n voters, with induced preference profile σ \sigma σ . The expected social welfare of a (possibly randomized) resolute social choice function f f f is
ESW p ( f ) = E [ W P M ( u , f ( σ ) , p ) ] . \operatorname{ESW}_p(f)=\mathbb{E}\left[W^{\mathrm{PM}}(\mathbf{u},f(\sigma),p)\right]. ESW p ( f ) = E [ W PM ( u , f ( σ ) , p ) ] . where the expectation is over u \mathbf{u} u and randomness of f f f (tie-breaking or a randomized winner), which is independent of u \mathbf{u} u given σ \sigma σ .
By A1 every preference profile occurs with positive probability, so f f f maximizes ESW p \operatorname{ESW}_p ESW p over all social choice functions if, and only if, at every preference profile σ \sigma σ it selects an alternative in arg max a ∈ A E [ W P M ( u , a , p ) ∣ σ ] \arg\max_{a\in A}\mathbb{E}[W^{\mathrm{PM}}(\mathbf{u},a,p)\mid\sigma] arg max a ∈ A E [ W PM ( u , a , p ) ∣ σ ] . This matches the average-case optimality definition of Boutilier et al. [13 ] .
Definition 2 (Average-Case Optimal). Let OPT n = max g ESW p ( g ) \operatorname{OPT}_n=\max_g\operatorname{ESW}_p(g) OPT n = max g ESW p ( g ) , where the maximum is over all (possibly randomized) SCFs g g g on n n n voters. We say that f f f is asymptotically average-case optimal if
lim n → ∞ OPT n − ESW p ( f ) OPT n − ESW p ( f 1 ) = 0. \lim_{n\to\infty}\frac{\operatorname{OPT}_n-\operatorname{ESW}_p(f)}{\operatorname{OPT}_n-\operatorname{ESW}_p(f_{\mathbf{1}})}=0. n → ∞ lim OPT n − ESW p ( f 1 ) OPT n − ESW p ( f ) = 0. where 1 = ( 1 , … , 1 ) \mathbf{1}=(1,\ldots,1) 1 = ( 1 , … , 1 ) and f 1 f_{\mathbf{1}} f 1 prioritizes uniform random selection of a winning alternative. That is, in the limit, the welfare gap between the optimal rule and f f f shrinks more quickly than the gap between the optimal rule and welfare resulting from a uniform random selection. By A1, every alternative approaches the same expected welfare as n n n grows, so the ESW of every rule converges to the same limit. The ratio magnifies the difference between rules as n n n grows, so suboptimal rules stay positive in the limit.
Optimal Deterministic Rules
This section examines deterministic PSRs – the winning alternative(s) are exactly those which receive maximal points. We assume any ties among winners are broken uniformly at random. We first show that, for finite p p p , the voting rule that maximizes expected power mean social welfare belongs to the family of PSRs. This follows from Young [37 ] who identifies a basic set of axioms which characterize the family of scoring correspondences, and extends the proof of Boutilier et al. [13 ] around the setting of utilitarian social welfare. Here, we identify the score vectors which maximize expected social welfare for any parameterization of the power mean family. The optimal score vector is based on the order statistic of D D D .
Theorem 4.1. Fix p ∈ R p \in\mathbb{R} p ∈ R and assume A3. There is a score vector s ∈ R m \mathbf{s} \in\mathbb{R}^{m} s ∈ R m such that the positional scoring rule f s f_{\mathbf{s}} f s is asymptotically average-case optimal. Additionally, when p = 1 p = 1 p = 1 , f s f_{\mathbf{s}} f s maximizes ESW 1 \operatorname{ESW}_{1} ESW 1 over all social choice functions for every n n n .
Theorem 4.1 applies Young’s characterization (Lemma 2) of scoring rules to the objective E [ ∑ i = 1 n ψ p ( u i ( a ) ) ∣ σ ] \mathbb{E}\left[\sum_{i=1}^{n}\psi_p(u_i(a)) \mid\boldsymbol{\sigma}\right] E [ ∑ i = 1 n ψ p ( u i ( a )) ∣ σ ] , which is additive across voters, and shows that this objective determines ESW p \operatorname{ESW}_p ESW p up to an additive o ( n − 1 2 ) o(n^{-\frac{1}{2}}) o ( n − 2 1 ) (Lemma 3). All missing proofs are in Appendix A.
The Shape of Optimality
Our primary theoretical result asymptotically describes the structure of the average-case optimal scoring vector for neutral utility distributions across the family of power mean social welfare functions. Each result below states which of the assumptions from Section 3.2.1 it relies on, and the optimal score vector is expressed through the Box-Cox transform ψ p \psi_p ψ p of Equation (1).
Theorem 4.2. Fix p ∈ R p \in\mathbb{R} p ∈ R , assume A3, and let s k ∗ ( p ) = E [ ψ p ( U ( k ) ) ] s_k^*(p) = \mathbb{E}[\psi_p(U_{(k)})] s k ∗ ( p ) = E [ ψ p ( U ( k ) )] for k = 1 , … , m k = 1,\ldots,m k = 1 , … , m . For every score vector s ∈ R m \mathbf{s} \in\mathbb{R}^{m} s ∈ R m the limit
Δ p ( s ) = lim n → ∞ 1 n 2 ( ESW p ( f s ∗ ( p ) ) − ESW p ( f s ) ) \Delta_p(\mathbf{s}) = \lim_{n \to\infty} \frac{1}{n^2}\left(\operatorname{ESW}_p(f_{\mathbf{s}^*(p)})-\operatorname{ESW}_p(f_{\mathbf{s}})\right) Δ p ( s ) = n → ∞ lim n 2 1 ( ESW p ( f s ∗ ( p ) ) − ESW p ( f s ) ) exists and is nonnegative, and Δ p ( s ) = 0 \Delta_p(\mathbf{s}) = 0 Δ p ( s ) = 0 if, and only if, s = s ∗ ( p ) \mathbf{s} = \mathbf{s}^*(p) s = s ∗ ( p ) . That is, s ∗ ( p ) \mathbf{s}^*(p) s ∗ ( p ) is the unique asymptotically average-case optimal PSR.
Together, Theorems 4.1 and 4.2 show that ESW p \operatorname{ESW}_p ESW p is asymptotically maximized by a positional scoring rule, and that this rule is s ∗ ( p ) \mathbf{s}^*(p) s ∗ ( p ) .
Remark 1 (Asymptotic Results and Limit on p p p ). Prior work finds an average case optimal score vector when p = 1 p = 1 p = 1 for any number of voters by splitting expected welfare into separate terms for each voter [13 ] . Here, the power 1 p \frac{1}{p} p 1 in W P M W^{\mathrm{PM}} W PM prevents such a decomposition except when p = 1 p = 1 p = 1 (Utilitarian; already known) and p = 0 p = 0 p = 0 (Nash; after taking logarithms which gives an exact score vector dependent on n n n ). We rely on the fact that, as n n n grows, each voter’s marginal contribution to W P M W^{\mathrm{PM}} W PM shrinks and W P M W^{\mathrm{PM}} W PM becomes near linear in per-voter terms ψ p ( u i ( a ) ) \psi_p(u_i(a)) ψ p ( u i ( a )) with negligible, bounded error (Lemma 3). As min and max functions are determined by a single element they admit no decomposition into per-voter terms, so Theorems 4.1 and 4.2 do not extend to p = ± ∞ p = \pm\infty p = ± ∞ . We cover these cases in Theorems A.3 and A.4.
Optimizing for Traditional SW Functions
The result of Theorem 4.2 is quite abstract. We now discuss the implications of the theorem for each of the named social welfare functions discussed earlier. The first result, for utilitarian social welfare, is exactly that found in prior work from Boutilier et al. [13 ] . In each case we continue to assume A3 holds.
Corollary 1 (Utilitarian; p = 1 p = 1 p = 1 ). For every n n n , the positional scoring rule with vector s ∗ ( 1 ) = ( E [ U ( 1 ) ] , E [ U ( 2 ) ] , … , E [ U ( m ) ] ) \mathbf{s}^*(1) = (\mathbb{E}[U_{(1)}],\mathbb{E}[U_{(2)}],\ldots,\mathbb{E}[U_{(m)}]) s ∗ ( 1 ) = ( E [ U ( 1 ) ] , E [ U ( 2 ) ] , … , E [ U ( m ) ]) maximizes ESW 1 \operatorname{ESW}_1 ESW 1 over all social choice functions.
Corollary 2 (Nash; p = 0 p = 0 p = 0 ). The positional scoring rule with score vector s ∗ ( 0 ) = ( E [ log U ( 1 ) ] , E [ log U ( 2 ) ] , … , E [ log U ( m ) ] ) \mathbf{s}^*(0) = (\mathbb{E}[\log U_{(1)}],\mathbb{E}[\log U_{(2)}],\ldots,\mathbb{E}[\log U_{(m)}]) s ∗ ( 0 ) = ( E [ log U ( 1 ) ] , E [ log U ( 2 ) ] , … , E [ log U ( m ) ]) is asymptotically average-case optimal for ESW 0 \operatorname{ESW}_0 ESW 0 and is the only positional scoring rule with this property.
Both Corollary 1 and 2 follow from a direct application of Theorem 4.2. We can also write a version of the Nash-optimal rule which is exactly optimal for a fixed, finite number of voters.
Corollary 3 (Exact Nash; p = 0 p = 0 p = 0 ). For each n n n , the positional scoring rule with score vector
s k ( n ) = n log E [ U ( k ) 1 / n ] , k = 1 , … , m , s_k^{(n)} = n\log\mathbb{E}\left[U_{(k)}^{1/n}\right], \qquad k = 1,\ldots,m, s k ( n ) = n log E [ U ( k ) 1/ n ] , k = 1 , … , m , maximizes ESW 0 \operatorname{ESW}_0 ESW 0 over all social choice functions on n n n voters. Additionally, as n → ∞ n \to\infty n → ∞ , s k ( n ) s_k^{(n)} s k ( n ) decreases to s k ∗ ( 0 ) = E [ log U ( k ) ] s_k^*(0) = \mathbb{E}[\log U_{(k)}] s k ∗ ( 0 ) = E [ log U ( k ) ] .
Proof. Nash welfare is a product of one component per voter. Conditional on σ \sigma σ , these components are independent and u i ( a ) u_i(a) u i ( a ) is distributed as U ( σ i ( a ) ) U_{(\sigma_i(a))} U ( σ i ( a )) (Lemma 4), so the expectation of the product is the product of expectations. Taking logs,
log E [ W P M ( u , a , 0 ) ∣ σ ] = ∑ i = 1 n log E [ U σ i ( a ) 1 / n ] = 1 n s s ( n ) ( a , σ ) . \log\mathbb{E}[W^{\mathrm{PM}}(u,a,0)\mid\sigma] = \sum_{i=1}^{n}\log\mathbb{E}\left[U_{\sigma_i(a)}^{1/n}\right] = \frac{1}{n}s_{\mathbf{s}^{(n)}}(a,\sigma). log E [ W PM ( u , a , 0 ) ∣ σ ] = i = 1 ∑ n log E [ U σ i ( a ) 1/ n ] = n 1 s s ( n ) ( a , σ ) .
Thus the alternative with the highest expected Nash welfare is exactly the alternative with the highest score under s ( n ) \mathbf{s}^{(n)} s ( n ) , and f s ( n ) f_{\mathbf{s}^{(n)}} f s ( n ) is optimal at every profile. □ \square □
Like utilitarian welfare, Nash welfare also admits an optimal score vector for any n n n . Unlike the utilitarian vector the Nash-optimal vector depends on n n n . The results for the case of p → ± ∞ p \to\pm\infty p → ± ∞ are more involved. For Corollary 4 and 5 we require A1+ and A2; that is, each voter samples utilities i.i.d. from D D D with a continuous CDF F F F .
Corollary 4 (Maximax; p → + ∞ p \to+\infty p → + ∞ ). As p → + ∞ p \to+\infty p → + ∞ , the score vector s ∗ ( p ) \mathbf{s}^*(p) s ∗ ( p ) of the unique asymptotically average-case optimal positional scoring rule, normalized so that s 1 ∗ ( p ) = 1 s_1^*(p) = 1 s 1 ∗ ( p ) = 1 and s m ∗ ( p ) = 0 s_m^*(p) = 0 s m ∗ ( p ) = 0 , converges to the plurality vector s P = ( 1 , 0 , … , 0 ) \mathbf{s}^{P} = (1,0,\ldots,0) s P = ( 1 , 0 , … , 0 ) .
Proof. Since s k ∗ ( p ) = ( E [ U ( k ) p ] − 1 ) / p s_k^*(p) = (\mathbb{E}[U_{(k)}^p]-1)/p s k ∗ ( p ) = ( E [ U ( k ) p ] − 1 ) / p , the normalized scores are ( r k ( p ) − r m ( p ) ) / ( 1 − r m ( p ) ) (r_k(p)-r_m(p))/(1-r_m(p)) ( r k ( p ) − r m ( p )) / ( 1 − r m ( p )) where r k ( p ) : = E [ U ( k ) p ] / E [ U ( 1 ) p ] r_k(p) := \mathbb{E}[U_{(k)}^p]/\mathbb{E}[U_{(1)}^p] r k ( p ) := E [ U ( k ) p ] / E [ U ( 1 ) p ] , so it suffices to show r k ( p ) → 0 r_k(p) \to0 r k ( p ) → 0 for k > 1 k > 1 k > 1 . Using the standard order-statistic density of U ( k ) U_{(k)} U ( k ) under our descending convention,
E [ U ( k ) p ] = m ! ( k − 1 ) ! ( m − k ) ! ∫ 0 ∞ x p F ( x ) m − k ( 1 − F ( x ) ) k − 1 d F ( x ) , \mathbb{E}[U_{(k)}^p] = \frac{m!}{(k-1)!(m-k)!}\int_0^\infty x^p F(x)^{m-k}(1-F(x))^{k-1}\,dF(x), E [ U ( k ) p ] = ( k − 1 )! ( m − k )! m ! ∫ 0 ∞ x p F ( x ) m − k ( 1 − F ( x ) ) k − 1 d F ( x ) ,
E [ U ( 1 ) p ] = m ∫ 0 ∞ x p F ( x ) m − 1 d F ( x ) . \mathbb{E}[U_{(1)}^p] = m\int_0^\infty x^p F(x)^{m-1}\,dF(x). E [ U ( 1 ) p ] = m ∫ 0 ∞ x p F ( x ) m − 1 d F ( x ) .
Both integrals share the factor x p d F ( x ) x^p\,dF(x) x p d F ( x ) . Define the probability measure d Q p ( x ) = x p d F ( x ) / E [ U p ] dQ_p(x) = x^p\,dF(x)/\mathbb{E}[U^p] d Q p ( x ) = x p d F ( x ) / E [ U p ] , which is well-defined since E [ U p ] < ∞ \mathbb{E}[U^p] < \infty E [ U p ] < ∞ and sample X ∼ Q p X \sim Q_p X ∼ Q p . Factoring E [ U p ] \mathbb{E}[U^p] E [ U p ] from both integrals and cancelling, the ratio becomes
r k ( p ) = ( m − 1 k − 1 ) E Q p [ F ( X ) m − k ( 1 − F ( X ) ) k − 1 ] E Q p [ F ( X ) m − 1 ] . r_k(p) = \binom{m-1}{k-1}\frac{\mathbb{E}_{Q_p}\left[F(X)^{m-k}(1-F(X))^{k-1}\right]}{\mathbb{E}_{Q_p}\left[F(X)^{m-1}\right]}. r k ( p ) = ( k − 1 m − 1 ) E Q p [ F ( X ) m − 1 ] E Q p [ F ( X ) m − k ( 1 − F ( X ) ) k − 1 ] .
As p → + ∞ p \to+\infty p → + ∞ , Q p Q_p Q p concentrates near sup ( F ) \sup(F) sup ( F ) , the largest possible utility, where F ( x ) → 1 F(x) \to1 F ( x ) → 1 , so ( 1 − F ( x ) ) k − 1 → 0 (1-F(x))^{k-1} \to0 ( 1 − F ( x ) ) k − 1 → 0 while the denominator → 1 \to1 → 1 . So r k ( p ) → 0 r_k(p) \to0 r k ( p ) → 0 for k > 1 k > 1 k > 1 , giving s P \mathbf{s}^{P} s P in the limit. □ \square □
Corollary 5 (Egalitarian; p → − ∞ p \to-\infty p → − ∞ ). As p → − ∞ p \to-\infty p → − ∞ , the score vector s ∗ ( p ) \mathbf{s}^*(p) s ∗ ( p ) of the unique asymptotically average-case optimal positional scoring rule, normalized so that s 1 ∗ ( p ) = 1 s_1^*(p) = 1 s 1 ∗ ( p ) = 1 and s m ∗ ( p ) = 0 s_m^*(p) = 0 s m ∗ ( p ) = 0 , converges to the veto vector s V = ( 1 , … , 1 , 0 ) \mathbf{s}^{V} = (1,\ldots,1,0) s V = ( 1 , … , 1 , 0 ) .
The proof is similar to the proof of Corollary 4. Corollary 4 and 5 describe the optimal score vector s ∗ ( p ) \mathbf{s}^{*}(p) s ∗ ( p ) as p → ± ∞ p \to\pm\infty p → ± ∞ , they are not identical to expected maximax or egalitarian welfare as our results take n → ∞ n \to\infty n → ∞ for a fixed and finite p p p . The corollaries also require A3 which mildly restricts D D D . For example, Corollary 5 fails on the uniform distribution on ( 0 , 1 ) (0,1) ( 0 , 1 ) but holds whenever the support of D D D lies in [ ε , M ] [\varepsilon,M] [ ε , M ] for 0 < ε < M < ∞ 0 < \varepsilon< M < \infty 0 < ε < M < ∞ . Appendix A shows that veto and plurality are asymptotically optimal for exact egalitarian/maximax cases. These results complement Apesteguia et al. [3 ] who describe optimal non-scoring rules for egalitarian and maximax settings.
Optimizing Randomized Rules
We now provide a characterization of the optimal randomized PSR. Under mild assumptions on utility and anonymity, k k k -approval maximizes ESW among randomized PSRs. Assuming voter independence and neutrality, the randomized plurality rule maximizes ESW.
While Theorem 4.2 shows that deterministic PSRs maximize expected welfare among all social choice functions, randomized PSRs are nonetheless of interest as they have desirable normative properties. For instance, randomized PSRs are strategy-proof while deterministic PSRs are not [7 , 20 ] . We first introduce notation to aid our theorems. Let s ( k ) = ( 1 , … , 1 , 0 , … , 0 ) \mathbf{s}^{(k)}=(1,\ldots,1,0,\ldots,0) s ( k ) = ( 1 , … , 1 , 0 , … , 0 ) denote the k k k -approval vector, with k k k ones followed by m − k m-k m − k zeros, so that s ( 1 ) \mathbf{s}^{(1)} s ( 1 ) is plurality. For an arbitrary voter i i i and position j j j , let b i j b_{ij} b ij be the alternative that voter i i i ranks in position j j j . Fix p ∈ [ − ∞ , ∞ ] p \in[-\infty,\infty] p ∈ [ − ∞ , ∞ ] and define
v j : = E [ W P M ( u , b i j , p ) ] , v ˉ k : = 1 k ∑ j = 1 k v j , v_j := \mathbb{E}\left[W^{\mathrm{PM}}(u,b_{ij},p)\right], \qquad\bar{v}_k := \frac{1}{k}\sum_{j=1}^{k}v_j, v j := E [ W PM ( u , b ij , p ) ] , v ˉ k := k 1 j = 1 ∑ k v j ,
the expected welfare of a voter’s j j j -th choice, and the average expected welfare over a voter’s top k k k choices. This gives an alternative equation for expected social welfare with anonymous voters:
ESW p ( f s R ) = ∑ j = 1 m s j s ˉ ⋅ 1 n ∑ i = 1 n E [ W P M ( u , b i j , p ) ] = ∑ j = 1 m s j v j ∑ j = 1 m s j . \operatorname{ESW}_p(f_{\mathbf{s}}^{\mathrm{R}})=\sum_{j=1}^{m}\frac{s_j}{\bar{s}}\cdot\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[W^{\mathrm{PM}}(u,b_{ij},p)\right]=\frac{\sum_{j=1}^{m}s_jv_j}{\sum_{j=1}^{m}s_j}. ESW p ( f s R ) = j = 1 ∑ m s ˉ s j ⋅ n 1 i = 1 ∑ n E [ W PM ( u , b ij , p ) ] = ∑ j = 1 m s j ∑ j = 1 m s j v j .
Theorem 5.1. Fix p ∈ [ − ∞ , ∞ ] p \in[-\infty,\infty] p ∈ [ − ∞ , ∞ ] . Assume utilities are anonymous, rankings are strict, and E [ u i ( a ) ] < ∞ \mathbb{E}[u_i(a)]<\infty E [ u i ( a )] < ∞ for all i ∈ V i \in V i ∈ V and a ∈ A a \in A a ∈ A .
(a) (No weight on suboptimal positions.) Let v ∗ = max j v j v^*=\max_j v_j v ∗ = max j v j . For every s \mathbf{s} s with ∑ j s j > 0 \sum_j s_j>0 ∑ j s j > 0 , ESW p ( f s R ) ≤ v ∗ \operatorname{ESW}_p(f_{\mathbf{s}}^{\mathrm{R}})\leq v^* ESW p ( f s R ) ≤ v ∗ , with equality if, and only if, s j = 0 s_j=0 s j = 0 for every j j j with v j < v ∗ v_j<v^* v j < v ∗ .
(b) (k-approval maximizes ESW.) Let v ˉ ∗ = max k v ˉ k \bar{v}^*=\max_k\bar{v}_k v ˉ ∗ = max k v ˉ k and K ∗ = { k : v ˉ k = v ˉ ∗ } K^*=\{k:\bar{v}_k=\bar{v}^*\} K ∗ = { k : v ˉ k = v ˉ ∗ } . For every feasible score vector s \mathbf{s} s , ESW p ( f s R ) ≤ v ˉ ∗ \operatorname{ESW}_p(f_{\mathbf{s}}^{\mathrm{R}})\leq\bar{v}^* ESW p ( f s R ) ≤ v ˉ ∗ . Randomized k k k -approval attains this if, and only if, k ∈ K ∗ k\in K^* k ∈ K ∗ .
Proof. (a) We have ESW p ( f s R ) = ∑ j w j v j \operatorname{ESW}_p(f_{\mathbf{s}}^{\mathrm{R}})=\sum_j w_jv_j ESW p ( f s R ) = ∑ j w j v j with weights w j = s j / s ˉ w_j=s_j/\bar{s} w j = s j / s ˉ , which are nonnegative and sum to 1. Therefore
v ∗ − ESW p ( f s R ) = ∑ j = 1 m w j ( v ∗ − v j ) . v^*-\operatorname{ESW}_p(f_{\mathbf{s}}^{\mathrm{R}})=\sum_{j=1}^{m}w_j(v^*-v_j). v ∗ − ESW p ( f s R ) = j = 1 ∑ m w j ( v ∗ − v j ) .
Each product w j ( v ∗ − v j ) w_j(v^*-v_j) w j ( v ∗ − v j ) is nonnegative, so the sum is zero, i.e., ESW p ( f s R ) = v ∗ \operatorname{ESW}_p(f_{\mathbf{s}}^{\mathrm{R}})=v^* ESW p ( f s R ) = v ∗ , if and only if every product is zero; that is, if and only if w j = 0 w_j=0 w j = 0 whenever v j < v ∗ v_j<v^* v j < v ∗ .
(b) Let s \mathbf{s} s be a feasible score vector, and write d k d_k d k for the drop in score after position k k k : d k = s k − s k + 1 d_k=s_k-s_{k+1} d k = s k − s k + 1 for k < m k<m k < m , and d m = s m d_m=s_m d m = s m . The drops from position j j j onwards add up to the score at position j j j , so
s j = ∑ k = j m d k and s = ∑ k = 1 m d k s ( k ) . (2) s_j=\sum_{k=j}^{m}d_k
\qquad\text{and}\qquad
\mathbf{s}=\sum_{k=1}^{m}d_k\mathbf{s}^{(k)}. \tag*{(2)} s j = k = j ∑ m d k and s = k = 1 ∑ m d k s ( k ) . (2)
With m = 3 m=3 m = 3 , ( 1 , 1 2 , 0 ) (1,\frac{1}{2},0) ( 1 , 2 1 , 0 ) has d = ( 1 2 , 1 2 , 0 ) \mathbf{d}=(\frac{1}{2},\frac{1}{2},0) d = ( 2 1 , 2 1 , 0 ) and is 1 2 ( 1 , 0 , 0 ) + 1 2 ( 1 , 1 , 0 ) \frac{1}{2}(1,0,0)+\frac{1}{2}(1,1,0) 2 1 ( 1 , 0 , 0 ) + 2 1 ( 1 , 1 , 0 ) .
We reformulate ESW in terms of drops. Substituting (2) and swapping the order of summation (both run over all pairs j ≤ k j\leq k j ≤ k ),
∑ j = 1 m s j v j = ∑ j = 1 m ∑ k = j m d k v j = ∑ k = 1 m d k ∑ j = 1 k v j = ∑ k = 1 m d k k v ˉ k , \sum_{j=1}^{m}s_jv_j=\sum_{j=1}^{m}\sum_{k=j}^{m}d_kv_j=\sum_{k=1}^{m}d_k\sum_{j=1}^{k}v_j=\sum_{k=1}^{m}d_kk\bar{v}_k, j = 1 ∑ m s j v j = j = 1 ∑ m k = j ∑ m d k v j = k = 1 ∑ m d k j = 1 ∑ k v j = k = 1 ∑ m d k k v ˉ k ,
and, in the same way, ∑ j s j = ∑ k d k k \sum_j s_j=\sum_k d_kk ∑ j s j = ∑ k d k k . Hence
ESW p ( f s R ) = ∑ k = 1 m ω k v ˉ k , ω k : = d k k ∑ k ′ = 1 m d k ′ k ′ . \operatorname{ESW}_p(f_{\mathbf{s}}^{\mathrm{R}})=\sum_{k=1}^{m}\omega_k\bar{v}_k,\qquad\omega_k:=\frac{d_kk}{\sum_{k'=1}^{m}d_{k'}k'}. ESW p ( f s R ) = k = 1 ∑ m ω k v ˉ k , ω k := ∑ k ′ = 1 m d k ′ k ′ d k k .
The weights ω k \omega_k ω k are nonnegative and sum to 1 (the denominator is ∑ j s j > 0 \sum_j s_j>0 ∑ j s j > 0 ). In the example above, ω = ( 1 3 , 2 3 , 0 ) \omega=(\frac{1}{3},\frac{2}{3},0) ω = ( 3 1 , 3 2 , 0 ) , so the welfare of ( 1 , 1 2 , 0 ) (1,\frac{1}{2},0) ( 1 , 2 1 , 0 ) is 1 3 v ˉ 1 + 2 3 v ˉ 2 \frac{1}{3}\bar{v}_1+\frac{2}{3}\bar{v}_2 3 1 v ˉ 1 + 3 2 v ˉ 2 . Now (a) applies with v ˉ k \bar{v}_k v ˉ k in place of v j v_j v j :
v ˉ ∗ − ESW p ( f s R ) = ∑ k = 1 m ω k ( v ˉ ∗ − v ˉ k ) ≥ 0 , \bar{v}^*-\operatorname{ESW}_p(f_{\mathbf{s}}^{\mathrm{R}})=\sum_{k=1}^{m}\omega_k(\bar{v}^*-\bar{v}_k)\geq0, v ˉ ∗ − ESW p ( f s R ) = k = 1 ∑ m ω k ( v ˉ ∗ − v ˉ k ) ≥ 0 ,
with equality if, and only if, ω k = 0 \omega_k=0 ω k = 0 (equivalently d k = 0 d_k=0 d k = 0 ) for every k ∉ K ∗ k\notin K^* k ∈ / K ∗ . The k k k -approval vector s ( k ) \mathbf{s}^{(k)} s ( k ) has one drop, d k = 1 d_k=1 d k = 1 , so ω k = 1 \omega_k=1 ω k = 1 . Its welfare is v ˉ k \bar{v}_k v ˉ k , which equals v ˉ ∗ \bar{v}^* v ˉ ∗ if, and only if, k ∈ K ∗ k\in K^* k ∈ K ∗ . □
When voters are anonymous, Theorem 5.1 shows the randomized PSR which maximizes ESW is k k k -approval. Our assumptions allow distributions where voter utilities are not independent. Intuitively, k > 1 k>1 k > 1 may result in optimal welfare when alternatives ranked lower by a voter are better for a group than their favourite. We explore this in Section 6. When voter utilities are independent and neutral, there is never an incentive to use k > 1 k>1 k > 1 for randomized PSRs.
Corollary 6. Fix p ∈ [ − ∞ , ∞ ] p\in[-\infty,\infty] p ∈ [ − ∞ , ∞ ] . Assume A1, A2, E [ U ] < ∞ \mathbb{E}[U]<\infty E [ U ] < ∞ . For all n n n , the plurality vector uniquely maximizes ESW p ( f s R ) \operatorname{ESW}_p(f_{\mathbf{s}}^{\mathrm{R}}) ESW p ( f s R ) over all score vectors, i.e., the optimal randomized PSR is random dictatorship.
Proof. Under these assumptions Theorem 5.1 applies. Consider p ∈ R p\in\mathbb{R} p ∈ R first. We show v 1 > v j v_1>v_j v 1 > v j for every j > 1 j>1 j > 1 . Voter 1 gives b 1 j b_{1j} b 1 j utility U ( j ) U_{(j)} U ( j ) , the j j j -th largest of their m m m utilities, while the other voters’ utilities for b 1 j b_{1j} b 1 j are independent of voter 1 and, by neutrality, have the same distribution for every j j j . Using the same draws for both, U ( 1 ) > U ( j ) U_{(1)}>U_{(j)} U ( 1 ) > U ( j ) by A2, and W P M W^{\mathrm{PM}} W PM strictly increases when one voter’s utility increases, so the welfare of b 11 b_{11} b 11 is always higher than b 1 j b_{1j} b 1 j . Taking expectations gives v 1 > v j v_1>v_j v 1 > v j . When p = ± ∞ p=\pm\infty p = ± ∞ , min \min min and max \max max never decrease when one voter’s utility increases, and with positive probability voter 1’s utility for b 1 j b_{1j} b 1 j is the minimum (p = − ∞ p=-\infty p = − ∞ ), or b 11 b_{11} b 11 is the maximum (p = + ∞ p=+\infty p = + ∞ ), again v 1 > v j v_1>v_j v 1 > v j . Thus v ∗ v^* v ∗ is attained only at j = 1 j=1 j = 1 , by Theorem 5.1 the optimal score vectors are exactly those with s j = 0 s_j=0 s j = 0 for all j > 1 j>1 j > 1 , i.e., positive multiples of s P \mathbf{s}^{\mathrm{P}} s P . □
Experiments
Our theoretical results describe the welfare-maximizing score vector across a wide range of settings but provide little intuition around what these optimal score vectors actually are and how much benefit there is to using a score vector optimized for a particular setting over one of the existing canonical vectors shown in Figure 1 . While applicable to many settings, our results are also limited by our assumptions around voter preferences which we can relax using experimental approaches. Here we explore our optimization setting experimentally. All experiments are run with n = 100 n = 100 n = 100 and m = 20 m = 20 m = 20 . We include additional discussion and results in Appendix B.
Optimal Vectors Across p p p
We prove in Section 4.2 the asymptotically average-case optimal score vector across the power mean family is s k ∗ ( p ) = E [ ψ p ( U ( k ) ) ] s_k^*(p) = \mathbb{E}[\psi_p(U_{(k)})] s k ∗ ( p ) = E [ ψ p ( U ( k ) )] . Here we visualize s ∗ s^* s ∗ across several utility distributions. In each, utilities are sampled i.i.d. for all voters. The mixture distribution selects another distribution uniformly at random for each voter.
U n i f o r m ( 0 , 1 ) Uniform(0, 1) U ni f or m ( 0 , 1 )
Exponential with λ = 1 \lambda= 1 λ = 1
B e t a ( 2 , 5 ) Beta(2, 5) B e t a ( 2 , 5 )
Trunc. Normal( 1 , 0.5 ) (1, 0.5) ( 1 , 0.5 ) on ( 0.01 , 2 ) (0.01, 2) ( 0.01 , 2 )
Pareto with α = 3 \alpha= 3 α = 3 on [ 1 , ∞ ) [1, \infty) [ 1 , ∞ )
Uniform mixture distribution
We show the results in Figure 2 . On values of p p p where s ∗ s^* s ∗ is not defined we report the experimentally optimized score vector using the procedure described in Section 6.2 with a dashed line. Hard-coded vectors for p = ± ∞ p = \pm\infty p = ± ∞ are included for illustrative purposes. The optimal vector takes a similar shape across distributions, suggesting a similar vector may perform well across settings. For low p p p score values remain large until late positions in the vector when it drops rapidly while the opposite holds true for higher values of p p p (> 1 > 1 > 1 ).
Figure 2. Shape of s ∗ ( p ) s^*(p) s ∗ ( p ) across varying values of p p p . The optimal score vector holds a relatively constant shape across a range of utility distributions. Dashed lines indicate experimentally optimal results where s ∗ ( p ) s^*(p) s ∗ ( p ) is not well-defined on the distribution.
Relaxing Utility Assumptions
Experimental analysis allows us to drop our prior assumptions. Here we study the optimal vector for utility distributions which are not neutral (Plackett-Luce) and where voters are not independent (Euclidean). We use experimental optimization methods to find highly optimized score vectors and explore how they change while p p p changes. We compare this with s ∗ s^* s ∗ to identify whether any relationship exists which could be used in future theoretical results.
In this experiment we sample utilities from two families of distributions: Plackett-Luce utilities [24 , 29 ] with γ ∈ { 0.5 , 2 } \gamma\in\{0.5, 2\} γ ∈ { 0.5 , 2 } with weight vector w w w is w j = exp ( γ 1 2 j − 1 m − 1 ) w_j = \exp\left(\gamma\frac{1}{2} \frac{j-1}{m-1}\right) w j = exp ( γ 2 1 m − 1 j − 1 ) for j ∈ 1 … m j \in1 \ldots m j ∈ 1 … m . When γ = 0 \gamma= 0 γ = 0 this reduces to the uniform distribution. We also use Euclidean preferences where voters and alternatives are placed uniformly at random in an d d d -dimensional space and a voter at position v i v_i v i receives utility u i = 1 − ∥ v i − a j ∥ 2 d u_i = 1 - \frac{\lVert v_i-a_j\rVert^2}{d} u i = 1 − d ∥ v i − a j ∥ 2 for an alternative at position a j a_j a j on a space with diameter d d d . We do not have an exact method for computing s ∗ s^* s ∗ for these distributions. Instead we generate utilities for 200,000 voters, with alternatives randomly regenerated for each voter under Euclidean preferences. We report U ( k ) U_{(k)} U ( k ) as the mean of the k k k -th largest element across each list and use it to calculate s ∗ s^* s ∗ .
We consider three basic methods for optimizing scoring rules:
Simulated annealing, as discussed by Armstrong et al. [4 ] .
Covariance Matrix Adaptation Evolution Strategy [23 ]
Random search over vectors.
Methods are restricted to feasible rules and run for 10,000 steps. The first two are run once starting from each canonical vector, a random vector, and s ∗ s^* s ∗ . We record the score vector achieving highest welfare on a training set of 20,000 profiles and report the welfare of that vector on a test set of 20,000 profiles from the same distribution.
Appendix B shows that this optimization process closely matches theoretical results when utilities are neutral and independent.
In Figure 3 we see that the experimentally optimal score vector (dashed lines) can significantly diverge from s ∗ ( p ) s^*(p) s ∗ ( p ) (dotted lines). Plackett-Luce models have a similar shape, which begins to diverge as they become less neutral. Euclidean distributions present what appear to be truly novel dynamics. Here differences from s ∗ ( p ) s^*(p) s ∗ ( p ) are much larger than can be explained by simulation noise. We explore additional parameterizations of these families in Appendix B.
Figure 3. Score vectors optimized for non-i.i.d. utility sampling. The optimal vector on Plackett-Luce utilities begins to diverge from s ∗ ( p ) s^*(p) s ∗ ( p ) as γ \gamma γ increases while on Euclidean utilities it significantly diverges from s ∗ ( p ) s^*(p) s ∗ ( p ) in most cases.
How Important is Optimality?
Thus far, we have illustrated the dynamics of the welfare-maximizing score vector across a range of power mean functions. What we have not yet explored is the amount of welfare which is gained or lost by use of one score vector over another. If the difference in social welfare between any scoring vectors is insignificant, the optimal vector is quite unimportant. We show in this section that the optimal vector is typically significantly better than others.
Using the settings from the previous two experiments we place the welfare given by each score vector on a scale between a randomly selected winner and an oracle f ∗ f^* f ∗ which selects the welfare-maximizing alternative on every profile. We call this measure normalized gain, with G ( s ) = E S W ( f s ) − E S W ( f 1 ) E S W ( f ∗ ) − E S W ( f 1 ) G(s) = \frac{ESW(f_s)-ESW(f_1)}{ESW(f^*)-ESW(f_1)} G ( s ) = E S W ( f ∗ ) − E S W ( f 1 ) E S W ( f s ) − E S W ( f 1 ) . A value of zero indicates that s s s provides no benefit over a random selection while a value of 1 corresponds to electing the welfare-maximizing alternative on every profile. G ( s ) G(s) G ( s ) links naturally with our definition of average-case optimality (Definition 2) and has been used in prior social choice experiments by [35 ] and [26 ] .
We see in Figure 4 (i.i.d.) and Figure 5 (non-i.i.d.) a large gap between canonical score vectors and the optimal score vector in most settings. Error bars show two standard errors of each rule’s mean welfare over 20,000 test profiles. No single canonical rule performs near optimal in all settings. One special case of interest is the Borda vector on the Euclidean Cube distribution: Here Borda performs extremely similarly to the optimized vector in all case, suggesting that Borda—or a Borda-like vector—may be exactly optimal in this setting. This result mirrors the experimental findings of Green-Armytage et al. [22 ] in exploring the utilitarian social welfare of Borda in a single-dimensional setting; Appendix B shows that this holds across higher dimensions of the Cube distribution.
Figure 4. Normalized gain of each positional scoring rule on a scale between the welfare of a random winner and a perfect oracle. Each canonical rule is significantly worse than the theoretically optimal s ∗ s^* s ∗ for at least some value of p p p . When s ∗ s^* s ∗ is marked with × it is not well defined and we report welfare from an experimentally optimized score vector.
Figure 5. Normalized gain of each positional scoring rule on non-i.i.d. utility distributions. s ∗ s^* s ∗ is not known to be optimal on these distributions and is included among a comparison with the experimentally optimized vector.
Randomized Rules
The previous experiments study optimal deterministic rules. We have shown that, among randomized PSRs, a k k k -approval rule maximizes ESW across the power mean family. Thus, there is less room to explore how the optimal rules changes across the power mean. However, the question of whether the best randomized PSR gives significantly more welfare than other canonical score vectors is yet unexplored. In fact, the optimal score vector does consistently provide a significant improvement to welfare over other score vectors on at least some values of p p p . On neutral distributions with independent voters, Figure 6 shows that plurality is often much better in terms of welfare than other rules. When utility assumptions are relaxed, Figure 7 shows a similar outcome. Plurality, or another k k k -approval vector is usually more performant than other score vectors on some cases. In Euclidean preferences where each voter’s most favoured alternative may not be the winner which maximizes social welfare we typically see that the best rule involves k > 1 k > 1 k > 1 . Randomized rules notably provide much lower normalized gain than deterministic rules across all distributions.
Figure 6. Normalized gain of randomized positional scoring rules on a scale between the welfare of a random winner and a perfect oracle. Plurality is optimal here and it significantly outperforms other rules on most values of p p p across distributions.
Figure 7. Normalized gain of each randomized positional scoring rule on non-i.i.d. utility distributions. Theorem 5.1 shows that a k k k -approval vector optimizes welfare. In most cases k = 1 k = 1 k = 1 (plurality) is best but our optimization finds k > 1 k > 1 k > 1 can give higher welfare on the Euclidean Cube distribution.
Discussion
In this paper we have analyzed from the perspective of ordinal voting a highly general form of social welfare function: the power mean. We show that, with an asymptotic number of voters, the social choice function which maximizes expected social welfare is always a deterministic PSR and we characterize the gap between optimal social welfare provided by an oracle and the welfare of the best ordinal social choice function. The optimal score vector is a direct transform of the order statistics of voter utility distributions. We present a novel result describing exact and asymptotic scoring functions for Nash social welfare and strengthen results showing that egalitarian and maximax welfare are optimized by veto and
plurality. We also show that among randomized PSRs, a k k k -approval rule will always maximize expected social welfare. When voter utilities are independent and neutral the plurality rule is optimal.
Experimentally, we find that optimal scoring vectors for deterministic rules often take similar shapes across utility distributions. This shape holds even on some distributions (Plackett-Luce) which are not covered by our assumptions on utility. On utility distributions in which voters and alternatives are highly structured (Euclidean preferences) we find that novel shapes of score vector, not described by our theoretical findings, maximize social welfare.
Our results highlight some novel directions worth attention:
Extension to Additional Distributions. Our assumptions on voter utility cover a wide range of distributions but many results rely on independence between voters, an assumption quite misaligned with reality. Meanwhile, our experimental results show that novel score vectors emerge when voter utilities are not independent. The well-defined domain of Euclidean preferences may be amenable to theoretical analysis on the question of which social choice function maximizes welfare and our experimental answers to this question suggest interesting and novel outcomes.
Bounded Randomness. Our work shows that deterministic score vectors outperform randomized ones in both a theoretical and empirical sense. However, randomized rules provide satisfying axiomatic properties around strategy-proofness and fairness. Developing and analyzing a novel blend of deterministic and randomized approaches – e.g., a temperature which controls the “level” of randomness – may be able to provide a high level of expected or worst-case welfare while also maintaining axiomatic properties not found in deterministic scoring rules.
References
Missing Proofs of Theoretical Claims
This appendix contains all proofs which are missing from the main body. The properties of the Box-Cox utility transform are shown in Section A.1. Young’s lemma and our use of the lemma to demonstrate that a positional scoring rule maximizes expected social welfare appear in Section A.2. We prove the shape of the optimal scoring rule in Section A.3.
Asymptotic Optimality. Each asymptotic optimality result in this appendix uses Definition 2 in the same way. Fix p ∈ R ∪ { ± ∞ } p \in\mathbb{R} \cup\{\pm\infty\} p ∈ R ∪ { ± ∞ } , a reference rule f ∘ f^\circ f ∘ and a rate c n → ∞ c_n \to\infty c n → ∞ with c n ( OPT n − ESW p ( f ∘ ) ) → 0 c_n(\operatorname{OPT}_n-\operatorname{ESW}_p(f^\circ)) \to0 c n ( OPT n − ESW p ( f ∘ )) → 0 . For any rule f f f , let
Δ ( f ) = lim n → ∞ c n ( ESW p ( f ∘ ) − ESW p ( f ) ) \Delta(f) = \lim_{n\to\infty} c_n(\operatorname{ESW}_p(f^\circ)-\operatorname{ESW}_p(f)) Δ ( f ) = n → ∞ lim c n ( ESW p ( f ∘ ) − ESW p ( f ))
whenever this limit exists. Then c n ( OPT n − ESW p ( f ) ) → Δ ( f ) c_n(\operatorname{OPT}_n-\operatorname{ESW}_p(f)) \to\Delta(f) c n ( OPT n − ESW p ( f )) → Δ ( f ) as well. So if Δ ( f 1 ) > 0 \Delta(f_1)>0 Δ ( f 1 ) > 0 , multiplying the numerator and denominator in Definition 2 by c n c_n c n gives
lim n → ∞ OPT n − ESW p ( f ) OPT n − ESW p ( f 1 ) = Δ ( f ) Δ ( f 1 ) , \lim_{n\to\infty}\frac{\operatorname{OPT}_n-\operatorname{ESW}_p(f)}{\operatorname{OPT}_n-\operatorname{ESW}_p(f_1)}
=\frac{\Delta(f)}{\Delta(f_1)}, n → ∞ lim OPT n − ESW p ( f 1 ) OPT n − ESW p ( f ) = Δ ( f 1 ) Δ ( f ) ,
and f f f is asymptotically average-case optimal if, and only if, Δ ( f ) = 0 \Delta(f)=0 Δ ( f ) = 0 . For finite p p p we use c n = n 1 / 2 c_n=n^{1/2} c n = n 1/2 and f ∘ = f s ∗ ( p ) f^\circ=f_s^*(p) f ∘ = f s ∗ ( p ) (Theorem A.2). For p = − ∞ p=-\infty p = − ∞ and p = + ∞ p=+\infty p = + ∞ we use c n = n 3 / 2 c_n=n^{3/2} c n = n 3/2 , with f ∘ f^\circ f ∘ being veto and plurality respectively (Theorems A.3 and A.4).
Utility Transformation
The first lemma below provides a simple utility transformation used throughout the rest of the proofs. While we use this function, other functions with identical properties could also provide similar results.
Lemma 1. Fix p ∈ R p \in\mathbb{R} p ∈ R and let ψ p : ( 0 , ∞ ) → R \psi_p:(0,\infty)\to\mathbb{R} ψ p : ( 0 , ∞ ) → R be the Box-Cox transform of Equation (1) . Then
(a) ψ p \psi_p ψ p is strictly increasing on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) ; and
(b) for every utility profile u \mathbf{u} u and every a ∈ A a\in A a ∈ A ,
ψ p ( W P M ( u , a , p ) ) = 1 n ∑ i = 1 n ψ p ( u i ( a ) ) . \psi_p(W^{\mathrm{PM}}(\mathbf{u},a,p))=\frac{1}{n}\sum_{i=1}^{n}\psi_p(u_i(a)). ψ p ( W PM ( u , a , p )) = n 1 i = 1 ∑ n ψ p ( u i ( a )) . Consequently, for all a , b ∈ A a,b\in A a , b ∈ A ,
W P M ( u , a , p ) ≥ W P M ( u , b , p ) ⟺ ∑ i = 1 n ψ p ( u i ( a ) ) ≥ ∑ i = 1 n ψ p ( u i ( b ) ) . W^{\mathrm{PM}}(\mathbf{u},a,p)\ge W^{\mathrm{PM}}(\mathbf{u},b,p)
\Longleftrightarrow
\sum_{i=1}^{n}\psi_p(u_i(a))\ge\sum_{i=1}^{n}\psi_p(u_i(b)). W PM ( u , a , p ) ≥ W PM ( u , b , p ) ⟺ i = 1 ∑ n ψ p ( u i ( a )) ≥ i = 1 ∑ n ψ p ( u i ( b )) . Proof. (a) For p ≠ 0 p\ne0 p = 0 , ψ p \psi_p ψ p is differentiable on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) with ψ p ′ ( t ) = t p − 1 > 0 \psi_p'(t)=t^{p-1}>0 ψ p ′ ( t ) = t p − 1 > 0 . For p = 0 p=0 p = 0 , log \log log is strictly increasing.
(b) All utilities are positive, so W P M ( u , a , p ) > 0 W^{\mathrm{PM}}(\mathbf{u},a,p)>0 W PM ( u , a , p ) > 0 and ψ p \psi_p ψ p may be applied to it. For p ≠ 0 p\ne0 p = 0 ,
ψ p ( W P M ( u , a , p ) ) = 1 p ( ( ( 1 n ∑ i u i ( a ) p ) 1 / p ) p − 1 ) = 1 n ∑ i u i ( a ) p − 1 p = 1 n ∑ i ψ p ( u i ( a ) ) . \psi_p(W^{\mathrm{PM}}(\mathbf{u},a,p))
=\frac{1}{p}\left(\left(\left(\frac{1}{n}\sum_i u_i(a)^p\right)^{1/p}\right)^p-1\right)
=\frac{1}{n}\sum_i\frac{u_i(a)^p-1}{p}
=\frac{1}{n}\sum_i\psi_p(u_i(a)). ψ p ( W PM ( u , a , p )) = p 1 ( n 1 i ∑ u i ( a ) p ) 1/ p p − 1 = n 1 i ∑ p u i ( a ) p − 1 = n 1 i ∑ ψ p ( u i ( a )) . For p = 0 p=0 p = 0 ,
ψ 0 ( ( ∏ i u i ( a ) ) 1 / n ) = 1 n log ∏ i u i ( a ) = 1 n ∑ i ψ 0 ( u i ( a ) ) . \psi_0\left(\left(\prod_i u_i(a)\right)^{1/n}\right)
=\frac{1}{n}\log\prod_i u_i(a)
=\frac{1}{n}\sum_i\psi_0(u_i(a)). ψ 0 ( i ∏ u i ( a ) ) 1/ n = n 1 log i ∏ u i ( a ) = n 1 i ∑ ψ 0 ( u i ( a )) . The final equivalence follows by applying the strictly increasing function ψ p \psi_p ψ p to both sides of the welfare comparison, rewriting each side using (b), and multiplying both sides by n n n .
The Optimal Rule is a PSR
Young [37 ] provided an axiomatic characterization of scoring rules which we use to prove that the rule maximizing expected social welfare is a scoring rule.
A social choice correspondence maps each preference profile, over any number of voters, to a nonempty set of alternatives. It is a scoring correspondence if there is a score vector s \mathbf{s} s , the same for every number of voters, such that it always returns exactly the alternatives with maximal score s ( σ , a ) s(\sigma,a) s ( σ , a ) .
Lemma 2 (Young). For preference profiles σ 1 \sigma_1 σ 1 and σ 2 \sigma_2 σ 2 write σ 1 + σ 2 \sigma_1+\sigma_2 σ 1 + σ 2 for the profile containing the voters of both, t σ 1 t\sigma_1 t σ 1 for the profile containing t ∈ N t\in\mathbb{N} t ∈ N copies of each voter of σ 1 \sigma_1 σ 1 , and for a permutation π \pi π of A A A , π σ 1 \pi\sigma_1 π σ 1 for the profile obtained by replacing every alternative b b b by π ( b ) \pi(b) π ( b ) in every ranking. Let g g g be a social choice correspondence defined on profiles of every size. Call g g g
anonymous if g ( σ 1 ) g(\sigma_1) g ( σ 1 ) is unchanged when the voters of σ 1 \sigma_1 σ 1 are reordered;
neutral if g ( π σ 1 ) = π ( g ( σ 1 ) ) g(\pi\sigma_1)=\pi(g(\sigma_1)) g ( π σ 1 ) = π ( g ( σ 1 )) for every permutation π \pi π of A A A and every σ 1 \sigma_1 σ 1 ;
consistent if g ( σ 1 + σ 2 ) = g ( σ 1 ) ∩ g ( σ 2 ) g(\sigma_1+\sigma_2)=g(\sigma_1)\cap g(\sigma_2) g ( σ 1 + σ 2 ) = g ( σ 1 ) ∩ g ( σ 2 ) whenever g ( σ 1 ) ∩ g ( σ 2 ) ≠ ∅ g(\sigma_1)\cap g(\sigma_2)\ne\varnothing g ( σ 1 ) ∩ g ( σ 2 ) = ∅ ;
continuous if g ( σ 1 ) = { a } g(\sigma_1)=\{a\} g ( σ 1 ) = { a } implies that for every σ 2 \sigma_2 σ 2 there is T ∈ N T\in\mathbb{N} T ∈ N with g ( σ 2 + t σ 1 ) = { a } g(\sigma_2+t\sigma_1)=\{a\} g ( σ 2 + t σ 1 ) = { a } for all t ≥ T t\ge T t ≥ T .
Then g g g is a scoring correspondence if and only if it is anonymous, neutral, consistent, and continuous.
Theorem A.1. Fix p ∈ R p\in\mathbb{R} p ∈ R and suppose A3 holds. There is a score vector s ∈ R m \mathbf{s}\in\mathbb{R}^m s ∈ R m such that the positional scoring rule f s f_s f s is asymptotically average-case optimal (Definition 2). When p = 1 p=1 p = 1 , f s f_s f s moreover maximizes ESW 1 \operatorname{ESW}_1 ESW 1 over all social choice functions for every n n n .
The proof applies Lemma 2 to the objective E [ ∣ ∑ i = 1 n ψ p ( u i ( a ) ) ∣ σ ∣ ] \mathbb{E}[\left|\sum_{i=1}^{n}\psi_p(u_i(a))\mid\sigma\right|] E [ ∣ ∑ i = 1 n ψ p ( u i ( a )) ∣ σ ∣ ] , which is additive across voters. The following lemma shows that this objective determines ESW p \operatorname{ESW}_p ESW p up to an additive term of o ( n − 1 / 2 ) o(n^{-1/2}) o ( n − 1/2 ) .
Lemma 3. Fix p ∈ R p\in\mathbb{R} p ∈ R and suppose A3 holds. Let
V p ( u , a ) = ∑ i = 1 n ψ p ( u i ( a ) ) = n ψ p ( W P M ( u , a , p ) ) , V_p(\mathbf{u},a)=\sum_{i=1}^{n}\psi_p(u_i(a))=n\psi_p(W^{\mathrm{PM}}(\mathbf{u},a,p)), V p ( u , a ) = i = 1 ∑ n ψ p ( u i ( a )) = n ψ p ( W PM ( u , a , p )) , where the second expression follows from Lemma 1(b), and let μ ψ = E [ ψ p ( U ) ] \mu_\psi=\mathbb{E}[\psi_p(U)] μ ψ = E [ ψ p ( U )] , C p = ψ p − 1 ( μ ψ ) C_p=\psi_p^{-1}(\mu_\psi) C p = ψ p − 1 ( μ ψ ) and κ p = ( ψ p − 1 ) ′ ( μ ψ ) = C p 1 − p > 0 \kappa_p=(\psi_p^{-1})'(\mu_\psi)=C_p^{1-p}>0 κ p = ( ψ p − 1 ) ′ ( μ ψ ) = C p 1 − p > 0 . There exist ε n ≥ 0 \varepsilon_n\ge0 ε n ≥ 0 with n 1 / 2 ε n → 0 n^{1/2}\varepsilon_n\to0 n 1/2 ε n → 0 such that for every n n n and every (possibly randomized) social choice function f f f ,
∣ ESW p ( f ) − C p − κ p ( E [ 1 n V p ( u , f ( σ ) ) ] − μ ψ ) ∣ ≤ ε n . \left|\operatorname{ESW}_p(f)-C_p-\kappa_p\left(\mathbb{E}\left[\frac{1}{n}V_p(\mathbf{u},f(\sigma))\right]-\mu_\psi\right)\right|\le\varepsilon_n. ESW p ( f ) − C p − κ p ( E [ n 1 V p ( u , f ( σ )) ] − μ ψ ) ≤ ε n . Proof. For each a ∈ A a\in A a ∈ A let Y ‾ n ( a ) = 1 n V p ( u , a ) \overline{Y}_n(a)=\frac{1}{n}V_p(\mathbf{u},a) Y n ( a ) = n 1 V p ( u , a ) , so that W P M ( u , a , p ) = ψ p − 1 ( Y ‾ n ( a ) ) W^{\mathrm{PM}}(\mathbf{u},a,p)=\psi_p^{-1}(\overline{Y}_n(a)) W PM ( u , a , p ) = ψ p − 1 ( Y n ( a )) by Lemma 1(b). By A1, Y ‾ n ( a ) \overline{Y}_n(a) Y n ( a ) is an average of n n n independent copies of ψ p ( U ) \psi_p(U) ψ p ( U ) . Hence E [ Y ‾ n ( a ) ] = μ ψ \mathbb{E}[\overline{Y}_n(a)]=\mu_\psi E [ Y n ( a )] = μ ψ and E [ ( Y ‾ n ( a ) − μ ψ ) 2 ] = Var ( ψ p ( U ) ) / n = O ( n − 1 ) \mathbb{E}[(\overline{Y}_n(a)-\mu_\psi)^2]=\operatorname{Var}(\psi_p(U))/n=O(n^{-1}) E [( Y n ( a ) − μ ψ ) 2 ] = Var ( ψ p ( U )) / n = O ( n − 1 ) , whence the variance is finite by A3.
(1) Linearization. ψ p − 1 \psi_p^{-1} ψ p − 1 is twice continuously differentiable on the range of ψ p \psi_p ψ p , an open interval containing μ ψ \mu_\psi μ ψ . Fix δ > 0 \delta>0 δ > 0 such that [ μ ψ − δ , μ ψ + δ ] [\mu_\psi-\delta,\mu_\psi+\delta] [ μ ψ − δ , μ ψ + δ ] lies in this range. As C p = ψ p − 1 ( μ ψ ) C_p=\psi_p^{-1}(\mu_\psi) C p = ψ p − 1 ( μ ψ ) and κ p = ( ψ p − 1 ) ′ ( μ ψ ) \kappa_p=(\psi_p^{-1})'(\mu_\psi) κ p = ( ψ p − 1 ) ′ ( μ ψ ) , Taylor’s theorem gives, for every a ∈ A a\in A a ∈ A ,
W P M ( u , a , p ) = C p + κ p ( Y ‾ n ( a ) − μ ψ ) + ρ p ( Y ‾ n ( a ) ) , W^{\mathrm{PM}}(\mathbf{u},a,p)=C_p+\kappa_p(\overline{Y}_n(a)-\mu_\psi)+\rho_p(\overline{Y}_n(a)), W PM ( u , a , p ) = C p + κ p ( Y n ( a ) − μ ψ ) + ρ p ( Y n ( a )) ,
where ∣ ρ p ( y ) ∣ ≤ c ( y − μ ψ ) 2 |\rho_p(y)|\le c(y-\mu_\psi)^2 ∣ ρ p ( y ) ∣ ≤ c ( y − μ ψ ) 2 whenever ∣ y − μ ψ ∣ ≤ δ |y-\mu_\psi|\le\delta ∣ y − μ ψ ∣ ≤ δ , for a constant c c c that does not depend on n n n . The identity κ p = C p 1 − p \kappa_p=C_p^{1-p} κ p = C p 1 − p follows from ψ p ′ ( t ) = t p − 1 \psi_p'(t)=t^{p-1} ψ p ′ ( t ) = t p − 1 .
(2) The remainder is negligible. We show E [ ∣ ρ p ( Y ‾ n ( a ) ) ∣ ] = o ( n − 1 / 2 ) \mathbb{E}[|\rho_p(\overline{Y}_n(a))|]=o(n^{-1/2}) E [ ∣ ρ p ( Y n ( a )) ∣ ] = o ( n − 1/2 ) . Let B n = { ∣ Y ‾ n ( a ) − μ ψ ∣ > δ } B_n=\{|\overline{Y}_n(a)-\mu_\psi|>\delta\} B n = { ∣ Y n ( a ) − μ ψ ∣ > δ } , so that Pr ( B n ) = O ( n − 1 ) \Pr(B_n)=O(n^{-1}) Pr ( B n ) = O ( n − 1 ) by Chebyshev’s inequality. Outside B n B_n B n , the remainder contributes at most c E [ ( Y ‾ n ( a ) − μ ψ ) 2 ] = O ( n − 1 ) c\mathbb{E}[(\overline{Y}_n(a)-\mu_\psi)^2]=O(n^{-1}) c E [( Y n ( a ) − μ ψ ) 2 ] = O ( n − 1 ) . On B n B_n B n , as W P M > 0 W^{\mathrm{PM}}>0 W PM > 0 and C p > 0 C_p>0 C p > 0 ,
∣ ρ p ( Y ‾ n ( a ) ) ∣ ≤ W P M ( u , a , p ) + C p + κ p ∣ Y ‾ n ( a ) − μ ψ ∣ . |\rho_p(\overline{Y}_n(a))|\le W^{\mathrm{PM}}(\mathbf{u},a,p)+C_p+\kappa_p|\overline{Y}_n(a)-\mu_\psi|. ∣ ρ p ( Y n ( a )) ∣ ≤ W PM ( u , a , p ) + C p + κ p ∣ Y n ( a ) − μ ψ ∣.
By Cauchy–Schwarz the last two terms contribute O ( n − 1 ) O(n^{-1}) O ( n − 1 ) . For the first term, let q q q be as in A3. Power means are nondecreasing in their parameter and q > p q>p q > p , so
E [ W P M ( u , a , p ) q ] ≤ E [ W P M ( u , a , q ) q ] = E [ U q ] < ∞ . \mathbb{E}[W^{\mathrm{PM}}(\mathbf{u},a,p)^q]\le\mathbb{E}[W^{\mathrm{PM}}(\mathbf{u},a,q)^q]=\mathbb{E}[U^q]<\infty. E [ W PM ( u , a , p ) q ] ≤ E [ W PM ( u , a , q ) q ] = E [ U q ] < ∞.
Hölder’s inequality then gives
E [ W P M ( u , a , p ) 1 B n ] ≤ E [ U q ] 1 / q Pr ( B n ) 1 − 1 / q = O ( n − 1 + 1 / q ) , \mathbb{E}[W^{\mathrm{PM}}(\mathbf{u},a,p)1_{B_n}]\le\mathbb{E}[U^q]^{1/q}\Pr(B_n)^{1-1/q}=O(n^{-1+1/q}), E [ W PM ( u , a , p ) 1 B n ] ≤ E [ U q ] 1/ q Pr ( B n ) 1 − 1/ q = O ( n − 1 + 1/ q ) ,
which is o ( n − 1 / 2 ) o(n^{-1/2}) o ( n − 1/2 ) since q > 2 q>2 q > 2 .
(3) Any social choice function. Let ω = f ( σ ) \omega=f(\boldsymbol{\sigma}) ω = f ( σ ) . Applying step 1 at a = ω a=\omega a = ω and taking expectations, with E [ Y ‾ n ( ω ) ] = 1 n E [ V p ( u , ω ) ] \mathbb{E}[\overline{Y}_n(\omega)]=\frac{1}{n}\mathbb{E}[V_p(\mathbf{u},\omega)] E [ Y n ( ω )] = n 1 E [ V p ( u , ω )] ,
ESW p ( f ) − C p − κ p ( 1 n E [ V p ( u , ω ) ] − μ ψ ) = E [ ρ p ( Y ‾ n ( ω ) ) ] . \operatorname{ESW}_p(f)-C_p-\kappa_p\left(\frac{1}{n}\mathbb{E}[V_p(\mathbf{u},\omega)]-\mu_\psi\right)=\mathbb{E}[\rho_p(\overline{Y}_n(\omega))]. ESW p ( f ) − C p − κ p ( n 1 E [ V p ( u , ω )] − μ ψ ) = E [ ρ p ( Y n ( ω ))] .
As ∣ ρ p ( Y ‾ n ( ω ) ) ∣ ≤ ∑ a ∈ A ∣ ρ p ( Y ‾ n ( a ) ) ∣ |\rho_p(\overline{Y}_n(\omega))|\le\sum_{a\in A}|\rho_p(\overline{Y}_n(a))| ∣ ρ p ( Y n ( ω )) ∣ ≤ ∑ a ∈ A ∣ ρ p ( Y n ( a )) ∣ and the Y ‾ n ( a ) \overline{Y}_n(a) Y n ( a ) are identically distributed (A1), the claim holds with ε n = m E [ ∣ ρ p ( Y ‾ n ( a ) ) ∣ ] \varepsilon_n=m\mathbb{E}[|\rho_p(\overline{Y}_n(a))|] ε n = m E [ ∣ ρ p ( Y n ( a )) ∣ ] . This does not depend on f f f and satisfies n 1 / 2 ε n → 0 n^{1/2}\varepsilon_n\to0 n 1/2 ε n → 0 by step 2.
Now we are ready to prove Theorem 4.1.
Proof of Theorem A.1. For every preference profile σ \boldsymbol{\sigma} σ , of any size n n n , and every a ∈ A a\in A a ∈ A let
G ( σ , a ) : = E [ V p ( u , a ) u i ( a ) ∣ σ ] = ∑ i = 1 n E [ ψ p ( u i ( a ) ) ∣ σ ] , G(\boldsymbol{\sigma},a):=\mathbb{E}\left[\left.\frac{V_p(\mathbf{u},a)}{u_i(a)}\right|\boldsymbol{\sigma}\right]=\sum_{i=1}^{n}\mathbb{E}\left[\left.\psi_p(u_i(a))\right|\boldsymbol{\sigma}\right], G ( σ , a ) := E [ u i ( a ) V p ( u , a ) σ ] = i = 1 ∑ n E [ ψ p ( u i ( a )) ∣ σ ] ,
which is finite by A3. Let f ∗ ( σ ) = arg max a ∈ A G ( σ , a ) f^*(\boldsymbol{\sigma})=\mathop{\arg\max}_{a\in A}G(\boldsymbol{\sigma},a) f ∗ ( σ ) = arg max a ∈ A G ( σ , a ) be the social choice correspondence returning all maximizers. Following Boutilier et al. [13 ] , we use Lemma 2 to show that f ∗ f^* f ∗ is a scoring correspondence. We then use Lemma 3 to show that the corresponding positional scoring rule is asymptotically average-case optimal.
G G G is a sum of per-voter terms. Voters are independent and identically distributed (A1), so for voter i i i conditioning on σ \boldsymbol{\sigma} σ is the same as conditioning on σ i \sigma_i σ i , and
G ( σ , a ) = ∑ i = 1 n h a ( σ i ) , h a ( σ ) : = E [ ψ p ( u 1 ( a ) ) ∣ σ 1 = σ ] , (3) G(\boldsymbol{\sigma},a)=\sum_{i=1}^{n}h_a(\sigma_i),\qquad h_a(\sigma):=\mathbb{E}\left[\left.\psi_p(u_1(a))\right|\sigma_1=\sigma\right], \tag*{(3)} G ( σ , a ) = i = 1 ∑ n h a ( σ i ) , h a ( σ ) := E [ ψ p ( u 1 ( a )) ∣ σ 1 = σ ] , (3)
where h a h_a h a depends neither on i i i nor on n n n . Therefore
G ( σ 1 + σ 2 , a ) = G ( σ 1 , a ) + G ( σ 2 , a ) ∀ a ∈ A . (4) G(\boldsymbol{\sigma}_1+\boldsymbol{\sigma}_2,a)=G(\boldsymbol{\sigma}_1,a)+G(\boldsymbol{\sigma}_2,a)\qquad\forall a\in A. \tag*{(4)} G ( σ 1 + σ 2 , a ) = G ( σ 1 , a ) + G ( σ 2 , a ) ∀ a ∈ A . (4)
f ∗ f^* f ∗ is a scoring correspondence. We check the conditions of Lemma 2.
Anonymous. By (3), G ( σ , a ) G(\boldsymbol{\sigma},a) G ( σ , a ) does not depend on the order of the voters.
Neutral. By A1, relabelling the alternatives by π \pi π does not change the distribution of utilities, so G ( π σ , π ( a ) ) = G ( σ , a ) G(\pi\boldsymbol{\sigma},\pi(a))=G(\boldsymbol{\sigma},a) G ( π σ , π ( a )) = G ( σ , a ) and f ∗ ( π σ ) = π ( f ∗ ( σ ) ) f^*(\pi\boldsymbol{\sigma})=\pi(f^*(\boldsymbol{\sigma})) f ∗ ( π σ ) = π ( f ∗ ( σ )) .
Consistent. Suppose f ∗ ( σ 1 ) ∩ f ∗ ( σ 2 ) ≠ ∅ f^*(\boldsymbol{\sigma}_1)\cap f^*(\boldsymbol{\sigma}_2)\ne\varnothing f ∗ ( σ 1 ) ∩ f ∗ ( σ 2 ) = ∅ . By (4), G ( σ 1 + σ 2 , ⋅ ) G(\boldsymbol{\sigma}_1+\boldsymbol{\sigma}_2,\cdot) G ( σ 1 + σ 2 , ⋅ ) is the sum of G ( σ 1 , ⋅ ) G(\boldsymbol{\sigma}_1,\cdot) G ( σ 1 , ⋅ ) and G ( σ 2 , ⋅ ) G(\boldsymbol{\sigma}_2,\cdot) G ( σ 2 , ⋅ ) , which have a common maximizer. So b b b maximizes the sum if, and only if, it maximizes both terms, i.e., f ∗ ( σ 1 + σ 2 ) = f ∗ ( σ 1 ) ∩ f ∗ ( σ 2 ) f^*(\boldsymbol{\sigma}_1+\boldsymbol{\sigma}_2)=f^*(\boldsymbol{\sigma}_1)\cap f^*(\boldsymbol{\sigma}_2) f ∗ ( σ 1 + σ 2 ) = f ∗ ( σ 1 ) ∩ f ∗ ( σ 2 ) .
Continuity. Suppose f ∗ ( σ 1 ) = { a } f^*(\boldsymbol{\sigma}_1)=\{a\} f ∗ ( σ 1 ) = { a } , so that δ : = min b ≠ a ( G ( σ 1 , a ) − G ( σ 1 , b ) ) > 0 \delta:=\min_{b\ne a}(G(\boldsymbol{\sigma}_1,a)-G(\boldsymbol{\sigma}_1,b))>0 δ := min b = a ( G ( σ 1 , a ) − G ( σ 1 , b )) > 0 . By (4), for every profile σ 2 \boldsymbol{\sigma}_2 σ 2 and every b ≠ a b\ne a b = a ,
G ( σ 2 + t σ 1 , a ) − G ( σ 2 + t σ 1 , b ) ≥ G ( σ 2 , a ) − G ( σ 2 , b ) + t δ , G(\boldsymbol{\sigma}_2+t\boldsymbol{\sigma}_1,a)-G(\boldsymbol{\sigma}_2+t\boldsymbol{\sigma}_1,b)\ge G(\boldsymbol{\sigma}_2,a)-G(\boldsymbol{\sigma}_2,b)+t\delta, G ( σ 2 + t σ 1 , a ) − G ( σ 2 + t σ 1 , b ) ≥ G ( σ 2 , a ) − G ( σ 2 , b ) + t δ ,
which is positive for all sufficiently large t t t . So f ∗ ( σ 2 + t σ 1 ) = { a } f^*(\boldsymbol{\sigma}_2+t\boldsymbol{\sigma}_1)=\{a\} f ∗ ( σ 2 + t σ 1 ) = { a } for all sufficiently large t t t .
By Lemma 2 there is a score vector s s s , the same for every n n n , with f ∗ ( σ ) = arg max a ∈ A S s ( a , σ ) f^*(\boldsymbol{\sigma})=\mathop{\arg\max}_{a\in A}S_s(a,\sigma) f ∗ ( σ ) = arg max a ∈ A S s ( a , σ ) . Breaking ties uniformly at random, f s f_s f s selects uniformly from f ∗ ( σ ) f^*(\sigma) f ∗ ( σ ) .
f s f_s f s is asymptotically average-case optimal. Let g g g be any (possibly randomized) social choice function on n n n voters. Conditioning on σ \sigma σ and the randomness of g g g ,
E [ V p ( u , g ( σ ) ) ] = E [ G ( σ , g ( σ ) ) ] ≤ E [ max a ∈ A G ( σ , a ) ] = E [ V p ( u , f s ( σ ) ) ] . \mathbb{E}[V_p(\mathbf{u},g(\sigma))]=\mathbb{E}[G(\sigma,g(\sigma))]\le\mathbb{E}\left[\max_{a\in A}G(\sigma,a)\right]=\mathbb{E}[V_p(\mathbf{u},f_s(\sigma))]. E [ V p ( u , g ( σ ))] = E [ G ( σ , g ( σ ))] ≤ E [ a ∈ A max G ( σ , a ) ] = E [ V p ( u , f s ( σ ))] .
Applying Lemma 3 to g g g and to f s f_s f s gives ESW p ( g ) − ESW p ( f s ) ≤ 2 ε n \operatorname{ESW}_p(g)-\operatorname{ESW}_p(f_s)\le2\varepsilon_n ESW p ( g ) − ESW p ( f s ) ≤ 2 ε n . Taking g g g to be optimal, 0 ≤ OPT n − ESW p ( f s ) ≤ 2 ε n = o ( n − 1 / 2 ) 0\le\operatorname{OPT}_n-\operatorname{ESW}_p(f_s)\le2\varepsilon_n=o(n^{-1/2}) 0 ≤ OPT n − ESW p ( f s ) ≤ 2 ε n = o ( n − 1/2 ) . The same argument, using Lemma 4 in place of the display above, gives OPT n − ESW p ( f s ( p ) ) = o ( n − 1 / 2 ) \operatorname{OPT}_n-\operatorname{ESW}_p(f_s(p))=o(n^{-1/2}) OPT n − ESW p ( f s ( p )) = o ( n − 1/2 ) .
We now apply the argument at the start of Appendix A with c n = n 1 / 2 c_n=n^{1/2} c n = n 1/2 and f ∘ = f s ∗ ( p ) f^\circ=f_s^*(p) f ∘ = f s ∗ ( p ) . As f s f_s f s and f s ∗ ( p ) f_s^*(p) f s ∗ ( p ) are both within o ( n − 1 / 2 ) o(n^{-1/2}) o ( n − 1/2 ) of OPT n \operatorname{OPT}_n OPT n , Δ ( f s ) = 0 \Delta(f_s)=0 Δ ( f s ) = 0 . By Theorem A.2, Δ ( f 1 ) = Δ p ( 1 ) > 0 \Delta(f_1)=\Delta_p(1)>0 Δ ( f 1 ) = Δ p ( 1 ) > 0 , since 1 is not a positive affine transformation of s ∗ ( p ) s^*(p) s ∗ ( p ) . Hence f s f_s f s is asymptotically average-case optimal.
When p = 1 p=1 p = 1 , ψ p − 1 ( y ) = 1 + y \psi_p^{-1}(y)=1+y ψ p − 1 ( y ) = 1 + y is affine, so the remainder ρ 1 \rho_1 ρ 1 in Lemma 3 vanishes, ε n = 0 \varepsilon_n=0 ε n = 0 , and f s f_s f s maximizes ESW 1 \operatorname{ESW}_1 ESW 1 exactly for every n n n . In this case G ( u , a ) = 1 n E [ W P M ( u , a , 1 ) ∣ σ ] = 1 n E [ V 1 ( u , a ) ∣ σ ] G(\mathbf{u},a)=\frac{1}{n}\mathbb{E}[W^{\mathrm{PM}}(\mathbf{u},a,1)\mid\sigma]=\frac{1}{n}\mathbb{E}[V_1(\mathbf{u},a)\mid\sigma] G ( u , a ) = n 1 E [ W PM ( u , a , 1 ) ∣ σ ] = n 1 E [ V 1 ( u , a ) ∣ σ ] , so f s ∗ f_s^* f s ∗ is exactly the average-case optimal correspondence of Boutilier et al. [13 ] . □
What is the Optimal Rule?
Theorem A.2. Fix p ∈ R p\in\mathbb{R} p ∈ R , assume A3 holds, and let s ∗ ( p ) = E [ ψ p ( U k ) ] s^*(p)=\mathbb{E}[\psi_p(U_k)] s ∗ ( p ) = E [ ψ p ( U k )] for k = 1 , … , m k=1,\ldots,m k = 1 , … , m . For every score vector s ∈ R m s\in\mathbb{R}^m s ∈ R m the limit
Δ p ( s ) = lim n → ∞ n 1 / 2 ( ESW p ( f s ∗ ( p ) ) − ESW p ( f s ) ) \Delta_p(s)=\lim_{n\to\infty}n^{1/2}\left(\operatorname{ESW}_p(f_{s^*(p)})-\operatorname{ESW}_p(f_s)\right) Δ p ( s ) = n → ∞ lim n 1/2 ( ESW p ( f s ∗ ( p ) ) − ESW p ( f s ) )
exists and is nonnegative, and Δ p ( s ) = 0 \Delta_p(s)=0 Δ p ( s ) = 0 if, and only if, s = s ∗ ( p ) s=s^*(p) s = s ∗ ( p ) . That is, up to positive affine transformation, s ∗ ( p ) s^*(p) s ∗ ( p ) is the unique asymptotically average-case optimal positional scoring rule.
The proof uses the following lemma, which holds exactly for every n n n . For p = 1 p=1 p = 1 it is the result of Boutilier et al. [13 ] , which shows that the Borda rule is optimal when utilities are uniform. Lemma 4. Fix p ∈ R p \in\mathbb{R} p ∈ R , assume A3 holds, and let V p V_p V p be as in Lemma 3 and s ∗ ( p ) s^{*}(p) s ∗ ( p ) as in Theorem 4.2. For every n n n , every preference profile σ \sigma σ and every a ∈ A a \in A a ∈ A ,
E [ V p ( u , a ) ∣ σ ] = S s ∗ ( p ) ( a , σ ) . \mathbb{E}[V_p(u,a)\mid\sigma]=S_{s^{*}(p)}(a,\sigma). E [ V p ( u , a ) ∣ σ ] = S s ∗ ( p ) ( a , σ ) .
Consequently, for every (possibly randomized) social choice function f f f ,
E [ V p ( u , f ( σ ) ) ] = E [ S s ∗ ( p ) ( f ( σ ) , σ ) ] ≤ E [ V p ( u , f s ∗ ( p ) ( σ ) ) ] . \mathbb{E}[V_p(u,f(\sigma))]=\mathbb{E}[S_{s^{*}(p)}(f(\sigma),\sigma)]\leq\mathbb{E}[V_p(u,f_{s^{*}(p)}(\sigma))]. E [ V p ( u , f ( σ ))] = E [ S s ∗ ( p ) ( f ( σ ) , σ )] ≤ E [ V p ( u , f s ∗ ( p ) ( σ ))] .
Proof. Fix voter i i i . By A1, relabelling the alternatives by any permutation π \pi π does not change the distribution of voter i i i ’s utility vector. Relabelling leaves the sorted utilities ( U ( 1 ) , … , U ( m ) ) (U_{(1)},\ldots,U_{(m)}) ( U ( 1 ) , … , U ( m ) ) unchanged and relabels the ranking σ i \sigma_i σ i , which is strict by A2. Hence, given the sorted utilities, every ranking is equally likely, so σ i \sigma_i σ i is uniform and independent of ( U ( 1 ) , … , U ( m ) ) (U_{(1)},\ldots,U_{(m)}) ( U ( 1 ) , … , U ( m ) ) . As u i ( a ) = U ( σ i ( a ) ) u_i(a)=U_{(\sigma_i(a))} u i ( a ) = U ( σ i ( a )) , conditioning on σ i \sigma_i σ i only reveals which order statistic u i ( a ) u_i(a) u i ( a ) is: if σ i ( a ) = k \sigma_i(a)=k σ i ( a ) = k then u i ( a ) u_i(a) u i ( a ) is distributed as U ( k ) U_{(k)} U ( k ) . Voters are independent (A1), so this also holds conditional on σ \sigma σ , and the utilities of different voters remain independent given σ \sigma σ . Therefore
E [ V p ( u , a ) ∣ σ ] = ∑ i = 1 n E [ ψ p ( U ( σ i ( a ) ) ) ] = ∑ i = 1 n s σ i ( a ) ∗ ( p ) = S s ∗ ( p ) ( a , σ ) , \mathbb{E}[V_p(u,a)\mid\sigma]=\sum_{i=1}^{n}\mathbb{E}[\psi_p(U_{(\sigma_i(a))})]=\sum_{i=1}^{n}s^{*}_{\sigma_i(a)}(p)=S_{s^{*}(p)}(a,\sigma), E [ V p ( u , a ) ∣ σ ] = i = 1 ∑ n E [ ψ p ( U ( σ i ( a )) )] = i = 1 ∑ n s σ i ( a ) ∗ ( p ) = S s ∗ ( p ) ( a , σ ) ,
where each term is finite by A3.
For the second claim, f ( σ ) f(\sigma) f ( σ ) depends only on σ \sigma σ and on randomness independent of u u u given σ \sigma σ . Applying the identity at a = f ( σ ) a=f(\sigma) a = f ( σ ) and averaging gives E [ V p ( u , f ( σ ) ) ] = E [ S s ∗ ( p ) ( f ( σ ) , σ ) ] \mathbb{E}[V_p(u,f(\sigma))]=\mathbb{E}[S_{s^{*}(p)}(f(\sigma),\sigma)] E [ V p ( u , f ( σ ))] = E [ S s ∗ ( p ) ( f ( σ ) , σ )] . This is at most E [ max a ∈ A S s ∗ ( p ) ( a , σ ) ] \mathbb{E}[\max_{a\in A}S_{s^{*}(p)}(a,\sigma)] E [ max a ∈ A S s ∗ ( p ) ( a , σ )] , which f s ∗ ( p ) f_{s^{*}(p)} f s ∗ ( p ) attains. □
Proof of Theorem A.2. For a preference profile σ \sigma σ of n n n voters, let Z ( n ) Z^{(n)} Z ( n ) be the m × m m\times m m × m matrix with entries
Z a , k ( n ) = n − 1 / 2 ( ∣ { i : σ i ( a ) = k } ∣ − n m ) , Z^{(n)}_{a,k}=n^{-1/2}\left(\left|\{i:\sigma_i(a)=k\}\right|-\frac{n}{m}\right), Z a , k ( n ) = n − 1/2 ( ∣ { i : σ i ( a ) = k } ∣ − m n ) ,
the centered and scaled number of voters ranking a a a in position k k k . Every row and column of Z ( n ) Z^{(n)} Z ( n ) sums to 0 0 0 , so Z ( n ) Z^{(n)} Z ( n ) lies in the subspace L L L of such matrices. For every score vector s s s ,
S s ( a , σ ) = n m ∑ k s k + n 1 / 2 ( Z ( n ) s ) a . (5) S_s(a,\sigma)=\frac{n}{m}\sum_k s_k+n^{1/2}(Z^{(n)}s)_a. \tag*{(5)} S s ( a , σ ) = m n k ∑ s k + n 1/2 ( Z ( n ) s ) a . (5)
so the winners of f s f_s f s are A s ( Z ( n ) ) A_s(Z^{(n)}) A s ( Z ( n ) ) , where A s ( Z ) = arg max a ∈ A ( Z s ) a A_s(Z)=\arg\max_{a\in A}(Zs)_a A s ( Z ) = arg max a ∈ A ( Z s ) a .
Fix a non-constant reference vector r ∈ R m r\in\mathbb{R}^m r ∈ R m and, for Z ∈ L Z\in L Z ∈ L , let
H s ( Z ) = max a ∈ A ( Z r ) a − 1 ∣ A s ( Z ) ∣ ∑ a ∈ A s ( Z ) ( Z r ) a ≥ 0. H_s(Z)=\max_{a\in A}(Zr)_a-\frac{1}{|A_s(Z)|}\sum_{a\in A_s(Z)}(Zr)_a\geq0. H s ( Z ) = a ∈ A max ( Z r ) a − ∣ A s ( Z ) ∣ 1 a ∈ A s ( Z ) ∑ ( Z r ) a ≥ 0.
By (5), averaging over uniformly random tie-breaking,
max a ∈ A S r ( a , σ ) − E [ S r ( f s ( σ ) , σ ) ∣ σ ] = n 1 / 2 H s ( Z ( n ) ) . (6) \max_{a\in A}S_r(a,\sigma)-\mathbb{E}[S_r(f_s(\sigma),\sigma)\mid\sigma]=n^{1/2}H_s(Z^{(n)}). \tag*{(6)} a ∈ A max S r ( a , σ ) − E [ S r ( f s ( σ ) , σ ) ∣ σ ] = n 1/2 H s ( Z ( n ) ) . (6)
So H s H_s H s measures how far the winner of f s f_s f s falls short of the highest r r r -score, at scale n 1 / 2 n^{1/2} n 1/2 . Steps 1–3 hold for every non-constant r r r . Step 4 takes r = s ∗ ( p ) r=s^{*}(p) r = s ∗ ( p ) .
(1) Limit of the count matrix. As shown in the proof of Lemma 4, each ranking σ i \sigma_i σ i is uniform over all m ! m! m ! rankings, and rankings are independent across voters (A1). So Z ( n ) Z^{(n)} Z ( n ) is a scaled sum of n n n i.i.d. uniformly random permutation matrices, each centered by subtracting 1 m 11 T \frac{1}{m}\mathbf{1}\mathbf{1}^{\mathsf T} m 1 1 1 T . By the multivariate Central Limit Theorem, Z ( n ) Z^{(n)} Z ( n ) converges in distribution to a centered Gaussian Z Z Z on L L L . Permutation matrices affinely span all matrices with row and column sums equal to 1 1 1 (Birkhoff–von Neumann), so Z Z Z has a positive density on L L L .
(2) Convergence of expectations. If s s s is constant, then A s ( Z ) = A A_s(Z)=A A s ( Z ) = A and H s H_s H s is continuous. Otherwise H s H_s H s is continuous wherever A s ( Z ) A_s(Z) A s ( Z ) is a single alternative. The remaining Z Z Z , with ( Z s ) a = ( Z s ) b (Zs)_a=(Zs)_b ( Z s ) a = ( Z s ) b for some a ≠ b a\ne b a = b , form finitely many proper subspaces of L L L and have probability 0 0 0 under Z Z Z . These subspaces are proper because, taking s k + s l s_k+s_l s k + s l , the matrix with row a a a equal to e k − e l e_k-e_l e k − e l , row b b b equal to e l − e k a n d a l l o t h e r r o w s e_l-e_k and all other rows e l − e k an d a l l o t h er r o w s 0 lies in L L L and separates a a a from b b b . By the continuous mapping theorem, H s ( Z ( n ) ) → H s ( Z ) H_s(Z^{(n)})\to H_s(Z) H s ( Z ( n ) ) → H s ( Z ) in distribution. Moreover H s ( Z ( n ) ) ≤ 2 max k ∣ r k ∣ ∑ a , k ∣ Z a , k ( n ) ∣ H_s(Z^{(n)})\leq2\max_k|r_k|\sum_{a,k}|Z^{(n)}_{a,k}| H s ( Z ( n ) ) ≤ 2 max k ∣ r k ∣ ∑ a , k ∣ Z a , k ( n ) ∣ , whose second moment is bounded in n n n . So ( H s ( Z ( n ) ) ) n (H_s(Z^{(n)}))_n ( H s ( Z ( n ) ) ) n is uniformly integrable and E [ H s ( Z ( n ) ) ] → E [ H s ( Z ) ] \mathbb{E}[H_s(Z^{(n)})]\to\mathbb{E}[H_s(Z)] E [ H s ( Z ( n ) )] → E [ H s ( Z )] .
(3) When is the limit zero? We show E [ H s ( Z ) ] ≥ 0 \mathbb{E}[H_s(Z)]\geq0 E [ H s ( Z )] ≥ 0 , with equality if, and only if, s = α r + β 1 s=\alpha r+\beta\mathbf{1} s = α r + β 1 for some α > 0 \alpha>0 α > 0 and β ∈ R \beta\in\mathbb{R} β ∈ R . If s s s is of this form, then A s = A r A_s=A_r A s = A r , so H s = 0 H_s=0 H s = 0 . Otherwise we show H s > 0 H_s>0 H s > 0 with positive probability.
If s s s is constant, then A s ( Z ) = A A_s(Z)=A A s ( Z ) = A . As the columns of Z Z Z sum to 0 0 0 , ∑ a ( Z r ) a = 0 \sum_a(Zr)_a=0 ∑ a ( Z r ) a = 0 , so H s ( Z ) = max a ( Z r ) a H_s(Z)=\max_a(Zr)_a H s ( Z ) = max a ( Z r ) a . This is positive unless Z r = 0 Zr=0 Z r = 0 , an event of probability 0 0 0 .
Otherwise, the projections of s s s and r r r onto { d : ∑ k d k = 0 } \{d:\sum_k d_k=0\} { d : ∑ k d k = 0 } are nonzero and not positive multiples of one another. So there is a d d d with ∑ k d k = 0 \sum_k d_k=0 ∑ k d k = 0 and s ⋅ d < 0 < s ⋅ r s\cdot d<0<s\cdot r s ⋅ d < 0 < s ⋅ r . Fix a ≠ b a\ne b a = b and let Z 0 ∈ L Z_0\in L Z 0 ∈ L have row a a a equal to d d d , row b b b equal to − d -d − d and all other rows 0 0 0 . Then A r ( Z 0 ) = { a } A_r(Z_0)=\{a\} A r ( Z 0 ) = { a } and A s ( Z 0 ) = { b } A_s(Z_0)=\{b\} A s ( Z 0 ) = { b } , so H s ( Z 0 ) = 2 r ⋅ d > 0 H_s(Z_0)=2r\cdot d>0 H s ( Z 0 ) = 2 r ⋅ d > 0 . By continuity, H s > 0 H_s>0 H s > 0 on a neighbourhood of Z 0 Z_0 Z 0 in L L L , which has positive probability under Z Z Z .
(4) The limit Δ p ( s ) \Delta_p(s) Δ p ( s ) . Take r = s ∗ ( p ) r=s^{*}(p) r = s ∗ ( p ) , which is not constant as ψ p \psi_p ψ p is strictly increasing and U ( 1 ) > U ( m ) U_{(1)}>U_{(m)} U ( 1 ) > U ( m ) by A2. By Lemma 4 and (6),
E [ V p ( u , f s ∗ ( p ) ( σ ) ) ] − E [ V p ( u , f s ( σ ) ) ] = n 1 / 2 E [ H s ( Z ( n ) ) ] . \mathbb{E}[V_p(u,f_{s^{*}(p)}(\sigma))]-\mathbb{E}[V_p(u,f_s(\sigma))]=n^{1/2}\mathbb{E}[H_s(Z^{(n)})]. E [ V p ( u , f s ∗ ( p ) ( σ ))] − E [ V p ( u , f s ( σ ))] = n 1/2 E [ H s ( Z ( n ) )] .
By Lemma 3, the difference in ESW p \operatorname{ESW}_p ESW p is κ p n \frac{\kappa_p}{n} n κ p times this difference, up to an error of 2 ε n = o ( n − 1 / 2 ) 2\varepsilon_n=o(n^{-1/2}) 2 ε n = o ( n − 1/2 ) . So by step 2,
Δ p ( s ) = lim n → ∞ κ p E [ H s ( Z ( n ) ) ] = κ p E [ H s ( Z ) ] . \Delta_p(s)=\lim_{n\to\infty}\kappa_p\mathbb{E}[H_s(Z^{(n)})]=\kappa_p\mathbb{E}[H_s(Z)]. Δ p ( s ) = n → ∞ lim κ p E [ H s ( Z ( n ) )] = κ p E [ H s ( Z )] .
As κ p > 0 \kappa_p>0 κ p > 0 , step 3 shows this is nonnegative, with equality if, and only if, s s s is a positive affine transformation of s ∗ ( p ) s^{*}(p) s ∗ ( p ) .
(5) The ratio in Definition 2. For every social choice function g g g , Lemma 4 gives E [ V p ( u , g ( σ ) ) ] ≤ E [ V p ( u , f s ∗ ( p ) ( σ ) ) ] \mathbb{E}[V_p(u,g(\sigma))]\leq\mathbb{E}[V_p(u,f_{s^{*}(p)}(\sigma))] E [ V p ( u , g ( σ ))] ≤ E [ V p ( u , f s ∗ ( p ) ( σ ))] . By Lemma 3 this gives ESW p ( g ) − ESW p ( f s ∗ ( p ) ) ≤ 2 ε n \operatorname{ESW}_p(g)-\operatorname{ESW}_p(f_{s^{*}(p)})\leq2\varepsilon_n ESW p ( g ) − ESW p ( f s ∗ ( p ) ) ≤ 2 ε n , so OPT n − ESW p ( f s ∗ ( p ) ) = o ( n − 1 / 2 ) \operatorname{OPT}_n-\operatorname{ESW}_p(f_{s^{*}(p)})=o(n^{-1/2}) OPT n − ESW p ( f s ∗ ( p ) ) = o ( n − 1/2 ) . We apply the argument at the start of Appendix A with c n = n 1 / 2 c_n=n^{1/2} c n = n 1/2 and f ∘ = f s ∗ ( p ) f^\circ=f_{s^{*}(p)} f ∘ = f s ∗ ( p ) . This gives Δ ( f s ) = Δ p ( s ) \Delta(f_s)=\Delta_p(s) Δ ( f s ) = Δ p ( s ) , and Δ ( f 1 ) = Δ p ( 1 ) > 0 \Delta(f_1)=\Delta_p(1)>0 Δ ( f 1 ) = Δ p ( 1 ) > 0 by step 4, as 1 1 1 is constant. So the ratio converges to Δ p ( s ) / Δ p ( 1 ) \Delta_p(s)/\Delta_p(1) Δ p ( s ) / Δ p ( 1 ) , which is 0 0 0 if, and only if, s s s is a positive affine transformation of s ∗ ( p ) s^{*}(p) s ∗ ( p ) . □
Exact Egalitarian Social Welfare
Throughout this section and the next we make a new assumption, slightly stronger than A1, which aligns our model with Apesteguia et al. [3 ] .
So each utility is an independent draw with CDF F F F , which is continuous by A2. Let ℓ = inf supp ( F ) \ell= \inf\operatorname{supp}(F) ℓ = inf supp ( F ) denote the lowest possible utility. Write ESW − ∞ ( f ) = E [ min i u i ( f ( σ ) ) ] \operatorname{ESW}_{-\infty}(f) = \mathbb{E}[\min_i u_i(f(\boldsymbol{\sigma}))] ESW − ∞ ( f ) = E [ min i u i ( f ( σ ))] for the expected egalitarian social welfare of a social choice function f f f , and take OPT n \operatorname{OPT}_n OPT n in Definition 2 with respect to ESW − ∞ \operatorname{ESW}_{-\infty} ESW − ∞ .
We also require that F F F has a continuous and positive density near its lowest value. This holds, for example, for the uniform distribution on any interval and for the exponential distribution.
(A4) For some δ > 0 \delta> 0 δ > 0 , F F F is continuously differentiable on [ ℓ , ℓ + δ ] [\ell, \ell+\delta] [ ℓ , ℓ + δ ] , with λ : = F ′ ( ℓ ) > 0 \lambda:= F'(\ell) > 0 λ := F ′ ( ℓ ) > 0 .
Theorem A.3. Assume A1+, A4, and E [ U ] < ∞ \mathbb{E}[U] < \infty E [ U ] < ∞ , and denote the veto vector as s v = ( 1 , … , 1 , 0 ) \mathbf{s}^{v} = (1,\ldots,1,0) s v = ( 1 , … , 1 , 0 ) . For every score vector s ∈ R m \mathbf{s} \in\mathbb{R}^{m} s ∈ R m the limit
Δ − ∞ ( s ) = lim n → ∞ n 3 2 ( ESW − ∞ ( f s v ) − ESW − ∞ ( f s ) ) \Delta_{-\infty}(\mathbf{s}) = \lim_{n\to\infty} n^{\frac{3}{2}}\left(\operatorname{ESW}_{-\infty}(f_{\mathbf{s}^{v}})-\operatorname{ESW}_{-\infty}(f_{\mathbf{s}})\right) Δ − ∞ ( s ) = n → ∞ lim n 2 3 ( ESW − ∞ ( f s v ) − ESW − ∞ ( f s ) ) exists and is nonnegative, and Δ − ∞ ( s ) = 0 \Delta_{-\infty}(\mathbf{s}) = 0 Δ − ∞ ( s ) = 0 if, and only if, s = s v \mathbf{s} = \mathbf{s}^{v} s = s v . That is, veto is the unique asymptotically average-case optimal positional scoring rule for egalitarian social welfare.
Proof. Fix a preference profile σ \boldsymbol{\sigma} σ . For each a ∈ A a \in A a ∈ A let K a K_a K a be the number of voters who rank a a a last, M a = min i u i ( a ) M_a = \min_i u_i(a) M a = min i u i ( a ) the egalitarian social welfare of a a a , and L a L_a L a its last-place welfare (Lemma 5). Write f v = f s v f_v = f_{\mathbf{s}^{v}} f v = f s v , K min = min a K a K_{\min} = \min_a K_a K m i n = min a K a and b = f s ( σ ) b = f_{\mathbf{s}}(\boldsymbol{\sigma}) b = f s ( σ ) . As S s v ( a , σ ) = n − K a S_{\mathbf{s}^{v}}(a,\boldsymbol{\sigma}) = n-K_a S s v ( a , σ ) = n − K a , veto elects an alternative ranked last least often. The proof shows that egalitarian welfare is almost exactly last-place welfare, which veto maximizes, and that any other rule loses welfare in proportion to the extra last places of its winner.
Step 1: veto maximizes expected last-place welfare. By Lemma 5(b), E [ L a ∣ σ ] = φ ( K a ) \mathbb{E}[L_a\mid\boldsymbol{\sigma}] = \varphi(K_a) E [ L a ∣ σ ] = φ ( K a ) decreases with the number of voters ranking a a a last. Veto elects an alternative with the fewest such voters, so for any social choice function g g g ,
E [ L g ( σ ) ∣ σ ] ≤ φ ( K min ) = E [ L f v ( σ ) ∣ σ ] . \mathbb{E}[L_{g(\boldsymbol{\sigma})}\mid\boldsymbol{\sigma}] \le\varphi(K_{\min}) = \mathbb{E}[L_{f_v(\boldsymbol{\sigma})}\mid\boldsymbol{\sigma}]. E [ L g ( σ ) ∣ σ ] ≤ φ ( K m i n ) = E [ L f v ( σ ) ∣ σ ] .
Step 2: last-place welfare approximates egalitarian welfare. Typically every alternative is ranked last by about n m \frac{n}{m} m n voters. Let B B B be the event that some alternative is ranked last by fewer than n 2 m \frac{n}{2m} 2 m n voters. By Hoeffding’s inequality, B B B has exponentially small probability, and as expected welfare is bounded, profiles in B B B can be ignored. Outside B B B , Lemma 5(c) shows that L a L_a L a and M a M_a M a differ in expectation by at most C ′ n − 2 C'n^{-2} C ′ n − 2 for every alternative. Combined with Step 1, no social choice function has expected egalitarian welfare more than O ( n − 2 ) O(n^{-2}) O ( n − 2 ) above that of veto, that is,
0 ≤ OPT n − ESW − ∞ ( f v ) = O ( n − 2 ) . (7) 0 \le\operatorname{OPT}_n-\operatorname{ESW}_{-\infty}(f_v)=O(n^{-2}). \tag*{(7)} 0 ≤ OPT n − ESW − ∞ ( f v ) = O ( n − 2 ) . (7)
For a positional scoring rule f s f_{\mathbf{s}} f s , the same bounds give
n 3 2 ( ESW − ∞ ( f v ) − ESW − ∞ ( f s ) ) = n 3 2 E [ ( φ ( K min ) − φ ( K b ) ) 1 B c ] + o ( 1 ) , (8) n^{\frac{3}{2}}\left(\operatorname{ESW}_{-\infty}(f_v)-\operatorname{ESW}_{-\infty}(f_{\mathbf{s}})\right)
= n^{\frac{3}{2}}\mathbb{E}\left[(\varphi(K_{\min})-\varphi(K_b))\mathbf{1}_{B^c}\right]+o(1), \tag*{(8)} n 2 3 ( ESW − ∞ ( f v ) − ESW − ∞ ( f s ) ) = n 2 3 E [ ( φ ( K m i n ) − φ ( K b )) 1 B c ] + o ( 1 ) , (8)
so it remains to compare expected last-place welfare.
Step 3: the cost of electing an alternative ranked last too often. Electing b b b instead of the veto winner means electing an alternative ranked last K b − K min K_b-K_{\min} K b − K m i n more times. Outside B B B , both are close to n m \frac{n}{m} m n , so by Lemma 6 this costs
φ ( K min ) − φ ( K b ) ≈ m ( K b − K min ) λ n 2 . \varphi(K_{\min})-\varphi(K_b)\approx\frac{m(K_b-K_{\min})}{\lambda n^2}. φ ( K m i n ) − φ ( K b ) ≈ λ n 2 m ( K b − K m i n ) .
The excess K b − K min K_b-K_{\min} K b − K m i n is of order n 1 2 n^{\frac{1}{2}} n 2 1 , the scale at which the counts K a K_a K a fluctuate. Let Z ( n ) Z^{(n)} Z ( n ) , Z Z Z and H s H_s H s be as in the proof of Theorem A.2 with reference vector r = s \mathbf{r}=\mathbf{s} r = s . As S s ( a , σ ) = n − K a S_{\mathbf{s}}(a,\boldsymbol{\sigma})=n-K_a S s ( a , σ ) = n − K a , (6) gives E [ K b − K min ∣ σ ] = n 1 2 H s ( Z ( n ) ) \mathbb{E}[K_b-K_{\min}\mid\boldsymbol{\sigma}]=n^{\frac{1}{2}}H_s(Z^{(n)}) E [ K b − K m i n ∣ σ ] = n 2 1 H s ( Z ( n ) ) . By steps 1 and 2 of that proof, H s ( Z ( n ) ) H_s(Z^{(n)}) H s ( Z ( n ) ) is uniformly integrable and E [ H s ( Z ( n ) ) ] → E [ H s ( Z ) ] \mathbb{E}[H_s(Z^{(n)})]\to\mathbb{E}[H_s(Z)] E [ H s ( Z ( n ) )] → E [ H s ( Z )] . The approximations become exact in the limit, so by (8) the limit exists and
Δ − ∞ ( s ) = m λ E [ H s ( Z ) ] . \Delta_{-\infty}(\mathbf{s})=\frac{m}{\lambda}\mathbb{E}[H_s(Z)]. Δ − ∞ ( s ) = λ m E [ H s ( Z )] .
So the welfare a positional scoring rule loses is proportional to how many extra last places, on average, its winner has.
Step 4: veto minimizes welfare loss. By step 3 of the proof of Theorem A.2 with r = s v \mathbf{r}=\mathbf{s}^{v} r = s v , Δ − ∞ ( s ) ≥ 0 \Delta_{-\infty}(\mathbf{s})\ge0 Δ − ∞ ( s ) ≥ 0 , with equality if, and only if, s = α s v + β 1 \mathbf{s}=\alpha\mathbf{s}^{v}+\beta\mathbf{1} s = α s v + β 1 for some α > 0 \alpha>0 α > 0 and β ∈ R \beta\in\mathbb{R} β ∈ R . In particular Δ − ∞ ( 1 ) > 0 \Delta_{-\infty}(\mathbf{1})>0 Δ − ∞ ( 1 ) > 0 . By (7), n 3 2 ( OPT n − ESW − ∞ ( f v ) ) → 0 n^{\frac{3}{2}}(\operatorname{OPT}_n-\operatorname{ESW}_{-\infty}(f_v))\to0 n 2 3 ( OPT n − ESW − ∞ ( f v )) → 0 , so the argument at the start of Appendix A applies with c n = n 3 2 c_n=n^{\frac{3}{2}} c n = n 2 3 and f ∘ = f v f^\circ=f_v f ∘ = f v . Hence veto is, up to positive affine transformation, the unique asymptotically average-case optimal positional scoring rule. The factor m λ \frac{m}{\lambda} λ m cancels in the ratio, so its limit, E [ H s ( Z ) ] / E [ H 1 ( Z ) ] \mathbb{E}[H_s(Z)]/\mathbb{E}[H_{\mathbf{1}}(Z)] E [ H s ( Z )] / E [ H 1 ( Z )] , depends only on m m m and s \mathbf{s} s and not on F F F . □ \square □
Lemma 5 (Last-place welfare). Assume A1+, A4 and E [ U ] < ∞ \mathbb{E}[U] < \infty E [ U ] < ∞ . Fix a preference profile σ \boldsymbol{\sigma} σ and a ∈ A a \in A a ∈ A . Let K a K_a K a be the number of voters who rank a a a last, M a : = min i u i ( a ) M_a := \min_i u_i(a) M a := min i u i ( a ) , and let L a : = min i : σ i ( a ) = m u i ( a ) L_a := \min_{i:\sigma_i(a)=m} u_i(a) L a := min i : σ i ( a ) = m u i ( a ) be the last-place welfare of a a a , with L a = + ∞ L_a=+\infty L a = + ∞ if K a = 0 K_a=0 K a = 0 . Then
(a) M a ≤ L a M_a \le L_a M a ≤ L a ;
(b) Pr ( L a > x ∣ σ ) = ( 1 − F ( x ) ) m K a \Pr(L_a>x\mid\boldsymbol{\sigma})=(1-F(x))^{mK_a} Pr ( L a > x ∣ σ ) = ( 1 − F ( x ) ) m K a for every x x x , so E [ L a ∣ σ ] = φ ( K a ) \mathbb{E}[L_a\mid\boldsymbol{\sigma}]=\varphi(K_a) E [ L a ∣ σ ] = φ ( K a ) , where φ ( k ) : = ∫ 0 ∞ ( 1 − F ( x ) ) m k d x \varphi(k):=\int_0^\infty(1-F(x))^{mk}\,dx φ ( k ) := ∫ 0 ∞ ( 1 − F ( x ) ) mk d x is nonincreasing in k k k ; and
(c) there is a constant C ′ C' C ′ , depending only on F F F and m m m , such that E [ L a − M a ∣ σ ] ≤ C ′ n − 2 \mathbb{E}[L_a-M_a\mid\boldsymbol{\sigma}]\le C'n^{-2} E [ L a − M a ∣ σ ] ≤ C ′ n − 2 whenever K a ≥ n 2 m K_a\ge\frac{n}{2m} K a ≥ 2 m n .
Intuitively, (b) says that the more voters rank a a a last, the lower its expected last-place welfare. Part (c) says that the lowest utility given to a a a almost always comes from a voter who ranks a a a last.
Proof. Condition on σ \boldsymbol{\sigma} σ throughout. Utilities of different voters remain independent. By Lemma 4, a voter who ranks a a a in position k k k gives a a a a utility distributed as U ( k ) U_{(k)} U ( k ) , which by A1+ is the k k k -th largest of m m m independent draws from F F F .
(a) The voters ranking a a a last are a subset of all voters.
(b) L a L_a L a is the smallest of K a K_a K a independent copies of U ( m ) U_{(m)} U ( m ) , each the smallest of m m m draws from F F F . So L a L_a L a is the minimum of m K a mK_a m K a independent draws from F F F , which gives the stated probability. Integrating over x x x gives E [ L a ∣ σ ] = φ ( K a ) \mathbb{E}[L_a\mid\boldsymbol{\sigma}]=\varphi(K_a) E [ L a ∣ σ ] = φ ( K a ) . More voters ranking a a a last means more draws, so φ \varphi φ is nonincreasing.
(c) As L a − M a = ∫ 0 ∞ 1 { M a ≤ x < L a } d x L_a-M_a=\int_0^\infty\mathbf{1}\{M_a\le x<L_a\}\,dx L a − M a = ∫ 0 ∞ 1 { M a ≤ x < L a } d x , we bound Pr ( M a ≤ x < L a ∣ σ ) \Pr(M_a\le x<L_a\mid\boldsymbol{\sigma}) Pr ( M a ≤ x < L a ∣ σ ) . This event requires two independent things. First, every voter ranking a a a last gives a more than x x x , which by (b) has probability ( 1 − F ( x ) ) m K a (1-F(x))^{mK_a} ( 1 − F ( x ) ) m K a . Second, some other voter gives a a a at most x x x . Such a voter ranks some alternative below a a a , so at least two of their m m m draws are at most x x x , which has probability at most ( m 2 ) F ( x ) 2 \binom{m}{2}F(x)^2 ( 2 m ) F ( x ) 2 . A union bound over at most n n n such voters gives
Pr ( M a ≤ x < L a ∣ σ ) ≤ ( m 2 ) n ( 1 − F ( x ) ) m K a F ( x ) 2 . \Pr(M_a \le x < L_a \mid\sigma) \le\binom{m}{2} n (1-F(x))^{mK_a}F(x)^2. Pr ( M a ≤ x < L a ∣ σ ) ≤ ( 2 m ) n ( 1 − F ( x ) ) m K a F ( x ) 2 .
As m K a ≥ n 2 mK_a \ge\frac{n}{2} m K a ≥ 2 n , the factor ( 1 − F ( x ) ) m K a (1-F(x))^{mK_a} ( 1 − F ( x ) ) m K a is exponentially small in n n n except near ℓ \ell ℓ . Near ℓ \ell ℓ , F F F has slope at least λ 2 \frac{\lambda}{2} 2 λ by A4, so substituting u = F ( x ) u=F(x) u = F ( x ) bounds the integral over x x x by
2 λ ∫ 0 1 ( 1 − u ) n 2 u 2 d u = O ( n − 3 ) . \frac{2}{\lambda}\int_0^1 (1-u)^{\frac{n}{2}}u^2\,du=O(n^{-3}). λ 2 ∫ 0 1 ( 1 − u ) 2 n u 2 d u = O ( n − 3 ) .
Multiplying by ( m 2 ) n \binom{m}{2}n ( 2 m ) n gives (c). □ \square □
Lemma 6. Assume A1† ^{\dagger} † , A4 and E [ U ] < ∞ \mathbb{E}[U]<\infty E [ U ] < ∞ , and let φ \varphi φ be as in Lemma 5(b). For every θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) there are constants C > 0 C>0 C > 0 and γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) such that, for all integers 1 ≤ K ≤ K ′ 1\le K\le K' 1 ≤ K ≤ K ′ ,
∣ λ ( φ ( K ) − φ ( K ′ ) ) − A ∣ ≤ θ A + C γ K \left|\lambda(\varphi(K)-\varphi(K'))-A\right|\le\theta A+C\gamma^K ∣ λ ( φ ( K ) − φ ( K ′ )) − A ∣ ≤ θ A + C γ K where
A : = 1 m K + 1 − 1 m K ′ + 1 = m ( K ′ − K ) ( m K + 1 ) ( m K ′ + 1 ) . A:=\frac{1}{mK+1}-\frac{1}{mK'+1}=\frac{m(K'-K)}{(mK+1)(mK'+1)}. A := m K + 1 1 − m K ′ + 1 1 = ( m K + 1 ) ( m K ′ + 1 ) m ( K ′ − K ) .
Proof. Write φ ( K ) − φ ( K ′ ) = ∫ ℓ ∞ g ( F ( x ) ) d x \varphi(K)-\varphi(K')=\int_{\ell}^{\infty}g(F(x))\,dx φ ( K ) − φ ( K ′ ) = ∫ ℓ ∞ g ( F ( x )) d x with g ( u ) = ( 1 − u ) m K − ( 1 − u ) m K ′ ≥ 0 g(u)=(1-u)^{mK}-(1-u)^{mK'}\ge0 g ( u ) = ( 1 − u ) m K − ( 1 − u ) m K ′ ≥ 0 , which vanishes below ℓ \ell ℓ as g ( 0 ) = 0 g(0)=0 g ( 0 ) = 0 . If F F F were uniform with density λ \lambda λ starting at ℓ \ell ℓ , substituting u = F ( x ) u=F(x) u = F ( x ) would give exactly λ ( φ ( K ) − φ ( K ′ ) ) = ∫ 0 1 g ( u ) d u = A \lambda(\varphi(K)-\varphi(K'))=\int_0^1g(u)\,du=A λ ( φ ( K ) − φ ( K ′ )) = ∫ 0 1 g ( u ) d u = A . We bound the two ways F F F can deviate from this. By A4, choose ε ∈ ( 0 , δ ] \varepsilon\in(0,\delta] ε ∈ ( 0 , δ ] such that F ′ F' F ′ is within a factor 1 ± θ 2 1\pm\frac{\theta}{2} 1 ± 2 θ of λ \lambda λ on [ ℓ , ℓ + ε ] [\ell,\ell+\varepsilon] [ ℓ , ℓ + ε ] , and let η : = F ( ℓ + ε ) > 0 \eta:=F(\ell+\varepsilon)>0 η := F ( ℓ + ε ) > 0 .
Near ℓ \ell ℓ . Substituting u = F ( x ) u=F(x) u = F ( x ) on [ ℓ , ℓ + ε ] [\ell,\ell+\varepsilon] [ ℓ , ℓ + ε ] gives λ \lambda λ times the integral there within a factor 1 ± θ 1\pm\theta 1 ± θ of ∫ 0 η g ( u ) d u \int_0^\eta g(u)\,du ∫ 0 η g ( u ) d u . This differs from A A A by at most ∫ η 1 ( 1 − u ) m K d u ≤ ( 1 − η ) m K \int_\eta^1(1-u)^{mK}\,du\le(1-\eta)^{mK} ∫ η 1 ( 1 − u ) m K d u ≤ ( 1 − η ) m K .
Beyond ℓ + ε \ell+\varepsilon ℓ + ε . Here F ( x ) ≥ η F(x)\ge\eta F ( x ) ≥ η , so g ( F ( x ) ) ≤ ( 1 − F ( x ) ) m K ≤ ( 1 − η ) m K − 1 ( 1 − F ( x ) ) g(F(x))\le(1-F(x))^{mK}\le(1-\eta)^{mK-1}(1-F(x)) g ( F ( x )) ≤ ( 1 − F ( x ) ) m K ≤ ( 1 − η ) m K − 1 ( 1 − F ( x )) , which integrates to at most ( 1 − η ) m K − 1 E [ U ] (1-\eta)^{mK-1}\mathbb{E}[U] ( 1 − η ) m K − 1 E [ U ] .
Both errors are at most a constant times γ K \gamma^K γ K with γ = ( 1 − η ) m \gamma=(1-\eta)^m γ = ( 1 − η ) m , which gives the claim. □ \square □
Exact Maximax Social Welfare
The theorem in this section mirrors that of Section A.4 with the roles of the lowest and highest utilities, and of the last and first positions, exchanged. We again assume A1+, and now introduce an assumption on the utility density near the upper end of the utility distribution.
Let ℓ ˉ = sup supp ( F ) \bar{\ell} = \sup\operatorname{supp}(F) ℓ ˉ = sup supp ( F ) denote the highest possible utility. Write ESW + ∞ ( f ) = E [ max i u i ( f ( σ ) ) ] \operatorname{ESW}_{+\infty}(f) = \mathbb{E}[\max_i u_i(f(\boldsymbol{\sigma}))] ESW + ∞ ( f ) = E [ max i u i ( f ( σ ))] for the expected maximax social welfare of a social choice function f f f , and take OPT n \operatorname{OPT}_n OPT n in Definition 2 with respect to ESW + ∞ \operatorname{ESW}_{+\infty} ESW + ∞ .
Similar to A4, we require that F F F has bounded support and a continuous density near its highest value which is positive at ℓ ˉ \bar{\ell} ℓ ˉ . This holds, for example, for the uniform distribution on any interval.
(A5) ℓ ˉ < ∞ \bar{\ell} < \infty ℓ ˉ < ∞ , and for some δ > 0 \delta> 0 δ > 0 , F F F is continuously differentiable on [ ℓ ˉ − δ , ℓ ˉ ] [\bar{\ell} - \delta, \bar{\ell}] [ ℓ ˉ − δ , ℓ ˉ ] , with λ ˉ : = F ′ ( ℓ ˉ ) > 0 \bar{\lambda} := F'(\bar{\ell}) > 0 λ ˉ := F ′ ( ℓ ˉ ) > 0 .
As F F F has bounded support, E [ U ] < ∞ \mathbb{E}[U] < \infty E [ U ] < ∞ holds automatically.
Theorem A.4. Assume A1+ and A5, and denote the plurality vector as s p = ( 1 , 0 , … , 0 ) \mathbf{s}^{p} = (1,0,\ldots,0) s p = ( 1 , 0 , … , 0 ) . For every score vector s ∈ R m \mathbf{s} \in\mathbb{R}^{m} s ∈ R m the limit
Δ + ∞ ( s ) = lim n → ∞ n 3 2 ( ESW + ∞ ( f s p ) − ESW + ∞ ( f s ) ) \Delta_{+\infty}(\mathbf{s}) = \lim_{n \to\infty} n^{\frac{3}{2}}\left(\operatorname{ESW}_{+\infty}(f_{\mathbf{s}^{p}})-\operatorname{ESW}_{+\infty}(f_{\mathbf{s}})\right) Δ + ∞ ( s ) = n → ∞ lim n 2 3 ( ESW + ∞ ( f s p ) − ESW + ∞ ( f s ) ) exists and is nonnegative, and Δ + ∞ ( s ) = 0 \Delta_{+\infty}(\mathbf{s}) = 0 Δ + ∞ ( s ) = 0 if, and only if, s = s p \mathbf{s} = \mathbf{s}^{p} s = s p . That is, plurality is the unique asymptotically average-case optimal positional scoring rule for maximax social welfare.
Proof. Fix a preference profile σ \boldsymbol{\sigma} σ . For each a ∈ A a \in A a ∈ A let K ˉ a \bar{K}_a K ˉ a be the number of voters who rank a a a first, M ˉ a = max i u i ( a ) \bar{M}_a = \max_i u_i(a) M ˉ a = max i u i ( a ) the maximax social welfare of a a a , and L ˉ a \bar{L}_a L ˉ a its first-place welfare (Lemma 7). Write f p = f s p f_p = f_{\mathbf{s}^{p}} f p = f s p , K ˉ max = max a K ˉ a \bar{K}_{\max} = \max_a \bar{K}_a K ˉ m a x = max a K ˉ a and b = f s ( σ ) b = f_{\mathbf{s}}(\boldsymbol{\sigma}) b = f s ( σ ) . As S s p ( a , σ ) = K ˉ a S_{\mathbf{s}^{p}}(a,\boldsymbol{\sigma}) = \bar{K}_a S s p ( a , σ ) = K ˉ a , plurality elects an alternative ranked first most often. The proof mirrors that of Theorem A.3. Maximax welfare is almost exactly first-place welfare, which plurality maximizes, and any other rule loses welfare in proportion to the first places its winner lacks.
Step 1: plurality maximizes expected first-place welfare. By Lemma 7(b), E [ L ˉ a ∣ σ ] = φ ˉ ( K ˉ a ) \mathbb{E}[\bar{L}_a \mid\boldsymbol{\sigma}] = \bar{\varphi}(\bar{K}_a) E [ L ˉ a ∣ σ ] = φ ˉ ( K ˉ a ) increases with the number of voters ranking a a a first. Plurality elects an alternative with the most such voters, so for any social choice function g g g ,
E [ L ˉ g ( σ ) ∣ σ ] ≤ φ ˉ ( K ˉ max ) = E [ L ˉ f p ( σ ) ∣ σ ] . \mathbb{E}[\bar{L}_{g(\boldsymbol{\sigma})}\mid\boldsymbol{\sigma}] \le\bar{\varphi}(\bar{K}_{\max}) = \mathbb{E}[\bar{L}_{f_p(\boldsymbol{\sigma})}\mid\boldsymbol{\sigma}]. E [ L ˉ g ( σ ) ∣ σ ] ≤ φ ˉ ( K ˉ m a x ) = E [ L ˉ f p ( σ ) ∣ σ ] .
Step 2: first-place welfare approximates maximax welfare. Typically every alternative is ranked first by about n m \frac{n}{m} m n voters. Let B B B be the event that some alternative is ranked first by fewer than n 2 m \frac{n}{2m} 2 m n voters. By Hoeffding’s inequality, B B B has exponentially small probability, and as welfare is bounded by ℓ ˉ \bar{\ell} ℓ ˉ , profiles in B B B can be ignored. Outside B B B , Lemma 7(c) shows that L ˉ a \bar{L}_a L ˉ a and M ˉ a \bar{M}_a M ˉ a differ in expectation by at most C ′ n − 2 C'n^{-2} C ′ n − 2 for every alternative. Combined with Step 1, no social choice function has expected maximax welfare more than O ( n − 2 ) O(n^{-2}) O ( n − 2 ) above that of plurality, that is,
0 ≤ OPT n − ESW + ∞ ( f p ) = O ( n − 2 ) . (9) 0 \le\operatorname{OPT}_n-\operatorname{ESW}_{+\infty}(f_p)=O(n^{-2}). \tag*{(9)} 0 ≤ OPT n − ESW + ∞ ( f p ) = O ( n − 2 ) . (9)
For a positional scoring rule f s f_{\mathbf{s}} f s , the same bounds give
n 3 2 ( ESW + ∞ ( f p ) − ESW + ∞ ( f s ) ) = n 3 2 E [ ( φ ˉ ( K ˉ max ) − φ ˉ ( K ˉ b ) ) 1 B c ] + o ( 1 ) , (10) n^{\frac{3}{2}}\left(\operatorname{ESW}_{+\infty}(f_p)-\operatorname{ESW}_{+\infty}(f_{\mathbf{s}})\right)
= n^{\frac{3}{2}}\mathbb{E}\left[(\bar{\varphi}(\bar{K}_{\max})-\bar{\varphi}(\bar{K}_b))\mathbf{1}_{B^c}\right]+o(1), \tag*{(10)} n 2 3 ( ESW + ∞ ( f p ) − ESW + ∞ ( f s ) ) = n 2 3 E [ ( φ ˉ ( K ˉ m a x ) − φ ˉ ( K ˉ b )) 1 B c ] + o ( 1 ) , (10)
so it remains to compare expected first-place welfare.
Step 3: the cost of electing an alternative ranked first too rarely. Electing b b b instead of the plurality winner means electing an alternative ranked first K ˉ max − K ˉ b \bar{K}_{\max}-\bar{K}_b K ˉ m a x − K ˉ b fewer times. Outside B B B , both are close to n m \frac{n}{m} m n , so by Lemma 8 this costs
φ ˉ ( K ˉ max ) − φ ˉ ( K ˉ b ) ≳ m ( K ˉ max − K ˉ b ) λ n 2 . \bar{\varphi}(\bar{K}_{\max})-\bar{\varphi}(\bar{K}_b) \gtrsim\frac{m(\bar{K}_{\max}-\bar{K}_b)}{\lambda n^2}. φ ˉ ( K ˉ m a x ) − φ ˉ ( K ˉ b ) ≳ λ n 2 m ( K ˉ m a x − K ˉ b ) .
The deficit K ˉ max − K ˉ b \bar{K}_{\max}-\bar{K}_b K ˉ m a x − K ˉ b is of order n 1 2 n^{\frac{1}{2}} n 2 1 , the scale at which the counts K ˉ a \bar{K}_a K ˉ a fluctuate. Let Z ( n ) Z^{(n)} Z ( n ) , Z Z Z and H s H_s H s be as in the proof of Theorem A.2 with reference vector r = s p \mathbf{r}=\mathbf{s}^{p} r = s p . As S s p ( a , σ ) = K ˉ a S_{\mathbf{s}^{p}}(a,\boldsymbol{\sigma})=\bar{K}_a S s p ( a , σ ) = K ˉ a , (6) gives E [ K ˉ max − K ˉ b ∣ σ ] = n 1 2 H s ( Z ( n ) ) \mathbb{E}[\bar{K}_{\max}-\bar{K}_b\mid\boldsymbol{\sigma}]=n^{\frac{1}{2}}H_s(Z^{(n)}) E [ K ˉ m a x − K ˉ b ∣ σ ] = n 2 1 H s ( Z ( n ) ) . By steps 1 and 2 of that proof, H s ( Z ( n ) ) H_s(Z^{(n)}) H s ( Z ( n ) ) is uniformly integrable and E [ H s ( Z ( n ) ) ] → E [ H s ( Z ) ] \mathbb{E}[H_s(Z^{(n)})]\to\mathbb{E}[H_s(Z)] E [ H s ( Z ( n ) )] → E [ H s ( Z )] . The approximations become exact in the limit, so by (10) the limit exists and
Δ + ∞ ( s ) = m λ ˉ E [ H s ( Z ) ] . \Delta_{+\infty}(\mathbf{s}) = \frac{m}{\bar{\lambda}}\mathbb{E}[H_s(Z)]. Δ + ∞ ( s ) = λ ˉ m E [ H s ( Z )] .
So the welfare a positional scoring rule loses is proportional to how many fewer first places, on average, its winner has.
Step 4: plurality minimizes welfare loss. By step 3 of the proof of Theorem A.2 with r = s p \mathbf{r}=\mathbf{s}^{p} r = s p , Δ + ∞ ( s ) ≥ 0 \Delta_{+\infty}(\mathbf{s}) \ge0 Δ + ∞ ( s ) ≥ 0 , with equality if, and only if, s = α s p + β 1 \mathbf{s}=\alpha\mathbf{s}^{p}+\beta\mathbf{1} s = α s p + β 1 for some α > 0 \alpha>0 α > 0 and β ∈ R \beta\in\mathbb{R} β ∈ R . In particular Δ + ∞ ( 1 ) > 0 \Delta_{+\infty}(\mathbf{1})>0 Δ + ∞ ( 1 ) > 0 . By (9), n 3 2 ( OPT n − ESW + ∞ ( f p ) ) → 0 n^{\frac{3}{2}}(\operatorname{OPT}_n-\operatorname{ESW}_{+\infty}(f_p))\to0 n 2 3 ( OPT n − ESW + ∞ ( f p )) → 0 , so the argument at the start of Appendix A applies with c n = n 1 2 c_n=n^{\frac{1}{2}} c n = n 2 1 and f = f p f=f_p f = f p . Hence plurality is, up to positive affine transformation, the unique asymptotically average-case optimal positional scoring rule. As in Theorem A.3, the factor m λ ˉ \frac{m}{\bar{\lambda}} λ ˉ m cancels in the ratio, so its limit does not depend on F F F . □ \square □
Lemma 7 (First-place welfare). Assume A1+ and A5. Fix a preference profile σ \boldsymbol{\sigma} σ and a ∈ A a \in A a ∈ A . Let K ˉ a \bar{K}_a K ˉ a be the number of voters who rank a a a first, M ˉ a : = max i u i ( a ) \bar{M}_a := \max_i u_i(a) M ˉ a := max i u i ( a ) , and let L ˉ a : = max i : σ i ( a ) = 1 u i ( a ) \bar{L}_a := \max_{i:\sigma_i(a)=1}u_i(a) L ˉ a := max i : σ i ( a ) = 1 u i ( a ) be the first-place welfare of a a a , with L ˉ a = 0 \bar{L}_a=0 L ˉ a = 0 if K ˉ a = 0 \bar{K}_a=0 K ˉ a = 0 . Then
(a) L ˉ a ≤ M ˉ a \bar{L}_a \le\bar{M}_a L ˉ a ≤ M ˉ a ;
(b) Pr ( L ˉ a ≤ x ∣ σ ) = F ( x ) m K ˉ a \Pr(\bar{L}_a \le x\mid\boldsymbol{\sigma})=F(x)^{m\bar{K}_a} Pr ( L ˉ a ≤ x ∣ σ ) = F ( x ) m K ˉ a for every x ≥ 0 x\ge0 x ≥ 0 , so E [ L ˉ a ∣ σ ] = φ ˉ ( K ˉ a ) \mathbb{E}[\bar{L}_a\mid\boldsymbol{\sigma}]=\bar{\varphi}(\bar{K}_a) E [ L ˉ a ∣ σ ] = φ ˉ ( K ˉ a ) , where φ ˉ ( k ) : = ℓ ˉ − ∫ 0 ℓ ˉ F ( x ) m k d x \bar{\varphi}(k):=\bar{\ell}-\int_0^{\bar{\ell}}F(x)^{mk}\,dx φ ˉ ( k ) := ℓ ˉ − ∫ 0 ℓ ˉ F ( x ) mk d x is nondecreasing in k k k ; and
(c) there is a constant C ′ C' C ′ , depending only on F F F and m m m , such that E [ M ˉ a − L ˉ a ∣ σ ] ≤ C ′ n − 2 \mathbb{E}[\bar{M}_a-\bar{L}_a\mid\boldsymbol{\sigma}]\le C'n^{-2} E [ M ˉ a − L ˉ a ∣ σ ] ≤ C ′ n − 2 whenever K ˉ a ≥ n 2 m \bar{K}_a\ge\frac{n}{2m} K ˉ a ≥ 2 m n .
Intuitively, (b) says that the more voters rank a a a first, the higher its expected first-place welfare. Part (c) says that the highest utility given to a a a almost always comes from a voter who ranks a a a first.
Proof. Condition on σ \boldsymbol{\sigma} σ throughout. Utilities of different voters remain independent. By Lemma 4, a voter who ranks a a a in position k k k gives a a a a utility distributed as U ( k ) U_{(k)} U ( k ) , which by A1+ is the k k k -th largest of m m m independent draws from F F F .
(a) The voters ranking a a a first are a subset of all voters, and utilities are positive.
(b) L ˉ a \bar{L}_a L ˉ a is the largest of K ˉ a \bar{K}_a K ˉ a independent copies of U ( 1 ) U_{(1)} U ( 1 ) , each the largest of m m m draws from F F F . So L ˉ a \bar{L}_a L ˉ a is the largest of m K ˉ a m\bar{K}_a m K ˉ a independent draws from F F F , which gives the stated probability. As 0 ≤ L ˉ a ≤ ℓ ˉ 0\le\bar{L}_a\le\bar{\ell} 0 ≤ L ˉ a ≤ ℓ ˉ , integrating Pr ( L ˉ a ≤ x ∣ σ ) \Pr(\bar{L}_a\le x\mid\boldsymbol{\sigma}) Pr ( L ˉ a ≤ x ∣ σ ) over [ 0 , ℓ ˉ ] [0,\bar{\ell}] [ 0 , ℓ ˉ ] gives E [ L ˉ a ∣ σ ] = φ ˉ ( K ˉ a ) \mathbb{E}[\bar{L}_a\mid\boldsymbol{\sigma}]=\bar{\varphi}(\bar{K}_a) E [ L ˉ a ∣ σ ] = φ ˉ ( K ˉ a ) . More voters ranking a a a first means more draws, so φ ˉ \bar{\varphi} φ ˉ is nondecreasing.
(c) As M ˉ a − L ˉ a = ∫ 0 ℓ ˉ 1 { L ˉ a ≤ x < M ˉ a } d x \bar{M}_a-\bar{L}_a=\int_0^{\bar{\ell}}\mathbf{1}\{\bar{L}_a\le x<\bar{M}_a\}\,dx M ˉ a − L ˉ a = ∫ 0 ℓ ˉ 1 { L ˉ a ≤ x < M ˉ a } d x , we bound Pr ( L ˉ a ≤ x < M ˉ a ∣ σ ) \Pr(\bar{L}_a\le x<\bar{M}_a\mid\boldsymbol{\sigma}) Pr ( L ˉ a ≤ x < M ˉ a ∣ σ ) . This event requires two independent things. First, every voter ranking a a a first gives a a a at most x x x , which by (b) has probability F ( x ) m K ˉ a F(x)^{m\bar K_a} F ( x ) m K ˉ a . Second, some other voter gives a a a more than x x x . Such a voter ranks some alternative above a a a , so at least two of their m m m draws exceed x x x , which has probability at most ( m 2 ) ( 1 − F ( x ) ) 2 \binom{m}{2}(1-F(x))^2 ( 2 m ) ( 1 − F ( x ) ) 2 . A union bound over at most n n n such voters gives
Pr ( L ˉ a ≤ x < M ˉ a ∣ σ ) ≤ ( m 2 ) n F ( x ) m K ˉ a ( 1 − F ( x ) ) 2 . \Pr(\bar L_a \le x < \bar M_a \mid\sigma) \le\binom{m}{2}nF(x)^{m\bar K_a}(1-F(x))^2. Pr ( L ˉ a ≤ x < M ˉ a ∣ σ ) ≤ ( 2 m ) n F ( x ) m K ˉ a ( 1 − F ( x ) ) 2 .
As m K ˉ a ≥ n 2 m\bar K_a \ge\frac{n}{2} m K ˉ a ≥ 2 n , the factor F ( x ) m K ˉ a F(x)^{m\bar K_a} F ( x ) m K ˉ a is exponentially small in n n n except near ℓ ˉ \bar\ell ℓ ˉ . Near ℓ ˉ \bar\ell ℓ ˉ , F F F has slope at least λ ˉ 2 \frac{\bar\lambda}{2} 2 λ ˉ by A5, so substituting u = 1 − F ( x ) u=1-F(x) u = 1 − F ( x ) bounds the integral over x x x by
2 λ ˉ ∫ 0 1 ( 1 − u ) n / 2 u 2 d u = O ( n − 3 ) . \frac{2}{\bar\lambda}\int_0^1(1-u)^{n/2}u^2\,du=O(n^{-3}). λ ˉ 2 ∫ 0 1 ( 1 − u ) n /2 u 2 d u = O ( n − 3 ) .
Multiplying by ( m 2 ) n \binom{m}{2}n ( 2 m ) n gives (c). □
Lemma 8. Assume A1+ ^+ + and A5, and let φ ˉ \bar\varphi φ ˉ be as in Lemma 7(b). For every θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) there are constants C > 0 C>0 C > 0 and γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) such that, for all integers 1 ≤ K ≤ K ′ 1\le K\le K' 1 ≤ K ≤ K ′ ,
∣ λ ˉ ( φ ˉ ( K ′ ) − φ ˉ ( K ) ) − A ∣ ≤ θ A + C γ K , \left|\bar\lambda(\bar\varphi(K')-\bar\varphi(K))-A\right|\le\theta A+C\gamma^K, λ ˉ ( φ ˉ ( K ′ ) − φ ˉ ( K )) − A ≤ θ A + C γ K , where
A : = 1 m K + 1 − 1 m K ′ + 1 = m ( K ′ − K ) ( m K + 1 ) ( m K ′ + 1 ) . A:=\frac{1}{mK+1}-\frac{1}{mK'+1}=\frac{m(K'-K)}{(mK+1)(mK'+1)}. A := m K + 1 1 − m K ′ + 1 1 = ( m K + 1 ) ( m K ′ + 1 ) m ( K ′ − K ) . Proof. Write φ ˉ ( K ′ ) − φ ˉ ( K ) = ∫ 0 ℓ ˉ g ( 1 − F ( x ) ) d x \bar\varphi(K')-\bar\varphi(K)=\int_0^{\bar\ell}g(1-F(x))\,dx φ ˉ ( K ′ ) − φ ˉ ( K ) = ∫ 0 ℓ ˉ g ( 1 − F ( x )) d x with g ( u ) = ( 1 − u ) m K − ( 1 − u ) m K ′ ≥ 0 g(u)=(1-u)^{mK}-(1-u)^{mK'}\ge0 g ( u ) = ( 1 − u ) m K − ( 1 − u ) m K ′ ≥ 0 . If F F F were uniform with density λ ˉ \bar\lambda λ ˉ ending at ℓ ˉ \bar\ell ℓ ˉ , substituting u = 1 − F ( x ) u=1-F(x) u = 1 − F ( x ) would give exactly λ ˉ ( φ ˉ ( K ′ ) − φ ˉ ( K ) ) = ∫ 0 1 g ( u ) d u = A \bar\lambda(\bar\varphi(K')-\bar\varphi(K))=\int_0^1g(u)\,du=A λ ˉ ( φ ˉ ( K ′ ) − φ ˉ ( K )) = ∫ 0 1 g ( u ) d u = A . We bound the two ways F F F can deviate from this.
By A5, choose ε ∈ ( 0 , δ ] \varepsilon\in(0,\delta] ε ∈ ( 0 , δ ] such that F F F is within a factor 1 ± θ 2 1\pm\frac{\theta}{2} 1 ± 2 θ of λ ˉ \bar\lambda λ ˉ on [ ℓ ˉ − ε , ℓ ˉ ] [\bar\ell-\varepsilon,\bar\ell] [ ℓ ˉ − ε , ℓ ˉ ] , and let η : = 1 − F ( ℓ ˉ − ε ) > 0 \eta:=1-F(\bar\ell-\varepsilon)>0 η := 1 − F ( ℓ ˉ − ε ) > 0 .
Near ℓ ˉ \bar\ell ℓ ˉ . Substituting u = 1 − F ( x ) u=1-F(x) u = 1 − F ( x ) on [ ℓ ˉ − ε , ℓ ˉ ] [\bar\ell-\varepsilon,\bar\ell] [ ℓ ˉ − ε , ℓ ˉ ] gives λ ˉ \bar\lambda λ ˉ times the integral there within a factor 1 ± θ 2 1\pm\frac{\theta}{2} 1 ± 2 θ of ∫ η 1 g ( u ) d u \int_\eta^1g(u)\,du ∫ η 1 g ( u ) d u . This differs from A A A by at most ∫ 0 η ( 1 − u ) m K d u ≤ ( 1 − η ) m K \int_0^\eta(1-u)^{mK}\,du\le(1-\eta)^{mK} ∫ 0 η ( 1 − u ) m K d u ≤ ( 1 − η ) m K .
Below ℓ ˉ − ε \bar\ell-\varepsilon ℓ ˉ − ε . Here F ( x ) ≤ 1 − η F(x)\le1-\eta F ( x ) ≤ 1 − η , so g ( 1 − F ( x ) ) ≤ F ( x ) m K ( 1 − η ) m K g(1-F(x))\le F(x)^{mK}(1-\eta)^{mK} g ( 1 − F ( x )) ≤ F ( x ) m K ( 1 − η ) m K , which integrates to at most ℓ ˉ ( 1 − η ) m K \bar\ell(1-\eta)^{mK} ℓ ˉ ( 1 − η ) m K .
Both errors are at most a constant times γ K \gamma^K γ K with γ = ( 1 − η ) m \gamma=(1-\eta)^m γ = ( 1 − η ) m , which gives the claim. □
Additional Experiment Discussion
Our experiments utilize SciPy [34 ] for sampling from statistical distributions and PrefSampling [11 ] to generate Euclidean preferences. All experiments were performed on an M2 Macbook Air and the time required to run every experiment reported is roughly 7 hours (total; not 7 hours per experiment). This submission is accompanied by code with a detailed README that contains additional information about experiment runs.
Preference Distributions
Neutral Distributions. We use six different neutral utility distributions in our experiments. We illustrate the PDF and CDF of each distribution in Figure 8 . These are not the only distributions we could use, they are simply chosen to represent a variety of distributions. There is no reason to believe that human (or other agent) utility values would neatly correspond to any specific distribution so we focus on finding generalities that hold across distributions.
Figure 8. Probability Density Function and Cumulative Distribution Function for each utility distribution used in our experiments.
Euclidean Distributions. Euclidean distributions place both voters and alternatives into some underlying geometric space. We use cube and sphere topologies of varying dimensions, all with a diameter 1. With a cube of three dimensions, voters and alternatives are placed within a cube at a location chosen uniformly at random. We use the PrefSampling library [11 ] to generate points within an ℓ \ell ℓ -dimensional cube or on the surface of an ℓ \ell ℓ -dimensional sphere. We illustrate a random sample of m = 20 m = 20 m = 20 alternatives and n = 100 n = 100 n = 100 voters in Figure 9 . Voter utility is proportional to the distance from the voter to each alternative with a voter at location v i v_i v i receiving utility u i = 1 − ∥ v i − a j ∥ 2 d u_i = 1 - \frac{\lVert v_i-a_j\rVert_2}{d} u i = 1 − d ∥ v i − a j ∥ 2 for an alternative at position a j a_j a j . Spheres have a diameter of d = 1 d = 1 d = 1 and cubes have diameter d = ℓ d = \sqrt{\ell} d = ℓ .
Figure 9. Example Euclidean distributions of varying dimensions and topologies. Note that height of voters in the left figure is only included for visualization and each item in the plot is defined fully by its position on the line.
Plackett-Luce Distributions. The Plackett-Luce distribution is considered a generalization of the Bradley-Terry model of preferences and uses a vector of m m m parameters which correspond to the quality of alternatives. An alternative with a higher quality is more likely to be given a higher utility value by a voter. We set weights for each alternative j ∈ { 1 , … , m } j \in\{1,\ldots,m\} j ∈ { 1 , … , m } as,
w j = exp γ ( 1 2 − j − 1 m − 1 ) w_j = \exp\gamma\left(\frac{1}{2} - \frac{j-1}{m-1}\right) w j = exp γ ( 2 1 − m − 1 j − 1 )
Where γ \gamma γ parameterizes the family. Each voter then samples a utility value for each alternative from B e t a ( w j , 1 ) Beta(w_j,1) B e t a ( w j , 1 ) . Using γ = 0 \gamma= 0 γ = 0 recreates a uniform distribution while higher γ \gamma γ increases the expected range of utilities that a voter will take on. We show the CDF of each rank position for various γ \gamma γ in Figure 10 .
Figure 10. CDF of Plackett-Luce utilities for various values of γ \gamma γ . Each series corresponds to the CDF of utility for a single rank position.
Structured Utility Distributions
We include results on several additional parameterizations of distributions in which utilities are not sampled i.i.d. in Figure 11 and Figure 12 . These highlight the novel dynamics shown in the paper body. The optimized score vector on Euclidean distributions in particular exhibit interesting structure which differs based on geometry.
Figure 11. Optimized score vector across distributions as p p p changes. Plackett-Luce with γ = 0 \gamma= 0 γ = 0 provides uniformly distributed utilities and shows how closely optimization matches the theoretical optimal value of s ∗ s^* s ∗ .
Figure 12. Normalized gain across additional distributions as p p p changes. On Euclidean Cube distributions, Borda provides a very strong approximation of optimal welfare across multiple dimensions. As γ \gamma γ increases, all rules but veto appear to perform near optimally with Plackett-Luce utilities. When γ = 0 \gamma= 0 γ = 0 utilities are distributed uniformly at random.