PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Voting: Beyond a Utilitarian View

Ben Armstrong, Nicholas Mattei

arXiv:2610.33293v1cs.GT

TL;DR

Voting rules are evaluated by the social welfare of the alternatives they elect, and earlier results focus on utilitarian welfare. This paper extends optimization to power means, characterizes optimal scoring rules, and finds asymptotic optimality for deterministic PSRs alongside plurality’s randomized optimality under voter independence.

  • Problem

    Prior expected-welfare results focused on utilitarian welfare, leaving the broader power-mean family as a further optimization question.

    Source: §1 · p. 1

  • Method

    The authors characterize deterministic PSR scores for power-mean welfare and analyze which randomized PSRs maximize expected welfare.

    Source: §1 · p. 1, §4 · p. 4, §4.1 · p. 4

  • Results

    Deterministic PSRs are asymptotically optimal across power means; among randomized PSRs, k-approval is optimal and plurality is optimal with independent neutral utilities.

    Source: §7 · p. 8

  • Takeaways & Limitations

    Optimized score vectors often outperform canonical vectors, while highly structured utility distributions can yield novel score-vector shapes.

    Source: §1 · p. 1, §7 · p. 8

    Many theoretical results rely on voter independence, an assumption the authors describe as misaligned with reality.

    Source: §7 · p. 8

Abstract

from arXiv · show

A common measure of the quality of a voting rule is the social welfare of the alternatives it elects. Prior work shows that, when voter utilities are drawn from a neutral distribution, expected utilitarian welfare is maximized by a positional scoring rule. We extend this approach to the power mean family of welfare functions, which includes utilitarian, Nash, and egalitarian welfare as special cases. We show that, across the power mean family, a deterministic positional scoring rule (PSR) is asymptotically optimal for expected social welfare among all social choice functions and we characterize this rule for a broad class of utility distributions. We further show that, among randomized PSRs, plurality uniquely maximizes expected social welfare for all power means. Experimentally, we find that optimal score vectors often yield substantially higher welfare than canonical score vectors. On highly structured utility distributions, optimal score vectors take on novel shapes unlike existing canonical score vectors, highlighting open questions for future analysis.

1 Introduction

Voting rules aggregate ordinal rankings even though voters have underlying utilities, so their quality can be assessed by the welfare of elected alternatives. This paper takes an optimization perspective and extends expected-welfare analysis beyond utilitarian welfare.

1 Introduction

  • Voting aggregates stakeholder preferences into shared decisions, but voters may have underlying utilities they do not know exactly, so ordinal rankings are used.The introduction names uncertain or changing preferences, human–AI misalignment, and noisy communication as possible sources of uncertainty.Source: §1 · p. 1
  • Voting rules can be studied through axiomatic properties or by optimizing a target function such as the sum of voter utilities.The paper focuses on the optimization view, while noting that axiomatic work studies principles that hold across possible preferences.Source: §1 · p. 1
  • Optimization over bounded rule classes can combine with axiomatic considerations, whereas earlier black-box approaches found rules that were not immediately useful in practice.The paper argues PSRs are a suitable target because they are well understood axiomatically.Source: §1 · p. 1
  • The paper extends welfare optimization to power means, finding asymptotically optimal deterministic PSRs and plurality as the optimal randomized PSR under voter independence.Power means include utilitarian, Nash, and egalitarian welfare; the authors also characterize the deterministic rule for a broad class of utility distributions.Source: §1 · p. 1

2 Related Work

Prior average-case work has concentrated on utilitarian welfare, while other work studies worst-case distortion and a smaller set of non-utilitarian objectives. The paper positions its results within these strands of voting-rule optimization.

Average Case Analysis

  • Earlier average-case studies primarily optimize utilitarian welfare, with results for uniform utilities and extensions through simulation or order-statistic-based scoring rules.Borda is optimal under uniform utilities in cited models, and later work studies binomial voting and Euclidean preferences [21].Source: §2 · pp. 1–2

Worst Case Analysis

  • Worst-case distortion research finds unbounded distortion for deterministic PSRs such as Borda and Veto, while randomized harmonic scoring is near-optimal for utilitarian distortion.Subsequent work also shows PSRs can be learned with polynomially many samples.Source: §2 · p. 2

Optimization of Non-Utilitarian SW

  • Prior non-utilitarian work studies power-mean welfare and Nash rules, while Table 1 summarizes the paper’s average-case welfare-maximizing PSRs.The table marks prior exact non-PSR results for Apesteguia et al. and states that plurality applies with neutral alternatives and voter independence.Source: §2 · p. 2, Table 1 · p. 2

3 Model

The model draws voters’ utilities from neutral distributions, converts them to ordinal rankings, and evaluates rules using power-mean social welfare. It defines positional scoring rules and an expected-welfare framework for comparing them.

