PaperlayerView exact revision on arXiv

Source-linked AI summary

The Distortion of Threshold Approval Multiwinner Voting

Mohamad Latifian, Marzieh Nilipour, Alexandros A. Voudouris

arXiv:2610.13725v1cs.GT

TL;DR

The paper asks how much distortion threshold-based reports can produce in multiwinner voting when voters’ committee utilities take varied norm-based forms. It designs deterministic and randomized rules for this setting, with bounds that match up to constants for constant-size committees.

  • Problem

    In multiwinner voting, less informative preference reports may lead to outcomes with significantly lower social welfare, and the paper studies this distortion for threshold approvals and varied committee utilities.

    Source: §1 · pp. 1–2

  • Method

    The paper models committee utility with normalized monotone symmetric norms and designs rules using threshold-derived virtual utilities, with randomization also allowing a uniformly random committee.

    Source: §1 · p. 2, §1.1 · p. 2

  • Results

    For every committee size and norm in the framework, distortion is at most 2(2m)^(1/t) deterministically and 2 min{m^(1/(t+1)), m/k} randomly; for constant-size committees, bounds match up to constants.

    Source: §1.1 · p. 2, §6 · p. 28

  • Takeaways & Limitations

    The results show that distortion improves with more thresholds and that upper and lower bounds coincide up to constants for single-winner and constant-size committees.

    Source: §1.1 · p. 2, §6 · p. 28

    For general norms and growing committee sizes, closing the gap between the upper and lower bounds remains open; maximizing virtual welfare may also be computationally difficult for some utility functions.

    Source: §6 · pp. 28–29

Abstract

from arXiv · show

We study multiwinner voting with $n$ voters and $m$ candidates, where the goal is to select a committee of size $k$. Voters have unit-sum cardinal utilities but report only coarse information induced by $t$ utility thresholds. In particular, each voter partitions the candidates into approval sets, with the utilities of all candidates in the same set lying between the same pair of consecutive thresholds. We model the utility of each voter for a committee as a normalized monotone symmetric norm, capturing, among others, additive welfare, best-representative utility, top-$r$ welfare, $\ell_p$ welfare, and normalized non-increasing ordered weighted averages. We design a deterministic rule with distortion at most $2(2m)^{1/t}$ and a randomized rule with distortion at most $2\min\{m^{1/(t+1)},m/k\}$. These guarantees hold for every committee size $k$ and every norm in our framework. Consequently, a single threshold yields distortion $O(m)$ for deterministic rules and $O(\sqrt{m})$ for randomized rules, while $O(\log m)$ thresholds suffice for constant distortion. We complement these results with norm-dependent lower bounds that asymptotically match our upper bounds for constant committee sizes, including the single-winner case.

1 Introduction

This paper studies how threshold-based preference reports affect distortion in multiwinner voting, where committee utility can reflect different ways voters value selected candidates. It presents deterministic and randomized rules, lower bounds, and a framework relating these guarantees to thresholds, committee size, and the utility norm.

1 Introduction

  • Distortion measures the worst-case welfare loss that can arise when voters report less information than their cardinal utilities.The introduction contrasts detailed cardinal utilities with lower-effort ordinal rankings and approval votes.Source: §1 · p. 1
  • Threshold approvals lie between ordinal information and full cardinal utilities, and additional thresholds express finer preference intensity.The closest related threshold model cited is for matching rather than multiwinner voting.Source: §1 · pp. 1–2
  • The model uses normalized monotone symmetric norms to capture additive, best-representative, top-r, ℓp, and OWA committee utilities.The paper frames the number of utility thresholds and achievable distortion as its central tradeoff.Source: §1 · p. 2

1.1 Our Contribution

  • The deterministic rule has distortion at most 2(2m)^(1/t), while the randomized rule has distortion at most 2 min{m^(1/(t+1)), m/k}.The deterministic rule uses geometrically spaced thresholds and lower-endpoint virtual utilities; the randomized rule chooses equally between virtual-welfare maximization and a uniformly random size-k committee.Source: §1.1 · p. 2
  • For single-winner and constant-size committees, the upper and lower bounds match up to constants: Θ(m^(1/t)) deterministically and Θ(m^(1/(t+1))) randomly.The lower bounds depend on the number of candidates, committee size, and utility norm.Source: §1.1 · pp. 2–3

