Abstract
The paper studies group-separable preference profiles. Such a profile is group-separable if for each subset of alternatives there is a partition in two parts such that each voter prefers each alternative in one part to each alternative in the other part. We develop a parenthesization representation of group-separable domain. The precise formula for the number of group-separable preference profiles is obtained. The recursive formula for the number of narcissistic group-separable preference profiles is obtained. Such a profile is narcissistic group-separable if it is group-separable and each alternative is preferred the most by exactly one voter.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
We consider classical (Arrovian) social choice theory framework. We address n preference orders of an m-element set X = {1, …, m} that satisfy specific properties. Each preference order represents a binary relation of being better for a voter. The elements of set X are called alternatives. A multi-set of n preference orders is called a preference profile. We do not assume anonymity. A nontrivial permutation of different preference orders leads to a nonequivalent preference profile. A permutation of equal preference orders does not change preference profile.
Within the unrestricted set of preference profiles, it is impossible to find an aggregation rule (social welfare function) that satisfies a set of desirable properties (Arrow 1963; Campbell and Kelly 2002). In particular, the simple majority rule leads to intransitive social ordering.
One of the possible solutions of this problem is a restricted domain of preference profiles. Inada (1964, 1969) and Sen (1966) introduced several types of Condorcet domains (if a society consists of voters whose preferences belongs to a Condorcet domain, then the simple majority rule implies transitive social ordering). The aim of this paper is to analyze the group-separable preferencesFootnote 1. Inada (1964) defined separability property in the following way. Let A and B be the two groups of alternatives. For each possible preference order, any alternative in A is always preferred to any alternative in B, or any one in B is always preferred to any one in A. Then, we call the set of alternatives separable into two groups. The group-separability property implies a partition of each set of alternatives in two parts such that each voter prefers each alternative in one part to each alternative in the other part. Despite the common partition, a better part differs from voter to voter.
Structured preferences have theoretical importance. There are many examples of computational social choice problems that become easy when there are structured preferences (Elkind et al. 2017; Faliszewski et al. 2011). Brandt et al. (2015) presented a detailed study about the computational complexity of social choice problems for single-peaked preferences. In further research papers e.g. Bredereck et al. (2016), Faliszewski et al. (2014) a weaker notions of structured preferences (near single-peaked preferences, etc.) were introduced. Elkind et al. (2012) explored clone structures in preferences as useful tool for studying structured preferences. Our study applies clone structures for group-separable preferences analysis.
Ballester and Haeringer (2011) demonstrated that group-separable preferences can be defined via forbidden sequences in preference orders. There are two types of restrictions for group-separable preferences. The first condition is medium restrictedness; that is, for each triple of alternatives, the set of alternatives, which are in the middle of at least one suborder, has cardinality 1 or 2. This restriction was first discovered by Sen (1966). The second restriction is the separability of each pair of preference orders. Separability means that one preference order can be obtained from another preference order by means of a separable permutation. A permutation is separable if and only if it contains neither 2413 nor 3142 as a pattern. Separable permutations are counted by the large Schröder numbers (see the different proofs in West 1995; Stankova 1994; Ehrenfeucht et al. 1998). Separable permutations have different tree representations (West 1996; Bose et al. 1998; Albert et al. 2015; Kitaev 2011), which are applicable for related combinatorial problems.
Enumerative combinatorics of preference profiles is aimed at finding the number of preference profiles with the desired properties. It is applied for calculating corresponding probabilities. The impartial culture assumption states every possible preference order has the same probability of occurrence. The number of all possible preference profiles equals (m!)n.
Gehrlein and Fishburn (1976, 1979) obtained recursive and precise formulas for the number of preference profiles with a Condorcet winner. Lackner and Lackner (2017) obtained an asymptotic formula of the number of single-peaked preference profiles. Chen and Finnendahl (2018) found the number of single-peaked narcissistic and single-crossing narcissistic preference profiles. Following Chen and Finnendahl (2018), the narcissistic preference profile is a preference profile with n orders and n alternatives such that order i has alternative i in the first place. Our paper defines group-separable narcissistic preference profiles and counts them.
The only known result regarding the number of group-separable preference profiles is Lackner and Lackner’s (2017, Corollary 10) inequality:
.
This paper has two main results. First, the precise formula for the number of group-separable preference profiles is obtained (Theorem 1). The combinatorial proof is based on the bijection between group-separable domains and Schröder paths without the peaks at level one counted by the small Schröder numbers. Second, the recursive formula for the number of narcissistic group-separable preference profiles is obtained (Theorem 2).
The structure of the paper is as follows. Section 2 describes the properties of preference profiles and preference domains. Section 3 presents tree representations of a preference profile. Section 4 describes the group-separable domains and contains the enumeration result for group-separable preference profiles. Section 5 contains the enumeration result for narcissistic group-separable preference profiles. Section 6 concludes. Appendix contains all proofs.
2 Framework
Let a finite set X = {1, …, m} be the set of alternatives and a finite set \( {\mathcal{N}} = \left\{ {1, \ldots ,n} \right\} \) be the set of voters. Each voter \( i \in {\mathcal{N}} \) has a linear preference order Pi over X. The first element is the best alternative. The last element is the worst. Let \( {\mathcal{L}}\left( X \right) \) be the set of all possible linear orders on X. An n-tuple of the preference orders generates the preference profile \( {\mathcal{P}} = \left( {P_{1} , \ldots ,P_{n} } \right) \in {\mathcal{L}}\left( X \right)^{n} \). Function \( pos\left( {P_{i} ,j} \right) = \left| {\left\{ {x \in X |xP_{i} j} \right\}} \right| + 1 \) indicates the position of alternative j in preference profile Pi.
A preference profile \( {\mathcal{P}} \) is group-separable if for every \( A \subseteq X, \) |A| ≥ 2 there exists a partition on two nonempty sets \( A',A\backslash A' \) such that for each \( i \in {\mathcal{N}} \), we have either \( aP_{i} b \) for each \( a \in A' \), \( b \in A\backslash A' \) or \( bP_{i} a \) for each \( a \in A \), \( b \in A\backslash A' \).
A preference profile \( {\mathcal{P}} \) is medium restricted if for any triple of alternatives \( A \subseteq X, \left| A \right| = 3 \) we have \( \left| {\left\{ {y \in A |\exists i \in {\mathcal{N}}:\mathop {\hbox{max} }\nolimits_{j \in A} pos\left( {P_{i} ,j} \right) > pos\left( {P_{i} ,y} \right) > \mathop {\hbox{min} }\nolimits_{j \in A} pos\left( {P_{i} ,j} \right)} \right\}} \right| \le 2 \).
A preference profile \( {\mathcal{P}} \) is β-restricted if there is no \( i,j \in {\mathcal{N}} \) and four alternatives \( a,b,c,d \in X \) such that \( aP_{i} bP_{i} cP_{i} d \) and \( bP_{j} dP_{j} aP_{j} c \). This pattern leads to separable pairs of permutations. The number of separable permutations with m elements is the m − 1th large Schröder number (it is the A006318 sequence in the On-line Encyclopedia of Integer Sequences, published electronically at http://oeis.org; henceforth, OEIS). Proposition 1 characterizes group-separable preference profiles via forbidden subprofiles.
Proposition 1 (Ballester and Haeringer 2011)
A preference profile\( {\mathcal{P}} \)is group-separable if and only if it is medium restricted and β-restricted.
A domain\( {\mathcal{D}} \in {\mathcal{L}}\left( X \right)^{d} \) is a set of d distinct preference orders. We say that a preference profile belongs to a domain if all of the preference orders from this preference profile belong to the domain.
A domain of preferences is a maximal Condorcet domain if each preference profile with an odd number of voters from this domain does not yield cycles in the simple majority relation. Condorcet domains are extensively studied in social choice theory (see Monjardet 2009 for a review of this field).
A domain of preferences is symmetric if it contains the reversed order of each preference order in the domain. A domain, which is maximal Condorcet domain and also a symmetric domain, is a maximal symmetric Condorcet domain (for an extensive study of this property, see Danilov and Koshevoy 2013).
A domain of preferences is minimally rich if for any alternative \( x \in X \) there is an order \( P \in {\mathcal{D}} \) such that P has x as the first alternative. The minimal richness plays an important role in the characterization of the single-peaked domain (Puppe 2018).
A domain of preferences is normal if it contains the order 123…m and the opposite to it (Danilov and Koshevoy 2013).
3 Clone Sets
A nonempty set \( A \subseteq X \) is a clone set if and only if when \( \forall z \in X\backslash A \), \( \forall x,y \in A \), and \( \forall i \in {\mathcal{N}} \), we have either \( xP_{i} z \), \( yP_{i} z \) or \( zP_{i} x \), z \( P_{i} y \). This definition is common in the social choice literature and was considered in Tideman (1987), Zavist and Tideman (1989) and Elkind et al. (2012). A clone set is proper if it is neither singleton nor set X.
A partition \( {\mathcal{D}}\left( {X, {\mathcal{P}}} \right) \) of set X into disjointed clone sets is called a clone partition. A clone partition \( {\mathcal{D}}\left( {X, {\mathcal{P}}} \right) \) is finer than another clone partition \( {\mathcal{D}}'\left( {X, {\mathcal{P}}} \right) \) if for any \( D \in {\mathcal{D}}\left( X \right) \) there exists \( D' \in {\mathcal{D}}'\left( {X, {\mathcal{P}}} \right) \) such that \( D = D' \) or \( D \subseteq D' \). The inverse relation is called being coarser. A clone partition \( {\mathcal{D}}\left( {X, {\mathcal{P}}} \right) \) is coarser than another clone partition \( {\mathcal{D}}'\left( {X, {\mathcal{P}}} \right) \) if for any \( D \in {\mathcal{D}}\left( {X, {\mathcal{P}}} \right) \) there exists \( D' \in {\mathcal{D}}'\left( {X, {\mathcal{P}}} \right) \) such that \( D = D' \) or \( D' \subseteq D \).
A clone partition \( {\mathcal{D}}\left( {X, {\mathcal{P}}} \right) \) is trivial if all its parts are singletons. A clone partition \( {\mathcal{D}}\left( {X, {\mathcal{P}}} \right) \) is a null partition if the only part is the set X. A clone partition \( {\mathcal{D}}\left( {X, {\mathcal{P}}} \right) \) is proper if it is neither trivial nor a null partition. A clone partition \( {\mathcal{D}}\left( {X, {\mathcal{P}}} \right) \) is minimal if its only coarser clone partition is the null partition.
If there is a two-part clone partition of set X with respect to preference profile \( {\mathcal{P}} \), then this set and corresponding preference profile is called reducible, and otherwise, it is irreducible. A clone partition \( {\mathcal{D}}\left( {X, {\mathcal{P}}} \right) \) is ordered if there is an order of parts such that the union of any number of subsequent parts is a clone set.
We differentiate reversible and nonreversible clone sets. If for each preference order, a clone set reversal does not break other clone sets induced by the preference profile, then this clone set is reversible. Otherwise, it is nonreversible. For example, in the preference profile
{4, 5} is a reversible clone set and {1, 2, 3} is a nonreversible clone set. Clone set {3, 4, 5} would be broken after 123 reversal in any preference order.
3.1 Tree Representations of the Preference Profile
Elkind et al. (2012) proposed a PQ-tree representation of a family of clone sets [PQ-trees are formally introduced in Booth and Lueker (1976)]. Here, we define this representation in our terms. A PQ-tree is an ordered tree with two types of nodes. If a node is of type P, then its children can be permuted arbitrarily. If a node is of type Q, then the order of its children can be reversed.
A clone decomposition tree\( {\mathcal{G}}\left( {\mathcal{P}} \right) \) is a PQ-tree. Set X is the root of the tree. If X is irreducible, then the node X is of type P and parts of the minimal clone partition are the children. If X is reducible, then the node X is of type Q and parts of the finest ordered clone partition are the children. Each non-singleton child becomes a root vertex and generates children from its own minimal clone partition (for irreducible set) or its own finest ordered clone partition. Tree leaves are singletons.
Proposition 2
Each preference profile has a unique clone decomposition tree.
The proof for Proposition 2 and subsequent propositions are given in the Appendix. Similar result is known for tournament decomposition trees (Laslier 1997, Brandt et al. 2011). Tournament decomposition trees also exploit reducibility property.
For a node with two children, the type of node does not matter. In our framework, all such nodes are Q-nodes. All P-nodes have at least 3 children.
If a Q-node has more than two children, then for any three parts A, B, and C, one part is between the other parts according to the decomposition ordering. If B is between A and C, then for any \( a \in A, b \in B, {\text{and }}c \in C \) and for any voter \( i \in {\mathcal{N}} \), we have either \( aP_{i} bP_{i} c \), or \( cP_{i} bP_{i} a \). The betweenness relation reflects the structure of alternatives even without introducing any geometric space. We call the clone decomposition tree with only Q-nodes the Q-tree. From the reducibility of each clone set, we obtain Proposition 3.
Proposition 3
A preference profile is group-separable if and only if its clone decomposition tree is a Q-tree.
Each node in a Q-tree represents reversible clone set and each nontrivial reversible clone set corresponds to node in a Q-tree representation.
It is convenient to represent Q-trees and corresponding reversible clone sets as a parenthesization for set X. Each pair of parentheses corresponds to a reversible clone set. For example, parenthesization ((12)3) means that {1, 2} are {1, 2, 3} are reversible clone sets. {1, 2}, {3} is the finest ordered partition of set {1, 2, 3} with respect to preference profile \( {\mathcal{P}} \). {1}, {2} is the finest ordered partition of set {1, 2} with respect to preference profile \( {\mathcal{P}} \). The next section utilizes parenthesization representation for group-separable domains.
4 Group-Separable Domains
A domain of preferences is group-separable if all of the preference profiles from this domain are group-separable. After having a labeled clone decomposition Q-tree and corresponding parenthesization, we define a parenthesization domain\( D\left( {\mathcal{G}} \right) \) such that a preference profile containing all of the preference orders from this domain generates a parenthesization \( {\mathcal{G}}:{\mathcal{G}} = {\mathcal{G}}\left( {{\mathcal{D}}\left( {\mathcal{G}} \right)} \right) \), and if we add any other preference order, then a parenthesization will be different. Any parenthesization \( {\mathcal{G}} \) induces a parenthesization domain.
Each parenthesization domain is group-separable. Each group-separable preference profile belongs to corresponding parenthesization domain.
A parenthesization with one parentheses generates a domain with two reversed orders. Any additional parentheses doubles the number of preference orders in a domain. A parenthesization domain has 2f preference orders, where f is the number of parentheses.
A maximal group-separable domain is a group-separable domain such that any other domain of a higher cardinality, which includes this domain, is not a group-separable domain. Parenthesizations that generate maximal group-separable domain are called binary parenthesizations. These parenthesizations have m − 1 parentheses. Thus, each maximal group-separable domain contains 2m−1 orders. Each group-separable preference profile belongs to a maximal group-separable domain.
The number of labeled binary parenthesizations of a word with m letters equals the number of maximal group-separable domains. From Murtagh (1984), the number of such parenthesizations and number of maximal group-separable domains is equal to
with \( \#^{MGSD} \left( 1 \right) = 1 \).
Theorem 3 from Danilov and Koshevoy (2013) states that each normal symmetric Condorcet domain of size 2m−1 has the form of some parenthesization of 12…n (normal parenthesization). Thus, we state the following characterization a maximal group-separable domain.
Proposition 4
(Danilov and Koshevoy 2013) A domain is a maximal symmetric Condorcet domain of size 2m−1if and only if it is a maximal group-separable domain.
All maximal group-separable domains also satisfy minimal richness. Maximal symmetric Condorcet domains of a size smaller than 2m−1 may not be group-separable domains. For example, the domain constructed in Proposition 5 of Danilov and Koshevoy (2013)
is a maximal symmetric Condorcet domain, but it is neither group-separable nor minimally rich. Dittrich (2018) found minimally rich maximal symmetric Condorcet domain, which is not group-separable:
4.1 Number of Group-Separable Preference Profiles
Here, we construct two bijections. The first one is a bijection µ between the normal parenthesization domains and Schröder paths of semilength m − 1 (i.e., the lattice paths from (0, 0) to (2m − 2, 0) with steps H = (2, 0), U = (1, 1) and D = (1, − 1) that do not go below the x-axis) with no peaks at level one. The second one is a bijection φ between the normal parenthesization domains and the sets of all proper reversible clone sets (reversible clone sets are defined below in this section). All of these objects are counted by the small Schröder numbers (it is the A001003 sequence in OEIS).
Schröder path UD has peak at level one, Schröder path UUDD has peak at level two. By counting the number of peaks at different levels it is convenient to categorize Schröder paths.
Let us define a function µ from normal parenthesization domains to Schröder paths of semilength m − 1 without peaks at level 1.
-
1.
m = 1. Normal parenthesization domain generates an empty Schröder path.
-
2.
m = 2. Normal parenthesization domain generates the Schröder path H.
-
3.
For m ≥ 3, function µ is defined recursively. There are three types of normal parenthesizations.
Type A
Type A parenthesization is a unique parenthesization type, which has “(1”, where 1 is the first element of parenthesized word. Type A Schröder path is a unique Schröder path type, which has no peaks at level 2 and has D at the end.
Type B
Type B parenthesization is a unique parenthesization type, which has “m)”, where m is the last element of parenthesized word. Type B Schröder path is a unique Schröder path type, which has H at the end.
Type C
where \( \left( {k_{i - 1} + 1 \ldots k_{i} } \right) \) is the ith reversible clone (it can be a singleton).
Type C parenthesization is a unique parenthesization type, which has neither “(1”, where 1 is the first element of parenthesized word, nor “m)”, where m is the last element of parenthesized word. Type C Schröder path is a unique Schröder path type, which has an inner common point with the x-axis and has no H at the end.
Because all types have unique features, function µ is bijective. The image of function µ is the set of all Schröder paths of semilength m − 1 without peaks at level 1. Examples 1 and 2 clarify the bijection.
Example 1
\( \mu \left( {\left( {123} \right)4\left( {5\left( {67} \right)} \right)} \right) = \mu \left( {123} \right){\text{U}}\mu \left( 4 \right){\text{UD}}\mu \left( {5\left( {67} \right)} \right){\text{D}} \) (Type C). Having \( \mu \left( {123} \right) = UUDD \) (Type C), \( \mu \left( {5\left( {67} \right)} \right) = U\mu \left( {67} \right)D = UHD \) (Type A), we obtain
Inverse problem. Because \( UUDD{\text{UUD}}UHD{\text{D}} \) has an inner common point with the x-axis and has no H at the end, it is type C. Thus, we have
Let Ω be the set of all proper reversible clone sets of a preference profile with all of the preference orders from a normal parenthesization domain. Each set between a pair of parentheses is a proper reversible clone set. One proper reversible clone set can be a subset of another proper reversible clone set, but it is impossible to have nonempty intersection without inclusion. By introducing parentheses, we obtain a correct parenthesization. Thus, we construct a bijection φ between normal parenthesization domains and sets of all proper reversible clone sets of normal parenthesization domains. Example 2 in Table 1 clarifies the constructed bijections.
Proposition 5
For m ≥ 2, the sum of the number of proper reversible clone sets and number of peaks in the corresponding Schröder path equals m − 2.
Each maximal parenthesization domain contains m − 2 proper reversible clone sets. There are \( \left( {\begin{array}{*{20}c} {m - 2} \\ i \\ \end{array} } \right) \) parenthesization domains with i proper reversible clone sets (m − i − 2 peaks in the corresponding Schröder path) that belong to the maximal parenthesization domain.
Chen et al. (2006, Theorem 3.3) found that the number of Schröder paths with no peaks at level one contained exactly k peaks at other levels. From Proposition 5, bijections µ we know, that these Schröder paths correspond normal parenthesization domains.
From the bijection µ, Chen et al.’s (2006) Theorem 3.3 and the sequence A126216 from OEIS, we directly have Proposition 6.
Proposition 6
The number of normal parenthesization domains with 2 m– k−1 preference orders (k is the number of peaks in the corresponding Schröder path) is equal to
The total number of normal parenthesization domains can be obtained by summation \( \#^{NPD} \left( {k,m} \right) \) over k from 0 to m − 2. Chen et al. (2006) showed, that this number is the m − 1th small Schröder number (A001003 in OEIS).
Proposition 7
The number of normal parenthesization domains equals the m − 1th small Schröder number (A001003 in OEIS).
The small Schröder numbers have no brief explicit formula. Stanley (1997) and Deutsch (2001) discussed in details several interpretations and related bijections of these numbers. Some paths, trees, parenthesizations, triangulations, etc. are counted by the small Schröder numbers.
Substituting k = 0 in formula from proposition 6 we obtain the number of normal maximal parenthesization domains.
Proposition 8
The number of normal maximal parenthesization domains equals the m − 1th Catalan number (A000108 in OEIS)
Proposition 8 also immediately follows from Danilov and Koshevoy (2013, p 191). Proposition 6 also leads to the main result.
Theorem 1
The number of group-separable preference profiles is equal to
For m = 3, m = 4, and m = 5, we have the following formulas:
These formulas have a polynomial form with coefficients from the sequence A126216 from OEIS.
For m = 3, the number of group-separable preference profiles is equal to the number of single-peaked preference profiles. By using the asymptotic formula for the number of single-peaked preference profiles from Lackner and Lackner (2017) for m ≥ 2 and n ≥ 2, we obtain the limits
Both the maximal group-separable and maximal single-peaked domains contain 2m−1 preference orders. The number of group-separable preference profiles is higher than the number of single-peaked preference profiles, but for small numbers of alternatives, this difference is not too large.
5 Number of Narcissistic Group-Separable Preference Profiles
Following Chen and Finnendahl (2018), the narcissistic preference profile is a preference profile with n orders and n alternatives such that order i has alternative i in the first place.
Theorem 2
The following recursive formula for the number of narcissistic group-separable preference profiles holds:
with\( \#^{NGSPP} \left( 1 \right) = 1 \).
The first terms of \( \#^{NGSPP} \left( n \right) \) are 1, 1, 6, 144, 13,440, 4,976,640, 7,390,494,720, and so on (for n = 1, 2, 3,…). Starting from n = 3, the number of narcissistic group separable preference profiles is higher than the number of narcissistic single peaked preference profiles and narcissistic single crossing preference profiles.
6 Conclusion
This paper shows that group-separable domains are a subclass of maximal symmetric Condorcet domains and that all maximal symmetric Condorcet domains of the largest cardinality are group-separable. All of the presented examples of the maximal symmetric Condorcet domain have a cardinality of 2 k for some \( k \in {\mathbb{N}} \). Whether this is true for all maximal symmetric Condorcet domains is an open question.
This paper connects group-separable preference domains, ordered trees, and Schröder paths and thus provides new bijections. These bijections lead to a new combinatorial result of the enumeration of group-separable preference profiles. This result fundamentally solves the enumeration problem first studied in Lackner and Lackner (2017).
Notes
Group separable preferences are also known as severe disagreement preferences (Van Deemen 2014).
References
Albert M, Homberger C, Pantone J (2015) Equipopularity classes in the separable permutations. Electron J Combin 22(2), P2.2
Arrow KJ (1963) Social choice and individual values. Yale University Press, New Haven
Ballester MA, Haeringer G (2011) A characterization of the single-peaked domain. Soc Choice Welf 36:305–322
Booth E, Lueker G (1976) Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-trees algorithms. J Comput Syst Sci 13:335–379
Bose P, Buss JF, Lubiw A (1998) Pattern matching for permutations. Inf Process Lett 65:277–283
Brandt F, Brill M, Seedig HG (2011) On the fixed-parameter tractability of composition-consistent tournament solutions. In: Proceedings of the 22nd international joint conference on artificial intelligence (IJCAI). AAAI Press, pp 85–90
Brandt F, Brill M, Hemaspaandra E, Hemaspaandra LA (2015) Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. J Artif Intell Res 53:439–496
Bredereck R, Chen J, Woeginger GJ (2016) Are there any nicely structured preference profiles nearby? Math Soc Sci 79(2016):61–73
Campbell DE, Kelly JS (2002) Impossibility theorems in the Arrovian framework. In: Arrow KJ, Sen AK, Suzumura K (eds) Handbook of social choice and welfare, Chap 1, vol 1. Elsevier, Amsterdam
Chen J, Finnendahl UP (2018) On the number of single-peaked narcissistic or single-crossing narcissistic preference profiles. Discrete Math 341:1225–1236
Chen WYC, Mansour T, Yan SHF (2006) Matchings avoiding partial patterns. Electron J Combin 13:#R112
Danilov VI, Koshevoy GA (2013) Maximal Condorcet domains. Order 30:181–194
Deutsch E (2001) A bijective proof of the equation linking the Schröder numbers, large and small. Discrete Math 241(1–3):235–240
Dittrich T (2018) Eine vollständige Klassifikation von Condorcet Domains für kleine Alternativenmengen. Dissertation. Karlsruher Instituts für Technologie (KIT)
Ehrenfeucht A, Harju T, ten Pas P, Rozenberg G (1998) Permutations, parenthesis words, and Schröder numbers. Discrete Math 190:259–264
Elkind E, Faliszewski P, Slinko A (2012) Clone structures in voters’ preferences. In: Proceedings of the 13th ACM conference on electronic commerce (EC). ACM, pp 496–513
Elkind E, Lackner M, Peters D (2017) Structured preferences. In: Endriss U (ed) Trends in Computational social choice, Chap 10. AI Access, pp 187–207
Faliszewski P, Hemaspaandra E, Hemaspaandra LA, Rothe J (2011) The shield that never was: societies with single-peaked preferences are more open to manipulation and control. Inf Comput 209(2):89–107
Faliszewski P, Hemaspaandra E, Hemaspaandra LA (2014) The complexity of manipulative attacks in nearly single-peaked electorates. Artif Intell 207:69–99
Gehrlein WV, Fishburn PC (1976) The probability of the paradox of voting: a computable solution. J Econ Theory 13:14–25
Gehrlein WV, Fishburn PC (1979) Proportions of profiles with a majority candidate. Comput Math Appl 5:117–124
Inada K (1964) A note on the simple majority decision rule. Econometrica 32(4):525–531
Inada K (1969) The simple majority decision rule. Econometrica 37(3):490–506
Kitaev S (2011) Why such patterns? A few motivation points. In: Kitaev S (ed) Patterns in permutations and words. Springer, Berlin, pp 29–80
Lackner ML, Lackner M (2017) On the likelihood of single-peaked preferences. Soc Choice Welf 48(4):717–745
Laslier J-F (1997) Tournament solutions and majority voting. Springer, Berlin, p 1997
Monjardet B (2009) Acyclic domains of linear orders: a survey. In: Brams S, Gehrlein W, Roberts F (eds) The mathematics of preference, choice and order. Springer, Berlin, pp 136–160
Murtagh F (1984) Counting dendrograms: a survey. Discrete Applied Math 7:191–199
OEIS. The on-line encyclopedia of integer sequences, published electronically at http://oeis.org
Puppe C (2018) The single-peaked domain revisited: a simple global characterization. J Econ Theory 176:55–80
Sen AK (1966) A possibility theorem on majority decisions. Econometrica 34(2):491–499
Stankova ZE (1994) Forbidden subsequences. Discrete Math 132:291–316
Stanley RP (1997) Hipparchus, Plutarch, Schröder, and Hough. Am Math Mon 104(4):344–350
Tideman TN (1987) Independence of clones as a criterion for voting rules. Soc Choice Welf 4:185–206
Van Deemen MA (2014) On the empirical relevance of Condorcet’s paradox. Public Choice 158:311–330
West J (1995) Generating trees and the Catalan and Schröder numbers. Discrete Math 146:247–262
West J (1996) Generating trees and forbidden subsequences. Discrete Math 157:363–374
Zavist TM, Tideman TN (1989) Complete independence of clones in the ranked pairs rule. Soc Choice Welf 6:167–173
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The author would like to thank Fuad Aleskerov, Gleb Koshevoy, Clemens Puppe, Tobias Dittrich and two anonymous referees for their valuable comments and also the user joriki for the useful combinatorial identity. The paper was prepared within the framework of the Basic Research Program at the National Research University Higher School of Economics (HSE) and supported within the framework of a subsidy by the Russian Academic Excellence Project ‘5–100’. The work was conducted by the International Laboratory of Decision Choice and Analysis (DeCAn Lab) of the National Research University Higher School of Economics.
Appendix
Appendix
Proof of Proposition 2
From Theorem 3.12 in Elkind et al. (2012) we have that the family of all clone sets satisfy axioms A1-A5. Let \( {\mathcal{F}} \) be a family of clone sets. Axioms A1-A5 are the following.
-
A1. \( \left\{ x \right\} \in {\mathcal{F}} \) for any \( x \in X \), \( \emptyset \notin {\mathcal{F}} \), and \( X \in {\mathcal{F}} \).
-
A2. If \( A,B \in {\mathcal{F}} \) and \( A \cap B \ne \emptyset \), then \( A \cup B \in {\mathcal{F}} \) and \( A \cap B \in {\mathcal{F}} \).
-
A3. If \( A,B \in {\mathcal{F}} \), \( A \cap B \ne \emptyset \), \( A\backslash B \ne \emptyset \), \( B\backslash A \ne \emptyset \), then \( A\backslash B \in {\mathcal{F}} \) and \( B\backslash A \in {\mathcal{F}} \).
-
A4. For each \( C \in {\mathcal{F}} \) there are at most two sets (minimal supersets) \( Z \in {\mathcal{F}} \) with the following properties: \( C \subseteq Z \), \( C \ne Z \) and there is no set \( Y \in {\mathcal{F}} \) such that \( Y \ne Z \) and \( C \subseteq Y \subseteq Z \).
-
A5. There is no set family \( A_{0} , \ldots ,A_{k - 1} \) with k ≥ 3 such that for all i = 0, …, k − 1
-
(1)
\( A_{i} \cap A_{i + 1} \ne \emptyset \), \( A_{i} \backslash A_{i + 1} \ne \emptyset \), \( A_{i + 1} \backslash A_{i} \ne \emptyset \);
-
(2)
\( A_{i - 1} \cap A_{i} \cap A_{i + 1} = \emptyset \);
-
(3)
\( A_{i} \in A_{i - 1} \cup A_{i + 1} \);
where all indices are computed modulo k.
(i) Suppose that the reducible preference profile has two different finest ordered partitions, \( {\mathcal{D}}^{A} \left( {X, {\mathcal{P}}} \right) \) and \( {\mathcal{D}}^{B} \left( {X, {\mathcal{P}}} \right) \), with ordered clone partitions A1, …, Aa and B1, …, Bb, respectively. Thus, there is Ai and \( l \in \left\{ {1, \ldots ,b} \right\} \) such that \( A_{i} {\bigcap }\left( {\bigcup\nolimits_{j = 1}^{l} {B_{j} } } \right) \ne \emptyset \) and \( A_{i} {\bigcap }\left( {\bigcup\nolimits_{j = l + 1}^{b} {B_{j} } } \right) \ne \emptyset \).. If \( \left( {\bigcup\nolimits_{j = 1}^{i - 1} {A_{j} } } \right){\bigcap }\left( {\bigcup\nolimits_{j = 1}^{l} {B_{j} } } \right) \ne \emptyset \) and \( \left( {\bigcup\nolimits_{j = 1}^{i - 1} {A_{j} } } \right){\bigcap }\left( {\bigcup\nolimits_{j = l + 1}^{b} {B_{j} } } \right) \ne \emptyset \), then sets Ai, \( \left( {\bigcup\nolimits_{j = 1}^{l} {B_{j} } } \right) \), \( \left( {\bigcup\nolimits_{j = l + 1}^{b} {B_{j} } } \right) \), and \( \left( {\bigcup\nolimits_{j = 1}^{i - 1} {A_{j} } } \right) \) contradict with axiom A Thus, we have either \( \left( {\bigcup\nolimits_{j = 1}^{i - 1} {A_{j} } } \right){\bigcap }\left( {\bigcup\nolimits_{j = 1}^{l} {B_{j} } } \right) = \emptyset \) or \( \left( {\mathop {\bigcup }\nolimits_{j = 1}^{i - 1} A_{j} } \right){\bigcap }\left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right) = \emptyset \). By applying the same argument for \( \left( {\mathop {\bigcup }\nolimits_{j = i + 1}^{a} A_{j} } \right) \), we have either \( \left( {\mathop {\bigcup }\nolimits_{j = i + 1}^{a} A_{j} } \right){\bigcap }\left( {\mathop {\bigcup }\nolimits_{j = 1}^{l} B_{j} } \right) = \emptyset \) or \( \left( {\mathop {\bigcup }\nolimits_{j = i + 1}^{a} A_{j} } \right){\bigcap }\left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right) = \emptyset \).
Case i = 1. We have either \( \left( {\mathop {\bigcup }\nolimits_{j = 1}^{l} B_{j} } \right){\bigcap }A_{2}\ne \emptyset \) or \( \left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right){\bigcap }A_{2}\ne \emptyset \). If \( \left( {\mathop {\bigcup }\nolimits_{j = 1}^{l} B_{j} } \right){\bigcap }A_{2}\ne \emptyset \); then, \( \left( {A_{1} {\bigcup }A_{2} } \right) \cap \left( {\left( {\mathop {\bigcup }\nolimits_{j = 1}^{l} B_{j} } \right){\bigcup }A_{2} } \right) \) is a clone set and an ordered partition \( C_{1} , \ldots ,C_{a + 1} \) such that \( C_{1}= A_{1}\cap \left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right) \), \( C_{2}= A_{1}\cap \left( {\mathop {\bigcup }\nolimits_{j = 1}^{l} B_{j} } \right) \) and \( C_{j + 1} = A_{j} \) for \( j \in \left\{ {2, \ldots ,a} \right\} \) is a clone ordered partition. If \( \left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right){\bigcap }A_{2}\ne \emptyset \), then \( \left( {A_{1} {\bigcup }A_{2} } \right) \cap \left( {\left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right){\bigcup }A_{2} } \right) \) is a clone set and an ordered partition \( C_{1} , \ldots ,C_{a + 1} \) such that \( C_{1}= A_{1}\cap \left( {\mathop {\bigcup }\nolimits_{j = 1}^{l} B_{j} } \right) \), \( C_{2}= A_{1}\cap \left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right) \), and \( C_{j + 1} = A_{j} \) for \( j \in \left\{ {2, \ldots ,a} \right\} \) is a clone ordered partition. These partitions are finer than \( {\mathcal{D}}^{A} \left( {X, {\mathcal{P}}} \right) \).
Case i = a is similar.
Case \( a > i > 1 \). If \( \left( {\mathop {\bigcup }\nolimits_{j = 1}^{i - 1} A_{j} } \right){\bigcap }\left( {\mathop {\bigcup }\nolimits_{j = 1}^{l} B_{j} } \right) = \emptyset \) and \( \left( {\mathop {\bigcup }\nolimits_{j = i + 1}^{a} A_{j} } \right){\bigcap }\left( {\mathop {\bigcup }\nolimits_{j = 1}^{l} B_{j} } \right) = \emptyset \), then clone set \( A_{i}\cap \left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{l} } \right) \) has three minimal supersets: the subsets of \( \left( {\mathop {\bigcup }\nolimits_{j = 1}^{i} A_{j} } \right){\bigcap }\left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right) \), \( \left( {\mathop {\bigcup }\nolimits_{j = i}^{a} A_{j} } \right){\bigcap }\left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right) \), and Ai. It contradicts with axiom A4. The same argument exists for the case of \( \left( {\mathop {\bigcup }\nolimits_{j = 1}^{i - 1} A_{j} } \right){\bigcap }\left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right) = \emptyset \) and \( \left( {\mathop {\bigcup }\nolimits_{j = i + 1}^{a} A_{j} } \right){\bigcap }\left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right) = \emptyset \). If \( \left( {\mathop {\bigcup }\nolimits_{j = 1}^{i - 1} A_{j} } \right){\bigcap }\left( {\mathop {\bigcup }\nolimits_{j = 1}^{l} B_{j} } \right) = \emptyset \). and \( \left( {\mathop {\bigcup }\nolimits_{j = i + 1}^{a} A_{j} } \right){\bigcap }\left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right) = \emptyset \), then an ordered partition \( C_{1} , \ldots ,C_{a + 1} \) such that \( C_{j} = A_{j} \) for \( j \in \left\{ {1, \ldots ,i - 1} \right\} \), \( C_{i}= A_{i}\cap \left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right) \), \( C_{i + 1}= A_{i}\cap \left( {\mathop {\bigcup }\nolimits_{j = 1}^{l} B_{j} } \right) \), and \( C_{j + 1} = A_{j} \) for \( j \in \left\{ {i + 1, \ldots ,a} \right\} \) is a clone ordered partition. If \( \left( {\mathop {\bigcup }\nolimits_{j = 1}^{i - 1} A_{j} } \right){\bigcap }\left( {\mathop {\bigcup }\nolimits_{j = l + 1}^{b} B_{j} } \right) = \emptyset \) and \( \left( {\mathop {\bigcup }\nolimits_{j = i + 1}^{a} A_{j} } \right){\bigcap }\left( {\mathop {\bigcup }\nolimits_{j = 1}^{l} B_{j} } \right) = \emptyset \), then an ordered partition \( C_{1} , \ldots ,C_{a + 1} \) such that \( C_{j} = A_{j} \) for \( j \in \left\{ {1, \ldots ,i - 1} \right\} \), \( C_{i}= A_{i}\cap \left( {\mathop {\bigcup }\nolimits_{j = 1}^{l} B_{j} } \right) \), and \( C_{j + 1} = A_{j} \) for \( j \in \left\{ {i + 1, \ldots ,a} \right\} \) is a clone ordered partition. These partitions are finer than \( {\mathcal{D}}^{A} \left( {X, {\mathcal{P}}} \right) \).
(ii) Suppose that an irreducible preference profile has two different minimal partitions \( {\mathcal{D}}^{A} \left( {X, {\mathcal{P}}} \right) \) and \( {\mathcal{D}}^{B} \left( {X, {\mathcal{P}}} \right) \) with clone partitions A1, …, Aa and B1, …, Bb, where \( a \le b \).
Let us consider the bipartite graph with vertices A1, …, Aa and B1, …, Bb. If \( A_{i} {\bigcap }B_{j} \ne \emptyset \), then we have an edge between Ai and Bj. Because of Axiom A5, this graph is a bipartite graph without cycles, Because of Axiom A4, each vertex is connected with, at most, two vertices with a degree of two or more. If this graph is not connected, then clone partitions A1, …, Aa and B1, …, Bb are not minimal. Thus, there is a chain, that connects vertices A1, …, Aa and a chain that connects a − 1 A type vertices. By axiom A2, this chain corresponds to a clone set. Thus, \( {\mathcal{D}}^{A} \left( {X, {\mathcal{P}}} \right) \) is reducible.□
Proof of Proposition 3
By proposition 2 each preference profile has unique clone decomposition tree. Suppose that a group-separable preference profile has P-node in a clone decomposition tree. The set associated with this node is irreducible. It contradicts with definition of group-separability. Thus, there is no P-node.
If a clone decomposition tree of a preference profile is a Q-tree, then for each subset of alternatives \( A \subseteq X, \left| A \right| \ge 2 \), there is a minimal reversible clone superset (it is a clone set which contains set A, but there is no other smaller reversible clone set, which also contains set A). Tree representation presents the finest ordered partition of this set. Because we find minimal reversible clone superset, the set A belongs to at least two parts of this partition. Thus, if for every \( A \subseteq X, \)\( \left| A \right| \ge 2 \) there exists a partition on two nonempty sets \( A',A\backslash A' \) such that for each \( i \in {\mathcal{N}} \), we have either \( aP_{i} b \) for each \( a \in A' \), \( b \in A\backslash A' \) or \( bP_{i} a \) for each \( a \in A \), \( b \in A\backslash A' \).□
Proof of Proposition 5
Let a be a function, which possess the value of the number of proper reversible clone sets, and b be a function, which possess the value of the number of peaks in the corresponding Schröder path.
According to bijection µ for m = 2, we have Schröder path H and the sum equals to 0. Suppose that for all \( \hat{m} < m \) we have a + b = m − 2. Let us prove for m.
For m ≥ 3, function µ is defined recursively. For type A, we have
From induction assumption we have \( a\left( {2 \ldots m} \right) + b\left( {\mu \left( {2 \ldots m} \right)} \right) = m - 3 \). Thus, we obtain \( a\left( {1\left( {2 \ldots m} \right)} \right) + b\left( {U\mu \left( {2 \ldots m} \right)D} \right) = m - 2 \).
For type B, we have
From induction assumption we have \( a\left( {1 \ldots m - 1} \right) + b\left( {\mu \left( {1 \ldots m - 1} \right)} \right) = m - 3 \). Thus, we obtain \( a\left( {\left( {1 \ldots m - 1} \right)m} \right) + b\left( {\mu \left( {1 \ldots m - 1} \right)H} \right) = m - 2 \).
For type C, we have
From induction assumption we have for nonsingletons \( a\left( {k_{i} + 1 \ldots k_{i + 1} } \right) + b\left( {\mu \left( {k_{i} + 1 \ldots k_{i + 1} } \right)} \right) = k_{i + 1} - k_{i} - 2 \), and for singletons \( a\left( {k_{i} + 1 \ldots k_{i + 1} } \right) + b\left( {\mu \left( {k_{i} + 1 \ldots k_{i + 1} } \right)} \right) = k_{i + 1} - k_{i} - 1 = 0 \). Thus, we obtain
□
Proof of Theorem 1
Each group-separable preference profile belongs to a parenthesization domain. Each parenthesization domain is group-separable. The number of group-separable preference profiles with the first order 1, 2 … m is m! times less than \( \#^{GSPP} \left( {n,m} \right) \). We call this preference profile a normal preference profile.
The number of preference orders in a normal parenthesization domain with r proper reversible clone sets is equal to 2(r+1). The number of normal preference profiles in a normal parenthesization domain with r proper reversible clone sets is equal to 2(r+1)(n−1). From inclusion–exclusion principle the number of normal preference profiles in two normal parenthesization domains with \( r_{1} = \left| {{{\Omega }}_{1} } \right|, r_{2} = \left| {{{\Omega }}_{2} } \right|,r_{3} = \left| {{{\Omega }}_{1} \cap {{\Omega }}_{2} } \right| \) is equal to \( 2^{{\left( {r_{1} + 1} \right)\left( {n - 1} \right)}} + 2^{{\left( {r_{2} + 1} \right)\left( {n - 1} \right)}} - 2^{{\left( {r_{3} + 1} \right)\left( {n - 1} \right)}} \).
Applying inclusion–exclusion principle we obtain the number of normal preference profiles that belong to a parenthesization domain with k peaks in the corresponding Schröder path and m − 2 − k proper reversible clone sets, which do not belong to any other normal parenthesization domains with the lower number preference orders
The parenthesization domain without proper reversible clone sets does not contain any other parenthesization domain. The number of normal preference profiles in this domain equals 2(n−1). By knowing the number of normal parenthesization domains from proposition 6, we obtain
By introducing a = k + j and modifying, we have
By using the following combinatorial identity
(both sides are the number of ways of selecting m − 1 elements from the 2(m − 1) element set such that a particular elements are not included in the selection), we obtain the result
□
Proof of Theorem 2
Each narcissistic group-separable preference profile generates a parenthesization, which corresponds to a maximal parenthesization domain. Each maximal parenthesization domain has 2n−1 orders.
Each maximal parenthesization partitions the set of alternatives into two parts (two clone sets). Let, a part with alternative 1 be a set A, |A| = k. The number of ways to choose A with k elements equals to \( \left( {\begin{array}{*{20}c} {n - 1} \\ {k - 1} \\ \end{array} } \right) \). \( \#^{NGSPP} \left( k \right) \) is the number of ways to define narcissistic group-separable preference subprofile with k voters and the first alternatives from A. Each such preference profile belongs to a maximal parenthesization domain with 2 k−1 preference orders. \( \#^{NGSPP} \left( {n - k} \right) \). is the number of ways to define narcissistic group-separable preference subprofile with n-k voters and alternatives from X\A\( X\backslash A \). Each such preference profile belongs to a maximal parenthesization domain with 2n−k−1 preference orders. For each pair of narcissistic group-separable preference subprofiles there are (2n−k−1)k(2 k−1)n−k ways to define remainder preference profile. Thus, we have
Through simplification we obtain the result.□
Rights and permissions
About this article
Cite this article
Karpov, A. On the Number of Group-Separable Preference Profiles. Group Decis Negot 28, 501–517 (2019). https://doi.org/10.1007/s10726-019-09621-w
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10726-019-09621-w