Coherent domains and improved lower bounds for the maximum size of Condorcet domains
File(s)1-s2.0-S0166218X25001313-main.pdf (599.18 KB)
Published version
Author(s)
Karpov, Alexander
Markström, Klas
Riis, Søren
Zhou, Bei
Type
Journal Article
Abstract
In this paper, we study Condorcet domains, sets of linear orders from which majority ranking produces a linear order. We introduce a new class of Condorcet domains, called coherent domains, which is natural from both a voting theoretic and combinatorial perspective. After studying the properties of these domains we introduce set-alternating schemes. This is a method for constructing well-behaved coherent domains. Using this we show that, for sufficiently large numbers of alternatives n, there are coherent domains of size more than 2.1973n. This improves the best existing asymptotic lower bounds for the size of the largest general Condorcet domains.
Date Issued
2025-07-31
Date Acceptance
2025-03-02
Citation
Discrete Applied Mathematics, 2025, 370, pp.57-70
ISSN
0166-218X
Publisher
Elsevier
Start Page
57
End Page
70
Journal / Book Title
Discrete Applied Mathematics
Volume
370
Copyright Statement
© 2025 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
License URL
Publication Status
Published
Date Publish Online
2025-03-14