A characterization of the single-crossing domain

Abstract

We characterize single-crossing preference profiles in terms of two forbidden substructures, one of which contains three voters and six (not necessarily distinct) alternatives, and one of which contains four voters and four (not necessarily distinct) alternatives. We also provide an efficient way to decide whether a preference profile is single-crossing.

1 Introduction

Single-peaked and single-crossing preferences have become standard domain restrictions in many economic models. Preferences are single-peaked if there exists a linear ordering of the alternatives such that any voter’s preference relation along this ordering is either always strictly increasing, always strictly decreasing, or first strictly increasing and then strictly decreasing. Preferences are single-crossing if there exists a linear ordering of the voters such that for any pair of alternatives along this ordering, there is a single spot where the voters switch from preferring one alternative above the other one. In many situations, these assumptions guarantee the existence of a strategy-proof collective choice rule, or the existence of a Condorcet winner, or the existence of an equilibrium.

Single-peaked preferences go back to the work of Black (1948) and have been studied extensively over the years. Single-peakedness implies a number of nice properties, as for instance non-manipulability (Moulin 1980) and transitivity of the majority rule (Inada 1969). Single-crossing preferences go back to the seminal paper of Roberts (1977) on income taxation. Grandmont (1978), Rothstein (1990), and Gans and Smart (1996) analyze various aspects of the majority rule under single-crossing preferences. Furthermore, single-crossing preferences play a role in the areas of income redistribution (Meltzer and Richard 1981), coalition formation (Demange 1994; Kung 2006), local public goods and stratification (Westhoff 1977; Epple and Platt 1998), and in the choice of constitutional voting rules (Barberà and Jackson 2004). Saporiti and Tohmé (2006) study single-crossing preferences in the context of strategic voting and the median choice rule, and Saporiti (2009) investigates them in the context of strategy proof social choice functions. Barberà and Moreno (2011) develop the concept of top monotonicity as a common generalization of single-peakedness and single-crossingness (and of several other domain restrictions).

1.1 Forbidden substructures

Sometimes mathematical structures allow characterizations through forbidden substructures. For example, Kuratowski’s theorem (Kuratowski 1930) characterizes planar graphs in terms of forbidden subgraphs: a graph is planar if and only if it does not contain a subdivision of $K_5$ or $K_{3,3}.$ For another example, Hoffman et al. (1985) characterize totally-balanced 0-1-matrices in terms of certain forbidden submatrices. In a similar spirit, Lekkerkerker and Boland (1962) characterize interval-graphs through five (infinite) families of forbidden induced subgraphs.

In the area of social choice, a beautiful result by Ballester and Haeringer (2011) characterizes single-peaked preference profiles in terms of two forbidden substructures. The first forbidden substructure concerns three voters and three alternatives, where each of the voter ranks another one of the alternatives worst. The second forbidden substructure concerns two voters and four alternatives, where (sloppily speaking) both voters rank the first three alternatives in opposite ways with the second alternative in the middle, but prefer the fourth alternative to the second one.

1.2 Contribution of this paper

Inspired by the approach and by the results of Ballester and Haeringer (2011), we present a forbidden substructure characterization of single-crossing preference profiles. One of our forbidden substructures consists of three voters and six alternatives (as described in Example 4) and the other one consists of four voters and four alternatives (as described in Example 5). We stress that the (six respectively four) alternatives in these forbidden substructures are not necessarily distinct: the substructures only partially specify the preferences of the involved voters; hence by identifying and collapsing some of the involved alternatives we can easily generate a number of smaller forbidden substructures (which of course are just special cases of our larger forbidden substructures). Finally, we will discuss the close relation of single-crossing preference profiles to consecutive ones matrices. A $0$-1-matrix has the consecutive ones property if its columns can be permuted such that the $1$-values in each row are consecutive. We hope that our results will turn out useful for future research on single-crossing profiles.

In Sect. 2 we summarize the basic definitions and provide some examples. In Sect. 3 we formulate and prove our main result (Theorem 6). In Sect. 4 we discuss the tightness of our characterization, and we argue that there does not exist a characterization that works with smaller forbidden substructures. Finally, in Sect. 5 we briefly discuss simple approaches to finding a single-crossing ordering of the voters in polynomial time.

2 Definitions, notations, and examples