3 Model

  • Each voter draws a utility vector over alternatives, and the resulting utility functions form a utility profile that induces a preference profile.A voter ranks an alternative higher exactly when its utility is greater; profiles may refer to either utilities or rankings.Source: §3 · p. 2
  • The baseline assumptions make voters’ utility vectors independent draws from the same neutral distribution, with strict rankings; A1+ additionally makes alternatives’ utilities i.i.d.A1 permits within-voter correlation across alternatives, unlike A1+ [3, 13].Source: §3 · p. 2

3.1 Positional Scoring Rules

  • A positional scoring rule assigns each rank a score and selects alternatives with maximal total score; randomized PSRs choose a winner in proportion to score.Scores can be transformed without changing the rule, and feasibility requires nonincreasing scores with the top score strictly above the bottom.Source: §3.1 · p. 2
  • Canonical scoring rules encode different rank-value patterns: plurality rewards only the top rank, while Borda scales scores linearly by rank.The paper also names Veto and Harmonic among canonical PSRs and visualizes these vectors in Figure 1.Source: §3.1 · p. 2, Figure 1 · p. 3

3.2 Social Welfare

  • Social welfare maps voters’ utilities for an alternative to a single quality value, and the power-mean family covers utilitarian, Nash, egalitarian, and maximax cases.The limiting parameter cases p = ±∞ are treated as minimum and maximum welfare.Source: §3.2 · p. 3

3.2.1 Social Welfare Optimization.

  • The framework compares expected welfare over random utility profiles and rule randomization, then defines asymptotic average-case optimality against the best social choice function.Under A1, welfare-optimal rules select alternatives maximizing conditional expected welfare at each preference profile; the asymptotic comparison uses a ratio to distinguish rules as voter counts grow.Source: §3.2.1 · p. 3

4 Optimal Deterministic Rules

For finite p, an asymptotically optimal deterministic positional scoring rule exists, with its score vector characterized through utility order statistics. The traditional welfare cases yield specific optimal vectors, with qualifications for the limiting egalitarian and maximax cases.

4 Optimal Deterministic Rules

  • For finite p, a deterministic positional scoring rule is asymptotically average-case optimal; for utilitarian welfare it maximizes expected welfare for every n.The theorem assumes A3.Source: §4 · p. 4

4.1 The Shape of Optimality

  • The unique asymptotically optimal score vector s*(p) is characterized from the utility distribution's order statistics.The asymptotic welfare gap is nonnegative and equals zero only for this vector.Source: §4.1 · p. 4

4.2 Optimizing for Traditional SW Functions

  • For utilitarian welfare, scores equal the expected utilities of the successive order statistics and are optimal for every n.Source: §4.2 · p. 4
  • For Nash welfare, expected log utilities of successive order statistics give the unique asymptotically optimal scoring rule; an exact optimum also exists for each n.Unlike the utilitarian vector, the exact Nash-optimal vector depends on n.Source: §4.2 · p. 4
  • As p approaches positive infinity, the normalized optimal score vector converges to plurality.Source: §4.2 · p. 4
  • As p approaches negative infinity, the normalized optimal score vector converges to veto.Source: §4.2 · p. 4
  • These limiting vectors are not exact maximax or egalitarian results; the corollaries require A3, and the egalitarian limit fails for Uniform(0,1).Exact egalitarian and maximax cases are treated separately in the appendix.Source: §4.1 · p. 4, §4.2 · p. 5

5 Optimizing Randomized Rules

Among randomized positional scoring rules, the optimal rule depends on assumptions about voter utilities: anonymity yields an optimal k-approval rule, while independent neutral utilities single out plurality. The latter is random dictatorship.

5 Optimizing Randomized Rules

  • Under anonymity, a k-approval rule maximizes expected welfare among randomized PSRs when k maximizes the average expected welfare of voters’ top k choices.Source: §5 · p. 5
  • Randomized PSRs are of normative interest because they are strategy-proof, unlike deterministic PSRs.The cited passage notes this distinction while motivating the analysis of randomized rules.Source: §5 · p. 5
  • When utilities are dependent, k>1 may be optimal if voters’ lower-ranked alternatives benefit the group; independent neutral utilities never favor k>1.Source: §5 · p. 5
  • With independent, neutral utilities, plurality uniquely maximizes randomized-PSR expected welfare for every p and n, yielding random dictatorship.Source: §5 · p. 5

6 Experiments

Experiments examine how optimized score vectors vary across power means and utility settings, and how their welfare compares with canonical rules. They also test settings that relax assumptions about voter preferences.

