A Counterexample to Fishburn’s Conjecture

Draft: December 9, 2003

Marston Conder^{1}  Arkadii Slinko
Department of Mathematics  Department of Mathematics
University of Auckland  University of Auckland
Private Bag 92019 Auckland  Private Bag 92019 Auckland
New Zealand  New Zealand

conder@math.auckland.ac.nz        slinko@math.auckland.ac.nz

Abstract

Kraft, Pratt and Seidenberg (1959) provided an infinite set of axioms which, when taken together with de Finetti’s axiom, gives a necessary and sufficient set of “cancellation” conditions for representability of an ordering relation on subsets of a set by an order-preserving probability measure. Fishburn (1996) defined f(n) to be the smallest positive integer k such that every comparative probability ordering on an n-element set which satisfies the cancellation conditions C_{4}, …, C_{k} is representable. By the work of Kraft, Pratt and Seidenberg (1959) and Fishburn (1996, 1997), it is known that n − 1 ≤ f(n) ≤ n + 1 for all n ≥ 5. Also Fishburn proved that f(5) = 4, and conjectured that f(n) = n − 1 for all n ≥ 5. In this paper we confirm that f(6) = 5, but give counter-examples to Fishburn’s conjecture for n = 7, showing that f(7) ≥ 7. We summarise, correct and extend many of the known results on this topic, including the notion of “almost representability”, and offer an amended version of Fishburn’s conjecture.

1Research supported by N.Z. Centres of Research Excellence Fund (grant UOA 201)

1 Introduction

The topic of this article dates back to fundamental work by Bruno de Finetti [3], who asked whether a certain axiom for a comparative probability ordering relation ⪰ on the subsets of a set is sufficient for the existence of an order-preserving probability measure on that set. For infinite sets, assuming there is a uniform partition into an arbitrary number of events, Savage [10] answered this question positively. For finite sets of cardinality 5 or more, a negative answer to this question was given by Kraft, Pratt and Seidenberg [6]. It became clear from these observations that comparative probability is a broader concept than probability.

Nevertheless, de Finetti’s axioms were very attractive, especially for use in applications where relative frequency characterization of probabilities is not available or meaningful, for example when we have to deal with the socalled “subjective probability” (also called “intuitive probability” or “personal probability”), which is essentially a belief of an individual that some events are more probable than the others [8]. This led to development of comparative probability as a separate area of research (see a recent survey of Giuliana Regoli [9]).

Sometimes comparative probability orderings emerge in circumstances where we cannot speak even about subjective probability. For example, they appeared in an article by Vladimir Danilov [2], who, in the case of dichotomous preferences, characterised all social choice rules which satisfy the famous Arrow’s condition of Independence of Irrelevant Alternatives. It appeared that each such rule corresponds to a comparative probability ordering, and the rule is a weighted majority rule if and only if the comparative probability ordering is representable by an order-preserving probability measure on the set of voters.

Kraft, Pratt and Seidenberg [6] discovered an infinite set of axioms which, when taken together with de Finetti’s axiom, gives a necessary and sufficient set of conditions for representability of an ordering relation on subsets by an order-preserving probability measure. Implicitly, these axioms involved a concept of a multiset, which was not widely understood at the time, and reformulation of these axioms by Scott [11] helped to clarify things. Krantz, Luce, Suppes and Tversky [7] called these axioms cancellation conditions. Peter Fishburn [4, 5] opined that they “play a central role in the representational theory of measurement”, and devoted much effort to their study.

Fishburn introduced a function f(n), which for each positive integer n measures the maximal deviation of a comparative probability ordering on an n-element set from one which arises from an order-preserving probability measure. It follows from [6] that f(n) ≤ n+1. Fishburn then proved in [4, 5] that f(n) ≥ n − 1 for all n ≥ 5, and so combining these two results gives the following bounds for this function: n − 1 ≤ f(n) ≤ n + 1. Fishburn also proved that f(5) = 4, and conjectured that f(n) = n − 1 for all n ≥ 5.

In this paper we confirm that f(6) = 5, but give counter-examples to Fishburn’s conjecture for n = 7 showing that f(7) ≥ 7. We summarise all known results, correcting and extending some of them, and offer an amended version of Fishburn’s conjecture.

