An orderly algorithm for generation of Condorcet Domains

Bei Zhou, Klas Markström · 2025

Read An orderly algorithm for generation of Condorcet Domains by Bei Zhou, Klas Markström (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-20865.txt.

Introduction

Majority voting can cycle in circles unless voters' rankings come from a well-behaved set. Bei Zhou and Klas Markstrom present an algorithm for listing all such sets in a 2025 paper on Condorcet domains. A Condorcet domain guarantees that pairwise majority voting yields a consistent ranking.

Their orderly algorithm generates every non-isomorphic maximal Condorcet domain for a given number of alternatives. Orderly generation avoids producing the same domain twice under renamed options. The method adapts to important subclasses of domains as well. Using their implementation, the authors extend existing enumerations for several subclasses. They release both the data and the code publicly, giving social choice researchers a larger catalog of voting domains to study.

Catalog record

CREATORBei Zhou, Klas Markström
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-20865

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An orderly algorithm for generation of Condorcet Domains Bei Zhou, Klas Markström Abstract Condorcet domains are fundamental objects in the theory of majority voting; they are sets of linear orders with the property that if every voter picks a linear order from this set, assuming that the number of voters is odd, and alternatives are ranked according to the pairwise majority ranking, then the result is a linear order on the set of all alternatives. In this paper we present an efficient orderly algorithm for the generation of all non-isomorphic maximal Condorcet domains on n n alternatives. The algorithm can be adapted to generate domains from various important subclasses of Condorcet domains. We use an example implementation to extend existing enumerations of domains from several such subclasses and make both data and the implementation publicly available. 1 Introduction A Condorcet domain is a set of linear orders on a set of alternatives such that if an odd number of voters select a linear order from this set to represent their preferences, the pairwise majority relation among these alternatives leads to a linear order. Condorcet domains have been actively studied since the 1950’s, motivated by the works of Black [ 1 ] and Arrow [ 2 ] , but the earliest mathematical work on this topic was done by Marquis de Condorcet in 1785 [ 3 ] . Work on Condorcet domains has mainly been conducted by economists and social choice theorists [ 4 ] , but algorithmic aspects are increasingly studied by computer scientists [ 5 ] and mathematicians have investigated their combinatorial structure [ 6 ] . The early works provided some constructions of well-behaved Condorcet domains for general n , the number of alternatives. Black [ 1 ] introduced the single-peaked domains, which correspond to an opinion landscape based on an underlying one-dimensional axis, e.g. signifying a left-right scale. Black’s domains have size 2^{n-1} and are maximal , meaning that they are not contained in any larger Condorcet domains. Arrow [ 7 ] introduced a larger class of domains, which includes Black’s, and these domains also turn out to have size at most 2^{n-1} (Recently, Slinko [ 8 ] showed that all maximal members of this class have size 2^{n-1} ). Motivated by these and other examples Johnson [ 9 ] conjectured that Condorcet domains cannot be larger than the single-peaked domains. Six years later Johnson and Abello [ 10 ] disproved this conjecture, though only by an additive constant. Fishburn [ 11 ] both constructed the well-structured domains which are now called Fishburn domains, which are a polynomial factor larger than 2^{n} , and gave a recursively defined class of domains of size \mathcal{O}(a^{n}) , for an a>2 . On the other hand, Raz [ 12 ] proved that the maximum size is bounded by \mathcal{O}(c^{n}) , for some c>0 . Over the years many other conjectures and open problems on the structure of Condorcet domains were posed, often motivated by the behaviour of the known handcrafted examples for small n . More recently, Dittrich [ 13 ] enumerated all maximal non-isomorphic Condorcet domains on n\leq 5 alternatives and investigated their properties. Here two domains are considered isomorphic if they differ only by a relabeling of the alternatives. This enumeration was significantly extended in [ 14 ] , where all maximal domains on n\leq 7 alternatives were enumerated, using a new algorithm. The latter paper also investigated the properties of the constructed domains and found counterexamples to several conjectures as well as unexpected answers to some open problems. In [ 15 ] a variant on the same algorithm was used to determine the maximum size of a Condorcet domain for n=8 and it was found to differ strongly in structure from the maximum domains for smaller n . 1.1 Our contribution As the computational investigations mentioned above have shown, the study of Condorcet domains has gained much from the non-intuitive examples found by complete enumerations. However, the algorithms used so far all have a common drawback, despite being very different algorithms, namely that they generate a huge number of isomorphic copies of each domain. Thus the generation step must be followed by a separate isomorphism reduction step in order to get just one member from each isomorphism class. This two-step process becomes less and less efficient for larger n , where the size of each isomorphism class becomes larger. The existing search algorithms work with actual domains during the search, something which works well for small n but becomes very memory consuming for larger n , as the domains become larger. The purpose of this paper is to describe an orderly algorithm for generating Condorcet domains, producing only one member of each isomorphism class as output. For a general discussion of orderly algorithms we recommend [ 16 ] . The algorithm drastically reduces the size of the underlying search tree and eliminates the need for a separate isomorphism reduction after the search. The algorithm can easily be adapted to produce only members of some specific classes of domains, such as Arrow’s single-peaked domains [ 7 ] , or the generalised Fishburn domains [ 17 , 18 ] . The main difference between our algorithm and the existing ones is that instead of working with domains as sets of linear orders, we work with sets of never conditions. A classic theorem of Sen [ 19 ] shows that a Condorcet domain can be represented by a set of constraints now known as never conditions (these are defined in the next section). Isomorphism of domains can be translated into isomorphism of sets of never conditions and our algorithm enumerates all isomorphism classes of such sets. This approach substantially reduces memory usage as storing a set of never conditions requires at most \mathcal{O}(n^{3}) bits, while a full domain typically has size exponential in n . There are some pitfalls here. As shown in [ 20 ] it is in general an NP-complete problem to determine if a set of never conditions corresponds to a non-empty domain, so a naive approach might generate sets which correspond to the empty domain. However, as noticed in [ 14 ] all Condorcet domains on the set of alternatives [n] are isomorphic to a unitary domain, i.e. one which contains the standard linear order on [n] , and only some never conditions correspond to unitary domains. By working only with those never conditions we still generate all isomorphism classes and avoid making an NP-complete test for each output from the search. Since we work with a smaller set of never conditions this also reduces the branching factor of the search tree, leading to another speed up. As a demonstration of our algorithm, we enumerate all maximal domains in three restricted classes for n=8 , thereby going a step past the results in [ 14 ] , and for one class we give data for n=9,10 as well. For larger n the number of domains becomes very large and targeted searches make more sense. 1.2 Organisation of the paper In section 2 we give additional notation and background material. In Section 3 we discuss the isomorphism of Condorcet domains and their connection to never conditions in

Read the complete text