Let $a_1,\ldots ,a_m$ be $m$ alternatives and let $V_1,\ldots ,V_n$ be $n$ voters. A preference profile specifies the preference orderings of the voters, where voter $V_i$ ranks the alternatives according to a strict linear order $\succ _i.$ For alternatives $a$ and $b,$ the relation $a\succ _i b$ means that voter $V_i$ strictly prefers $a$ to $b.$

An unordered pair of two distinct alternatives is called a couple. A subset $\mathcal{V }$ of the voters is mixed with respect to couple $\{a,b\},$ if $\mathcal{V }$ contains two voters one of which ranks $a$ above $b,$ whereas the other one ranks $a$ below $b.$ If $\mathcal{V }$ is not mixed with respect to $\{a,b\},$ then it is said to be pure with respect to $\{a,b\}.$ Hence, an empty set of voters is pure with respect to any pair of alternatives. A couple $\{a,b\}$ separates two sets $\mathcal{V }_1$ and $\mathcal{V }_2$ of voters from each other, if no voter in $\mathcal{V }_1$ agrees with any voter in $\mathcal{V }_2$ on the relative ranking of $a$ and $b;$ in other words, sets $\mathcal{V }_1$ and $\mathcal{V }_2$ must both be pure with respect to $\{a,b\},$ and if both are non-empty then their union $\mathcal{V }_1\cup \mathcal{V }_2$ is mixed.

An ordering of the voters is single-crossing with respect to couple $\{a,b\},$ if the ordered list of voters can be split into an initial piece and a final piece that are separated by $\{a,b\}.$ An ordering of the voters is single-crossing, if it is single-crossing with respect to every possible couple. Finally a preference profile is single-crossing, if it allows a single-crossing ordering of the voters. It is easy to see that single-crossing is a monotone property of preference profiles:

Lemma 1

Let $\mathcal{P }$ be a preference profile, and let $\mathcal{P }^{\prime }$ result from $\mathcal{P }$ by removing some alternatives and/or voters. If $\mathcal{P }$ is single-crossing, then also $\mathcal{P }^{\prime }$ is single-crossing. $\square$

In the remaining part of this section we present several instructive examples of preference profiles that are single-crossing (Sect. 2.1) respectively that are not single-crossing (Sect. 2.2).

2.1 Profiles from weak Bruhat orders

Let $S_m$ denote the set of permutations of $1,\ldots ,m.$ We specify permutations $\pi \in S_m$ by listing the entries as $\pi =\langle \pi (1),\pi (2),\ldots ,\pi (n)\rangle .$ The identity permutation $\langle 1,2,\ldots ,m\rangle$ arranges the integers in increasing order, and the order reversing permutation $\langle m,{m-1},\ldots ,2,1\rangle$ arranges them in decreasing order. A descent in $\pi$ is a pair $(\pi (i),\pi (i+1))$ of consecutive entries with $\pi (i)>\pi (i+1).$ We write $\pi \lhd \rho ,$ if permutation $\pi$ can be obtained from permutation $\rho$ by a series of swaps, each of which interchanges the two elements of a descent.

The partially ordered set $(S_m,\lhd )$ is known as weak Bruhat order; see for instance Bóna (2004). The weak Bruhat order has the identity permutation as minimum element and the order reversing permutation as maximum element. Every maximal chain (that is: every maximal subset of pairwise comparable permutations) in the weak Bruhat order has length $\frac{1}{2}m(m-1)+1$ and contains the identity permutation and the order reversing permutation.

The following example illustrates the well-known connection between weak Bruhat orders and single-crossing preference profiles; we refer the reader to Abello (1991) or Galambos and Reiner (2008) for more information.

Example 2

Let $C=(\pi _1\lhd \pi _2\lhd \cdots \lhd \pi _n)$ be a maximal chain with $n=\frac{1}{2}m(m-1)+1$ permutations in the weak Bruhat order $(S_m,\lhd ).$ We construct a profile by using $1,\ldots ,m$ as alternatives, and by interpreting every permutation $\pi$ as preference ordering $\pi (1)\succ \pi (2)\succ \ldots \succ \pi (n)$ over the alternatives. Voter $V_i$ has preference ordering $\pi _i.$ See Fig. 1 for an illustration with $m=5$ alternatives and $n=11$ voters.

The resulting profile is single-crossing: any two alternatives $a$ and $b$ start off in the right order in the identity permutation $\pi _1,$ eventually are swapped into the wrong order, and then can never be swapped back again at later steps. Furthermore, the profile contains $n=\frac{1}{2}m(m-1)+1$ voters with pairwise distinct preference orderings. $\square$

Fig. 1

A single-crossing preference profile with $11$ voters and $5$ alternatives.

If one starts the construction in Example 2 from arbitrary (not necessarily maximal!) chains in the weak Bruhat order, then one can generate this way every possible single-crossing preference profile (up to isomorphism). This is another well-known connection, which follows from the fact that $\pi \lhd \rho$ if and only if every inversion of permutation $\pi$ also is an inversion of permutation $\rho .$

2.2 Some profiles that are not single-crossing

We next present three examples of profiles that are not single-crossing. The first example is due to Saporiti and Tohmé (2006) and shows a profile that is single-peaked but fails to be single-crossing. The other two examples introduce two principal actors of this paper.

Example 3

Consider four alternatives 1, 2, 3, 4 and three voters $V_1,\,V_2,\,V_3$ with the following preference orders:

$$\begin{aligned} \text{ Voter}~V_1:~ 2\succ _1 3\succ _1 4\succ _1 1\\ \text{ Voter}~V_2:~ 4\succ _2 3\succ _2 2\succ _2 1\\ \text{ Voter}~V_3:~ 3\succ _3 2\succ _3 1\succ _3 4 \end{aligned}$$

It can be verified that this profile is not single-crossing but single-peaked (with respect to the ordering $1<2<3<4$ of alternatives, for instance). $\square$

Example 4

($\gamma$-Configuration) A profile with three voters $V_1,\,V_2,\,V_3$ and six (not necessarily distinct) alternatives $a,b,c,d,e,f$ is a $\gamma$-configuration, if it satisfies the following:

$$\begin{aligned} \text{ Voter}~V_1:~ b\succ _1 a ~\text{ and}~ c\succ _1 d ~\text{ and}~ e\succ _1 f\\ \text{ Voter}~V_2:~ a\succ _2 b ~\text{ and}~ d\succ _2 c ~\text{ and}~ e\succ _2 f\\ \text{ Voter}~V_3:~ a\succ _3 b ~\text{ and}~ c\succ _3 d ~\text{ and}~ f\succ _3 e \end{aligned}$$

This profile represents a situation where each voter disagrees with the other two voters on exactly one couple. The profile is not single-crossing, as none of the three voters can be put between the other two: the couple $\{a,b\}$ prevents us from putting $V_1$ into the middle, the couple $\{c,d\}$ forbids voter $V_2$ in the middle, and the couple $\{e,f\}$ forbids $V_3$ in the middle. $\square$

Example 4 provides an easy proof that the profile in Example 3 is not single-crossing, as this profile contains a $\gamma$-configuration with $a=3,\,b=c=2,\,d=e=4,$ and $f=1.$

Example 5

($\delta$-Configuration) A profile with four voters $V_1,\,V_2,\,V_3,\,V_4$ and four (not necessarily distinct) alternatives $a,b,c,d$ is a $\delta$-configuration, if it satisfies the following:

$$\begin{aligned} \text{ Voter}~V_1:~ a\succ _1 b ~\text{ and}~ c\succ _1 d\\ \text{ Voter}~V_2:~ a\succ _2 b ~\text{ and}~ d\succ _2 c\\ \text{ Voter}~V_3:~ b\succ _3 a ~\text{ and}~ c\succ _3 d\\ \text{ Voter}~V_4:~ b\succ _4 a ~\text{ and}~ d\succ _4 c \end{aligned}$$

This profile shows a different kind of voter behavior: two voters disagree with the other two voters on one couple, but also disagree between each other on another couple. As before, this profile is not single-crossing, as couple $\{a,b\}$ forces us to place $V_1$ and $V_2$ next to each other, and to put $V_3$ and $V_4$ next to each other; couple $\{c,d\}$ forces us to place $V_1$ and $V_3$ next to each other, and to put $V_2$ and $V_4$ next to each other. This means that no voter can be put into the first position. $\square$

3 A characterization through forbidden configurations

Examples 4 and 5 demonstrate that preference profiles that contain a $\gamma$-configuration or a $\delta$-configuration cannot be single-crossing. It turns out that these two configurations are the only obstructions for the single-crossing property.