2 Preliminaries

To formulate cancellation conditions, let us first recall some other definitions and fix some notation. Here 2^{X} denotes the set of all subsets of a set X.

Definition 1. Let S be a finite set. Any reflexive, complete and transitive binary relation ⪰ on S will be called an order on S. (Note: sometimes this is called a complete pre-order.) Such an order ⪰ gives rise to two other relations ≻ and ∼ on S, defined for all x, y ∈ S 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 ordering on X, if A ≻ ∅ for every non-empty subset A of X, and ⪰ satisfies de Finetti’s axiom, namely for all A, B, C ∈ 2^{X},

A ⪰ B ⟺ A ∪ C ⪰ B ∪ C whenever (A ∪ B) ∩ C = ∅ .  (1)

For convenience, we will further suppose that X = I_{n} = {1, 2, …, n}. Note that 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 a relation ⪰ on 2^{X} by

A ⪰ B if and only if p(A) ≥ p(B).

If p_{i} > 0 for all i, and the probabilities of all events are different, then ⪰ is a comparative probability ordering on X, and any such ordering is called representable [9]. On the other hand, any comparative probability ordering ⪰ which is not obtainable in this way is called non-representable.

It can also be possible that for some measure p on X the probabilities of two or more events coincide, that is p(A) = p(B) when A ⪰ B but A ≠ B.

In this case we have an ordering ⪰ which still satisfies the de Finetti axiom (1), and we call it a weak comparative probability ordering arising from p.

If we have a non-representable comparative probability ordering ⪰ on X, then we cannot specify the exact probability of every event, but if A ≻ B then we can say that A is more probable than B. The class of comparative probability measures is therefore broader than the class of probability measures [6]. A non-representable comparative probability ordering ⪰ on X is said to almost agree with the measure p on X if

A ⪰ B ⟹ p(A) ≥ p(B).  (2)

If such a measure p exists, then the ordering ⪰ is said to be almost representable. When p defines a weak comparative probability ordering on X, the ordering ⪰ may not be representable.

We now recall that a set is a special case of a multiset. Multisets are collections of objects which may include several copies of the same object. If we consider multisets on X, then we allow an element x ∈ X to enter such a multiset M with multiplicity μ_{M}(x), which is a non-negative integer. Multiset union ∪ is an operation over multisets that adds multiplicities of elements, that is, μ_{A∪B}(x) = μ_{A}(x) + μ_{B}(x). See Stanley [12] for more information on multisets.

Definition 3. A linear order ⪰ is said to satisfy the mth cancellation condition C_{m} if for no m distinct comparisons A_{i} ≻ B_{i} (for 1 ≤ i ≤ m), there exist positive integers a_{1}, …, a_{m} such that the following two multiset unions coincide:

⋃_{i=1}^{m} \underbrace{(A_{i} ∪ … ∪ A_{i})}_{a_{i}} = ⋃_{i=1}^{m} \underbrace{(B_{i} ∪ … ∪ B_{i})}_{a_{i}} .  (3)

Alternatively, in the spirit of [11] (and also [13]), condition (3) can be reformulated in terms of characteristic functions of subsets, as follows:

∑_{i=1}^{m} a_{i}χ_{A_{i}} = ∑_{i=1}^{m} a_{i}χ_{B_{i}},

where the characteristic function χ_{S} of the set S is given by χ_{S}(x) = 1 if x ∈ S and χ_{S}(x) = 0 if x ∉ S.

Example 1. The non-representable linear order ⪰ on I_{5} constructed in [6] does not satisfy the condition C_{4} since it contains the following comparisons:

{2, 4, 5} ≺ {1, 3}, {1, 5} ≺ {2, 4}, {3, 4} ≺ {2, 5}, {2} ≺ {4, 5}. (4)

Indeed, the multiset union of the sets on the right and the multiset union of the sets on the left are both equal to the multiset {1, 2^{2}, 3, 4^{2}, 5^{2}}, where powers denote multiplicities. Hence the cancellation condition C_{4} is violated with a_{1} = a_{2} = a_{3} = a_{4} = 1.

