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
- Ji Ho Bae
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