Bipartite peak-pit domains

The simplest non-trivial model for the possible rankings of a collection of alternatives is perhaps the single-peaked domain. This domain was introduced formally in Black (1948) and corresponds to a society in which all voters have a common political axis, each voter has a preferred position on this axis and ranks alternatives according to how close to this preferred position they are. Black (1948) showed that on any domain of this type majority voting will select a unique winner, and in fact produce a transitive ranking of all alternatives. In terms of modelling the behaviour of a group of voters the single-peaked domain provides a sensible first approximation of, for example, a society where opinions correlate with a left-right, or a liberal-conservative axis. It is however clearly not a universal model. A second distinct model is given by the single-dipped domains, in which voters instead have a least preferred position on a common axis and rank alternatives higher when they are further away from this position. Up to relabeling of alternatives there is exactly one maximal single-peaked domain for $n$ alternatives, known as Black’s single-peaked domain, and one maximal singe-dipped domain. Both have size $2^{n-1}$, where $n$ is the number of alternatives, and are in fact each other’s duals, i.e. each order in one appears reversed in the other.

In real life situations the collection of opinions is often not strictly determined by a common political axis and modeling requires more flexible options than Black’s single-peaked domain, and the single-dipped domain. Arrow (1963) introduced one such class by requiring that the restriction to any triple of alternatives must be single-peaked in Black’s sense, but letting go of the common political axis. These domains are now known as Arrow’s single-peaked domains and have been studied in great detail. Slinko (2019) showed that maximal domains of this type have size $2^{n-1}$, just as Black’s, and they are minimally rich, meaning that every alternative is ranked first by some order. While this class generalises the single-peaked domain greatly it does not include the single-dipped domain. In the theory of computational social choice an alternative approach to expanding the set of domains has been to investigate if a domain is in fact, for a suitable distance measure, close to being single-peaked. When this is the case one then can attempt to exploit the nearby single-peaked domain to simplify computational problems which are known to have efficient algorithms on single-peaked domains. Examples of this approach can be found in (Bredereck et al., 2016).

One common generalisation of the single-peaked and single-dipped domains is given by the peak-pit domains. These domains follow the set-up given by Arrow and require the restriction to each triple of alternatives to be either single-peaked or single-dipped in Black’s sense. The class of peak-pit domains is much larger and structurally diverse than the Arrow’s single-peaked domains, giving the modeller the ability to match a wider range of groups or societies. However, this diversity also means that general peak-pit domains do not have the unified social interpretation that the single-peaked domains have. Peak-pit domains have been studied in numerous papers, see e.g Danilov et al. (2012); Li et al. (2021), and within the class one finds interesting trade-offs between different forms of diversity. It is easy to show that if a peak-pit domain is minimally rich then it is an Arrow’s single-peaked domain. However, if we consider domains which are not minimally rich we find examples which are much larger than Arrow’s domains, thereby giving more diversity in terms of the total number of distinct opinions. The first such examples were found by Fishburn (1996), and were only larger than Arrow’s domains by a linear factor, but by now several constructions Fishburn (2002); Karpov and Slinko (2023) have given exponentially larger domains. Most such examples have been relatively complicated to describe and analyse.

Another common generalisation has been given in terms of domains which are unions of single-peaked and single-dipped domains. In these domains each voter either has single-dipped or single-peaked preferences, and the domain may not be a Condorcet domain. For the union of the maximal single-peaked and single-dipped domains Achuthankutty and Roy (2018); Berga and Serizawa (2000) showed that the conclusion of the Gibbard-Satterwhaite theorem remains valid, saying that strategy-proof voting rules must be dictatorial. Later works Feigenbaum and Sethuraman (2015); Alcalde-Unzu and Vorsatz (2018); Alcalde-Unzu et al. (2023) have shown that by adding additional public information about the voters one can derive strategy-proof non-dictatorial decision rules for domains in this class. The main limitation of these models is that each voter must belong to one of two quite restrictive classes. Another generalisation is given in Yang (2020) which consider domains which are the union of several single-peaked domains, each with a separate axis. Here the case of two distinct axes was found to remain well-behaved for several computational social choice problems.