Proposition 1 (Kraft-Pratt-Seidenberg [6]). For a comparative probability ordering to be representable, it is necessary and sufficient that all cancellation conditions C_{m} are satisfied.

These cancellation conditions look rather unnatural and complicated. Since they are derived from linear algebra, it is not surprising that they can be made to look much more natural by being reformulated in terms of vectors, as we do later in this paper.

It is clear that any representable linear order satisfies C_{m} for all m ≥ 1. It was also shown in [4] that C_{2} and C_{3} follow from de Finetti’s axiom and properties of linear orders. Hence C_{4} is the first nontrivial cancellation condition.

As was noticed in [6], for n < 5 all comparative probability orderings are representable, but for n = 5 there are non-representable ones. Fishburn [4] showed that all non-representable comparative probability orderings on a 5element set X fail to satisfy C_{4}, and conjectured [4, 5] that any such ordering on an n-element set X, which satisfies C_{4}, …, C_{n−1}, is representable.

In Section 3 we will exhibit counter-examples to this conjecture for n = 7. More precisely, we will construct non-representable comparative probability orderings on a 7-element set X which satisfy C_{4}, C_{5} and C_{6}. In addition, we will show these orderings are almost representable.

We will always assume here that a linear order ⪰ on 2^{X} is a comparative probability ordering. As in [4, 5], we will also assume that 1 ≻ 2 ≻ … ≻ n, which is equivalent to assuming that p_{1} > p_{2} > … > p_{n} for a comparative probability ordering arising from a probability measure p = (p_{1}, …, p_{n}). To every such linear order ⪰, there corresponds a discrete cone C(⪰) in T^{n}, where T = {−1, 0, 1} (as defined in [4]).

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

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

D2. {−x, x} ∩ C ≠ ∅ for every x ∈ T^{n},

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

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

Given a (weak) comparative probability ordering ⪰ on X, we may construct a characteristic vector χ(A, B) = χ_{A} − χ_{B} ∈ T^{n} for every possible comparison A ⪰ B. The cone C(⪰) is then defined as the set of all characteristic vectors χ(A, B), for A, B ∈ 2^{X} such that A ⪰ B. The two axioms of comparative probability guarantee that C(⪰) is indeed a discrete cone (see [4, Lemma 2.1]).

Example 2. For the comparative probability ordering ⪰ from Example 1, the four vectors

(1, −1, 1, −1, −1), (−1, 1, 0, 1, −1), (0, 1, −1, −1, 1), (0, −1, 0, 1, 1) (5)

all belong to C(⪰), and correspond to the four comparisons listed in (4) above.

We will say that a discrete cone C ⊆ T^{n} is generated by a set of vectors V = {v_{1}, …, v_{m}} ⊆ T^{n} if C is the smallest discrete cone containing V. It follows that the cone C(⪰) associated with a comparative probability ordering ⪰ must always contains the discrete cone U in T^{n} generated by

{e_{1} − e_{2}, …, e_{n−1} − e_{n}, e_{n}}.  (6)

We observe that a vector x = (x_{1}, …, x_{n}) ∈ T^{n} belongs to U if and only if

x_{1} ≥ 0, x_{1} + x_{2} ≥ 0, …, x_{1} + x_{2} + … + x_{n} ≥ 0.  (7)

Hence we can reformulate the cancellation conditions as follows [4]:

Proposition 2. A comparative probability ordering ⪰ satisfies the mth cancellation condition C_{m} if and only if for no set {x_{1}, …, x_{m}} of non-zero vectors in C(⪰) do there exist positive integers a_{1}, …, a_{m} such that

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

Proof. Take a vector x_{i} = χ(A_{i}, B_{i}) ∈ C(⪰) for each comparison A_{i} ⪰ B_{i} (for 1 ≤ i ≤ m) involved in Definition 3, and observe that condition (3) is equivalent to the equation a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{m}x_{m} = 0.

Example 3. The four vectors from the cone C(⪰) given in Example 2 add up to the zero vector, hence the corresponding ordering ⪰ is not representable.

Geometrically, what happens is clear. A comparative probability ordering ⪰ is representable if and only if there exists a positive integer-valued vector a ∈ ℝ^{n} such that

