Sorting out single-crossing preferences on networks

Abstract

We extend the single-crossing property to tree networks to facilitate its application in network games. It is equivalent to intermediate preferences and order restriction (also extended to networks). Moreover, to facilitate broader applications in real world cases and simulations, we develop algorithms that answer the following two questions. Given a preference profile, can we construct a tree graph that supports single-crossing? Given a set of alternatives, can we generate single-crossing preference profiles with associated tree graphs?

1 Introduction

Single-crossing property is widely used for obtaining voting equilibrium in economic models. It assures that voters’ preferences can be linearly ordered, so that their best choices correlate with this order. Many models of public decision assume single-crossing utility functions, for example, Roberts (1977), Ellickson (1979), Epple et al. (1984), Epple and Romer (1992), Epple et al. (2006). Single-crossing is also implied in local public good economies by the structure of utility function and tax scheme; see, for example, Greenberg and Weber (1986) and Konishi et al. (1998). There are properties in the literature that assume similar versions of regularity among individual preferences. Grandmont (1978) proposes “intermediate preferences,” which requires that individuals ordered in between two others with the same preference should also share the same preference. Rothstein (1990) proposes “order restriction” which requires that individuals with similar preferences are linearly ordered together (it is shown by Gans and Smart 1996 to be equivalent to single-crossing). Recent studies provide further understanding of the single-crossing property. Saporiti and Tohmé (2006) find that single-crossing preferences support social choice rules that are immune to strategic manipulations (see also Saporiti 2009). Barberà and Moreno (2011) develop a more general property, “top monotonicity,” which is a common root for both single-crossing and single-peaked properties. Quah and Strulovici (2012) develop conditions under which an aggregated function, for example, integrating utility over the measure of agents, of single-crossing functions is also single-crossing. Donder (2013) investigates conditions where a global Condorcet winner exists when single-crossing is satisfied within separate voter groups.

These preference properties are also instrumental in attaining core allocations when players form coalitions to provide public goods on networks. Demange (1994) and Kung (2006, 2010) are the first applications of preference properties on network graphs. They extend, in games where public goods are provided on a network, results of the network game in Le Breton et al. (1992) and the local public good game in Konishi et al. (1997, 1998). Considerations of public goods bring new elements into the growing literature of network formation (for example, Jackson and Wolinsky 1996; Jackson and Watts 2002). Broader applications of graph-based preference properties are necessary for equilibrium of public good decisions on networks. For this purpose, preference properties based on linear orders need to be generalized to tree networks. Tree graphs allow a multi-dimensional structure to link individuals.

In this paper, we extend single-crossing, intermediate preferences and order restriction to tree graphs, and show that they are all equivalent. To further improve the applicability of single-crossing in real world cases and simulations, we provide algorithms to answer the following two questions: First, suppose we have a preference profile from a real situation, but not the underlying linear order or tree network. Can we test whether a profile is single-crossing, and construct the tree that makes it single-crossing? Second, we may want to examine the performance of a decision rule or a solution for a situation. The set of alternatives is known for the situation but the decision rule or solution should be evaluated before potential individuals embody actual preferences. Can we obtain a comprehensive list of possible singe-crossing preferences? For example, a test on the efficiency performance of the core would be carried out in simulations by calculating welfare over all possible single-crossing profiles.

Section 2 defines the above mentioned preference properties on tree graphs and show that they are equivalent. Section 3 presents two algorithms. The first sorts out a tree graph that supports single-crossing for a given preference profile. The second generates single-crossing preference profiles for a given set of alternatives. Section 4 concludes.

2 Single-crossing on networks

We utilize “path orders” on a tree to extend single-crossing, intermediate preferences and order restriction on to tree graphs. This is the order we get by moving from one node along a path to another node. Preference regularities are checked along every path order on a tree. $X$ is the finite set of alternatives, $N$ is the finite set of individuals, and there is a tree graph $G$ on $N$ that links individuals as nodes. Each individual $i\in N$ has a preference relation $\succeq _{i}$ (transitive and complete) over alternatives in $X$. Let $\succeq$ denote a preference profile $\left( \succeq _{i}\right) _{i\in N}$. A path from $i$ to $j$ on $G$, denoted by $p\left( ij\right)$, is the collection of nodes connected from $i$ to $j$. The path order $>_{ij}$ on $G$ is the order over nodes on $p(ij)$ such that $m>_{ij}n$ if $m$ is closer to $i$ than $n$. (Definitions of these properties over linear orders are collected in footnote 1.¹ Notice that they are special cases of our definitions when the tree is linear.²)