In this paper we will introduce several sub-classes of the peak-pit domains which mix the structures of single-peaked and single-dipped domains in a new well-structured way. Instead of dividing the voters into two classes we divide the alternatives into two classes, which informally can be seen as attractive and repulsive alternatives respectively. The most general of our classes are the bipartite peak-pit domains. A peak-pit domain is bipartite if the set of alternatives can partitioned into two parts, such that on the first part the domain is single-peaked and on the second part the domain is single-dipped. This type of domain captures situations where voters have different rationales for their ranking of the two classes of alternatives. Within the first class they have a most preferred location on a societal axis, and within the second class they have a least preferred location. Here we impose no additional restrictions on the ranking of pairs of alternatives from both classes. As we shall show, most peak-pit domains on $n\leq 7$ alternatives are bipartite, as are the largest peak-pit domains on $n\leq 8$ alternatives.

Next we introduce a subclass of the bipartite peak-pit domains called midpoint bipartite peak-pit domains. Here alternatives from the two parts are intermixed by saying that the restriction to a triple whose midpoint belongs to the first of the two parts, shall be single-peaked, and vice versa. Equivalently, we can think of these domains as describing a society in which voters rank triples in a single-peaked or a single-dipped way, and they have one set of local midpoints which they prefer to give high local rank and one set of local midpoints which they prefer to give low local rank. Up to $n=7$ all maximum Condorcet domains belong to this class, but most peak-pit domains do not.

Finally, in order to simplify the structure of our domains further, and allow us to give a lower bound for how large bipartite peak-pit domains can become, we restrict our focus to domains with just two distinct never conditions, rather than the full set allowed for peak-pit domains. These are the set-alternating domains. As we will show, this class contains domains larger than any previously known, both when seen as peak-pit domains and more generally as Condorcet domains.

Let a finite set $X=[n]=\{1,\dots,n\}$ be the set of alternatives. Let $L(X)$ be the set of all linear orders over $X$. Each agent $i\in N$ has a preference order $P_{i}$ over $X$ (each preference order is a linear order). For brevity, we will write preference orders as strings, e.g. $12\dots n$ means $1$ is the best alternative, $n$ is the worst.

A subset of preference orders $D\subseteq L(X)$ is called a domain of preference orders. A domain $D$ is a Condorcet domain if whenever the preferences of all agents belong to the domain, the majority relation of any preference profile with an odd number of agents is transitive. A Condorcet domain $D$ is maximal if every Condorcet domain $D^{\prime}\supseteq D$ (on the same set of alternatives) coincides with $D$. In our paper we are focused on maximal Condorcet domains unless otherwise specified.

The dual of a partial order $R_{1}$ is the partial order $R_{2}$ for which $xR_{2}y$ if and only if $yR_{1}x$. The dual of a domain $D$ is the domain consisting of the dual of each order in $D$.

A societal axis for a domain is a designated linear order on the set of alternatives. This is usually assumed to correspond to some organising principle for the alternatives, e.g. a left-right political scale. The societal axis is not necessarily an element of the domain, e.g. for some domains which are not maximal domains.

Sen (1966) proved that a domain is a Condorcet domain if the restriction of the domain to any triple of alternatives $(a,b,c)$ satisfies a never condition. A never condition can be of three forms $xNb$, $xNm$ $xNt$, referred to as a never bottom, a never middle, and a never top condition respectively. Here $x$ is an alternative from the triple and $xnb$, $xNm$, and $xNt$ means that $x$ is not ranked last, second, or first respectively in the restricted domain. Fishburn noted that for domains with a societal axis never conditions can instead be described as $iNj$, $i,j\in[3]$. $iNj$ means that $i^{th}$ alternative from the triple according to societal axis does not fill in $j^{th}$ place within this triple in each order from the domain. For example restriction $abc$ to triple $a,b,c\in[n]$, $a<b<c$ satisfies never conditions $1N2,1N3,2N1,2N3,3N1,3N2$, but violates never conditions $1N1,2N2,3N3$.

A Condorcet domain $D$ is connected if, given any two orders from the domain, the second order can be obtained from the first by a sequence of transpositions of neighbouring alternatives such that all orders generated by this sequence belong to the domain. A Condorcet domain has maximal width if it contains a pair of completely reversed linear orders. A Condorcet domain $D$ is unitary if it contains order $123\ldots n$.

Following Slinko (2019) we say that a Condorcet domain is copious if the restriction to any triple has size 4, or equivalently every triple, satisfies a single never condition. A domain is ample if the restriction to any pair has size two. Every copious Condorcet domain is ample.

A domain which satisfies a never condition of the form $xN3$ for every triple is called Arrow’s single-peaked domain.

A domain $D$ is a peak-pit domain if, for each triple of alternatives, the restriction of the domain to this triple is either single-peaked ($iN3$ restriction), or single-dipped ($iN1$ restriction).