x ∈ C(⪰) ⟺ (a, x) > 0 for all x ∈ T^{n} \ {0},

that is, every vector in the cone C(⪰), apart from the zero vector, lies in the open half-space S_{a} = {x ∈ ℝ^{n} | (a, x) > 0}.

Similarly, for a non-representable but almost representable comparative probability ordering ⪰, there exists an integer-valued vector a ∈ ℝ^{n} with non-negative entries such that

x ∈ C(⪰) ⟺ (a, x) ≥ 0 for all x ∈ T^{n} \ {0},

and hence in this case the whole cone C(⪰) must lie in the closed half-space \overline{S_{a}} = \{x ∈ ℝ^{n} | (a, x) ≥ 0\}.

In both cases, the normalised vector a gives us the probability measure, namely p = (a_{1} + … + a_{n})^{−1} (a_{1}, …, a_{n}), from which ⪰ arises or with which it almost agrees.

3 Almost representable orderings

Proposition 3. Let ⪰ be a non-representable but almost representable comparative probability ordering which almost agrees with a probability measure p. Suppose that the mth cancellation condition C_{m} is violated, and that for some non-zero vectors {x_{1}, …, x_{m}} ⊆ C(⪰) and some positive integers a_{1}, …, a_{m}, the condition (8) holds. Then all of the vectors x_{1}, …, x_{m} lie in the hyperplane H_{p} = {x ∈ ℝ^{n} | (p, x) = 0}.

Proof. First note that for every x ∈ C(⪰) which does not belong to H_{p}, we have (p, x) > 0. Hence the condition (8) can hold only when all x_{i} ∈ H_{p}.

Corollary 1. Any almost representable comparative probability ordering ⪰ on an n-element set X, which satisfies C_{4}, …, C_{n}, is representable.

Proof. Suppose that (8) holds for some non-zero vectors x_{1}, …, x_{m} ∈ C(⪰) and positive integers a_{1}, …, a_{m}, where m > 0. As all m vectors x_{1}, …, x_{m} lie in the (n−1)-dimensional subspace H_{p}, we may, using standard linear algebra, reduce the number of vectors in this linear combination to at most n vectors while still having positive coefficients. Hence we may suppose that m ≤ n. However, this is impossible since we assumed that C_{m} is satisfied. Therefore ⪰ must be representable.

Following Fishburn [4], we now define f(n) to be the smallest positive integer k such that every comparative probability ordering on an n-element set which satisfies the cancellation conditions C_{4}, …, C_{k} is representable. Fishburn proved in [4] that f(5) = 4, and in [5] that n − 1 ≤ f(n) ≤ n + 1 for all n ≥ 6, and conjectured that f(n) = n − 1 for all n ≥ 5 (see [5, p.354]).

In the spirit of Kraft, Pratt and Seidenberg [6], we further define g(n) to be the smallest positive integer k such that every almost reresentable comparative probability ordering on an n-element set which satisfies the cancellation conditions C_{4}, …, C_{k} is representable. Clearly g(n) ≤ f(n) for all n, and also by Corollary 1 above, we have the following:

Corollary 2. g(n) ≤ n for all n.

Now Fishburn’s conjecture, if valid, would imply that g(n) ≤ n − 1 for all n. We can confirm that f(6) = 5, which is consistent with Fishburn’s conjecture, but we also prove that g(7) = 7, which refutes it. To do this, we will need the following theorem which simplifies and generalises Theorem 6.1 from [4] (and its generalisation to Lemma 1 in [5]).

Theorem 1 (Construction method 1). Let X = {x_{1}, …, x_{m}}, m ≥ 4, be a system of non-zero vectors from T^{n}, such that ∑_{i=1}^{m} a_{i}x_{i} = 0 for some positive integers a_{1}, …, a_{m}, and such that no proper subsystem X′ ⊂ X is linearly dependent with positive coefficients. Suppose further that the m × n matrix A having the vectors x_{1}, …, x_{m} as its rows has the property that Ab = 0 for some positive integer-valued vector b = (b_{1}, …, b_{n}) with b_{1} > b_{2} > … > b_{n} > 0, and that

Span{x_{1}, …, x_{m}} ∩ T^{n} = {±x_{1}, …, ±x_{m}}.

