login
A369614
Maximal size of Condorcet domain on n alternatives.
2
1, 1, 2, 4, 9, 20, 45, 100, 224
OFFSET
0,3
COMMENTS
A Condorcet domain is a set D of permutations of [n] such that for any i, j, k from [n] there do not exist three permutations in D in which i, j, k are ordered in all three different cyclic permutations of the order (i, j, k). If these permutations are interpreted as voters' preferences, this condition prevents the Condorcet effect.
Condorcet domains are also known as acyclic domains, acyclic sets of linear orders, consistent profiles, or consistent sets.
LINKS
Dolica Akello-Egwell, Charles Leedham-Green, Alastair Litterick, Klas Markström and Søren Riis, Condorcet Domains of Degree at most Seven, arXiv:2306.15993 [cs.DM], 2023. See the website presenting all maximal unitary Condorcet domains on 4, 5, 6, 7 alternatives.
Clemens Puppe and Arkadii Slinko, Maximal Condorcet domains: A further progress report, KIT Working Paper Series in Economics, 159 (2022).
Charles Leedham-Green, Klas Markström and Søren Riis, The largest Condorcet domain on 8 alternatives, Soc. Choice Welf., 62 (2024), 109-116.
Bernard Monjardet, Acyclic domains of linear orders: a survey, in "The Mathematics of Preference, Choice and Order: Essays in Honor of Peter Fishburn", edited by Steven Brams, William V. Gehrlein and Fred S. Roberts, Springer, 2009, pp. 139-160; preprint: halshs-00198635.
Wikipedia, Condorcet paradox.
EXAMPLE
For n <= 2, the set of all n! permutations is a Condorcet domain.
For n = 3, an example of a Condorcet domain of maximal size is the following set of permutations:
123
213
231
321
For n = 4, an example of a Condorcet domain of maximal size is:
1234
1324
1342
3124
3142
3412
3421
4312
4321
CROSSREFS
Cf. A144685 (size of Fishburn's alternating domain), A144686 (maximal size of Condorcet domain containing a maximal chain), A144687, A289684.
Sequence in context: A108469 A144685 A085584 * A080019 A052534 A213411
KEYWORD
nonn,hard,more
AUTHOR
Andrey Zabolotskiy, Jan 27 2024
STATUS
approved