1.2 Related Work

  • The related-work discussion distinguishes this model from earlier threshold-approval work using a single independently chosen threshold or additive committee utility.The paper instead uses multiple common thresholds and general committee-utility norms.Source: §1.2 · p. 3

2 Model

The model combines unit-sum candidate utilities, threshold-based reports, and norm-based committee utility. It defines social welfare and distortion for deterministic and randomized size-k committee rules.

2.1 Utilities and Elicitation Method

  • Each voter has unit-sum utilities over m candidates and reports t + 1 approval sets induced by common thresholds; committees contain k candidates.The reported profile must be consistent with the underlying unit-sum utility profile.Source: §2.1 · p. 4, §2.2 · p. 4

2.2 From Candidate Utility to Committee Utility

  • Committee utility can represent best-representative, additive, top-r, ℓp, and ordered weighted average objectives.OWA weights are non-increasing and normalized so the largest weight is one; ℓp objectives interpolate between additive utility and best-representative utility as p increases.Source: §2.2 · pp. 4–5

2.3 Monotone Symmetric Norms

  • The norm framework requires properties including monotonicity, symmetry, positive homogeneity, triangle inequality, and normalization.Normalization sets each candidate’s singleton utility to one, placing different norms on a common scale.Source: §2.3 · pp. 5–6

2.5 Committee Rules and Distortion

  • Social welfare sums voters’ norm-based committee utilities, and distortion compares a rule’s welfare with the optimal size-k committee welfare.Rules map reported profiles to a committee or a probability distribution; distortion uses expected welfare for randomized rules.Source: §2.4 · p. 6, §2.5 · p. 7

2.4 Committee Welfare under Monotone Symmetric Norms

  • For every normalized monotone symmetric norm, 1 ≤ L_N,k ≤ k, bounding the norm of a size-k indicator vector.This quantity equals k for additive utility and 1 for best-representative utility.Source: §2.4 · pp. 6–7

3 Upper Bounds

The upper bounds use lower-endpoint virtual utilities to select committees, with randomization adding a report-independent baseline. Both rules apply across the paper’s norm framework, and more thresholds reduce distortion.

3.1 Virtual Utilities and Preliminary Bounds

  • Virtual utilities use the lower endpoint of each reported interval, never exceed true utilities, and induce virtual welfare no greater than true welfare.Utilities below the last threshold are discarded; their norm is bounded by τtL_N,k per voter.Source: §3.1 · p. 8
  • A uniformly random size-k committee provides a report-independent baseline welfare guarantee.The analysis also compares its expected welfare with optimal welfare.Source: §3.1 · pp. 9–10

3.2 Deterministic Rule

  • 2(2m)^(1/t) bounds deterministic distortion for every committee size and normalized monotone symmetric norm.The rule maximizes virtual welfare using geometrically spaced thresholds.Source: §3.2 · p. 11

3.3 Randomized Rule

  • The randomized rule combines the information-driven deterministic choice with a random committee, whose baseline helps when optimal welfare is small.When optimal welfare is large, lower-endpoint replacement loses only a bounded fraction.Source: §3.3 · p. 11
  • 2 min{m^(1/(t+1)), m/k} bounds randomized distortion for every committee size and normalized monotone symmetric norm.The rule mixes a virtual-welfare-maximizing committee with a uniformly random size-k committee.Source: §3.3 · pp. 11–12

3.4 Consequences and Special Cases

  • One threshold gives deterministic distortion at most 4m and randomized distortion at most 2√m; ⌈log2 m⌉ thresholds give bounds of 8 and 4, respectively.The guarantees cover additive, best-representative, top-r, ℓp, and normalized non-increasing OWA utilities, although maximizing virtual welfare may be computationally hard.Source: §3.4 · p. 12, §3.3 · p. 12

4 Lower Bounds

The deterministic lower-bound argument exploits utilities that reports cannot distinguish. It separates a too-high final threshold, which permits unbounded distortion, from a case with a large gap between consecutive thresholds.

4.1 Deterministic Rules

  • If the last threshold exceeds 1/(m−k), every deterministic size-k rule using it has unbounded distortion.The last approval set can contain every candidate, allowing utility to be concentrated outside the selected committee.Source: §4.1 · p. 12
  • The arbitrary-threshold lower bound combines the last-threshold obstruction with the large-gap case.The argument uses report-indistinguishable candidates to make a selected committee miss a high-utility candidate.Source: §4 · p. 12, §4.1 · p. 15
  • Otherwise, some consecutive auxiliary thresholds have ratio at least (m−k)^(1/t), and a ratio of at least k+1 triggers a deterministic lower-bound construction.The construction places substantially different utilities within the same approval set while preserving the report.Source: §4.1 · pp. 13–15