A domain $D$ is called a Fishburn domain if it satisfies the alternating scheme Fishburn (1996): there exists a linear ordering of alternatives $a_{1},\ldots,a_{m}$ such that for all $i,j,k$ with $1\leq i<j<k\leq m$ the restriction of the domain to the set $\{a_{i},a_{j},a_{k}\}$ is single-peaked with axis $a_{i}a_{j}a_{k}$ if $j$ if is even (odd), and it is single-dipped with axis $a_{i}a_{j}a_{k}$ if $j$ is odd (even). Note that there is either one or two Fishburn domains depending on the parity of $n$. The dual of a Fishburn domain is also a Fishburn domain.

Recall that the asymptotic notation $f(n)\in\Omega(g(n))$ means that $\lim_{n\rightarrow\infty}{\frac{f(n)}{g(n)}}>0$,

Fishburn (1996) introduced the function

Similarly Karpov and Slinko (2023) introduced the function

and also showed that $f(n)\in\Omega(2.1890^{n})$ and $h(n)\in\Omega(2.1045^{n})$.

Every domain $D$ is associated with a graph $G_{D}$ (Puppe and Slinko, 2019). The set of linear orders from $D$ is the set of vertices $V_{D}$ and for two orders $u,w\in D$ we draw an edge between them if $D$ does not contain order $x$ that is between $u,w$ in terms of Kemeny betweeness (which means that $x$ agrees with all binary comparisons on which $u,v$ agrees). Puppe and Slinko (2019) proved that for each Condorcet domain $D$ the graph $G_{D}$ is a median graph (as defined by (Mulder, 1978)). If Condorcet domain $D$ is connected, then in the associated domain each edge represents one swap of neighbouring alternatives.

For set complements we will use the notation $\overline{A}=[n]\setminus A$, where $A\subseteq[n]$.

We will start by formalising some of the domain types described in the introduction.

The class of bipartite peak-pit domains is closed under isomorphism so every domain of type is isomorphic to one where $A=\{1,2,\ldots,k\}$, $\bar{A}=\{k+1,\ldots,n\}$, for some $k$.

For $n<6$ all peak-pit domains are trivially bipartite, since, if $D$ is not single-dipped, we can take $A$ to be any triple which has a never bottom condition, and then $\bar{A}$ will have size less than 3 and hence define a single-dipped domain in a trivial way. However, for $n\geq 6$ this is a non-trivial sub-class of the peak-pit domains. For $n=6$ there are 9939 maximal peak-pit domains Akello-Egwell et al. (2023) and a computational search shows that 124 of these are not bipartite. In Table 1 we display the non-bipartite maximal peak-pit domain with the smallest number of orders. For $n=7$ there are 1465680 peak-pit domains, and of those 34393 are not bipartite. This is a slight increase in the proportion of non-bipartite domains from $n=6$, but only to about 2% of all peak-pit domains. For very large $n$ we expect most peak-pit domains to not be bipartite.

The maximum Condorcet domain for $n=8$, of size 224, found in Leedham-Green et al. (2023) is a bipartite peak-pit domain, with $A$ of size 4. In fact, up to $n=8$ all maximum Condorcet domains belong to this class.

In a bipartite peak-pit domain we have no restrictions on the never conditions for triples which intersect both $A$ and $\bar{A}$. A natural subclass, which contains many classical Condorcet domains, are those which have a societal axis and never conditions which are determined by a subset of that axis.

The restriction of the domain $D$ to $A$ is an Arrow’s single-peaked domain and the restriction to $\bar{A}$ is the dual of an Arrow’s single-peaked domain. Hence a midpoint bipartite peak-pit domain is indeed a bipartite peak-pit domain. Given a midpoint bipartite peak-pit domain $D$, its restriction to a subset of the alternatives is also a midpoint bipartite peak-pit domain.

The best-known examples of midpoint bipartite peak-pit domains are those defined by Fishburn’s alternating scheme. There the sets $A$ and $\bar{A}$ are given by the even and odd integers respectively. The generalized Fishburn domains studied in (Karpov, 2023; Slinko, 2023) are also midpoint bipartite peak-pit domains.

The smallest examples of maximal peak-pit Condorcet domain which are not midpoint bipartite peak-pit domain have four alternatives. One such example is the single-crossing domain (Slinko et al., 2021) on four alternatives. In this domain there is one never-top triple and three never-bottom (or dual of it), giving two triples with different never conditions but the same midpoint.

