PreprintarXiv licencearXiv
Kelly's conjectures on Condorcet winner probabilities for odd electorates
Abstract
Let C(m,n) denote the probability that, among n independent uniformly random permutations of m labels, there exists a label that precedes every other label in a strict majority of the permutations. We prove that C(m,n)>C(m,n+2) for m ≥ 3 and odd n ≥ 1, and that C(m,n)>C(m+1,n) for m ≥ 2 and odd n ≥ 3. These results establish Kelly's two monotonicity conjectures for odd electorates. The proofs use integral representations involving probabilities associated with sums of independent Bernoulli random variables.
Related
- Condorcet-type properties of the linear ordering problem with ties
- The Kelly--Trotter conjecture and dimension of poset products
- m-Set Adversarial Bandits with Winner Feedback
- Certified computations on no-three-in-line problems: exact values and witnesses in the cube, and the Guy-Kelly count in the plane
- A Winner Classification for Rooted Partizan Edge Geography on Heterogeneous Bouquets of Cycles
BibTeX
@misc{kim2026kellys,
title = {{Kelly's conjectures on Condorcet winner probabilities for odd electorates}},
author = {Seick Kim and Hocheol Shin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29904},
eprint = {2610.29904},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29904},
}
RIS
TY - UNPB
TI - Kelly's conjectures on Condorcet winner probabilities for odd electorates
AU - Seick Kim
AU - Hocheol Shin
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29904
UR - https://arxiv.org/abs/2610.29904
AB - Let C(m,n) denote the probability that, among n independent uniformly random permutations of m labels, there exists a label that precedes every other label in a strict majority of the permutations. We prove that C(m,n)>C(m,n+2) for m ≥ 3 and odd n ≥ 1, and that C(m,n)>C(m+1,n) for m ≥ 2 and odd n ≥ 3. These results establish Kelly's two monotonicity conjectures for odd electorates. The proofs use integral representations involving probabilities associated with sums of independent Bernoulli random variables.
ER -