{"ID":23474960,"CreatedAt":"2026-09-18T01:09:05.407443952Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19593","arxiv_id":"2609.19593","title":"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.","short_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 severa...","url_abs":"https://arxiv.org/abs/2609.19593","url_pdf":"https://arxiv.org/pdf/2609.19593v1","authors":"[\"Daichi Kawashima\",\"Noriyoshi Sukegawa\"]","published":"2026-09-17T02:19:47Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"math.CO\",\"math.OC\"]","methods":"[]","has_code":false}