Definition 1

Preference profile $\succeq$ satisfies single-crossing on $G$, if for any $i,j\in G$, there is a linear order $>_{X}$ on $X$, such that for all individuals $m,n\in p\left( ij\right)$ with $m>_{ij}n$ and any pair $x,y\in X$ with $x>_{X}y$, we have that (i) $x\succeq _{m}y$ implies $x\succeq _{n}y$, and (ii) $x\succ _{m}y$ implies $x\succ _{n}y$.

Definition 2

Preference profile $\succeq$ is intermediate on $G$, if for any pair $x,y\in X$, any two individuals $i,j\in G$, and any $k,m,n\in p\left( ij\right)$ with $k>_{ij}m>_{ij}n$, we have that (i) [$x\succ _{k}y$ and $x\succ _{n}y$] implies $x\succ _{m}y$, and (ii) [$x\succeq _{k}y$ and $x\succeq _{n}y$] implies $x\succeq _{m}y$.

Definition 3

Preference profile $\succeq$ satisfies order restriction on $G$ if for any path order $>_{ij}$ and any pair $x,y\in X$, we have either

• (i) $\left\{ l\in p\left( ij\right) \mid x\succ _{l}y\right\} >_{ij}\left\{ l\in p\left( ij\right) \mid x\sim _{l}y\right\} >_{ij}\left\{ l\in p\left( ij\right) \mid y\succ _{l}x\right\}$, or

• (ii) $\left\{ l\in p\left( ij\right) \mid y\succ _{l}x\right\} >_{ij}\left\{ l\in p\left( ij\right) \mid x\sim _{l}y\right\} >_{ij}\left\{ l\in p\left( ij\right) \mid x\succ _{l}y\right\}$.

These properties all describe certain degrees of similarity in individuals’ preferences that can be ordered.³ Single-crossing says that individual preferences follow an order on the alternatives that matches the order of individuals. Notice that individuals are ordered on paths, and the order of alternatives $>_{X}$ for each path of individuals $p(ij)$ can differ.⁴ Intermediate preferences requires that anyone ordered in between two individuals with the same preference would also share the same preference. Order restriction requires that individuals with the same preference would be ordered adjacently. Actually, they are three ways of describing the same property. This similarity in preferences can also be described without referring to an order, as shown in the following property, called connected group.

Definition 4

Preference profile $\succeq$ satisfies connected group on a tree $G$ if for any pair $x$ and $y$ , each of $\left\{ i\mid x\succ _{i}y\right\}$ and $\left\{ i\mid x\succeq _{i}y\right\}$ is a connected set on $G$.⁵

Proposition 1

Single crossing, intermediate preference, order restriction, and connected group are equivalent on $G$.

Proof

We proceed by showing that connected group is equivalent to each of the other three.

• (i) (Order restriction and connected group are equivalent.) Suppose profile $\succeq$ violates connected group for pair $x$ and $y$. If $\left\{ i\mid x\succeq _{i}y\right\}$ is not connected, then we can find $k,n\in \left\{ i\mid x\succeq _{i}y\right\}$, $m\in p\left( kn\right)$, and $y\succ _{m}x$ . This violates order restriction on path order $>_{kn}$. If $\left\{ i\mid x\succ _{i}y\right\}$ is not connected, then we can find $k,n\in \left\{ i\mid x\succ _{i}y\right\}$, $m\in p\left( kn\right)$, and $y\succeq _{m}x$ . This violates order restriction on $>_{kn}$. Next, suppose $\succeq$ violates order restriction for path $>_{ij}$ and pair $x,y$ in one of the following four ways: (a) There are $k>_{ij}m>_{ij}n$ such that $x\succ _{k}y$ and $x\succ _{n}y$ but $y\succeq _{m}x$. This means $\left\{ i\mid x\succ _{i}y\right\}$ is not connected. (b) There are $k>_{ij}m>_{ij}n$ such that $x\sim _{k}y$ and $x\sim _{n}y$ but $x\succ _{m}y$ (or $y\succ _{m}x$ respectively). Then $\left\{ i\mid y\succeq _{i}x\right\}$ (or $\left\{ i\mid x\succeq _{i}y\right\}$ respectively) is not connected. (c) There are $k>_{ij}m>_{ij}n$ such that $y\succ _{k}x$ and $y\succ _{n}x$ but $x\succeq _{m}y$. This means $\left\{ i\mid y\succ _{i}x\right\}$ is not connected. (d) The three sets $\left\{ l\in p\left( ij\right) \mid x\succ _{l}y\right\}$, $\left\{ l\in p\left( ij\right) \mid x\sim _{l}y\right\}$ and $\left\{ l\in p\left( ij\right) \mid y\succ _{l}x\right\}$ are each ranked together, but $\left\{ l\in p\left( ij\right) \mid x\succ _{l}y\right\}$ (or $\left\{ l\in p\left( ij\right) \mid y\succ _{l}x\right\}$ respectively) is ranked in the middle of the three. Then $\left\{ i\mid y\succeq _{i}x\right\}$ (or $\left\{ i\mid x\succeq _{i}y\right\}$ respectively) is not connected.

