Condorcet-type properties of the linear ordering problem with ties
Abstract
The Kemeny rule aggregates multiple strict rankings into a single strict ranking that minimizes the sum of its distances from the input rankings. The resulting optimization problem, called the Kemeny problem (\texttt{KP}), is a special case of the linear ordering problem (\texttt{LOP}). The Kemeny rule satisfies several desirable properties in social choice theory, including the extended Condorcet criterion (\texttt{XCC}). Ando et al. strengthened this result by introducing the strong Condorcet criterion (\texttt{SCC}) and showing that it holds for every optimal solution to an arbitrary \texttt{LOP} instance. Yoo and Escobedo extended the Kemeny rule to rankings with ties and showed that the resulting rule satisfies the non-strict extended Condorcet criterion (\texttt{NXCC}). This criterion gives a condition under which one candidate must be ranked strictly above another in every optimal solution. In this paper, we introduce the non-strict strong Condorcet criterion (\texttt{NSCC}), a counterpart of the \texttt{SCC} for rankings with ties, and show that it holds for every optimal solution to an arbitrary instance of the linear ordering problem with ties (\texttt{LOPT}). We also establish a complementary structural property that gives conditions under which two candidates must be tied in every optimal solution to an arbitrary \texttt{LOPT} instance.
Related
- Kelly's conjectures on Condorcet winner probabilities for odd electorates
- Linear dependencies, polynomial factors in the Duke–Erdős forbidden sunflower problem – CORRIGENDUM
- Formalizing Fefferman's Official Periodic Navier-Stokes Problem (B) in Lean 4: Global Linear Strain Exclusion on T3, Biot-Savart Direction Depletion Identities, and Conditional Reductions via Beale-Kato-Majda
- A rigidity result for a global vectorial free boundary problem with a linear datum
- The Global Asymptotic Stability Problem for Linear MPC Is Undecidable
BibTeX
@misc{kawashima2026condorcettype,
title = {{Condorcet-type properties of the linear ordering problem with ties}},
author = {Daichi Kawashima and Noriyoshi Sukegawa},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19593},
eprint = {2609.19593},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19593},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Condorcet-type properties of the linear ordering problem with ties
AU - Daichi Kawashima
AU - Noriyoshi Sukegawa
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.19593
UR - https://arxiv.org/abs/2609.19593
AB - The Kemeny rule aggregates multiple strict rankings into a single strict ranking that minimizes the sum of its distances from the input rankings. The resulting optimization problem, called the Kemeny problem (\texttt{KP}), is a special case of the linear ordering problem (\texttt{LOP}). The Kemeny rule satisfies several desirable properties in social choice theory, including the extended Condorcet criterion (\texttt{XCC}). Ando et al. strengthened this result by introducing the strong Condorcet criterion (\texttt{SCC}) and showing that it holds for every optimal solution to an arbitrary \texttt{LOP} instance. Yoo and Escobedo extended the Kemeny rule to rankings with ties and showed that the resulting rule satisfies the non-strict extended Condorcet criterion (\texttt{NXCC}). This criterion gives a condition under which one candidate must be ranked strictly above another in every optimal solution. In this paper, we introduce the non-strict strong Condorcet criterion (\texttt{NSCC}), a counterpart of the \texttt{SCC} for rankings with ties, and show that it holds for every optimal solution to an arbitrary instance of the linear ordering problem with ties (\texttt{LOPT}). We also establish a complementary structural property that gives conditions under which two candidates must be tied in every optimal solution to an arbitrary \texttt{LOPT} instance.
ER -