1. Best-representative utility:

For fixed committee sizes, the deterministic lower bound matches the upper bound up to constants. Randomized lower bounds use either a high last threshold or a large gap between consecutive thresholds.

1. Best-representative utility:

  • For any fixed k=O(1), optimal deterministic distortion with t thresholds is Θ(m^(1/t)).The lower bound matches the deterministic upper bound up to a constant factor.Source: §1 · p. 16

4.2 Randomized Rules

  • For randomized rules, a last threshold above 1/m allows a report that hides a candidate with high utility and low marginal inclusion probability.The argument uses the fact that the marginal inclusion probabilities of a size-k randomized committee sum to k.Source: §4.2 · pp. 16–17
  • A consecutive-threshold ratio of at least 2k yields a randomized lower-bound construction using candidates with small marginal inclusion probabilities.The arbitrary-threshold lower bound combines this large-gap case with the last-threshold obstruction.Source: §4.2 · pp. 17–19

1. Best-representative utility:

For fixed committee sizes, randomized lower bounds match the upper bounds up to constant factors, establishing the optimal distortion rate.

1. Best-representative utility:

  • For any fixed k=O(1), optimal randomized distortion with t thresholds is Θ(m^(1/(t+1))).The lower bound matches the randomized upper bound up to a constant factor.Source: §1 · p. 20

5 Best-Representative Utility

For best-representative utility (the ℓ∞-norm), the section establishes tight deterministic distortion when the committee excludes a constant fraction of candidates and tight randomized bounds for every committee size. Its lower-bound proof splits into cases according to g, giving an explicit bound for g = k and a complementary case for g < k.

5.1 Deterministic Rules

  • The section establishes tight deterministic bounds for best-representative utility when the committee excludes a constant fraction of candidates.For 1 ≤ k ≤ m/2, the lower-bound construction yields distortion Ω(m^1/t); for m/2 < k < m, it yields Ω((m − k)^1/t).Source: §5 · p. 21, §5.1 · pp. 22, 25
  • When m − k = Ω(m), the optimal deterministic distortion for best-representative utility with t thresholds is Θ(m^1/t).For m/2 < k < m, the lower bound is Ω((m − k)^1/t); the matching characterization applies when m − k = Ω(m).Source: §5.1 · pp. 25–26

5.2 Randomized Rules

  • The optimal randomized distortion for best-representative utility is tightly bounded for every committee size 1 ≤ k ≤ m.The theorem’s displayed bound is not present in the supplied passage.Source: §5.2 · p. 26
  • The distortion is at least 1/(12/R_j + k/(gq)); when g = k, this is at least R_j/20.Source: §5.2 · p. 28
  • When g < k, g = floor(m/q) and q ≤ (m − 1)/4 imply gq ≥ m/2; the proof then derives a distortion lower bound and uses R_j ≥ a/2.Source: §5.2 · p. 28

6 Conclusion and Open problems

The paper gives threshold-based distortion guarantees across normalized monotone symmetric norms, with tight bounds in constant-size settings and for specified best-representative regimes. Open questions remain for growing committees, computation, and threshold design.

6 Conclusion and Open problems

  • For normalized monotone symmetric norms, distortion improves with more thresholds, and O(log m) thresholds suffice for constant distortion.Source: §6 · p. 28
  • For single-winner and constant-size committees, upper and lower bounds match within constants: Θ(m^1/t) deterministic and Θ(m^1/(t+1)) randomized.Source: §6 · p. 28
  • Best-representative utility has tight randomized bounds for every committee size and tight deterministic bounds when m−k=Ω(m).Source: §6 · p. 28
  • For general norms, the gap between upper and lower bounds for growing committees remains open; deterministic best-representative distortion is also unresolved when 1 ≤ m−k=o(m).Source: §6 · pp. 28–29
  • Open directions include whether polynomial-time rules can match the guarantees, and whether adaptive, non-geometric, or voter-specific thresholds improve the information-distortion tradeoff.Source: §6 · p. 29
Loading 2610.13725v1…