• (ii) (Single crossing and connected group are equivalent.) Suppose profile $\succeq$ satisfies single-crossing. Take $k,n\in \left\{ i\mid x\succ _{i}y\right\}$ and $m$ such that $k>_{kn}m>_{kn}n$, we have, on the associated order $>_{X}$, either (a) $x>_{X}y$ and $x\succ _{k}y$, which implies $x\succ _{m}y$, or (b) $y>_{X}x$ and $\sim \left( y\succeq _{n}x\right)$, which implies $\sim \left( y\succeq _{m}x\right)$ because $m>_{kn}n$. So, $m\in \left\{ i\mid x\succ _{i}y\right\}$ also and $\left\{ i\mid x\succ _{i}y\right\}$ is connected. Similarly, take $k,n\in \left\{ i\mid x\succeq _{i}y\right\}$ and $m$ such that $k>_{kn}m>_{kn}n$, we have, on the associated order $>_{X}$, either (a) $x>_{X}y$ and $x\succeq _{k}y$, which implies $x\succeq _{m}y$, or (b) $y>_{X}x$ and $\sim \left( y\succ _{n}x\right)$, which implies $\sim ( y\succ _{m}x)$. So, $m\in \left\{ i\mid x\succeq _{i}y\right\}$ also and $\left\{ i\mid x\succeq _{i}y\right\}$ is connected. Next, suppose profile $\succeq$ satisfies connected group (we will use order restriction since they are equivalent). We determine the order $>_{X}$ on $X$ for each path $p\left( ij\right)$ by taking the reverse preference order of $i$ and, in case of $i$’s indifference, taking the preferences of $j$. Define $>_{X}$ as follows: (Notice that such $>_{X}$ is acyclic since it follows $i$ ’s preferences together with $j$’s preferences where $i$ is indifferent). Let $y>_{X}x$ if (a) $x\succ _{i}y$, or (b) $x\sim _{i}y$ and $y\succ _{j}x$. Let $x>_{X}y$ if (c) $y\succ _{i}x$, or (d) $x\sim _{i}y$ and $x\succ _{j}y$ , or (e) $x\sim _{i}y$ and $x\sim _{i}y$. We then verify single-crossing. When $y>_{X}x$ (above cases a and b), because of order restriction, we have $\left\{ l\in p\left( ij\right) \mid x\succ _{l}y\right\} >_{ij}\left\{ l\in p\left( ij\right) \mid x\sim _{l}y\right\} >_{ij}\left\{ l\in p\left( ij\right) \mid y\succ _{l}x\right\}$ since $\dot{i}>_{ij}j$; some of these sets may be empty though. Therefore, if $m>_{ij}n$, then $n$’s preferences follows $m$’s in that $y\succ _{m}x$ implies $y\succ _{n}x$, and $y\succeq _{m}x$ implies $y\succeq _{n}x$. When $x>_{X}y$ (above cases c, d, and e), we have $\left\{ l\in p\left( ij\right) \mid y\succ _{l}x\right\} >_{ij}\left\{ l\in p\left( ij\right) \mid x\sim _{l}y\right\} >_{ij}\left\{ l\in p\left( ij\right) \mid x\succ _{l}y\right\}$ since $\dot{i}>_{ij}j$; some of these sets may be empty though. Therefore, if $m>_{ij}n$, then $n$’s preferences follow $m$’s in that $x\succ _{m}y$ implies $x\succ _{n}y$, and $x\succeq _{m}y$ implies $x\succeq _{n}y$.

• (iii) (Intermediate preferences and connected group are equivalent.) Suppose profile $\succeq$ is intermediate, then for any two individuals $k,n\in \left\{ i\mid x\succ _{i}y\right\}$, take $>_{kn}$, this means for all $m$ on $p\left( kn\right)$, we have $x\succ _{m}y$ for any pair $x$ and $y$, and thus $m\in \left\{ i\mid x\succ _{i}y\right\}$ and $\left\{ i\mid x\succ _{i}y\right\}$ is a connected set. Similarly, $\left\{ i\mid x\succeq _{i}y\right\}$ is also a connected set. Next, suppose profile $\succeq$ is not intermediate. (a) Suppose there are $k>_{ij}m>_{ij}n$ on path $p\left( ij\right)$, with $x\succ _{k}y$ and $x\succ _{n}y$, but $y\succeq _{m}x$. Thus, $k,n\in \left\{ i\mid x\succ _{i}y\right\}$, but $m$ does not. Since there is only one path on $G$ connecting $k$ and $n$, this means $\left\{ i\mid x\succ _{i}y\right\}$ is not a connected set. (b) Suppose there are $k>_{ij}m>_{ij}n$, on $p\left( ij\right)$, with $x\succeq _{k}y$ and $x\succeq _{n}y$, but $y\succ _{m}x$. Thus, $k,n\in \left\{ i\mid x\succeq _{i}y\right\}$, but $m$ does not, and $\left\{ i\mid x\succeq _{i}y\right\}$ is not a connected set. $\square$

3 Sorting out single-crossing preferences

We propose to make single-crossing property more operational than just being an assumption. In Sect. 3.1, we consider a preference profile without a preexisting order or tree linking them together. This profile may be single-crossing on a particular tree graph, or on none. An algorithm is provided that can sort out the tree graph on which the preference profile is single-crossing, and also determine if it is not single-crossing on any tree. In Sect. 3.2, we start with a set of alternatives. There potentially are single-crossing preference profiles over these alternatives. An algorithm is provided that generates single-crossing preference profiles systematically by linking grid points on a multi-dimensional cube.

3.1 Constructing the tree graph for a preference profile

For a preference profile $\succeq$ over set $X=\left\{ x_{1},...,x_{\left| X\right| }\right\}$, we can sort out the tree graph and check if it is single-crossing. There are $\left| X\right| \left( \left| X\right| -1\right) /2$ pairs of alternatives from set $X$. Through out the paper, we label a pair $x_{m}x_{n}$ so that $m<n$. Label these pairs from $p_{1}$ to $p_{\left| X\right| \left( \left| X\right| -1\right) /2}$ in any order. Suppose $p_{k}=x_{m}x_{n}$, let $C^{+}\left( p_{k}\right) =\left\{ i\mid x_{m}\succ _{i}x_{n}\right\}$, $C^{0}\left( p_{k}\right) =\left\{ i\mid x_{m}\sim _{i}x_{n}\right\}$ and $C^{-}\left( p_{k}\right) =\left\{ i\mid x_{n}\succ _{i}x_{m}\right\}$.

First, start with pair $p_{1}$ and separate individuals into “cells” $C^{+}\left( p_{1}\right)$, $C^{0}\left( p_{1}\right)$ and $C^{-}\left( p_{1}\right)$. A cell is a subset of individuals. We will use cells as nodes of the tree graph. Link nonempty cells as $C^{+}\left( p_{1}\right) -C^{0}\left( p_{1}\right) -C^{-}\left( p_{1}\right)$; modify the links accordingly if some of them are empty. Denote the resulting graph $G\left( 1\right)$ and let $P\left( 1\right) =\left\{ p_{1}\right\}$. $G\left( 1\right)$ is a tree composed of cells (not individuals) as nodes, and each cell is a subset of individuals with the same preferences over $P\left( 1\right)$.

We say that tree graph $G\left( k\right)$, composed of cells, is $P\left( k\right)$ -connected if for all pairs $x_{m}x_{n}\in P\left( k\right)$, each of the sets $\{ c\in G( k) |x_{m}\succ _{i}x_{n},\text { for all }i\in c\}$, $\{ c\in G( k)| x_{m}\succeq _{i}x_{n},\text { for all }i\in c\}$, $\{ c\in G( k) |x_{n}\succ _{i}x_{m},\text { for all }i\in c\}$, and $\{ c\in G( k) |x_{n}\succeq _{i}x_{m},\text { for all }i\in c\}$ is a connected set on $G( k)$. Obviously, $G( 1)$ is $P( 1)$-connected.

The following notation will be used: $c\in G\left( k\right)$ means that cell $c$ is a node on tree $G\left( k\right)$, and $c\cap C^{+}\left( p_{k}\right)$ is the intersection of cell $c$ and $C^{+}\left( p_{k}\right)$ as a set of individuals. $G\left( k\right) \mid _{C^{+}\left( p_{k+1}\right) }$ is the subgraph of tree $G\left( k\right)$ based on $C^{+}\left( p_{k+1}\right)$. It consist of cells $c$ as nodes such that $c\cap C^{+}\left( p_{k+1}\right) \ne \varnothing$, with all cells $c\cap C^{+}\left( p_{k+1}\right) =\varnothing$ deleted from $G\left( k\right)$. (So, if two such cells, where $c\cap C^{+}\left( p_{k+1}\right) \ne \varnothing$, are linked on the original tree $G\left( k\right)$ across another cell not in $C^{+}\left( p_{k+1}\right)$, then they are not connected on the subgraph $G\left( k\right) \mid _{C^{+}\left( p_{k+1}\right) }$.) $G\left( k\right) \backslash C^{+}\left( p_{k+1}\right)$ is the subgraph obtained by deleting all individuals $i\in C^{+}\left( p_{k+1}\right)$ from cells, and delete the whole cell if it becomes empty.

The rest of the tree is constructed recursively: Suppose we have worked with $k$ pairs in $P\left( k\right)$ and obtained a tree $G\left( k\right)$, which is $P\left( k\right) \,$-connected. Take the next pair $p_{k+1}$.

• (i) If $C^{+}\left( p_{k+1}\right) =\varnothing$, then let $G^{\prime }\left( k\right) =G\left( k\right)$ and go to step ii.

  Cells $c$ such that $c\cap C^{+}\left( p_{k+1}\right) \ne \varnothing$ must be connected together on the subgraph $G\left( k\right) \mid _{C^{+}\left( p_{k+1}\right) }$, otherwise single-crossing (connected group) is violated. If every cell $c\in G\left( k\right)$ is such that either $c\subseteq C^{+}\left( p_{k+1}\right)$ or $c\subseteq N\backslash C^{+}\left( p_{k+1}\right)$, no modification is need. Let $G^{\prime }\left( k\right) =G\left( k\right)$ and go to step ii.

• (i.a) Suppose only one cell $c\in G\left( k\right)$ is such that $c\cap C^{+}\left( p_{k+1}\right) \ne \varnothing$ and $c\backslash C^{+}\left( p_{k+1}\right) \ne \varnothing$ (see Fig. 1). Then we split cell $c$ into $c^{+}=$ $c\cap C^{+}\left( p_{k+1}\right)$ and $c^{0}=c\backslash C^{+}\left( p_{k+1}\right)$ with link $l^{+}{}_{k+1}$ in between. Denote this new graph $G^{\prime }\left( k\right)$ (see Fig. 2). Actually, there cannot be more than one such cell as shown in the following lemma.

Fig. 1

Set $C^{+} (p_{k+1})$ separates $G(k)$

Fig. 2

Split $c$ into $c^{+}$ and $c^{0}$

Lemma 1

If profile $\succeq$ is single-crossing, then there cannot be more than one cell $c\in G\left( k\right)$ such that $c\cap C^{+}\left( p_{k+1}\right) \ne \varnothing$ and $c\backslash C^{+}\left( p_{k+1}\right) \ne \varnothing$.

Proof

Suppose there are two such cells $c$ and $c^{\prime }$. Since $C^{+}\left( p_{k+1}\right)$ is connected, $c\backslash C^{+}\left( p_{k+1}\right)$ and $c^{\prime }\backslash C^{+}\left( p_{k+1}\right)$ have to be disjoint to each other on graph $G\left( k\right) \backslash C^{+}\left( p_{k+1}\right)$, otherwise there is a cycle. Furthermore, $c\backslash C^{+}\left( p_{k+1}\right) ,c^{\prime }\backslash C^{+}\left( p_{k+1}\right) \subset C^{0}\left( p_{k+1}\right) \cup C^{-}\left( p_{k+1}\right)$. And $C^{0}\left( p_{k+1}\right) \cup C^{-}\left( p_{k+1}\right)$ on graph $G\left( k\right) \backslash C^{+}\left( p_{k+1}\right)$ has to be a connected set; a contradiction. $\square$

