A144686 -id:A144686 - cp's OEIS frontend

1, 1, 2, 4, 9, 20, 45, 100, 224

Offset: 0

Andrey Zabolotskiy, Jan 27 2024

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.

			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

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.

Cf. A144685 (size of Fishburn's alternating domain), A144686 (maximal size of Condorcet domain containing a maximal chain), A144687, A289684.

cp's OEIS Frontend

A369614 Maximal size of Condorcet domain on n alternatives.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs