Flippable Pairs and Subset Comparisons in Comparative Probability Orderings

Robin Christian Deptartment of Combinatorics and Optimization, University of Waterloo

                              r3christ@math.uwaterloo.ca

Marston Conder Department of Mathematics, University of Auckland

                                m.conder@auckland.ac.nz

Arkadii Slinko^{∗} Department of Mathematics, University of Auckland

                                a.slinko@auckland.ac.nz

October 2006

Abstract. We show that every additively representable comparative probability order on n atoms is determined by at least n − 1 binary subset comparisons. We show that there are many orders of this kind, not just the lexicographic order. These results provide answers to two questions of Fishburn et al (2002). We also study the flip relation on the class of all comparative probability orders introduced by Maclagan. We generalise an important theorem of Fishburn, Pekeč and Reeds, by showing that in any minimal set of comparisons that determine a comparative probability order, all comparisons are flippable. By calculating the characteristics of the flip relation for n = 6 we discover that the polytopes associated with the regions in the corresponding hyperplane arrangement can have no more than 13 facets and that there are 20 regions whose associated polytopes have 13 facets. All the neighbours of the 20 comparative probability orders which correspond to those regions are representable.

AMS classification: 60A05, 91B08 (primary), 06A07, 91A12, 91E99 (secondary)

Keywords: comparative probability, flip relation, elicitation, subset comparisons, additively representable linear orders

Acknowledgement: Research partially supported by the N.Z. Centres of Research Excellence Fund (grant UOA 201).

∗ Corresponding author.

1 Introduction

In this paper we study algebraic and combinatorial properties of comparative probability orders on a finite set X of n elements. A significant part of this research direction was initiated by Fishburn et al [9] and is related to problems in decision theory and the theory of measurement, especially to the problem of preference elicitation. We answer two questions posed in that paper.

Another factor that influenced our research was a paper by Maclagan [11], who introduced the concept of a flippable pair, and related comparative probability orders to oriented matroids and the Baues problem. We believe that the concept of a flippable pair is very important and adds richness to the whole theory. Maclagan also formulated a number of very interesting questions (see [11, p. 295]). We develop the concept of a lexicographic product of two orders, as briefly outlined by Maclagan (see [11, p. 294]), and use it extensively throughout this paper. In particular we give a new method of constructing comparative probability orders which are not even ‘almost representable’ by a probability measure. Only one such example appears to have been given previously in the literature [10].

Fishburn et al [9] paid significant attention to elicitation of comparative probability orders representable by a probability measure. They proved that any minimal set of comparisons that determines an order ⪯ on 2^{X} consists of critical pairs. By relating flippable pairs with irreducible elements of the discrete cone corresponding to ⪯, we prove a much stronger condition, namely that any minimal set of comparisons consists of flippable pairs. For orders which are not representable by probability measures, we show that the sequence of flippable pairs does not determine the order uniquely. For n = 6 we discovered eight pairs of comparative probability orders with the same sequences of flippable pairs.

Let L_{n} be the set of all comparative probability orders on the set consisting of n elements which are representable by an order preserving positive probability measure. Fishburn et al formulated the following two problems (see [9, p. 243, Open problems 2 and 3]):

1. Show that no order ⪯ ∈ L_{n} is determined by n − 2 (or fewer) binary subset comparisons;

2. Decide whether every ⪯ ∈ L_{n} which is determined by n − 1 comparisons has the structure of the

lexicographic order determined by {i_{1}, …, i_{j}} ≺ i_{j+1} for j = 1, 2, …, n − 1. We prove the first statement in Section 5, and show that the lexicographic order is just one of many orders that can be determined by n − 1 comparisons. We cannot characterise all of these orders, but we can show that they are in one-to-one correspondence with the comparative probability orders on the set consisting of n − 1 elements determined by exactly n − 1 comparisons.

It is a well-known fact that every representable comparative probability order on n elements can be characterised by a region in the hyperplane arrangement H_{n} [5]. The closure of every such region is a convex polytope. Maclagan [11] asked how many facets those polytopes have. We fully answer this question for n = 6 in Section 8.

Some of these results were delivered at the 4th International Symposium on Imprecise Probabilities and Their Applications (ISIPTA 05); see [2].

2 Preliminaries

Definition 1. Let X be a finite set. Any reflexive, complete and transitive binary relation ⪯ on 2^{X} will be called an order on 2^{X}. (Note: sometimes this is called a complete pre-order or a weak order.) Such an order gives rise to two other relations ≺ and ∼ on 2^{X}, defined for all x, y ∈ X by

(a) x ≺ y ⟺ x ⪯ y and not (y ⪯ x);

(b) x ∼ y ⟺ x ⪯ y and y ⪯ x.

If an order ⪯ is anti-symmetric, then all equivalence classes (under the relation ∼) are singletons, and ⪯ is called a linear order.

Definition 2. Let X be a finite set. A linear order ⪯ on 2^{X} is called a comparative probability order if ∅ ⪯ A for every non-empty subset A of X, and ⪯ satisfies de Finetti’s axiom, namely

A ⪯ B ⟺ A ∪ C ⪯ B ∪ C,  (1)

for all A, B, C ∈ 2^{X} such that (A ∪ B) ∩ C = ∅.

For convenience, we will further suppose that X = [n] = {1, 2, …, n} and denote the set of all comparative probability orders on 2^{[n]} as P_{n}.

If we have a probability measure p = (p_{1}, …, p_{n}) on X, where p_{i} is the probability of i, then we know the probability of every event A, by the rule p(A) = ∑_{i∈A} p_{i}. We may now define an order ⪯_{p} on 2^{X} by

A ⪯_{p} B if and only if p(A) ≤ p(B).  (2)

If p_{i} > 0 for all i, and the probabilities of all events are different, then ⪯_{p} is a comparative probability order on X. Any such order is called (additively) representable. The set of representable comparative probability orders is denoted L_{n}. It is known [10] that L_{n} is strictly contained in P_{n} for all n ≥ 5.

We will always assume here that a linear order ⪯ on 2^{X} is a comparative probability order. As in [7, 8], it is often convenient to assume without loss of generality that

1 ≺ 2 ≺ … ≺ n,  (3)

which is equivalent to assuming that p_{1} < p_{2} < … < p_{n} when ⪯ is the comparative probability order represented by the probability measure p = (p_{1}, …, p_{n}). The set of all comparative probability orders on [n] that satisfy (3), will be denoted P_{n}^{∗}. The set of all representable comparative probability orders on [n] that satisfy (3), will be denoted L_{n}^{∗}.

To every linear order ⪯ ∈ P_{n}^{∗}, there corresponds a discrete cone C(⪯) in T^{n}, where T = {−1, 0, 1} (as defined in [7]).

Definition 3. A subset C ⊆ T^{n} is said to be a discrete cone if the following properties hold:

D1. {e_{1}, e_{2} − e_{1}, …, e_{n} − e_{n−1}} ⊆ C, where {e_{1}, …, e_{n}} is the standard basis of ℝ^{n},

D2. 0 ∈ C and for every 0 ≠ x ∈ T^{n}, either x or −x (but not both) is in C,

D3. x + y ∈ C whenever x, y ∈ C and x + y ∈ T^{n}.

We note that Fishburn requires 0 ∉ C in [7] because his orders are anti-reflexive. In our case, condition D2 implies 0 ∈ C.

For each subset A ⊆ X we define the characteristic vector χ_{A} of this subset by