Note that unlike the bipartite peak-pit domain, this class is not closed under isomorphism, since an isomorphism typically changes the societal axis in a way which means that midpoints for triples are not preserved. The dual of a midpoint bipartite peak-pit domain will however be a midpoint bipartite peak-pit domain.

For $n\leq 7$ we have used the data from Akello-Egwell et al. (2023) to find all maximal peak-pit domains which are mid-point bipartite. The results are displayed in Table 2.

Note that the midpoint bipartite maximal peak-pit domains all have size at least $2^{n-1}$ for $n\leq 7$. We conjecture that this is true for all $n$.

In section 4 we will show that this lower bound is true for the domains generated by set-alternating schemes, a strict subclass of the midpoint bipartite peak-pit domains.

Up to $n=7$, the maximum size Condorcet domains for each $n$ are midpoint bipartite peak-pit domains. However, the maximum size Condorcet domain for $n=8$, which is a bipartite peak-pit domain, is not a midpoint bipartite domain²²2This has been checked computationally., giving the first example of a maximum Condorcet domain which does not belong to this class.

In our next section we will proceed to study set-alternating schemes. These define a class midpoint bipartite peak-pit domains which use only two distinct never conditions but, as we shall show, for large $n$ they nonetheless produce the largest known Condorcet domains.

Our focus in this section is a class of domains which have a societal axis and relative to that axis are defined using only the never conditions $1N3$ and $3N1$. As we will see our particular class of such domains are mathematically natural, but the general class of domains using only these never conditions also have a natural social choice interpretation. Given a societal axis the never conditions $1N3$ and $3N1$ can both be seen as expressing a weak form of agreement with the ranking on the axis. The condition $1N3$ for a triple $a>b>c$ implies that the domain never ranks $a$ last of the three, and $3N1$ means that $c$ is never placed first. Consequently, this can be used to model a relatively homogeneous society where the population mostly agree with a common societal axis. There are some exceptional domains in the class. If we have only $1N3$ for all triples we get a unique Arrow’s single-peaked domains, which is minimally rich, with only two alternatives ranked last. Dually, the domain with only $3N1$ has only two top alternatives and all alternatives are ranked last in some order. However, for all other domains in this class the set of top ranked alternatives, and last ranked alternatives, are both strict subsets of the alternatives, often quite small. So, in this type of homogeneous societies, or domains, there is little diversity among the highest and lowest ranked alternatives. Strikingly, as our results will show, in terms of domain size some of these seemingly austere societies provide a larger variety of opinions than the single-peaked domains. Though here the source of variation is a diversity of alternatives ranked near the middle of the societal axis, rather than a variety of potential top or bottom alternatives.

Let us start our analysis by defining the class of set-alternating schemes.

Given that our definition of set-alternating schemes could easily be modified to use any other pair of never conditions, one may ask why we focus on the particular pair $1N3,3N1$? If one tests out all pairs of peak-pit never conditions on all sets $A$ for some small $n$, say $n=5$, one finds that most pairs do not generate a copious domain for every $A$, but a small set of pairs do. These pairs fall into four families.

The first are those which assign the same never condition to every triple. These domains have size $2^{n-1}$ by Raynaud (1981) and the domain does not depend on $A$, but it does depend on the choice of never condition. The second family are those which use two never-bottom conditions, or two never-top conditions. This is a subset of the class of Arrow’s single-peaked domains, and their duals. These also have size $2^{n-1}$ but here the domain does depend on $A$. The class of all Arrow’s single-peaked domains has been studied in detail in Slinko (2019). The third family uses the pair $2N1/2N3$. If we use this pair and take $A$ to be the set of odd numbers, or even numbers, we recover Fishburn’s alternating scheme. Generalised versions of Fishburn’s domains are discussed in Karpov (2023)). The fourth family, which we will show to be copious for all $n$, is given by the pair $1N3,3N1$ and is the focus of the remainder of the paper.

Let us consider some examples. If $A=[n]$, then all triples are assigned the $1N3$ never condition. This gives an Arrow’s single-peaked domain, but it is not Black’s single-peaked since the domain does not contain two mutually reversed orders. This is the only Arrow’s single-peaked domain given by a set-alternating scheme. By Slinko (2019) the cardinality of $D_{X}([n])$ is $2^{n-1}$. For $A=\emptyset$ we get a domain which can be related to that for the empty set via the following lemma.