Let C(⪰) be the discrete cone belonging to the weak comparative probability ordering which arises from the measure p = (b_{1} +…+b_{n})^{−1} (b_{1}, …, b_{n}), that is, C(⪰) = {x ∈ ℝ^{n} | (x, b) ≥ 0}. Then the discrete cone

C′ = C(⪰) \ {−x_{1}, …, −x_{m}}

corresponds to an almost representable comparative probability ordering which almost agrees with p, and satisfies C_{i} for all i < m, but does not satisfy C_{m}.

Proof. We first note that {±x_{1}, …, ±x_{m}} ⊆ H_{b} = {x ∈ ℝ^{n} | (b, x) = 0}. Next (e_{i} − e_{i+1}, b) = b_{i} − b_{i+1} > 0 for 1 ≤ i < n, and also (e_{n}, b) = b_{n} > 0, so the property D1 holds for the cone C′. Property D2 holds for C′ because it holds for C(⪰) and when we remove vectors −x_{1}, …, −x_{m} from C′ the vectors x_{1}, …, x_{m} remain in C′. Finally let us prove D3. Suppose that y, z ∈ C′ and y + z ∈ T^{n}, but y + z ∉ C′. Since y + z ∈ C(⪰) \ C′, we deduce that y + z = −x_{i} for some i. Moreover, y, z ∈ H_{b}, since otherwise (y + z, b) = (y, b) + (z, b) > 0. Hence y = x_{j} for some j and z = x_{k} for some k, but from this it follows that x_{i} + x_{j} + x_{k} = 0, a contradiction since |X| = m ≥ 4 and hence no three rows of A may have sum zero.

Suppose now that some violation of C_{k} occurs, say

c_{1}y_{1} + c_{2}y_{2} + ⋯ + c_{k}y_{k} = 0,

with positive integers c_{1}, …, c_{k} and y_{i} ∈ C(⪰) for 1 ≤ i ≤ k, where k < m. If (y_{i}, b) > 0 from some i, then (0, b) = (c_{1}y_{1} + c_{2}y_{2} + ⋯ + c_{k}y_{k}, b) = c_{1}(y_{1}, b) + c_{2}(y_{2}, b) + … + c_{k}(y_{k}, b) > 0, a contradiction, hence y_{i} ∈ H_{b} for all i, and therefore {y_{1}, …, y_{k}} ⊆ {x_{1}, …, x_{m}}, which is impossible. On the other hand, C_{m} fails because ∑_{i=1}^{m} a_{i}x_{i} = 0.

A major difference between our theorem and Theorem 6.1 of [4] is that we claim almost representability of the constructed ordering. Using this, we can now prove the following:

Theorem 2. f(7) ≥ g(7) = 7.

Proof. Consider the following 7 × 7 matrix

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

Denote the rows of A by x_{1}, …, x_{7}. As the null space of A^{T} is spanned by the vector (1, 1, 1, 1, 1, 1, 1), we can see that x_{1} + x_{2} + … + x_{7} = 0 and that no six rows of A are linearly dependent. We also observe that Ab = 0 for b = (27, 25, 24, 22, 19, 15, 11). Let us take the probability measure p = \frac{1}{116}(27, 25, 24, 22, 19, 15, 11), and now consider the weak comparative probability ordering on I_{7} = {1, 2, 3, 4, 5, 6, 7} that arises from p.

Ignoring braces when writing subsets, and listing only half of all terms (as A ⪰ B if and only if B̄ ⪰ Ā), we may describe this ordering by the following sequence (given in reverse order for simplicity):

∅ ≺ 7 ≺ 6 ≺ 5 ≺ 4 ≺ 3 ≺ 2 ≺ 67 ≺ 1 ≺ 57 ≺ 47 ≺ 56 ≺ 37 ≺ 27 ≺ 46 ≺ 17 ≺ 36 ≺ 26 ≺ 45 ≺ 16 ≺ 35 ≺ 25 ≺ 567 ≺ 15 ∼ 34 ≺ 24 ≺ 467 ≺ 23 ∼ 14 ≺ 367 ≺ 13 ∼ 267 ≺ 457 ∼ 12 ≺ 167 ≺ 357 ≺ 257 ≺ 456 ≺ 157 ∼ 347 ≺ 247 ∼ 356 ≺ 256 ≺ 237 ∼ 147 ≺ 156 ∼ 346 ≺ 246 ∼ 137 ≺ 127 ≺ 236 ∼ 146 ≺ 345 ≺ 136 ∼ 245 ≺ 4567 ∼ 126 ≺ 235 ∼ 145 ≺ 3567 ≺ 135 ∼ 2567 ≺ 125 ∼ 234 < ….

The only equivalences in the first half of this sequence are these:

15 ∼ 34, 157 ∼ 347, 156 ∼ 346, 125 ∼ 234,
23 ∼ 14, 237 ∼ 147, 236 ∼ 146, 235 ∼ 145,
13 ∼ 267, 135 ∼ 2567,
457 ∼ 12, 4567 ∼ 126,
246 ∼ 137,
136 ∼ 245,
247 ∼ 356.

Note that in each row of the above list, all equivalences are the consequences of the leftmost equivalence, and all contribute the same pair of vectors ±x_{i} to the cone C(⪰), where x_{1}, …, x_{7} are the rows of A. All equivalences from the second half of the sequence are also consequences of these. It follows that

Span{x_{1}, …, x_{7}} ∩ T^{7} = {±x_{1}, …, ±x_{7}}.

We may now apply Theorem 1, to deduce the existence of a non-representable comparative probability ordering on I_{7}, which satisfies C_{4}, C_{5} and C_{6}.

Note that the example given in the above proof fails the cancellation condition C_{7} with (a_{1}, …, a_{7}) = (1, 1, 1, 1, 1, 1, 1). There are hundreds of other examples with the same property. Another interesting example will be given in Section 4.

4 Alternative form of cancellation conditions

In the spirit of Fishburn’s earlier paper [4], we now introduce an alternative form of cancellation conditions.

Definition 5. A comparative probability ordering ⪰ is said to satisfy the mth cancellation condition C_{m}^{†} if for no set {x_{1}, …, x_{k}} of non-zero vectors in C(⪰) do there exist positive integers a_{1}, …, a_{k} such that

a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{k}x_{k} = 0  (9)

and ∑_{i=1}^{k} a_{i} = m.

Note here that while the condition C_{m} emphasises the total number of distinct comparisons A_{i} ≻ B_{i} involved, the alternative condition C_{m}^{†} is more concerned with the total number of (not necessarily distinct) comparisons actually required for the sum.

It is clear (and was observed by Fishburn [4]) that a comparative probability ordering satisfies C_{m} for all m ≥ 4 if and only if it satisfies C_{m}^{†} for all m ≥ 4. It follows that these alternative cancellation conditions can also be used for measuring the degree of deviation of a comparative probability ordering from one that arises from a probability measure.

Hence we may define f^{†}(n) to be the smallest positive integer k such that every comparative probability ordering on an n-element set, which satisfies the cancellation conditions C_{4}^{†}, …, C_{k}^{†}, is representable. The corresponding analogue of g(n) can also be introduced. We define g^{†}(n) to be the smallest positive integer k such that every almost reresentable comparative probability ordering on an n-element set, which satisfies the cancellation conditions C_{4}^{†}, …, C_{k}^{†}, is representable. Obviously, f^{†}(n) ≥ g^{†}(n), and also f^{†}(n) ≥ f(n) and g^{†}(n) ≥ g(n) for all n. Also Kraft, Pratt and Seidenberg effectively commented without proof that f^{†}(n) ≤ (n + 1)! (see [6, p. 413]).

Despite such a large upper bound, it appears that to date no examples have been found for which f^{†}(n) ≠ f(n) or g^{†}(n) ≠ g(n). We show below that f^{†}(7) ≥ g^{†}(7) ≥ 8, which, together with our earlier finding that g(7) = 7, proves that g^{†}(7) > g(7). To do this, we will need a variation of Theorem 1.

