A369614 Maximal size of Condorcet domain on n alternatives.

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

Offset: 0

Author

Andrey Zabolotskiy, Jan 27 2024

Keywords

• nonn
• hard
• more

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.

Examples

			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
		

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.

Crossrefs

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