• (ii) Next we work on $G^{\prime }\left( k\right) \backslash C^{+}\left( p_{k+1}\right)$. If $C^{0}\left( p_{k+1}\right) =\varnothing$, let $G\left( k+1\right) =G^{\prime }\left( k\right)$ and go to step iii. Cells $c$ such that $c\cap C^{0}\left( p_{k+1}\right) \ne \varnothing$ must be connected on $G^{\prime }\left( k\right) \mid _{C^{0}\left( p_{k+1}\right) }$ , otherwise single-crossing is violated. And there is one and only one cell $c\in C^{0}\left( p_{k+1}\right)$ linked directly to $G^{\prime }\left( k\right) \mid _{C^{+}\left( p_{k+1}\right) }$, otherwise there is a cycle. If every cell $c\in G^{\prime }\left( k\right) \backslash C^{+}\left( p_{k+1}\right)$ is such that $c\subseteq C^{0}\left( p_{k+1}\right)$ or $c\subseteq N\backslash \left( C^{+}\left( p_{k+1}\right) \cup C^{0}\left( p_{k+1}\right) \right)$, no modification is needed. Let $G\left( k+1\right) =G^{\prime }\left( k\right)$ and go to step iii.

• (ii.a) Suppose there is one cell $d\in G^{\prime }\left( k\right) \backslash C^{+}\left( p_{k+1}\right)$ such that $d\cap C^{0}\left( p_{k+1}\right) \ne \varnothing$ and $d\backslash C^{0}\left( p_{k+1}\right) \ne \varnothing$, split cell $d$ into $d^{0}=$ $d\cap C^{0}\left( p_{k+1}\right)$ and $d^{-}=d\backslash C^{0}\left( p_{k+1}\right)$, with a link $l^{-}{}_{k+1}$ in between. Denote this new tree $G\left( k+1\right)$. Lemma 2 follows Lemma 1.

Lemma 2

If profile $\succeq$ is single-crossing, then there cannot be more than one cell $c\in G^{\prime }\left( k\right) \backslash C^{+}\left( p_{k+1}\right)$ such that $c\cap C^{0}\left( p_{k+1}\right) \ne \varnothing$ and $c\backslash C^{0}\left( p_{k+1}\right) \ne \varnothing$.

• (iii) For all remaining cells on the tree, $c\in G\left( k+1\right) \backslash \left( C^{+}\left( p_{k+1}\right) \cup C^{0}\left( p_{k+1}\right) \right)$, check that all cells $c\subset C^{-}\left( p_{k+1}\right)$ and they are connected on $G\left( k+1\right) \mid _{C^{-}\left( p_{k+1}\right) }$, otherwise single-crossing is violated. And there is one and only one cell $c\in C^{-}\left( p_{k+1}\right)$ linked directly to $G\left( k+1\right) \backslash C^{-}\left( p_{k+1}\right)$, otherwise there is a cycle (notice that $G\left( k+1\right) \mid _{C^{-}\left( p_{k+1}\right) }$ is not linked directly to $G\left( k+1\right) \mid _{C^{+}\left( p_{k+1}\right) }$ unless $C^{0}\left( p_{k+1}\right) =\varnothing$). Let $P\left( k+1\right) =P\left( k\right) \cup p_{k+1}$.

Lemma 3

$G\left( k+1\right)$ is $P\left( k+1\right)$-connected.

Proof

For all pairs $x_{m}x_{n}\in P\left( k\right)$, $G\left( k+1\right)$ is obtained from $G\left( k\right)$ by splitting cells, so if the set of cells $\left\{ c\in G\left( k\right) |x_{m}\succ _{i}x_{n}\text {, for all }i\in c\right\}$ is connected in $G\left( k\right)$, $\left\{ c\in G\left( k+1\right) |x_{m}\succ _{i}x_{n}\text {, for all } i\in c\right\}$ is also connected in $G\left( k+1\right)$. For the new pair $p_{k+1}\in P\left( k+1\right) \backslash P\left( k\right)$, the construction assures that $C^{+}\left( p_{k+1}\right)$, $C^{0}\left( p_{k+1}\right)$ and $C^{-}\left( p_{k+1}\right)$ each contains connected cells on $G\left( k+1\right)$, and are linked properly. $\square$

Therefore, when we finish with all pairs down to $p_{\left| X\right| \left( \left| X\right| -1\right) /2}$, the graph $G\left( \left| X\right| \left( \left| X\right| -1\right) /2\right)$ is a tree, and for all pairs $x_{m}x_{n}\in P\left( k\right)$, each of $\big \{ c\in G\big ( \left| X\right| \left( \left| X\right| -1\right) /2\big ) |x_{m}\succ _{i}x_{n},\text { for all }i\in c\big \}$ and $\big \{ c\in G\left( \left| X\right| \left( \left| X\right| -1\right) /2\right) \mid x_{m}\succeq _{i}x_{n},\text { for all }i\in c\big \}$ is a connected set.

3.2 Generating single-crossing preference profiles

Given a set of alternatives $X$, we can generate a preference profile that is single-crossing by linking the grid points of a multi-dimensional cube. Denote a pair of alternatives $x_{m}x_{n}=\chi _{mn}$. Let $\chi$ be a coordinate system whose coordinates represent the $\left| X\right| \left( \left| X\right| -1\right) /2$ pairs from $X$. Pairs are ordered lexicographically as $( \chi _{12},\chi _{13},...,\chi _{( \left| X\right| -1) \left| X\right| }) =\chi$. Each coordinate can take a value from $\chi _{mn}\in \{ 1, 0, -1\}$ . Let $\chi _{mn}=1$ represent $x_{m}\succ x_{n}$, $\chi _{mn}=1$ represent $x_{m}\sim x_{n}$, and $\chi _{mn}=-1$ represent $x_{n}\succ x_{m}$. Therefore, $\chi \in \{ -1,0,1\} ^{\left| X\right| ( \left| X\right| -1) /2}$, and there are $3^{\left| X\right| ( \left| X\right| -1) /2}$ grid points of such $\chi$ values which constitute a $(\left| X\right| -1)!$ dimensional cube. Each grid point represents a potential ranking of alternatives. Transitivity requires that for any numbers $n_{1},...,n_{k}\in \{ 1,...\left| X\right| \}$, ranked as $n_{1}>...>n_{k}$,

• (i) $\chi _{n_{1}n_{k}}=0$, if $\chi _{n_{h}n_{h+1}}=0$ for all $h=1,...,k-1$.

• (ii) $\chi _{n_{1}n_{k}}=1$, if $\chi _{n_{h}n_{h+1}}\ge 0$ for all $h=1,...,k-1$, and $\chi _{n_{h}n_{h+1}}=1$ for some $h=1,...,k-1$.

• (iii) $\chi _{n_{1}n_{k}}=-1$, if $\chi _{n_{h}n_{h+1}}\le 0$ for all $h=1,...,k-1$, and $\chi _{n_{h}n_{h+1}}=-1$ for some $h=1,...,k-1$.

Let $\hat{C}$ denote the set of grid points satisfying transitivity. Each grid point in $\hat{C}$ represents a preference ordering. A tree graph can be constructed by linking points in $\hat{C}$ in the following way: Two links $l^{+} (\chi _{mn})$ and $l^{-}( \chi _{mn})$ are allowed alone each dimension $\chi _{mn}$, and can only be used between two points which differs only in the values of $\chi _{mn}$. For example, coordinate $\chi _{mn}$ takes value in $\{ 1, 0, -1\}$. Link $l^{+}( \chi _{mn})$ can be put between two points $( .,...,\chi _{mn}=1,...,.)$ and $( .,...,\chi _{mn}=0,...,.)$, indicating $\chi _{mn}$ changing between $1$ and $0$ . Link $l^{-}( \chi _{mn})$ can be put between two points $( .,...,\chi _{mn}=0,...,.)$ and $( .,...,\chi _{mn}=-1,...,.)$, indicating $\chi _{mn}$ changing between $0$ and $-1$. The links can also be used together as $l^{+}\left( \chi _{mn}\right) l^{-}\left( \chi _{mn}\right)$, indicating $\chi _{mn}$ changing between $1$ and $-1$, linking $\left( .,...,\chi _{mn}=1,...,.\right)$ and $\left( .,...,\chi _{mn}=-1,...,.\right)$ together skipping $\chi _{mn}=0$. Any connected graph $\hat{G}$ composed of a subset of such $2^{\left| X\right| \left( \left| X\right| -1\right) /2}$ links over $\hat{C }$ is a tree with single-crossing preferences.

Proposition 2

Graph $\hat{G}$ is a tree that supports a single-crossing preference profile.

Proof