Theorem 3 (Construction method 2). Let X = {x_{1}, …, x_{k}}, k ≥ 4, be a system of non-zero vectors from T^{n} such that ∑_{i=1}^{k} a_{i}x_{i} = 0 for some non-negative integers a_{1}, …, a_{k} with ∑_{i=1}^{k} a_{i} = m, and such that for every equation ∑_{i=1}^{k} a′_{i}x_{i} = 0 with positive integer coefficients a′_{i} it happens that ∑_{i=1}^{k} a′_{i} ≥ m. Suppose further that the k × n matrix A having the vectors x_{1}, …, x_{k} as its rows has the property that Ab = 0 for some positive integervalued vector b = (b_{1}, …, b_{n}) with b_{1} > b_{2} > … > b_{n} > 0, and that

Span{x_{1}, …, x_{k}} ∩ T^{n} = {±x_{1}, …, ±x_{k}}.

Let C(⪰) be the discrete cone belonging to the weak comparative probability ordering which arises from the measure p = (b_{1} +…+b_{n})^{−1} (b_{1}, …, b_{n}), that is, C(⪰) = {x ∈ ℝ^{n} | (x, b) ≥ 0}. Then the discrete cone

C′ = C(⪰) \ {−x_{1}, …, −x_{m}}

corresponds to an almost representable comparative probability ordering which almost agrees with p, and satisfies C_{i}^{†} for all i < m, but does not satisfy C_{m}^{†}.

Proof. The proof is completely analogous to the proof of Theorem 1.

Theorem 4. f^{†}(7) ≥ g^{†}(7) ≥ 8.

Proof. Consider the following 7 × 7 matrix:

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

and let x_{1}, …, x_{7} denote its rows. It is easy to check that

x_{1} + … + x_{6} + 2x_{7} = 0,

that is, condition C_{7} is violated with (a_{1}, …, a_{7}) = (1, 1, 1, 1, 1, 1, 2), and there does not exist any “smaller” violation. Calculations also show that

Span{x_{1}, …, x_{7}} ∩ T^{7} = {±x_{1}, …, ±x_{7}},

and Ap = 0 for the probability measure p = \frac{1}{148}(48, 40, 27, 16, 12, 10, 7). For the weak comparative probability ordering determined by this measure, the equivalences are all consequences of one of the following seven: 146 ∼ 237, 15 ∼ 3467, 17 ∼ 345, 2457 ∼ 13, 347 ∼ 26, 3567 ∼ 24 and 23 ∼ 157. Again this is a non-representable but almost representable comparative probability ordering on I_{7}, but is one which satisfies C_{4}^{†}, C_{5}^{†}, C_{6}^{†}, and C_{7}^{†}, while failing C_{8}^{†} with (a_{1}, …, a_{7}) = (1, 1, 1, 1, 1, 1, 2).

5 Account for n = 5 and n = 6

The results of this section were obtained with the help of the computer algebra system Magma [1], using the same techniques of enumeration as described by Fishburn in [4, Section 4], but also checking the results for both representability and almost representability (using techniques of linear programming). Enumeration of the orderings required less than 60 seconds of computer time for the case n = 5, and 12 hours for the case n = 6, while determining representability (and/or partial representability) took just a little longer.

Theorem 5. There are 546 different comparative probability orderings of the subsets of I_{5} = {1, 2, 3, 4, 5}, of which 516 are representable, and the remaining 30 are almost representable.

In particular, our computations show that Fishburn’s claimed total number of 561 orderings in [4] is incorrect.

Note also that it is quite easy to decide if any given one of these orderings is almost representable. For example, one of the 30 non-representable orderings (the last in the list at the end of Section 4 of [4]) is completely determined by the four mutually-cancelling comparisons 234 ⪰ 15, 1 ⪰ 245, 25 ⪰ 34, 45 ⪰ 2, and the extra conditions 235 ≻ 1 and 1 ≻ 23. Now if this ordering arises from the probability measure p = (p_{1}, …, p_{5}), then the first four comparisons require that p_{1} = 2p_{4} + 2p_{5}, p_{2} = p_{4} + p_{5} and p_{3} = 2p_{5}, and the two extra conditions require that 2p_{5} > p_{4} and p_{4} > p_{5}. Choosing p_{4} = 3 and p_{5} = 2, for instance, we see that the given ordering almost agrees with the probability measure p = \frac{1}{24}(10, 5, 4, 3, 2).