6.1 Optimal Vectors Across 𝑝

  • Across i.i.d. utility distributions, optimal vectors have similar shapes; low p keeps scores high until late ranks, while p>1 reverses that pattern.Experimentally optimized vectors are shown where s*(p) is not defined.Source: Figure 2 · p. 6, §6.1 · p. 6

6.2 Relaxing Utility Assumptions

  • Optimized vectors can diverge substantially from s*(p): Plackett-Luce divergence grows as neutrality falls, while Euclidean vectors show much larger departures.The Euclidean differences exceed what simulation noise explains.Source: Figure 3 · p. 6, §6.2 · p. 7

6.3 How Important is Optimality?

  • Across settings, no canonical vector stays near-optimal; Borda nevertheless performs similarly to the optimized vector on the Euclidean Cube.The reported canonical-rule gap is large in most settings.Source: Figure 4 · p. 7, Figure 5 · p. 7, §6.3 · p. 7

6.4 Randomized Rules

  • Plurality usually outperforms other randomized rules, but k>1 can do better on Euclidean Cube; randomized rules yield much lower normalized gain than deterministic rules.The randomized-rule comparison spans neutral, independent and non-i.i.d. utility distributions.Source: §6.4 · pp. 7–8, Figure 6 · p. 8, Figure 7 · p. 8

7 Discussion

The discussion extends welfare optimization to power means and identifies deterministic positional scoring rules as asymptotically optimal. It highlights novel score-vector shapes for structured preferences and open questions about dependence and randomized rules.

7 Discussion

  • The optimal deterministic score vector is a direct transform of utility order statistics, and the best ordinal social choice function’s welfare gap from an oracle is characterized.The paper also presents exact and asymptotic scoring functions for Nash welfare and strengthens results for egalitarian and maximax welfare.Source: §7 · p. 8
  • Among randomized positional scoring rules, k-approval maximizes expected social welfare; under independent, neutral utilities, plurality is optimal.The discussion also proposes blending deterministic and randomized approaches to seek welfare alongside properties such as strategy-proofness and fairness.Source: §7 · p. 8
  • Optimal deterministic score vectors often have similar shapes across utility distributions, including Plackett-Luce distributions outside the stated assumptions.For Euclidean preferences, the optimal vectors take novel shapes not described by the theoretical findings.Source: §7 · p. 8
  • Many results rely on voter independence, which the authors describe as misaligned with reality; Euclidean preferences are a proposed direction for further theoretical analysis.The authors also suggest studying bounded-randomness approaches that could balance welfare with axiomatic properties.Source: §7 · p. 8

A Missing Proofs of Theoretical Claims

The appendix supplies omitted proofs, including an asymptotic-optimality argument and a utility transformation used throughout the proofs.

A Missing Proofs of Theoretical Claims

  • The appendix contains proofs for the Box-Cox transform, the use of Young’s lemma to establish a positional scoring rule, and the optimal scoring-rule shape.The asymptotic-optimality argument compares a rule with a reference rule using a rate that grows while the reference rule’s welfare gap shrinks.Source: A Missing Proofs of Theoretical Claims · p. 10
  • A rule is asymptotically average-case optimal exactly when its limiting gap Δ(f) is zero, using rates n^1/2 for finite p and n^3/2 for p=±∞.For p=−∞ and p=+∞, the reference rules are veto and plurality, respectively.Source: A Missing Proofs of Theoretical Claims · p. 10

A.1 Utility Transformation

  • The Box-Cox transform ψ_p is strictly increasing, and the proof uses it to preserve welfare comparisons when transforming the power mean.The passage notes that other functions with identical properties could yield similar results.Source: §A.1 · p. 10

A.2 The Optimal Rule is a PSR

The proof shows that a positional scoring rule is asymptotically average-case optimal by expressing the relevant objective additively across voters and applying a scoring-correspondence characterization.

A.2 The Optimal Rule is a PSR

  • For every finite p under A3, a positional scoring rule is asymptotically average-case optimal; for p=1, it maximizes expected utilitarian welfare exactly for every voter count.The appendix uses Young’s characterization: an anonymous, neutral, consistent, and continuous correspondence is a scoring correspondence.Source: §A.2 · pp. 10–11
  • The proof constructs a correspondence by maximizing an additive sum of per-voter conditional expected transformed utilities, then shows it satisfies the scoring-correspondence conditions.The conditions are anonymity, neutrality, consistency, and continuity.Source: §A.2 · p. 11
  • Breaking ties uniformly in the resulting positional scoring rule yields asymptotic optimality among all social choice functions, including randomized ones.The proof bounds the welfare difference between any rule and the scoring rule by 2ε_n, with ε_n=o(n^-1/2).Source: §A.2 · p. 11

A.3 What is the Optimal Rule?