Theorem 6

A preference profile $\mathcal{P }$ is single-crossing, if and only if $\mathcal{P }$ contains neither a $\gamma$-configuration nor a $\delta$-configuration.

The rest of this section is dedicated to the proof of Theorem 6. The (only if) part immediately follows from the monotonicity of the single-crossing property (Lemma 1) and from the observations stated in Examples 4 and 5.

For the (if) part, we first introduce some additional definitions and notations. An ordered partition $\langle X_1,\ldots ,X_p\rangle$ of the voters $V_1,\ldots ,V_n$ satisfies the following properties: every part $X_i$ is non-empty, distinct parts are disjoint, the union of all parts is the set of all voters, and the arrangement of the parts $X_i$s is crucial. The trivial ordered partition has $p=1$ and hence consists of a single part $\{V_1,\ldots ,V_n\}.$ We let $\{a_k,b_k\}$ with $1\le k\le \frac{1}{2}m(m-1)$ be an enumeration of all the possible couples, and we define $\mathcal{C }_k$ as the set containing the first $k$ couples in this enumeration.

Now let us prove the (if) part of the theorem. We consider some arbitrary preference profile $\mathcal{P }$ that neither contains a $\gamma$-configuration nor a $\delta$-configuration. Our argument is algorithmic in nature. We start from the trivial partition $\mathcal{X }^{\scriptscriptstyle (0)}$ of the voters, and then step by step refine this partition while working through $\frac{1}{2}m(m-1)$ phases. The $k$th such phase generates an ordered partition $\mathcal{X }^{\scriptscriptstyle (k)}=\langle X^{\scriptscriptstyle (k)}_1,\ldots ,X^{\scriptscriptstyle (k)}_p\rangle$ of the voters that satisfies the following two properties.

• (i) For $1\le j\le p-1,$ the union of parts $X^{\scriptscriptstyle (k)}_1,\ldots ,X^{\scriptscriptstyle (k)}_j$ is separated from the union of parts $X^{\scriptscriptstyle (k)}_{j+1},\ldots ,X^{\scriptscriptstyle (k)}_p$ by one of the couples in $\mathcal{C }_k.$

• (ii) For every couple in $\mathcal{C }_k,$ there is a $j$ with $1\le j\le p-1$ such that the couple separates the union of $X^{\scriptscriptstyle (k)}_1,\ldots ,X^{\scriptscriptstyle (k)}_j$ from the union of $X^{\scriptscriptstyle (k)}_{j+1},\ldots ,X^{\scriptscriptstyle (k)}_p.$

Note that property (ii) implies that every part $X^{\scriptscriptstyle (k)}_j$ is pure with respect to every couple in $\mathcal{C }_k.$ The following four lemmas summarize some useful combinatorial observations on the ordered partition $\mathcal{X }^{\scriptscriptstyle (k)}$ and how it relates to couple $\{a_{k+1},b_{k+1}\}.$

Lemma 7

At most one part in the ordered partition $\mathcal{X }^{\scriptscriptstyle (k)}$ is mixed with respect to couple $\{a_{k+1},b_{k+1}\}.$

proof

Suppose for the sake of contradiction that the parts $X^{\scriptscriptstyle (k)}_s$ and $X^{\scriptscriptstyle (k)}_t$ with $1\le s<t\le p$ both are mixed with respect to couple $\{a_{k+1},b_{k+1}\}.$ In other words, part $X^{\scriptscriptstyle (k)}_s$ contains a voter $V^{\prime }_1$ with $a_{k+1}\succ b_{k+1}$ and another voter $V^{\prime }_2$ with $b_{k+1}\succ a_{k+1},$ and part $X^{\scriptscriptstyle (k)}_t$ contains a voter $V^{\prime }_3$ with $a_{k+1}\succ b_{k+1}$ and another voter $V^{\prime }_4$ with $b_{k+1}\succ a_{k+1}.$