Theorem 6. There are exactly 169444 different comparative probability orderings of the subsets of I_{6} = {1, 2, 3, 4, 5, 6}. Of these, 124187 are representable, while 45257 are not. Of the 45257 that are non-representable, 44987 fail C_{4} with a_{1} = a_{2} = a_{3} = a_{4} = 1, while the other 270 satisfy C_{4} but fail C_{5} with a_{1} = a_{2} = a_{3} = a_{4} = a_{5} = 1. Moreover, of these 45257 orderings that are non-representable, 40055 are almost representable, while the other 5202 are not. In particular, of the 44987 non-representable orderings that fail C_{4}, exactly 39785 are almost representable, while the other 5202 are not, and all of the 270 non-representable orderings that satisfy C_{4} but fail C_{5} are almost representable. Hence there are exactly 164242 almost representable orderings, and of these, 124187 are representable, while 40055 are not, with 39785 failing C_{4} with a_{1} = a_{2} = a_{3} = a_{4} = 1, and the other 270 satisfying C_{4} but failing C_{5} with a_{1} = a_{2} = a_{3} = a_{4} = a_{5} = 1.

We say that the dual of a comparison A ≻ B is the comparison B ≻ A, and then the dual of a set of comparisons is the set of their duals. In the case n = 5, Fishburn categorised the 30 orderings that are non-representable into five types (and their duals) according to the violations of C_{4} that they exhibit, and noted that some orderings may exhibit more than one type of violation. For the case n = 6, we find that up to duality there are 423 such types, of which 385 (and their duals) involve four comparisons that together fail C_{4} with a_{1} = a_{2} = a_{3} = a_{4} = 1, while the remaining 38 (and their duals) involve five comparisons that together fail C_{5} with a_{1} = a_{2} = a_{3} = a_{4} = a_{5} = 1.

We note that the first example of a comparative probability ordering on a 6-element set which fails to be almost representable was constructed by Kraft, Pratt, and Seidenberg [6]. Our computations provide the following extension to the results of Fishburn [4, 5]:

Corollary 3. f(6) = g(6) = f^{†}(6) = g^{†}(6) = 5.

6 Conclusion and Open Questions

Kraft, Pratt, and Seidenberg [6] left open the question of whether or not all comparative probability orderings on a 5-element set are almost representable. We have answered this question by showing that all of them are indeed almost representable.

We know now that f(5) = g(5) = 4, and f(6) = g(6) = 5, but g(7) = 7. The question remains open as to whether f(7) is equal to 7 or 8. Nevertheless, it is clear that the situation for n ≥ 7 is different to that for n ∈ {5, 6}, so Fishburn’s conjecture is no longer adequate. We propose amending it to the following:

Conjecture: f(n) = g(n) = n for all n ≥ 7.

Some more research will have to be undertaken before any reasonable conjecture about f^{†}(n) and g^{†}(n) can be formulated.

References

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

[2] Danilov, V.I.: “Aggregation of dichotomic preferences,” Mathematical Social Sciences 13 (1987), 49–58.

[3] de Finnetti, B.: “Sul significato soggetivo della probabilità,” Fundamenta Mathematicae 17 (1931), 298–329.

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

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

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

[7] Krantz, D.H., Luce, R.D., Suppes, P., and Tversky, A.: Foundations of Measurement, Vol. 1, Academic Press, 1971.

[8] Luce, R.D., and Suppes, P.: “Preference, Utility, and Subjective Probability.” In: Luce, R.D., Bush, R.R., Galanter, E. (Eds.) Handbook of Mathematical Psychology, Vol. III, (Wiley), 1965, pp. 249–410.

[9] Regoli, G.: “Comparative probability orderings,” preprint on the Imprecise Probabilities Project website http://ippserv.rug.ac.be.

[10] Savage, L.J.: The Foundations of Statistics, New York, Wiley, 1954.

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

[12] Stanley, R.P.: Enumerative Combinatorics, Vol.1, Cambridge University Press, 1997.

[13] Suppes, P.: “Measurement of Belief,” Journal of the Royal Statistical Society Series B, 36 (1974), 160–191.