A counterexample to the coalition LP conjecture for metric distortion

Charikar and Ramakrishnan conjectured that normalizing an optimal solution of their coalition linear program gives a randomized voting rule attaining their proposed metric-distortion bounds. We give a counterexample with four candidates and 25 voters. The linear program has a unique optimal solution, and the resulting lottery has distortion at least 203/99 > 2.05, exceeding the proposed four-candidate bound of approximately 2.04957. The example admits realizations in which all voters and candidates are distinct and every ranking is strict. The proof consists of an exact linear-programming certificate and an explicit metric construction. This release contains the English manuscript, a separate Korean translation, and LaTeX source archives for both versions. Each source archive includes exact rational verification code, input data, and recorded results in its anc/ directory. The verifier uses only the Python standard library; see README.txt for instructions.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-10-11
DOI
https://doi.org/10.5281/zenodo.23287877
Primary Topic
Game Theory and Voting Systems
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

A counterexample to the coalition LP conjecture for metric distortion

Ji Ho Bae
Zenodo (CERN European Organization for Nuclear Research)
Game Theory and Voting Systems
preprint

A counterexample to the coalition LP conjecture for metric distortion

Ji Ho Bae
preprint en

Abstract

Charikar and Ramakrishnan conjectured that normalizing an optimal solution of their coalition linear program gives a randomized voting rule attaining their proposed metric-distortion bounds. We give a counterexample with four candidates and 25 voters. The linear program has a unique optimal solution, and the resulting lottery has distortion at least 203/99 > 2.05, exceeding the proposed four-candidate bound of approximately 2.04957. The example admits realizations in which all voters and candidates are distinct and every ranking is strict. The proof consists of an exact linear-programming certificate and an explicit metric construction. This release contains the English manuscript, a separate Korean translation, and LaTeX source archives for both versions. Each source archive includes exact rational verification code, input data, and recorded results in its anc/ directory. The verifier uses only the Python standard library; see README.txt for instructions.

Zenodo (CERN European Organization for Nuclear Research)
Game Theory and Voting Systems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.