Property (i) yields the existence of a couple $\{x,y\}\in \mathcal{C }_k$ that separates the union of parts $X^{\scriptscriptstyle (k)}_1,\ldots ,X^{\scriptscriptstyle (k)}_s$ from the union of the parts $X^{\scriptscriptstyle (k)}_{s+1},\ldots ,X^{\scriptscriptstyle (k)}_p.$ In particular, this couple separates $X^{\scriptscriptstyle (k)}_s$ from $X^{\scriptscriptstyle (k)}_t.$ This implies that voters $V^{\prime }_1$ and $V^{\prime }_2$ agree on couple $\{x,y\}$ (say, with $x\succ y$), whereas voters $V^{\prime }_3$ and $V^{\prime }_4$ have the opposite ranking (say $y\succ x$). Then the four voters $V^{\prime }_1,\,V^{\prime }_2,\,V^{\prime }_3,$ and $V^{\prime }_4$ together with the four alternatives $a_{k+1},\,b_{k+1},\,x,$ and $y$ form a $\delta$-configuration; this yields the desired contradiction. $\square$

Lemma 8

Consider $s$ and $t$ with $2\le s<t\le p.$ If some voter $V^{\prime }_1$ in part $X^{\scriptscriptstyle (k)}_1$ ranks $a_{k+1}\succ b_{k+1}$ and if some voter $V^{\prime }_2$ in part $X^{\scriptscriptstyle (k)}_s$ ranks $b_{k+1}\succ a_{k+1},$ then every voter $V^{\prime }_3$ in part $X^{\scriptscriptstyle (k)}_t$ ranks $b_{k+1}\succ a_{k+1}.$

proof

Suppose for the sake of contradiction that voter $V^{\prime }_3$ ranks $a_{k+1}\succ b_{k+1}.$ Then couple $\{a_{k+1},b_{k+1}\}$ separates $V^{\prime }_2$ from $V^{\prime }_1$ and $V^{\prime }_3.$ Property (i) yields a couple $\{x,y\}\in \mathcal{C }_{k}$ that separates $X^{\scriptscriptstyle (k)}_1$ from $X^{\scriptscriptstyle (k)}_s\cup X^{\scriptscriptstyle (k)}_t;$ this couple separates $V^{\prime }_1$ from $V^{\prime }_2$ and $V^{\prime }_3.$ Property (i) yields also a couple $\{u,v\}\in \mathcal{C }_{k}$ that separates $X^{\scriptscriptstyle (k)}_t$ from $X^{\scriptscriptstyle (k)}_1\cup X^{\scriptscriptstyle (k)}_s;$ this couple separates $V^{\prime }_3$ from $V^{\prime }_1$ and $V^{\prime }_2.$

Then the three voters $V^{\prime }_1,\,V^{\prime }_2,$ and $V^{\prime }_3$ together with the six alternatives $a_{k+1}, b_{k+1},\, x,\,y,\,u,$ and $v$ form a $\gamma$-configuration; a contradiction. $\square$

The statement of the following lemma is symmetric to the statement of Lemma 8, and it can be proved by symmetric arguments.

Lemma 9

Consider $s$ and $t$ with $1\le s<t\le p-1.$ If some voter $V^{\prime }_2$ in part $X^{\scriptscriptstyle (k)}_t$ ranks $a_{k+1}\succ b_{k+1}$ and some voter $V^{\prime }_3$ in part $X^{\scriptscriptstyle (k)}_p$ ranks $b_{k+1}\succ a_{k+1},$ then every voter $V^{\prime }_1$ in part $X^{\scriptscriptstyle (k)}_s$ ranks $a_{k+1}\succ b_{k+1}.$ $\square$

Lemma 10

There exists an index $\ell$ with $1\le \ell \le p$ such that the couple $\{a_{k+1},b_{k+1}\}$ separates the union of parts $X^{\scriptscriptstyle (k)}_1,\ldots ,X^{\scriptscriptstyle (k)}_{\ell -1}$ from the union of parts $X^{\scriptscriptstyle (k)}_{\ell +1},\ldots ,X^{\scriptscriptstyle (k)}_p.$

proof

If $p=1$ or if all voters in the profile agree on the relative ranking of $a_{k+1}$ and $b_{k+1},$ the choice $\ell =1$ works. Hence we assume that $p\ge 2$ and that there are two voters who disagree on the ranking of $a_{k+1}$ and $b_{k+1}.$ By Lemma 7 the parts $X^{\scriptscriptstyle (k)}_1$ and $X^{\scriptscriptstyle (k)}_p$ cannot both be mixed with respect to $\{a_{k+1},b_{k+1}\}.$