First, on $\hat{G}$, any change in the value of $\chi _{mn}$ between $0$ and $1$ happens only on link $l^{+}\left( \chi _{mn}\right)$, and there is only one such link $l^{+}\left( \chi _{mn}\right)$. Suppose $\hat{G}$ is not a tree, and without loss of generality assume that there is a cycle starting from point $\chi ^{1}$, $\chi _{mn}^{1}=1$, along link $l^{+}\left( \chi _{mn}\right)$. This means that along this cycle, there is point a point $\chi ^{\prime }$ with $\chi _{mn}^{^{\prime }}=0$ or $-1$. And there is another point $\chi ^{\prime \prime }$ with $\chi _{mn}^{^{\prime \prime }}$ has to change back to $1$. This is prohibited since there is only one link $l^{+}\left( \chi _{mn}\right)$. Therefore, $\hat{G}$ is a tree.

Apparently, when $\{ \chi \in \hat{G}\mid x_{mn}=0\}$ is not empty, link $l^{+}(\chi _{mn})$ separates $\hat{G}$ into two subsets: $\{ \chi \in \hat{G}\mid x_{mn}=1\}$ representing preference $x_{m}\succ x_{n}$, and $\{ \chi \in \hat{G}\mid x_{mn}=0, -1\}$ representing preference $x_{n}\succeq x_{m}$. Set $\{ \chi \in \hat{G}\mid x_{mn}=1\}$ is a connected set on $\hat{G }$, since there is only one link $l^{+}( \chi _{mn})$ connecting it to $\{ \chi \in \hat{G}\mid x_{mn}=0,-1\}$ and $\hat{G}$ is a connect graph. Similarly, link $l^{-}( \chi _{mn})$ separates $\hat{G}$ into two connected subsets: $\{ \chi \in \hat{G}\mid x_{mn}=1,0\}$ meaning $x_{m}\succeq x_{n}$, and $\{ \chi \in \hat{G}\mid x_{mn}=-1\}$ meaning $x_{n}\succ x_{m}$. And set $\{ \chi \in \hat{G}\mid x_{mn}=1,0\}$ is a connected set on $\hat{G}$. When $\{ \chi \in \hat{G}\mid x_{mn}=0\} =\varnothing$, link $l^{+}( \chi _{mn}) l^{-}( \chi _{mn})$ separates $\hat{G}$ in to two sets $\{ \chi \in \hat{G}\mid x_{mn}=1\}$, and $\{ \chi \in \hat{G}\mid x_{mn}=-1\}$, each of which is a connected set on $\hat{G}$. In the above cases, we conclude that the points on $\hat{G}$ represent a single-crossing preference profile. $\square$

Example

We will illustrate this cube construction with an example of three alternatives $\left\{ x,y,z\right\}$ (see Fig. 3). Three coordinates of pairs are $\left( xy, xz, yz\right)$. To make it simple, we eliminate indifference of $xy$ and of $xz$, thus each of pairs $xy$ and $xz$ takes value in $\left\{ -1,1\right\}$, and $yz$ takes value in $\left\{ -1,0,1\right\}$. We have twelve grid points. Set $\hat{C}$ includes eight solid grid points that satisfy transitivity (hollow grid points do not satisfy transitivity). We have four links,  $l_{xy}^{+}l_{xy}^{-}$, $l_{xz}^{+}l_{xz}^{-}$, $l_{yz}^{+}$ and $l_{yz}^{-}$, to be used in constructing the tree graph. An example of a linear tree is shown in Figure 3 with bold dashed lines representing these links. This tree contains four points representing the following preferences profile:

$$\begin{aligned} \begin{array}{c} \left( -1,1,1\right) \\ y\succ x\succ z \end{array} - \begin{array}{c} \left( 1,1,1\right) \\ x\succ y\succ z \end{array} - \begin{array}{c} \left( 1,1,0\right) \\ x\succ y\sim z \end{array} - \begin{array}{c} \left( 1,1,-1\right) \\ x\succ z\succ y \end{array} - \begin{array}{c} \left( 1,-1,-1\right) \\ z\succ x\succ y \end{array} \end{aligned}$$

Apparently, this profile is single-crossing.

Fig. 3

A linear tree with four links

4 Concluding remarks

Single-crossing property is very instrumental in modeling decision-making on public goods. We extended its applicability to tree networks and show that it is equivalent to other similar properties in the literature. We also present two algorithms; the first to sort out the tree graph for a preference profile if it is single-crossing while the tree is unknown, and the second to generate single-crossing preference profiles for a given set of alternatives. These operational results facilitate broader applications of single-crossing in real world cases and computer simulations.