On the Cardinality of the Smith Set Under Impartial Culture with Many Alternatives

Abstract

For some integer ℓ≥ 2, consider m=2ℓ−1 voters, each of which has a preference ranking over n alternatives. The Smith set is the smallest nonempty set of alternatives each of which defeats every alternative outside the set in a pairwise majority comparison. Under the standard benchmark impartial culture where each voter uniformly and independently chooses a random preference ranking over all alternatives, we study the asymptotic probability that the Smith set has cardinality s for fixed ℓ and n→ ∞. First, we prove that the probability that the Smith set has constant cardinality s goes to zero at a rate of Θ_ℓ,s (n^{−s(ℓ−1)/ℓ}). Next, if min{s,n−s}→∞, we show that this probability decays superpolynomially. Further, when s and n−s are both Θ(n), we prove that the probability decays exponentially and determine the exact exponential base. Finally, we prove that the probability that the Smith set contains all alternatives approaches one at a rate of Θ_ℓ(n^{−(ℓ−1)/ℓ}). These theorems resolve the conjectures in [Liu et al, Ann Stat 2026] under impartial culture.

An impartial Bayesian hypothesis test for audit sampling
Koen Derks, jacques de swart, Eric‐Jan Wagenmakers +1
International Journal of Applied Decision Sciences24 May 2026Peer-reviewedLicence not statedFull text7 citedStatisticsOpenAlex
The Smith-Toda complex V(4) exists for p >= 11
Vigleik Angeltveit
arXiv16 Oct 2026PreprintarXiv licenceFull textGeometry & topologyarXiv
An Improved Bound for Smith's Longest Cycles Conjecture via a Forbidden Subdivision
Douglas M. Chen
arXiv31 Aug 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Matrix equivalence to Smith normal form: new theoretical results for multivariate polynomial matrices
Dong Lu, Yuanyuan Ruan, Dingkang Wang +1
arXiv21 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
Quantum Latin Hypercubes with Maximal Cardinality
Mingzhen Lv, Haitao Cao
arXiv9 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{berchenko2026cardinality,
  title = {{On the Cardinality of the Smith Set Under Impartial Culture with Many Alternatives}},
  author = {Zachary Berchenko and Kaizhao Liu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.03814},
  eprint = {2610.03814},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.03814},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - On the Cardinality of the Smith Set Under Impartial Culture with Many Alternatives
AU  - Zachary Berchenko
AU  - Kaizhao Liu
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.03814
UR  - https://arxiv.org/abs/2610.03814
AB  - For some integer ℓ≥ 2, consider m=2ℓ−1 voters, each of which has a preference ranking over n alternatives. The Smith set is the smallest nonempty set of alternatives each of which defeats every alternative outside the set in a pairwise majority comparison. Under the standard benchmark impartial culture where each voter uniformly and independently chooses a random preference ranking over all alternatives, we study the asymptotic probability that the Smith set has cardinality s for fixed ℓ and n→ ∞. First, we prove that the probability that the Smith set has constant cardinality s goes to zero at a rate of Θ_ℓ,s (n^−s(ℓ−1)/ℓ). Next, if min{s,n−s}→∞, we show that this probability decays superpolynomially. Further, when s and n−s are both Θ(n), we prove that the probability decays exponentially and determine the exact exponential base. Finally, we prove that the probability that the Smith set contains all alternatives approaches one at a rate of Θ_ℓ(n^−(ℓ−1)/ℓ). These theorems resolve the conjectures in [Liu et al, Ann Stat 2026] under impartial culture.
ER  -

Abstract

Related

Cite