χ_{A}(i) = \{ \begin{matrix}1 & i ∈ A, \\ 0 & i ∉ A, \end{matrix}

for i = 1, 2, …, n. Given a comparative probability order ⪯ on X, we may define a characteristic vector χ(A, B) = χ_{B} − χ_{A} ∈ T^{n} for every pair of subsets A, B for which A ⪯ B is true. The set of all characteristic vectors χ(A, B), for A, B ∈ 2^{X} such that A ⪯ B, is denoted by C(⪯). The two axioms of comparative probability guarantee that C(⪯) is a discrete cone. Given a discrete cone C we can also reconstruct a comparative probability order ⪯ for which C = C(⪯); see [7, Lemma 2.1].

Definition 4. A comparative probability order ⪯ satisfies the mth cancellation condition C_{m} if and only if there is no set {x_{1}, …, x_{m}} of non-zero vectors in C(⪯) for which there exist positive integers a_{1}, …, a_{m} such that

a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{m}x_{m} = 0.  (4)

It is known (as shown in [10], and see also [4, 13, 7]) that a comparative probability order ⪯ is representable if and only if all cancellation conditions for C(⪯) are satisfied.

Suppose that ⪯ ∈ P_{n} is a not necessarily representable comparative probability order with the corresponding discrete cone C = C(⪯). Then the only way we can deduce one comparison from several others is by means of transitivity. Use of transitivity corresponds to the addition of the corresponding characteristic vectors of the cone. Indeed, suppose that A ⪯ B ⪯ C. Then χ(A, B) + χ(B, C) = χ(A, C). It might seem that closedness of C = C(⪯) under the addition is stronger than transitivity of ⪯, but in the presence of the de Finetti axiom, these two conditions are equivalent (see, for example, [7]).

Let us define a restricted sum for vectors in a discrete cone C. Let u, v ∈ C. Then

u ⊕ v = \{ \begin{matrix}u + v & if u + v ∈ T^{n}, \\ undefined & if u + v ∉ T^{n}. \end{matrix}

Definition 5. We say that the cone C is weakly generated by vectors v_{1}, …, v_{k} if every non-zero vector c ∈ C can be expressed as a restricted sum of v_{1}, …, v_{k}, in which each generating vector can be used as many times as needed. We denote this by C = <v_{1}, …, v_{k}>_{w}.

If ⪯ is known to be representable, then there is an additional way to obtain new vectors in C(⪯) from the existing ones, using the cancellation conditions. This can be formulated in terms of multilists of comparisons (see, for example, [9, proof of Theorem 3.7]). In terms of cones, this tool is given in Lemma 1, which says that in representable cones we can deduce new comparisons by forming linear combinations of the characteristic vectors of known comparisons with positive coefficients. This is also a reformulation of Axiom 3 from [9] in terms of discrete cones associated with ⪯.

Lemma 1. Let ⪯ ∈ L_{n} be a representable comparative probability order, and C(⪯) the corresponding discrete cone. Suppose {x_{1}, …, x_{m}} ⊆ C(⪯) and suppose that x = a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{m}x_{m} for some positive real numbers a_{1}, …, a_{m} and x ∈ T^{n}. Then x ∈ C(⪯).

Proof. Suppose that the positive real numbers a_{1}, …, a_{m} satisfy x = a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{m}x_{m}. Then these will be solutions of a system of linear equations with rational (even integer) coefficients. Hence there will be rational numbers satisfying the same equation, and therefore we may assume that a_{1}, …, a_{m} are rational. Let a_{i} = p_{i}/q_{i}, where p_{i} and q_{i} are positive integers. Then multiplying by the least common multiple of all the denominators, we see that the given equation can be written as s_{0}x = s_{1}x_{1} + s_{2}x_{2} + ⋯ + s_{m}x_{m}, where s_{0}, s_{1}, …, s_{m} are integers. If x ∉ C(⪯), then −x ∈ C(⪯) and so this equation can be written as s_{0}(−x) + s_{1}x_{1} + s_{2}x_{2} + ⋯ + s_{m}x_{m} = 0, which contradicts the (m + 1)th cancellation condition. Thus x ∈ C(⪯).

Definition 6. We say that the cone C is strongly generated by vectors v_{1}, …, v_{k} if every non-zero vector c ∈ C can be obtained from v_{1}, …, v_{k} using the operation of restricted sum and linear combinations with positive rational coefficients. We denote this by C = <v_{1}, …, v_{k}>.

In the process of elicitation of an individual’s comparative probability order ⪯, a single query will be of the form “Is A ≺ B?” for distinct non-empty subsets A, B ∈ 2^{[n]}. Hence we will sometimes assume the comparison A ≺ B means a positive answer to this query. In particular, for a representable comparative probability order ⪯, we will say that the comparisons A_{1} ≺ B_{1}, …, A_{ℓ} ≺ B_{ℓ} determine ⪯ in L_{n} if the vectors χ(A_{1}, B_{1}), …, χ(A_{ℓ}, B_{ℓ}) strongly generate C(⪯).

Example 1. Let us consider the order

∅ ≺ 1 ≺ 2 ≺ 12 ≺ 3 ≺ 13 ≺ 23 ≺ 123.

and its respective cone C = C(⪯). Let us choose v_{1} = (1, 0, 0), v_{2} = (−1, 1, 0), v_{3} = (−1, −1, 1), which correspond to comparisons

∅ ≺ 1, 1 ≺ 2, 12 ≺ 3,  (5)

respectively. Then all other non-zero vectors of C can be expressed using v_{1}, v_{2}, v_{3}. For example,

v_{1} ⊕ v_{2} = (0, 1, 0),
v_{1} ⊕ v_{3} = (0, −1, 1),
v_{2} ⊕ v_{3} = (−1, 0, 1),
v_{1} ⊕ (v_{1} ⊕ v_{2}) = (1, 1, 0),
(v_{1} ⊕ (v_{1} ⊕ v_{2})) ⊕ v_{3} = (0, 0, 1),

and so on. Thus C = <v_{1}, v_{2}, v_{3}>_{w}. The order ⪯ is representable, but we did not use linear combinations to generate C. Therefore the comparisons (5) determine ⪯ not only in the class of representable comparative probability orders L_{n}, but also in the class of all comparative probability orders P_{n}.

Let us now give an example which shows that for representable cones, weak and strong generation are different. We will construct a representable cone whose minimal set of weak generators cannot be a minimal set of strong generators.

Example 2. In an example constructed by Kraft, Pratt and Seidenberg ([10, p. 415]), we re-label q = 1, r = 2, s = 3, p = 4 and t = 5, to obtain a non-representable comparative probability order ⪯ on [5]:

∅ ≺ 1 ≺ 2 ≺ 3 ≺ 12 ≺ 13 ≺ 4 ≺ 14 ≺ 23 ≺ 5 ≺ 123 ≺ 24 ≺ 34 ≺ 15 ≺ 124 ≺ 25 ≺ 134 ….

(Here only the first 17 terms are shown, since the remaining ones can be uniquely reconstructed). This order does not satisfy the 4th cancellation condition, since it contains the following comparisons:

13 ≺ 4, 14 ≺ 23, 34 ≺ 15 and 25 ≺ 134,

whose characteristic vectors u_{1} = (−1, 0, −1, 1, 0), u_{2} = (−1, 1, 1, −1, 0), u_{3} = (1, 0, −1, −1, 1) and u_{4} = (1, −1, 1, 1, −1) satisfy

u_{1} + u_{2} + u_{3} + u_{4} = 0.

The structure of the corresponding cone C = C(⪯) is as follows: C includes all vectors of T^{n} lying in the half-space S_{b} = {x ∈ ℝ^{n} | (x, b) > 0}, and the four vectors u_{1}, u_{2}, u_{3}, u_{4} lying on the hyperplane H_{b} = {x ∈ ℝ^{n} | (x, b) = 0} with normal vector

b = \frac{1}{16}(1, 2, 3, 4, 6).

In this linear order, 25 is the 16th subset and 134 is the 17th, so 25 ≺ 134 is the central comparison. Obviously we can ‘flip’ this central comparison, replacing 25 ≺ 134 by 134 ≺ 25, and still have a comparative probability order ⪯′, with cone C′ = (C \ {u_{4}}) ∪ {−u_{4}}. Moreover, this will be a representable comparative probability order, since all cancellation conditions will be satisfied. Indeed, if we had a set of vectors {v_{1}, …, v_{k}} ⊂ C′ such that

v_{1} + v_{2} + … + v_{k} = 0,

then we would have {v_{1}, …, v_{k}} ⊂ H_{b} and therefore {v_{1}, …, v_{k}} ⊆ {u_{1}, u_{2}, u_{3}, −u_{4}}, which is impossible.

Since u_{1} + u_{2} ∉ T^{n}, u_{1} + u_{3} ∉ T^{n} and u_{2} + u_{3} ∉ T^{n}, any set of weak generators of C′ must include all of u_{1}, u_{2}, u_{3}, −u_{4}. But

−u_{4} = u_{1} + u_{2} + u_{3},

and hence any minimal set of weak generators of C cannot be a minimal set of strong generators since −u_{4} can be excluded from it.

Definition 7. Let C be a discrete cone. Define its weak rank rank_{w}(C) to be the smallest number of vectors in C that weakly generate C. Define its strong rank rank_{s}(C) to be the smallest number of vectors in C that strongly generate C.

Obviously rank_{s}(C) ≤ rank_{w}(C), and the previous example shows that it is possible in some cases to have rank_{s}(C) < rank_{w}(C).

3 Critical and flippable pairs

Definition 8. Let A and B be disjoint subsets of [n]. The pair (A, B) is said to be critical^{1} for ⪯ if A ≺ B and there is no C ⊆ [n] for which A ≺ C ≺ B.

Definition 9. Let A and B be disjoint subsets of [n]. The pair (A, B) is said to be flippable for ⪯ if for every D ⊆ [n] disjoint from A ∪ B the pair (A ∪ D, B ∪ D) is critical.

Since in the latter definition we allow the possibility that D = ∅, every flippable pair is critical.

We note that the set of flippable pairs is not empty, since the central pair of any comparative probability order is flippable. Indeed, this consists of a certain set A and its complement A^{c} = X \ A, and there is no D which has empty intersection with both of these sets. It is not known whether this can be the only flippable pair of the order.

1We follow Fishburn [9] in this definition, while Maclagan [11] calls such pairs primitive.

Suppose now that a pair (A, B) is flippable for a comparative probability order ⪯, and A ≠ ∅. Then reversing each comparisons A ∪ D ≺ B ∪ D (to B ∪ D ≺ A ∪ D), we will obtain a new comparative probability order ⪯′, since the de Finetti axiom will still be satisfied. We say that ⪯′ is obtained from ⪯ by flipping over A ≺ B. The orders ⪯ and ⪯′ are called flip-related. This flip relation turns P_{n} into a graph.

A pair (A, B) with A = ∅ can be flippable with no possibility of flipping over. Below we mark with an asterisk the three flippable pairs of the comparative probability order of Example 1:

∅ ≺_{∗} 1 ≺_{∗} 2 ≺ 12 ≺_{∗} 3 ≺ 13 ≺ 23 ≺ 123.

The first comparison ∅ ≺_{∗} 1 cannot be flipped over while the other two can be.

Definition 10. An element w of the cone C is said to be reducible if there exist two other vectors u, v ∈ C such that w = u ⊕ v, and irreducible otherwise.

Theorem 1. A pair (A, B) of disjoint subsets is flippable for ⪯ if and only if the corresponding characteristic vector χ(A, B) is irreducible in C(⪯).

Proof. Suppose (A, B) is flippable but w = χ(A, B) is reducible. Then w = u ⊕ v, where u = χ(C, D) and v = χ(E, F) for some C, D, E, F such that C ≺ D and E ≺ F. We may assume without loss of generality that C ∩ D = E ∩ F = ∅. Since u + v ∈ C(⪯) ⊂ T^{n} and C ∩ D = E ∩ F = ∅, we have C ∩ E = D ∩ F = ∅. Also since χ(A, B) = χ(C, D) + χ(E, F), it is easy to see that

A = (C \ F) ∪ (E \ D) and B = (D \ E) ∪ (F \ C).

Let X = C ∩ F. Then X ∩ (A ∪ B) = ∅, and since (C ∪ D) ∩ (E \ D) = (E ∪ F) ∩ (D \ E) = ∅ we have

A ∪ X = C ∪ (E \ D) ≺ D ∪ (E \ D) = (D \ E) ∪ E ≺ (D \ E) ∪ F = B ∪ X.

In particular, A ∪ X and B ∪ X are not neighbors in ⪯, so (A, B) is not flippable — contradiction.

Suppose now that A ≺ B but (A, B) is not flippable. Then there exist subsets C and D such that (A ∪ B) ∩ C = ∅ and

A ∪ C ≺ D ≺ B ∪ C.

We may assume that C is minimal with this property, and hence that C ∩D = ∅. Now if u = χ(A∪C, D) and v = χ(D, B ∪ C), then

u ⊕ v = χ(A ∪ C, B ∪ C) = χ(A, B) = w,

and so w is reducible.

Theorem 2. Let ⪯ be a representable comparative probability order. Then the set of irreducible elements of C = C(⪯) is the smallest set that weakly generates C.

Proof. It is clear that the set of all irreducible elements Irr(C) of C = C(⪯) is contained in any set of weak generators. Let x ∈ C. We will prove that either x belongs to Irr(C) or x can be represented as a restricted sum of elements of Irr(C). Suppose x ∉ Irr(C). Then x = x_{1} ⊕ x_{2} for some x_{i} ∈ C. If both of them belong to Irr(C), we are done. If at least one of them does not, then we continue representing both as restricted sums of vectors of C. In this way, we obtain a binary tree of elements of C. We claim that not a single branch of this tree can be longer than the cardinality of C. If one of the branches were longer, then there would be two equal elements in it. Hence it would be possible to start a tree with some element and find the same element deep inside the tree. Without loss of generality, we can assume that x itself can be found in a tree generated by x. If we stop when x has appeared for the second time, then we will have

x = G(x, x_{1}, …, x_{m}),

where G is some term in the algebra ⟨ C, ⊕ ⟩. Then if we express restricted addition through the ordinary one, the term x will cancel on both sides, and we will obtain an expression

a_{1}x_{1} + a_{2}x_{2} + … + a_{m}x_{m} = 0

with all coefficients a_{i} positive integers. This will violate the mth cancellation condition.

This theorem does not hold for non-representable orders as the following example shows.

Example 3. In the non-representable comparative probability order of Example 2, we mark all flippable pairs with an asterisk:

∅ ≺ 1 ≺ 2 ≺ 3 ≺ 12 ≺ 13 ≺_{∗} 4 ≺ 14 ≺_{∗} 23 ≺ 5 ≺_{∗} 123 ≺ 24 ≺ 34 ≺_{∗} 15 ≺ 124 ≺ 25 ≺_{∗} 134 ….

There are five such pairs. Let f_{1} = χ(13, 4), f_{2} = χ(14, 23), f_{3} = χ(5, 123), f_{4} = χ(34, 15), f_{5} = χ(25, 134), and also let x = χ(23, 5). Then it is easy to check that

x = f_{1} ⊕ ((f_{5} ⊕ (f_{2} ⊕ x)) ⊕ f_{4}),  (6)

but on the other hand, x cannot be represented as a restricted sum of f_{1}, …, f_{5} since it is not in the subspace spanned by f_{1}, …, f_{5}. The reason for (6) is of course the equation f_{1} + f_{2} + f_{4} + f_{5} = 0.

4 Elicitation of comparative probability orders

One of the problems in decision theory and the theory of measurement is to determine an individual’s preference order over subsets of objects, or an individual comparative probability order over subsets of states of the world [9]. This stipulates the design of strategies to elicit those comparisons between subsets which determine the preference order completely.

Let A, B ⊆ [n] be two non-empty disjoint subsets. Then given a comparative probability order ⪯, we can have both A ≺ B and B ≺ A, so by asking an individual to compare A and B we obtain certain information about this individual’s preference order. If, however, A = ∅ and B is non-empty, then A ≺ B and such comparison gives no information about the order.

Definition 11. A set S = {A_{1} ≺ B_{1}, …, A_{ℓ} ≺ B_{ℓ}} of comparisons determines a comparative probability order ⪯ in P_{n} if the characteristic vectors χ(A_{i}, B_{i}) together with the standard basis of ℝ^{n} weakly generate C(⪯).

Note that if such a set S determines a comparative probability order, then one can deduce all other comparisons in ⪯ by virtue of transitivity alone (using the comparisons from S and ‘trivial’ comparisons ∅ ≺ {i}). For representable orders we have the following:

Definition 12. A set S = {A_{1} ≺ B_{1}, …, A_{ℓ} ≺ B_{ℓ}} of comparisons determines a representable comparative probability order ⪯ in L_{n} if the characteristic vectors χ(A_{i}, B_{i}) together with the standard basis of ℝ^{n} strongly generate C(⪯).

Note that if such a set S determines a representable comparative probability order, then one can deduce all other comparisons in ⪯ by means of positive linear combinations of the characteristic vectors χ(A_{i}, B_{i}) and the standard basis vectors.

Now let S be a minimal set of comparisons that weakly (resp. strongly) determines a comparative probability order (resp. representable comparative probability order) ⪯. It is possible that all ‘trivial’ comparisons ∅ ≺ {i} are implied by comparisons from S; in this case the corresponding minimal set of generators of the cone C(⪯) has cardinality |S|. If not, then the corresponding minimal set of generators of C(⪯) has |S| + 1 generators. Indeed, both ∅ ≺ {i} and ∅ ≺ {j} cannot be in any minimal set of generators, since one of them implies the other.

Fishburn, Pekeč and Reeds [9, Theorem 3.7] proved that if A_{1} ≺ B_{1}, …, A_{ℓ} ≺ B_{ℓ} is a minimal set of subset comparisons that determines a representable comparative probability order ⪯ in L_{n}, then the pairs (A_{1}, B_{1}), …, (A_{ℓ}, B_{ℓ}) are critical for ⪯. Now we can generalise this important theorem and also give a more transparent proof of it.

Theorem 3. Let ⪯ ∈ L_{n} be a representable comparative probability order. Further, suppose that {A_{1} ≺ B_{1}, …, A_{ℓ} ≺ B_{ℓ}} is a minimal set of subset comparisons that determines ⪯ in L_{n}. Then all of the pairs (A_{1}, B_{1}), …, (A_{ℓ}, B_{ℓ}) are flippable for ⪯.

Proof. A smallest set of subset comparisons corresponds to a minimal set of strong generators of the respective cone C = C(⪯), and this is either G = {g_{1}, …, g_{ℓ}} or G = {g_{1}, …, g_{ℓ+1}} with g_{ℓ+1} = e_{i} for some i = 1, 2, …, n. Without loss of generality let us consider the first case. By Theorem 1, to show that a pair (A_{1}, B_{1}) is flippable, it is enough to show that g_{1} = u + v for no two vectors u, v ∈ C. Let us assume the contrary. Then mu = ∑_{i=1}^{ℓ} m_{i}g_{i} and kv = ∑_{i=1}^{ℓ} k_{i}g_{i} for some positive integers m, m_{i} and k, k_{j}. Let r = lcm (m, k). Then multiplying the two equations by their respective factors, we obtain ru = ∑_{i=1}^{ℓ} m′_{i}g_{i} and rv = ∑_{i=1}^{ℓ} k′_{i}g_{i}. Adding these we obtain

rg_{1} = ∑_{i=1}^{ℓ}(m′_{i} + k′_{i})g_{i}.

We now consider two cases. If r > m′_{1} + k′_{1}, then g_{1} can be excluded from the set of generators G which was supposed to be minimal, contradiction. If r ≤ m′_{1}+k′_{1}, then the ℓth cancellation condition is violated, again a contradiction. This proves the theorem.

5 Geometric representation of representable comparative

probability orders

Geometric representation of comparative probability orders was first introduced by Fine and Gill [5]. To explain it, we need to recall a few basic facts about hyperplane arrangements in ℝ^{n}; see [14, 12] for more information about these. A hyperplane is a translate of an (n − 1)-dimensional subspace of ℝ^{n}. Any hyperplane of the form H = {x ∈ ℝ^{n} | (n, x) = 0}, where n is a non-zero vector, will be called linear, with the vector n called the normal vector of H. Any hyperplane of the form J = {x ∈ ℝ^{n} | (n, x) = a} where a ≠ 0 will be called an affine hyperplane. Every affine hyperplane is a translate of the linear hyperplane having the same normal vector n.

A hyperplane arrangement A is any finite set of hyperplanes. A region of an arrangement A is a connected component of the complement of the union U of the hyperplanes of A — that is, the open set

U = ℝ^{n} \ ⋃_{H∈A} H.

In particular, every region of an arrangement is an open set. Each region has an associated polytope which is the closure of the region. This polytope is convex.

Let A be an arrangement of hyperplanes in ℝ^{n}, and let J be any hyperplane in ℝ^{n}. Then the set

A^{J} = {H ∩ J | H ∈ A}

is called the induced arrangement of hyperplanes in J.

Let A, B ⊆ [n] be disjoint subsets, of which at least one is non-empty. Corresponding to the pair (A, B) is a hyperplane H(A, B) consisting of all points x in ℝ^{n} satisfying the equation

∑_{a∈A} x_{a} − ∑_{b∈B} x_{b} = 0.

Such hyperplanes have normal vectors in the set {−1, 0, 1}^{n} \ 0, where 0 is the n-dimensional zero vector. Let us denote the corresponding hyperplane arrangement by A_{n}. Also let J be the hyperplane in ℝ^{n} defined by the equation x_{1} + x_{2} + … + x_{n} = 1, and let H_{n} = A_{n}^{J} be the induced hyperplane arrangement. We are interested in the regions of H_{n} which lie in the positive orthant ℝ_{+}^{n} of ℝ^{n}, given by x_{i} ≥ 0 for i = 1, 2, …, n. The closure of the union of all of these regions is an (n − 1)-dimensional simplex S^{n−1} in J.

As we know, every point p = (p_{1}, …, p_{n}) ∈ S^{n−1} defines a representable comparative probability order ⪯_{p} from L_{n} given by the rule (2) from Section 2. If p and q are two points of S^{n−1}, then the orders ⪯_{p} and ⪯_{q} will coincide if and only if p and q are in the same region of the hyperplane arrangement H_{n}. This immediately follows from the fact that the order A ≺ B changes to B ≺ A (or vice versa) precisely when we cross the hyperplane H(A, B). Thus every comparative probability order in L_{n} is so represented by one of the regions of H_{n}.

Let P be the polytope representing ⪯_{p}. A facet of the polytope will be called significant if it is not contained in any of the hyperplanes x_{i} = 0. It is now clear that the minimal number of subset comparisons needed to define ⪯_{p} is the number of significant facets of the polytope representing ⪯_{p}. We illustrate this using the following example.

Example 4. The 12 regions of H_{3} on the figure below represent all 12 comparative probability orders on [3].

The two shaded triangular regions correspond to the two orders for which 1 ≺ 2 ≺ 3, namely

1 ≺ 2 ≺ 12 ≺ 3 ≺ 13 ≺ 23 ≺ 123 and 1 ≺ 2 ≺ 3 ≺ 12 ≺ 13 ≺ 23 ≺ 123,

with the lighter one corresponding to the first order (the lexicographic order). Note, however, that one of the boundaries for the first order is the hyperplane x_{1} = 0, and it is determined by two comparisons, while the second order needs three comparisons, since all facets of the corresponding polytope are significant.

A simple but important statement is contained in the following

Lemma 2. Let P be the polytope representing the order ⪯_{p}, where p is a probability measure. Then P can have at most one insignificant facet.

Proof. Suppose P has at least one insignificant facet. We can show that if p_{j} = min_{i=1}^{n} p_{i}, then one of its facets is contained in the hyperplane x_{j} = 0, and this is the only insignificant facet of P. For suppose that another facet of P is contained in x_{k} = 0. Since P lies in the half-space x_{k} − x_{j} ≥ 0, we will have x_{k} = x_{j} = 0 on this facet. It follows that this facet has (n−2)-dimensional volume zero, in contradiction to the fact that every facet of an (n−1)-dimensional polytope has non-zero (n−2)-dimensional volume.

The following theorem answers Open Problem 2 posed by Fishburn et al in [9, p. 243]:

Theorem 4. Let ⪯ be a representable comparative probability order. Then ⪯ is determined by no fewer than n−1 binary subset comparisons A ≺ B, where A, B are disjoint non-empty subsets of [n]. Moreover, if all facets of the polytope P representing ⪯ are significant, then ⪯ is determined by no fewer than n binary subset comparisons.

Proof. Consider the hyperplane arrangement H_{n} (as defined earlier in this section), and let p be a probability measure that corresponds to a representable order ⪯ ∈ L_{n}. The closure of the region P to which p belongs is an convex polytope. Since it is open, it has a non-zero (n − 1)-dimensional volume in J and, therefore must have at least n vertices and, hence, at least n facets.

If all facets are significant, then each facet corresponds to a non-trivial subset comparison, hence we need at least n subset comparisons to determine ⪯. Otherwise, by Lemma 2 there is a single insignificant facet, and in that case n − 1 subset comparisons are needed to determine ⪯.

For orders in L_{n}^{∗} — that is, for those satisfying condition (3) from Section 2 — we have the following:

Corollary 1. Let ⪯ be a representable comparative probability order in L_{n}^{∗} which is determined by exactly n − 1 binary subset comparisons. Then the hyperplane x_{1} = 0 contains one of the facets of the polytope corresponding to ⪯.

This can be expressed in terms of discrete cones as follows:

Corollary 2. Let ⪯ be a representable comparative probability order in L_{n}^{∗} which is determined by exactly n − 1 binary subset comparisons. Then the vector g_{1} = (1, 0, … 0) is present in any set of generators of the corresponding discrete cone C(⪯).

6 The product of two comparative probability orders

We will use a construction for the product of two orders. An outline of this construction was given by Maclagan in [11, p. 294]. We now give a rigorous definition.

Definition 13. Suppose we have two comparative probability orders ⪯_{1} ∈ P_{k} and ⪯_{2} ∈ P_{m}. Let us define a new order ⪯ = ⪯_{1} × ⪯_{2} on [k+m]. First we transfer the order ⪯_{2} from the set [m] to the set [k+m]\[k] as follows: for any set A = {i_{1}, …, i_{s}} ⊆ [k + m] \ [k] we define its ‘shift’ Ā = {i_{1} − k, …, i_{s} − k} ⊆ [m], and then for any two subsets A, B ⊆ [k + m] \ [k], we define A ⪯_{2} B if and only if Ā ⪯_{2} B̄. (NB: there will be no confusion in using the same notation for both the original order and the shifted order here.) Now let A, B ⊆ [k + m]. Such sets can be uniquely represented as A = A_{1} ∪ A_{2} and B = B_{1} ∪ B_{2}, where A_{1}, B_{1} ⊆ [k] and A_{2}, B_{2} ⊆ [k + m] \ [k]. Then finally we let A ≺ B if and only if either A_{2} ≺_{2} B_{2}, or A_{2} = B_{2} and A_{1} ≺_{1} B_{1}. We call ⪯ the product of ⪯_{1} and ⪯_{2}.

Proposition 1. Let ⪯_{1} ∈ P_{k} and ⪯_{2} ∈ P_{m} be two comparative probability orders with cones C_{1} ⊂ T^{k} and C_{2} ⊂ T^{m}, respectively. Then their product ⪯ = ⪯_{1} × ⪯_{2} is also a comparative probability order whose cone C(⪯) consists of all vectors (g, 0) with g ∈ C_{1} and all vectors (g, h) with g ∈ T^{k} and 0 ≠ h ∈ C_{2}.

Proof. Let us consider the set of all characteristic vectors χ(A, B), where A ⪯ B. These sets can be uniquely represented as A = A_{1} ∪ A_{2} and B = B_{1} ∪ B_{2}, where A_{1}, B_{1} ∈ [k] and A_{2}, B_{2} ∈ [k + m] \ [k]. If A_{2} ≺_{2} B_{2}, then χ(A, B) = (g, h), where g ∈ T^{k} and 0 ≠ h ∈ C_{2}. If A_{2} = B_{2}, then χ(A, B) = (g, 0), where g ∈ C_{1}. We claim that the set C of all χ(A, B) so obtained is a discrete cone. Indeed, first the property D1 for C follows from the same property for C_{1} and C_{2}. Second, if v = (x, 0) with x ∈ T^{k}, then either v or −v belongs to C, since either x or −x belongs to C_{1} (by property D2). On the other hand, if v = (g, h) is any vector from T^{k+m} for which 0 ≠ h ∈ T^{m}, then if h ∈ C_{2} then clearly v is in C, while if h ∉ C_{2} then −h ∈ C_{2} and −v = (−g, −h) is in C. Hence D2 holds for C. We leave the proof of D3 to the reader. Since C is a discrete cone, ⪯ is a comparative probability order, and C = C(⪯).

Definition 14. The order ⪯ ∈ L_{n} is called reducible if it can be represented as a product of two other orders.

Example 5. The lexicographic order ⪯ ∈ L_{n}

1 ≺ 2 ≺ 12 ≺ 3 ≺ 13 ≺ 23 ≺ 23 ≺ 4 ≺ …

can be represented as the product

(… (⪯_{0} × ⪯_{0})× ⪯_{0}) × …)× ⪯_{0}

of n copies of ⪯_{0}, where ⪯_{0} is the only order in L_{1} (namely: ∅ ≺_{0} {1}).

Theorem 5. Let ⪯_{1} ∈ P_{k} and ⪯_{2} ∈ P_{m} be two comparative probability orders. Then the weak rank (resp. strong rank) of ⪯_{1} × ⪯_{2} is the sum of the weak ranks (resp. strong ranks) of ⪯_{1} and ⪯_{2}.

Proof. We will prove the theorem for the case of a weak rank. The proof for the case of a strong rank is similar.

Let C_{1}, C_{2}, C be the discrete cones of ⪯_{1}, ⪯_{2} and ⪯_{1} × ⪯_{2}, respectively. Let {g_{1}, …, g_{s}} and {h_{1}, …, h_{t}} be minimal sets of weak generators for C_{1} and C_{2}. Let G be the s × k matrix whose rows are the generators {g_{1}, …, g_{s}}, and let H be the t × m matrix whose rows are the generators {h_{1}, …, h_{t}}. Also let 1_{t×k} be the t × k matrix whose all entries are 1, and let 0_{s×m} be an s × m zero matrix. Now we are going to check that the rows of the (s + t) × (k + m) matrix

M = [ \begin{matrix}G & 0_{s×m} \\ −1_{t×k} & H \end{matrix} ]

generate C.

It is obvious that any row (g, 0), where 0 ≠ g ∈ C_{1}, can be obtained from the first s rows using the operation ⊕. In particular, the row (1, 0) can be so obtained, where 1 is the k-dimensional vector whose entries are all 1. We will now show that every vector (−1, h), where 0 ≠ h ∈ C_{2} can be generated. For this, all we need do is show is that if (−1, h_{1}) and (−1, h_{2}) can be generated, and h_{1} ⊕ h_{2} is defined, then also (−1, h_{1} ⊕ h_{2}) can be generated; but that is easy, since

(−1, h_{1} ⊕ h_{2}) = ((1, 0) ⊕ (−1, h_{1})) ⊕ (−1, h_{2}).

Suppose now that c = (g, h) ∈ T^{k+m}, where g ∈ T^{k} and 0 ≠ h ∈ C_{2}. We wish to show that c can be generated using the rows of M as generators. It is not difficult to see that there exist vectors g_{1}, g_{2} ∈ C_{1} such that

g = (−1 ⊕ g_{1}) ⊕ g_{2}.

If the ith coordinate of g is 1, then both g_{1} and g_{2} should have a 1 in the same position. If the ith coordinate of g is 0, then one of the vectors g_{1} or g_{2} should have a 1 in that position. Finally, If the ith coordinate of g is −1, then both g_{1} and g_{2} should have a 0 in that position. Since all coordinates of g_{1} and g_{2} are positive, they belong to C_{1}. The vector c can now be obtained as follows:

c = (g, h) = ((−1, h) ⊕ (g_{1}, 0)) ⊕ (g_{2}, 0).

This completes the proof. Note that it is also clear that the given set of generators (the rows of M) is minimal.

Example 6. Let us consider the order

∅ ≺ 1 ≺ 2 ≺ 3 ≺ 12 ≺ 13 ≺ 23 ≺ 123.

and its respective cone C = C(⪯). This cone has the following set of generators (both weak and strong):

h_{1} = (−1, 1, 0),
h_{2} = (0, −1, 1),
h_{3} = (1, 1, −1).

Let ⪯_{0} be the order ∅ ≺_{0} 1 of L_{1}. Then as in the proof of Theorem 5, the rows u_{1}, …, u_{4} of the matrix

M = [ \begin{matrix}1 & 0 & 0 & 0 \\ −1 & −1 & 1 & 0 \\ −1 & 0 & −1 & 1 \\ −1 & 1 & 1 & −1 \end{matrix} ]

generate the cone for the order ⪯_{0} × ⪯.

Another important property of the product is that it preserves representability.

Theorem 6. The product of two representable comparative probability orders ⪯_{1} ∈ L_{k} and ⪯_{2} ∈ L_{m} is a representable comparative probability order in L_{k+m}.

Proof. Let p = (p_{1}, …, p_{k}) and q = (q_{1}, …, q_{m}) be the probability measures that represent ⪯_{1} and ⪯_{2}, respectively. Since q is linear, the following number is non-zero:

ε = min_{I,J} {|∑_{i∈I} q_{i} − ∑_{j∈J} q_{j}| : I, J ⊆ [m], I ∩ J = ∅} .

It is then easy to check that the measure given by

\frac{1}{ε + 1} (εp_{1}, εp_{2}, …, εp_{k}, q_{1}, q_{2}, …, q_{m})

defines the order ⪯_{1} × ⪯_{2}.

7 Structural characterisation of comparative probability orders

determined by n − 1 binary comparisons

We can now give a structural characterisation of the comparative probability orders in L_{n}^{∗} whose corresponding polytope has a facet contained in the hyperplane x_{1} = 0.

Theorem 7. Let ⪯ be a representable comparative probability order in L_{n}^{∗} whose corresponding polytope P has a facet contained in the hyperplane x_{1} = 0. Then ⪯ = ⪯_{0} × ⪯′, where ⪯_{0} is the only order in L_{1} and ⪯′ is a comparative probability order in L_{n−1}^{∗}.

Proof. Let S be the minimal set of comparisons that define ⪯. By Theorem 3, all comparisons in S are critical. Let A ≺ B be any one comparison from S, where A, B ⊆ [n] are disjoint and non-empty, and consider the hyperplane associated with this comparison, consisting of all points x ∈ ℝ^{n} for which

∑_{a∈A} x_{a} = ∑_{b∈B} x_{b}.  (7)

Let p be any probability measure such that ⪯=⪯_{p}. Since A ≺ B, we see that p does not lie on the hyperplane (7), and that

∑_{a∈A} p_{a} < ∑_{b∈B} p_{b}.

We wish to show that also

∑_{a∈A∪{1}} p_{a} < ∑_{b∈B\{1}} p_{b}.  (8)

First, assume that 1 ∈ B. Since A ≺ B is critical, we have B \ {1} ≺ A, and so

∑_{b∈B\{1}} p_{b} < ∑_{a∈A} p_{a} < ∑_{b∈B} p_{b}.

It follows that

∑_{b∈B\{1}} x_{b} < ∑_{a∈A} x_{a} < ∑_{b∈B} x_{b}  (9)

for every interior point x of this region, while

∑_{b∈B\{1}} x_{b} ≤ ∑_{a∈A} x_{a} ≤ ∑_{b∈B} x_{b}  (10)

for every point x on any facet of P. In particular, condition (10) must hold on the facet that is contained in the hyperplane x_{1} = 0, which is a contradiction since no internal point of that facet is on the hyperplane ∑_{b∈B\{1}} x_{b} = ∑_{a∈A} x_{a}. Hence 1 ∉ B.

Similarly, if we assume that 1 ∉ A, then the same kind of argument gives

∑_{a∈A} p_{a} < ∑_{b∈B} p_{b} < ∑_{a∈A∪{1}} p_{a},

again leading to a contradiction, so 1 ∈ A.

Next, we consider C = C(⪯). We know that this cone has n strong generators g_{1}, …, g_{n}, with g_{1} = (1, 0, … 0). The other strong generators g_{2}, …, g_{n} correspond to characteristic vectors of critical pairs A_{i} ≺ B_{i} from S with non-empty A_{i} and B_{i}. Now we know that 1 ∈ A_{i} for i = 2, …, n, and hence the corresponding generators will be g_{i} = (−1, g′_{i}) for all 2 ≤ i ≤ n, where g′_{i} ∈ T^{n−1}. Thus the rows of the following matrix are the strong generators of C:

G = [ \begin{matrix}1 & 0 \\ −1 & g′_{2} \\ ⋮ & ⋮ \\ −1 & g′_{n} \end{matrix}  ] .

Clearly g′_{2}, … g′_{n} generate a cone C′ = C(⪯′) for some ⪯′ ∈ L_{n−1}. As rank(C′) ≤ n − 1, the order ⪯′ is determined by no more than n − 1 comparisons. The form of G demonstrates that ⪯ = ⪯_{0} × ⪯′.

Now we can give a characterisation of the comparative probability orders in L_{n}^{∗} that can be determined by n − 1 binary comparisons, answering Open Problem 3 posed by Fishburn et al in [9, p. 243]:

Theorem 8. Let ⪯ be a comparative probability order in L_{n}^{∗} that can be determined by n − 1 binary comparisons. Then ⪯ is reducible, and ⪯ = ⪯_{0} × ⪯′, where ⪯_{0} is the only order in L_{1} and ⪯′ is a comparative probability order in L_{n−1}^{∗} that can be determined by no more than n − 1 comparisons. Conversely, if ⪯′ ∈ L_{n−1}^{∗} is determined by no more than n−1 comparisons, then the product ⪯ = ⪯_{0} × ⪯′ is a comparitive probability order in L_{n}^{∗} that can be determined by n − 1 binary comparisons, unless ⪯′ requires exactly n − 1 comparisons and is reducible as ⪯′ = ⪯_{0} × ⪯′′.

Proof. Let ⪯ ∈ L_{n}^{∗} be any order determined by a set of n−1 binary comparisons, and let p be a probability measure that determines ⪯, and P the corresponding polytope in J. Then Corollary 1 implies that the hyperplane x_{1} = 0 contains a facet of P. By Theorem 7, we know that ⪯ = ⪯_{0} × ⪯′, where ⪯_{0} is the only order in L_{1} and ⪯′ is a comparative probability order in L_{n−1}^{∗}. Let C′ = C(⪯′). Then C′ has rank n − 1, and ⪯′ is determined by n − 1 or n − 2 comparisons.

For the converse, if ⪯′ ∈ L_{n−1} is determined by at most n − 1 comparisons, we have two cases to consider, as follows: Case 1: ⪯′ is determined by n − 1 comparisons and ⪯′ ≠⪯_{0} × ⪯′′. In this case, if H is a matrix with n − 1 rows that are strong generators of C(⪯′), then

G = [ \begin{matrix}1 & 0 \\ −1 & H \end{matrix} ]

generates the cone C = C(⪯_{0} × ⪯′). Here the first row is g_{1} = (1, 0, … 0) ∈ ℝ^{n} and so ⪯ = ⪯_{0} × ⪯′ is determined by n − 1 binary comparisons. (We do not have to add a row (1, 0, , …, 0) ∈ ℝ^{n−1} to H because the row (−1, 1, 0, …, 0) ∈ ℝ^{n} is strongly implied by the other rows of G.) Case 2: ⪯′ is determined by n − 2 comparisons. In this case, by Theorem 7, the cone C(⪯′) has n − 1 strong generators h_{1}, …, h_{n−1} (with h_{1} = (1, 0, …, 0) ∈ ℝ^{n−1}), none of which can be removed. Hence the rows of

G = [ \begin{matrix}1 & 0 \\ −1 & H \end{matrix} ]

form a minimal set of strong generators of C, and because the first row is g_{1} = (1, 0, … 0) ∈ ℝ^{n}, the corresponding order ⪯ is determined by n − 1 comparisons.

Example 7. We illustrate this proof using the two orders from Example 4. The first one (which is the lexicographic order), denoted say by ≺_{1}, is determined by the comparisons 1 ≺ 2 and 12 ≺ 3, and its cone is generated by the vectors

v_{1} = (1, 0, 0), v_{2} = (−1, 1, 0), v_{3} = (−1, −1, 1).

The cone of ≺_{0} × ≺_{1} is generated by the vectors

v_{1} = (1, 0, 0, 0), v_{2} = (−1, 1, 0, 0), v_{3} = (−1, −1, 1, 0), v_{4} = (−1, −1, −1, 1),

and ≺_{0} × ≺_{1} itself is determined by the comparisons 1 ≺ 2, 12 ≺ 3, and 123 ≺ 4.

The second order, denoted say by ≺_{2}, is determined by comparisons 1 ≺ 2, 2 ≺ 3, and 3 ≺ 12, and its cone is generated by the vectors

u_{1} = (−1, 1, 0), u_{2} = (0, −1, 1), u_{3} = (1, 1, −1).

(Note that the vector (1, 0, 0) can be obtained from these.) The cone of ≺_{0} × ≺_{2} is generated by the vectors

u_{1} = (1, 0, 0, 0), u_{2} = (−1, −1, 1, 0), u_{3} = (−1, 0, −1, 1), u_{4} = (−1, 1, 1, −1),

and ≺_{0} × ≺_{2} itself is determined by the comparisons 12 ≺ 3, 13 ≺ 4, and 14 ≺ 23. Theorem 9. There are 2 orders in L_{4}^{∗} that can be determined by 3 binary comparisons, 11 orders in L_{5}^{∗} that can be determined by 4 comparisons, and 180 orders in L_{6}^{∗} that can be determined by 5 comparisons. Proof. First, there are two members of L_{3}^{∗}. One is the lexicographic order ⪯_{1}, which is determined by the two comparisons 1 ≺_{1} 2 and 12 ≺_{1} 3, and hence ⪯ = ⪯_{0} × ⪯_{1} ∈ L_{4} is determined by 1 ≺ 2, 12 ≺ 3 and 123 ≺ 4. The other order ⪯_{2} in L_{3}^{∗} is determined by the three comparisons 1 ≺_{2} 2, 2 ≺_{2} 3 and 3 ≺_{2} 12, and this cannot be represented as a product of ⪯_{0} and another order, hence ⪯ =⪯_{0} × ⪯_{2} ∈ L_{4}^{∗} is determined by 12 ≺ 3, 13 ≺ 4 and 14 ≺ 23. These are the two orders from Example 7.

Next, the 14 members of L_{4}^{∗} are listed in [9]. Here we give the minimal set of determining binary comparisons for each:

1. 2 ≺ 3, 3 ≺ 4, 4 ≺ 12, 14 ≺ 23;

2. 1 ≺ 2, 2 ≺ 3, 4 ≺ 12, 23 ≺ 14;

3. 3 ≺ 12, 12 ≺ 4, 4 ≺ 13, 14 ≺ 23;

4. 1 ≺ 2, 3 ≺ 12, 12 ≺ 4, 4 ≺ 13, 23 ≺ 14;

5. 12 ≺ 3, 3 ≺ 4, 4 ≺ 13, 14 ≺ 23;

6. 1 ≺ 2, 12 ≺ 3, 4 ≺ 13, 23 ≺ 14;

7. 2 ≺ 3, 3 ≺ 12, 13 ≺ 4, 14 ≺ 23;

8. 2 ≺ 3, 3 ≺ 12, 13 ≺ 4, 4 ≺ 23, 23 ≺ 14;

9. 12 ≺ 3, 13 ≺ 4, 14 ≺ 23;

10. 12 ≺ 3, 13 ≺ 4, 4 ≺ 23, 23 ≺ 14;

11. 1 ≺ 2, 2 ≺ 3, 3 ≺ 12, 23 ≺ 4, 4 ≺ 123;

12. 1 ≺ 2, 2 ≺ 3, 3 ≺ 12, 123 ≺ 4;

13. 1 ≺ 2, 12 ≺ 3, 23 ≺ 4, 4 ≺ 123;

14. 1 ≺ 2, 12 ≺ 3, 123 ≺ 4. In this list, every order determined by 4 comparisons is irreducible, and therefore all of the 11 orders in L_{4}^{∗} that are determined by up to 4 binary comparisons can be extended to orders in L_{5}^{∗} determined by exactly 4 binary comparisons. Finally, the last statement about orders in L_{6}^{∗} follows from our computational results which can be found in [3].

8 A Note on Maclagan’s problem

We know that every representable comparative probability order in L_{n} corresponds to a region of the hyperplane arrangement H_{n}. A very interesting question, emphasised by Maclagan in [11, p. 295], is this: How many facets do the polytopes associated with the regions of this hyperplane arrangement have?

It is clear that it is sufficient to solve this problem for comparative probability orders in L_{n}^{∗} — that is, those which satisfy (3). We can find a solution computationally in the cases n = 5 and n = 6, using the following obvious fact:

Proposition 2. Let ⪯ be a representable comparative probability order in L_{n}, and let P be the corresponding convex polytope, which is the closure of a region of the hyperplane arrangement H_{n}. Then the number of significant facets of P equals the number of representable comparative probability orders that are flip-related to ⪯.

The results for n = 5 are given in Tables 1 and 2 below. These numbers are for comparative probability orders from L_{5}^{∗} and L_{6}^{∗}, respectively. The total number of comparative probability orders in P_{5} in each category can be obtained by multiplying by 5! = 120 and, respectively 6! = 720.

Table 1: The number of facets of the polytopes associated with H_{5} corresponding to orders of P_{5}^{∗}

# facets  5  6 7 8 all
# regions 265 177 65 9 512

Table 2: The number of facets of the polytopes associated with the regions of H_{6} corresponding to L_{6}^{∗}

# facets  6  7  8  9  10  11 12 13  all
# orders 38,025 45,536 25,931 10,280 3,400 819 176 20 124,187

It is worth paying attention to the fact that for n = 5 and n = 6 all comparative probability orders with the largest possible number of flips (namely 8 for n = 5, and 13 for n = 6) are representable, and all of their flips are friendly. This does not always happen, however, when an order has the smallest possible number of flips.

Maclagan [11] gave an example of a non-representable comparative probability order in P_{6} whose set of flippable pairs was a subset of the set of all flippable pairs of a representable comparative probability order. She concluded that for n ≥ 6, an order might not be determined by the set of its flippable pairs.

Strictly speaking, we have to talk about the sequence of flippable pairs of an order ⪯, since these pairs may occur in ⪯ in a different order. Strengthening the result of Maclagan, we have found eight sequences of comparisons with the property that each is the sequence of flippable pairs for two different non-representable comparative probability orders in P_{6}. We list these eight sequences below:

( 14 ≺ 5, 15 ≺ 24, 125 ≺ 34, 45 ≺ 16, 26 ≺ 145, 1245 ≺ 36 ); ( 14 ≺ 5, 15 ≺ 24, 125 ≺ 34, 45 ≺ 16, 26 ≺ 14, 36 ≺ 1245 ); ( 5 ≺ 14, 24 ≺ 15, 125 ≺ 34, 16 ≺ 45, 145 ≺ 26, 1245 ≺ 36 ); ( 5 ≺ 14, 24 ≺ 15, 34 ≺ 125, 16 ≺ 45, 145 ≺ 26, 1245 ≺ 36 ); ( 4 ≺ 13, 23 ≺ 14, 125 ≺ 34, 134 ≺ 6, 16 ≺ 234, 1245 ≺ 36 ); ( 4 ≺ 13, 23 ≺ 14, 125 ≺ 34, 134 ≺ 6, 16 ≺ 234, 36 ≺ 1245 ); ( 13 ≺ 4, 14 ≺ 23, 125 ≺ 34, 6 ≺ 134, 234 ≺ 16, 1245 ≺ 36 ); ( 13 ≺ 4, 14 ≺ 23, 34 ≺ 125, 6 ≺ 134, 234 ≺ 16, 1245 ≺ 36 ).

These were found with the help of the Magma [1] system, which we used to determine and analyse several examples of orders on sets of small order. More computational results on the flip relation for n = 5 and n = 6 can be found in [3].

9 Further research

A number of interesting questions remain open. Among those are the following:

• Is the graph P_{n} connected? (See [11, p. 295])

• Can any order in P_{n} be connected to a representable order by a sequence of non-central flips?

• What is a sharp lower bound for the number of flippable pairs of a non-representable comparative probability order? At the moment we can guarantee only one flippable pair (viz. the central one).

• What is a sharp upper bound on the number of flippable pairs for orders in L_{n}? and in P_{n}?

• Are all of the comparative probability orders in P_{n} having the maximum possible number of flippable pairs representable? Are all their neighbors representable?

References

[1] Bosma, W., Cannon, J., and Playoust, C. (1997). The Magma Algebra System I: The User Language, J. Symbolic Comput. 24, 235–265.

[2] Christian, R. and Slinko, A. (2005). Answers to Two Questions of Fishburn on Subset Comparisons in Comparative Probability Orderings, Proceedings of The 4th International Symposium on Imprecise Probabilities and Their Applications (ISIPTA 05), Pittsburg, Pensylvania, 2005, 117–124.

[3] Christian, R., Conder, M. and Slinko, A. (2006). Flippable Pairs and Subset Comparisons in Comparative Probability Orderings and Related Simple Games, The Centre for Interuniversity Research in Qualitative Economics (CIREQ), Cahier 15-2006. University of Montreal, 2006 http://www.cireq.umontreal.ca/publications/15-2006-cah.pdf [4] Conder, M. and Slinko, A. (2004). A counterexample to Fishburn’s conjecture on finite linear quali-

tative probability. Journal of Mathematical Psychology 48, 425–431.

[5] Fine, T., and Gill, J., (1976) The enumeration of comparative probability relations. Annals of Probability 4: 667–673.

[6] de Finetti, B. (1931). Sul significato soggetivo della probabilità, Fundamenta Mathematicae 17, 298–329.

[7] Fishburn, P.C. (1996). Finite Linear Qualitative Probability, Journal of Mathematical Psychology 40, 64–77.

[8] Fishburn, P.C. (1997). Failure of Cancellation Conditions for Additive Linear Orders, Journal of Combinatorial Designs 5, 353–365.

[9] Fishburn, P.C., Pekeč A., Reeds, J.A. (2002). Subset Comparisons for Additive Linear Orders, Mathematics of Operations Research 27, 227–243.

[10] Kraft, C.H., Pratt, J.W., and Seidenberg, A. (1959). Intuitive Probability on Finite Sets, Annals of Mathematical Statistics 30, 408–419.

[11] Maclagan D. (1999) Boolean Term Orders and the Root System B_{n}. Order 15, 279–295.

[12] Orlik, P., and Terao, H. (1992) Arrangements of Hyperplanes. Springer-Verlag, Berlin.

[13] Scott, D. (1964) Measurement structures and inequalities, Journal of Mathematical Psychology 1, 233–247.

[14] Stanley, R. (2004) An Introduction to Hyperplane Arrangements. Lecture Notes for Graduate Stu-

dents. MIT. http://www-math.mit.edu/^{∼}rstan/arrangements/arr.html