If the first part $X^{\scriptscriptstyle (k)}_1$ is pure with respect to $\{a_{k+1},b_{k+1}\},$ we pick an arbitrary voter $V^{\prime }_1$ from $X^{\scriptscriptstyle (k)}_1.$ We choose $\ell$ as the smallest index for which $X^{\scriptscriptstyle (k)}_{\ell }$ contains some voter $V^{\prime }_2$ who ranks $a_{k+1}$ versus $b_{k+1}$ differently from voter $V^{\prime }_1.$ Then Lemma 8 yields that every voter $V^{\prime }_3$ in the parts $X^{\scriptscriptstyle (k)}_{\ell +1},\ldots ,X^{\scriptscriptstyle (k)}_p$ must rank $a_{k+1}$ versus $b_{k+1}$ differently from voter $V^{\prime }_1.$ Hence the chosen index $\ell$ has all the desired properties, and this case is closed. In the remaining case the last part $X^{\scriptscriptstyle (k)}_p$ is pure with respect to $\{a_{k+1},b_{k+1}\};$ this case can be settled in a symmetric fashion while using Lemma 9. $\square$

Now let us finally describe how to construct the ordered partition $\mathcal{X }^{\scriptscriptstyle (k+1)}$ in the $(k+1)$th phase. Our starting point is the ordered partition $\mathcal{X }^{\scriptscriptstyle (k)},$ and we determine an index $\ell$ as defined in Lemma 10. If part $X^{\scriptscriptstyle (k)}_{\ell }$ is pure with respect to $\{a_{k+1},b_{k+1}\},$ then we make the new partition $\mathcal{X }^{\scriptscriptstyle (k+1)}$ coincide with the old partition $\mathcal{X }^{\scriptscriptstyle (k)};$ properties (i) and (ii) are satisfied in $\mathcal{X }^{\scriptscriptstyle (k+1)}.$ If part $X^{\scriptscriptstyle (k)}_{\ell }$ is mixed with respect to $\{a_{k+1},b_{k+1}\},$ then we subdivide it into two parts $Y$ and $Z$ so that $\{a_{k+1},b_{k+1}\}$ separates the union of parts $X^{\scriptscriptstyle (k)}_1,\ldots ,X^{\scriptscriptstyle (k)}_{\ell -1}, Y$ from the union of parts $Z,X^{\scriptscriptstyle (k)}_{\ell +1},\ldots ,X^{\scriptscriptstyle (k)}_p.$ Then the resulting partition

$$\begin{aligned} \mathcal{X }^{\scriptscriptstyle (k+1)} ~=~ \langle X^{\scriptscriptstyle (k)}_1,\,\ldots ,\,X^{\scriptscriptstyle (k)}_{\ell -1},\,Y,\,Z,\,X^{\scriptscriptstyle (k)}_{\ell +1},\,\ldots ,\,X^{\scriptscriptstyle (k)}_p\rangle \end{aligned}$$

satisfies properties (i) and (ii) by construction.

We keep working like this and complete phase after phase. After the very last phase $k=\frac{1}{2}m(m-1)$ we generate the final ordered partition $\mathcal{X }^*~=~\langle X^*_1,\ldots ,X^*_q\rangle .$ We construct an ordering $\pi ^*$ of the voters that lists the voters in every part $X^*_j$ before all the voters in part $X^*_{j+1}$ ($1\le j\le q-1$). Property (ii) guarantees that every couple separates an initial piece of partition $\mathcal{X }^*$ from the complementary final piece, which implies that the ordering $\pi ^*$ for the voters in $\mathcal{P }$ is single-crossing. This completes the proof of Theorem 6.

We conclude this section with two comments on this proof. If $\mathcal{P }$ is a single-crossing profile where all voters have distinct preference orderings, then there are exactly two single-crossing orderings of the voters which are mirror images of each other. This follows directly from the last part of the proof of Theorem 6.

By property (i), every two consecutive parts $X^*_j$ and $X^*_{j+1}$ must be separated by one of the couples. Since there are $\frac{1}{2}m(m-1)$ distinct couples, there are at most $\frac{1}{2}m(m-1)+1$ parts in the final partition. This implies that a single-crossing preference profile contains at most $\frac{1}{2}m(m-1)+1$ voters with distinct preference orderings. Of course, this bound is already known from the connection between single-crossing profiles and weak Bruhat orders as indicated in Sect. 2.1.