This section identifies the optimal score vector through transformed utility order statistics and establishes its asymptotic uniqueness up to positive affine transformation. It also gives an exact finite-voter optimality result under the stated assumptions.

A.3 What is the Optimal Rule?

  • For each p, the optimal score vector s*(p) is uniquely asymptotically optimal up to positive affine transformation.The limiting welfare gap is zero exactly for score vectors that are positive affine transformations of s*(p).Source: §A.3 · p. 11
  • For p=1, the result recovers the prior finding that Borda is optimal when utilities are uniform.The cited passage attributes that result to Boutilier et al..Source: §A.3 · p. 11
  • For every voter count and preference profile, expected transformed welfare is bounded above by the score attained by the rule using s*(p).The scoring rule attains the maximum expected score among alternatives.Source: §A.3 · p. 12
  • Under independent, neutral utilities with strict rankings, conditioning on a ranking assigns each alternative the corresponding utility order statistic, independently across voters.The optimal score entries are expressed as expectations of transformed utilities at each order-statistic rank.Source: §A.3 · pp. 11–12

A.4 Exact Egalitarian Social Welfare

For exact egalitarian welfare, veto is asymptotically optimal among positional scoring rules, with its advantage tied to how often the elected alternative is ranked last.

A.4 Exact Egalitarian Social Welfare

  • Veto elects an alternative ranked last least often, and welfare loss tracks the winner’s extra last-place rankings.Last-place welfare approximates egalitarian welfare when an alternative is ranked last by at least n/(2m) voters.Source: §A.4 · p. 13
  • No social choice function exceeds veto’s expected egalitarian welfare by more than O(n^-2), and veto is uniquely asymptotically optimal among positional scoring rules up to positive affine transformation.The asymptotic optimality characterization holds under the section’s stated assumptions on the utility distribution.Source: §A.4 · p. 13
  • More last-place rankings lower an alternative’s expected last-place welfare, and the proof assumes A1+, finite expected utility, and a continuous positive density near the lowest possible utility.The density condition holds, for example, for uniform and exponential distributions.Source: §A.4 · p. 13

A.5 Exact Maximax Social Welfare

For exact maximax welfare, plurality is asymptotically optimal among positional scoring rules because it maximizes first-place welfare, which approximates maximax welfare.

A.5 Exact Maximax Social Welfare

  • The result assumes A1+ and a bounded utility distribution with a continuous density positive at its highest possible utility.A5 requires differentiability near the upper endpoint; bounded support also ensures finite expected utility.Source: §A.5 · p. 15
  • Plurality elects an alternative ranked first most often, and welfare loss tracks how many fewer first-place rankings its winner has.The proof identifies first-place welfare as the quantity plurality maximizes.Source: §A.5 · p. 15
  • No social choice function exceeds plurality’s expected maximax welfare by more than O(n^-2), and plurality is uniquely asymptotically optimal among positional scoring rules up to positive affine transformation.The theorem assumes A1+ and the upper-tail condition A5.Source: §A.5 · p. 15
  • More first-place rankings raise expected first-place welfare, which approximates maximax welfare when an alternative is ranked first by at least n/(2m) voters.Under A1+ and A5, the approximation error is at most C'n^-2 in the stated condition.Source: §A.5 · p. 15

B Additional Experiment Discussion

The experiments use neutral, Euclidean, and Plackett-Luce utility settings; additional non-i.i.d. cases show that optimized score vectors can vary with geometry.

B Additional Experiment Discussion

  • The experiments use SciPy for distribution sampling and PrefSampling for Euclidean preferences, and the reported experiments take roughly seven hours total.The paper says the accompanying code includes a README with further run information.Source: B Additional Experiment Discussion · p. 17

B.1 Preference Distributions

  • Six neutral utility distributions were chosen to represent variety, rather than to match a presumed distribution of human or agent utilities.Figure 8 presents their probability density and cumulative distribution functions.Source: §B.1 · p. 17, Figure 8 · p. 18
  • Euclidean settings place voters and alternatives in cube or sphere spaces of varying dimensions, with utility proportional to distance-based closeness.The reported utility is 1 − ||v_i − a_j||^d.Source: §B.1 · p. 17
  • In the Plackett-Luce family, γ = 0 gives uniform utilities, while higher γ increases the expected range of utilities.The model assigns alternative-quality weights and samples each utility from Beta(w_j, 1).Source: §B.1 · p. 17, Figure 10 · p. 18

B.2 Structured Utility Distributions

  • Optimized score-vector structure on Euclidean distributions varies with geometry; Borda closely approximates optimal welfare on Euclidean Cubes across multiple dimensions.With Plackett-Luce utilities, all rules but veto appear near-optimal as γ increases.Source: §B.2 · p. 17, Figure 12 · p. 19
Loading 2610.33293v1…