Pith. sign in

REVIEW 4 cited by

On the Randomized Metric Distortion Conjecture

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2111.08698 v2 pith:54UYITFC submitted 2021-11-16 cs.GT cs.DS

Haripriya Pulyassary , Chaitanya Swamy This is my paper · ORCID
classification cs.GTcs.DS
keywords distortionrandomizedcandidatechoiceconjecturecostdeterminationefficiency
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

In the single winner determination problem, we have n voters and m candidates and each voter j incurs a cost c(i, j) if candidate i is chosen. Our objective is to choose a candidate that minimizes the expected total cost incurred by the voters; however as we only have access to the agents' preference rankings over the outcomes, a loss of efficiency is inevitable. This loss of efficiency is quantified by distortion. We give an instance of the metric single winner determination problem for which any randomized social choice function has distortion at least 2.063164. This disproves the long-standing conjecture that there exists a randomized social choice function that has a worst-case distortion of at most 2.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Metric Distortion for Tournament Voting and Beyond

    cs.GT 2025-05 conditional novelty 8.0 of 10

    Deterministic tournament rules have metric distortion between 3.1128 and 3.9312, and deterministic k-tournament rules approach distortion 3 while randomized 3-tournament rules can beat 3.

  2. Constant-Factor Distortion Mechanisms for $k$-Committee Election

    cs.GT 2025-01 conditional novelty 7.0 of 10

    First constant-factor distortion mechanisms for Top-l k-committee election using only O(log k log n) value queries per agent or polylog queries in total.

  3. Distortion of Metric Voting with Bounded Randomness

    cs.GT 2026-02 conditional novelty 6.0 of 10

    Constant-randomness voting can achieve metric distortion below 3, breaking the deterministic barrier with only a fixed-size uniform lottery.

  4. Bi-Criteria Metric Distortion

    cs.GT 2024-12 conditional novelty 6.0 of 10

    In line metrics, a constant-size committee can achieve the same cost as the optimal single winner, bypassing the factor-3 barrier that applies to any single winner.

Pith tools