4 The size of forbidden configurations

Throughout this short section, we speak of preference profiles with $m$ alternatives and $n$ voters as $m\times n$ configurations. Theorem 6 characterizes single-crossing preference profiles through certain forbidden $6\times 3$ and $4\times 4$ configurations. Are there perhaps other characterizations that work with smaller forbidden configurations? The following lemma shows that this is not the case, and hence our characterization uses the smallest possible forbidden configurations.

Lemma 11

Every characterization of single-crossing preference profiles through forbidden configurations must forbid

• (a) some $m\times n$ configuration with $m\ge 6$ and $n\ge 3$ and

• (b) some $m\times n$ configuration with $m\ge 4$ and $n\ge 4.$

proof

Consider an arbitrary characterization of single-crossing profiles with forbidden configurations $F_1,\ldots ,F_k.$ Consider the following $6\times 3$ configuration $C.$

$$\begin{aligned} \text{ Voter}~V_1:~ b\succ _1 a\succ _1 c\succ _1 d\succ _1 e\succ _1 f\\ \text{ Voter}~V_2:~ a\succ _2 b\succ _2 d\succ _2 c\succ _2 e\succ _2 f\\ \text{ Voter}~V_3:~ a\succ _3 b\succ _3 c\succ _3 d\succ _3 f\succ _3 e \end{aligned}$$

This profile contains a $\gamma$-configuration and thus is not single-crossing. If we remove any alternative from $C,$ the resulting $5\times 3$ configuration is single-crossing and cannot be forbidden. And if we remove any voter from $C,$ the resulting $6\times 2$ configuration is again single-crossing and again cannot be forbidden. Hence the only possibility for correctly recognizing $C$ as not single-crossing is by either forbidding $C$ itself or by forbidding appropriate larger configurations that contain $C.$ This proves (a). The proof of (b) is based on the following $4\times 4$ configuration $C^{\prime }$ which contains a $\delta$-configuration.

$$\begin{aligned} \text{ Voter}~V_1:~ a\succ _1 b\succ _1 c\succ _1 d\\ \text{ Voter}~V_2:~ a\succ _2 b\succ _2 d\succ _2 c\\ \text{ Voter}~V_3:~ b\succ _3 a\succ _3 c\succ _3 d\\ \text{ Voter}~V_4:~ b\succ _4 a\succ _4 d\succ _4 c \end{aligned}$$

Since the argument is analogous to the one in (a), we omit the details. $\square$

5 Conclusions

In this final section, we briefly discuss the algorithmic problem of recognizing single-crossing profiles with $n$ voters and $m$ alternatives. Elkind et al. (2012) showed that this problem is polynomial-time solvable. A straightforward implementation of their algorithm works in $O(n^2 m^2)$ time.

The arguments in Sect. 3 implicitly give an $O(nm^2)$ algorithm which decides whether a given voter profile is single-crossing and, if so, computes a single-crossing ordering. To show an extremely simple connection between single-crossing orderings and the so-called consecutive ones matrix property, we sketch an alternative way of recognizing single-crossing profiles by utilizing the PQ-tree algorithm of Booth and Lueker (1976). The algorithm was designed to recognize, inter alia, consecutive ones matrices. A 0-1-matrix has the consecutive ones property, if its columns can be permuted such that the ones in each row are consecutive (and hence form an interval).

Consider an arbitrary preference profile $\mathcal{P }$ and transform it into a corresponding 0-1-matrix $M(\mathcal{P })$ in the following way. For each voter, the matrix $M(\mathcal{P })$ contains a corresponding column. For each ordered pair $\langle a,b\rangle$ of alternatives, matrix $M(\mathcal{P })$ has a corresponding row with value $1$ at column $j$ if voter $j$ prefers alternative $a$ to alternative $b$ and value $0$ otherwise. In total, $M(\mathcal{P })$ has $n$ columns and $m(m-1)$ rows. As one can easily verify, each consecutive ones ordering of columns corresponds to a single-crossing ordering of the voters in the original profile.

The PQ-tree algorithm by Booth and Lueker (1976) solves the consecutive ones matrix problem in $O(x+y+z)$ time, where $x$ and $y$ are the number of columns and rows, and $z$ is the total number of 1s in the matrix. Hence, single-crossing profiles can be recognized in $O(m^2+n+nm^2)=O(nm^2)$ time.