For $n=4$, $D_{X}(\{2\})$ is isomorphic to Fishburn’s alternating scheme. $D_{X}(\{2\})$ leads to a $1N3$ never condition for triples 1,2,3 and 1,2,4, and a $3N1$ never condition for triples 1,3,4 and 2,3,4. The same set of never conditions follows from $2N3$ never condition in case of median 1 and $2N1$ never condition in case of median 4 for ordering of alternatives 2143. For $n>4$ there is no $A$ corresponding to Fishburn’s alternating scheme.

Here we may ask which domain sizes set-alternating schemes more generally generate. In Figure 1 we plot the pair (set size, domain size) for all subsets of $\{2,\ldots,n-1\}$ for $n=8$ and 9. We exclude 1 and $n$ from $A$ since they cannot be midpoints of a triple and hence do not affect which domain we generate. As we can expect from Lemma 1 the size distribution is symmetrical. The lowest domain sizes in the figure are of the form $2^{n-1}$ and in Corollary 1 we show that this is the minimum possible size. We also see many schemes which lead to much larger domains and we can identify the maximum ones.

This scheme produces the largest domain sizes for small $n$ and we will later investigate their growth rate. For even $n$ $B_{n}$ is equal to its reverse complement. For odd $n$ the reverse complement consists of the even numbers $B_{n}^{*}=\{2,\ldots n-3\}$, which by Lemma 1 generates a domain of the same size as $B_{n}$. If we extend this set of even numbers by $n-1$ we get a new scheme which we will use in our asymptotic analysis.

We will refer to the scheme given by taking $B_{n}^{*}$ for odd $n$ and $A_{n}\setminus(n-2)$ for even $n$ as the truncated even $1N33N1$-alternating scheme.

Figure 2 displays the median graph associated to the even $1N33N1$-alternating scheme for $n=6$.

In Table 3 we show the sizes of the domains generated by these schemes and Fishburn’s alternating scheme, each computed using the Condorcet Domain Library (CDL) from Zhou and Riis (2023); Zhou et al. (2023).

Regarding the maximum domain size we conjecture the following.

This conjecture has been verified computationally for $n\leq 24$. As we can see for $n<16$ Fishburn’s alternating scheme leads to larger domains than the odd $1N33N1$-alternating scheme.

In addition to potentially large sizes, the set-alternating schemes generate domains with good local structure.

All set-alternating domains have a well-structured common part. The Condorcet domain which for each triple satisfies the two never conditions 1N3 and 3N1 is a subset of every set-alternating domain. For unitary domains the common part has the following structure. Each order from the common part is obtained by swaps of disjoint pairs of neighbouring alternatives in order $12\ldots n$. For each triple of neighbouring alternatives $x-1,x,x+1$ we have orders $x-1xx+1,xx-1x+1,x-1x+1x$ as the restriction to the set $\{x-1,x,x+1\}$.

The asymptotic growth rate of the Fibonacci sequence is $\frac{1+\sqrt{5}}{2}\approx 1.618$.

Set-alternating schemes can be used as a straightforward way of producing random examples of maximal Condorcet domains. For a given $n$ we can construct a set $A$ at random by including each value from $X_{n}$ with probability $p$, independently, and then construct a domain $D$ by using the set-alternating scheme given by $A$. For $p=\frac{1}{2}$ we get the uniform distribution for $A$.

Since the domain size here is exponential in $n$ the expected size might deviate significantly from the median size. The same question could be asked for the median.

Here we analyze even set-alternating domain $D_{X}(A_{n})$ and its size $a(n)$. In proofs we use $A_{n}=\{1,2,4,6,\ldots,n-2+p_{n}\}$, $p_{n}=(n\bmod 2)$. Adding 1 to set $A_{n}$ does not change the definition, but universalizes notation. From now on we let $a(n)$ denote the size of the domain resulting from the even $1N33N1$-alternating scheme.

We partition all orders in $D_{X}(A_{n})$ on orders that start from set $\{1,2\}$, orders that start from set $\{1,2,3,4\}$, but not from set $\{1,2\}$, orders that start from set $\{1,2,3,4,5,6\}$, but not from set $\{1,2,3,4\}$, etc. Orders from part $k$ start from $[2k]$, but not from $[2(k-1)]$.

Orders from the first part start from 12, 21. There are $2a(n-2)$ such orders. Orders from the second part start from 1324, 1342, 3124, 3142, 3412. There are $5a(n-4)$ such orders. For $n=6$, 18 orders from the upper side of Figure 2 constitute the first part, 10 orders from the bottom left side of Figure 2 constitute the second part, 14 orders from the bottom right side of Figure 2 constitute the third part.