Orders on Multisets and Discrete Cones

Marston Conder Department of Mathematics, University of Auckland

                    m.conder@auckland.ac.nz

Simon Marshall Department of Mathematics, Princeton University

                    slm@math.princeton.edu

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

                    a.slinko@auckland.ac.nz

Abstract. We study additive representability of orders on multisets (of size k drawn from a set of size n) which satisfy the condition of Independence of Equal Submultisets (IES) introduced by Sertel and Slinko (2002, 2007). Here we take a geometric view of those orders, and relate them to certain combinatorial objects which we call discrete cones. Following Fishburn (1996) and Conder and Slinko (2004), we define functions f(n, k) and g(n, k) which measure the maximal possible deviation of an arbitrary order satisfying the IES and an arbitrary almost representable order satisfying the IES, respectively, from a representable order. We prove that g(n, k) = n − 1 whenever n ≥ 3 and (n, k) ≠ (5, 2). In the exceptional case, g(5, 2) = 3. We also prove that g(n, k) ≤ f(n, k) ≤ n and establish that for small n and k the functions g(n, k) and f(n, k) coincide.

AMS classification: 06F25, 91B16

Keywords: multiset, linear order, additive representability, Independence of Equal Submultisets

∗ Corresponding author.

1 Introduction

One of the most common preference orderings in economics is that of bundles of commodities, and one of the most common problems is to rationalise such an ordering, representing it by a numerical order-preserving function of utilities of those commodities. The space of commodity bundles can be naturally represented as a subset of a Cartesian product X = ∏_{i=1}^{n} X_{i}, where X_{i} can vary depending on the model.

It is often assumed that each X_{i} has a very rich structure and is isomorphic to a subset of ℝ, so that X becomes a subset of a finite-dimensional Euclidean space ℝ^{n}. This model corresponds to existence of n types of infinitely divisible goods. An element x = (x_{1}, …, x_{n}) ∈ X denotes a bundle with n goods, and x_{i} shows the quantity of the ith good. This case was extensively studied by J. von Neumann and O. Morgenstern [22], J. Marshak [13], I.N. Herstein and J. Milnor [8] and others.

Another extreme case is when elements in each X_{i} belong to the same class but cannot be compared and measured in units of something, such as when X_{1} = {apple, banana} and X_{2} = {pepsi, coca cola}. In this particular case the X_{i} have no structure at all and are arbitrary finite sets. This case was studied by Krantz et al [12] and significant progress was made on it by P. Fishburn [7]. The case most studied is one where every X_{i} consists of just two elements. In this case elements of the Cartesian product 2^{[n]} can be identified with subsets of [n] = {1, 2, …, n} and we obtain the classical case of comparative probability orders [17, 15] for which the basic rationality condition is the following axiom of de Finetti:

Definition 1. A linear order ⪯ on 2^{[n]} is called a comparative probability if it satisfies the following de Finetti axiom: for any A, B ∈ 2^{[n]} and any C ∈ 2^{[n]} such that C ∩ (A ∪ B) = ∅

A ⪰ B ⟺ A ∪ C ⪰ B ∪ C.  (1)

There is an important intermediate case which has not been studied systematically so far. We often have n types of goods which are divisible to a certain extent but not infinitely divisible (such as money, cars, houses etc.). These goods can be measured only in whole units of some quantity which is further indivisible. Let us call these goods finitely divisible. If X_{i} denotes the quantity of a certain finitely divisible good, then each X_{i} has the structure of the monoid of nonnegative integers ℕ. This model has numerous useful interpretations.

When we are in the situation of the X_{i} representing finitely divisible goods, the bundle x = (x_{1}, …, x_{n}) ∈ X can be replaced with the n-tuple of nonnegative integers (k_{1}, …, k_{n}), where k_{i} is the number of indivisible units that are contained in x_{i}. The main motivating example for this study comes from Sertel and Kalaycıoğlu [18] and Sertel and Slinko [19, 20].

Example 1. Consider a k-member parliament or committee. There are n political parties to which the members are affiliated. Here i is the type of political party and k_{i} is the number of members of this political party elected to the parliament. The total number of elected parliamentarians in parliament x = (k_{1}, …, k_{n}) is k = ∑_{i=1}^{n} k_{i}. The relation x ⪰ y means that a voter thinks parliament x is at least as good as parliament y.

Mathematically speaking, a parliament is a multiset on the set of political parties [n] = {1, 2, …, n}. Unlike sets, multisets allow multiple entry of elements, so a parliament can be represented as a multiset M = {1^{k_{1}}, 2^{k_{2}}, …, n^{k_{n}}}, where i^{k_{i}} means that element i (party i) enters the multiset (the parliament) k_{i} times. The number k_{i} is called the multiplicity of i in M. The multiset M can also be described as ([n], μ) where μ: [n] → ℕ is the multiplicity function given by μ(i) = k_{i} for all i ∈ [n]. The sum of multiplicities k = k_{1} + k_{2} + … + k_{n} is called the cardinality of M.

The set of all multisets of fixed cardinality k on the set [n] will be denoted by P_{k}[n]. The set of all multisets will be denoted P[n] = ⋃_{k=1}^{∞} P_{k}[n]. The union M_{1} ∪ M_{2} of two multisets M_{1} = ([n], μ_{1}) and M_{2} = ([n], μ_{2}) is again a multiset on [n] whose multiplicity function is defined as μ_{1} + μ_{2}. Similarly, the intersection M_{1} ∩ M_{2} is given by the multiplicity function min(μ_{1}, μ_{2}), where this minimum is defined pointwise on [n]. Next, we say that M_{1} is a submultiset of M_{2}, if μ_{1}(i) ≤ μ_{2}(i) for all i ∈ [n], and we denote this by M_{1} ⊆ M_{2}. For more information on multisets see, for example, [21].

Definition 2. An order ⪰ on P_{k}[n] (or on P[n]) is said to be (additively) representable if there exist nonnegative real numbers u_{1}, …, u_{m} such that for all M_{1} = ([n], μ_{1}) and M_{2} = ([n], μ_{2}),

M_{1} ⪰ M_{2} ⟺ ∑_{i=1}^{n} μ_{1}(i)u_{i} ≥ ∑_{i=1}^{n} μ_{2}(i)u_{i}.  (2)

We will refer to the coefficients u_{1}, …, u_{n} as the utilities; here the word ‘utility’ serves as a generic name for a number of related but distinct concepts.

Additive representability of preference orders is well-established topic of study. A systematic discussion of this idea and its history can be found in the monograph [23]. In the most studied case of comparative probability, de Finetti’s axiom (1) is not sufficient for additive representability — indeed, one needs infinitely many additional cancellation conditions [11]. Because of this, it is quite surprising that for an order ⪰ on P[n], the multiset analogue of (1), in which the union is understood as the multiset union and the condition C ∩ (A ∪ B) = ∅ is dropped, is nearly sufficient for additive representability.

It was discovered by Robbiano [16] and rediscovered by Danilov [3] and Martin [14] that for any order satisfying the multiset analogue of de Finetti’s axiom, there is an m × n matrix of weights, with m ≤ n, that can be used to determine the order in which two multisets A and B appear in ⪰. The weights from the first row are used first, but if the total weights of A and B relative to this system of weights are the same, then the weights from the second row are used, and so on. Multisets with the multiset analogue of (1) have been extensively studied in computer science with regard to termination of rewriting systems; see [4].

We now note that there is an essential difference between this framework and Example 1. In the latter, the total number of objects k = ∑_{i=1}^{n} k_{i} is fixed, making us deal with an order on P_{k}[n], and there is no obvious analogue of de Finetti’s axiom. It is exactly the framework of Example 1 that Sertel and Slinko studied in [19, 20] and we continue to study in this article. We are interested in additive representation of orders on P_{k}[n]. This case is markedly different from the case of orders on P[n], and is much more similar to the case of comparative probability, explaining why Fishburn’s ideas could be made to work.

By an order we understand any reflexive, complete and transitive binary relation, which will be denoted as ⪰. If it is also antisymmetric, it will be called a linear order. The notation x ≻ y will mean x ⪰ y but not y ⪰ x.

The problem considered here and in many similar situations (as in [5, 7, 11, 12] for example) is to impose minimal conditions on the order ⪰ on P_{k}[n] to guarantee its representability. This means that the voter must be (to a certain extent) rational in order for their preferences to be representable. The question is, just how rational they should be.

The following basic rationality condition was suggested by Sertel and Slinko [19, 20], who called it consistency. Here we give a slightly different (but equivalent) definition of this concept, which makes it a close relative to the concept of the Independence of Equal Coordinates [23, p.30].

Definition 3. An order ⪰ on P_{k}[n] is said to satisfy the Independence of Equal Submultisets condition (IES) if for every two multisets U and V of the same cardinality j with 1 ≤ j ≤ k − 1, the relation U ∪ W ⪰ V ∪ W holds for one particular multiset W of cardinality k − j if and only if this relation holds for every multiset W of cardinality k − j.

This is also an analogue of de Finetti’s axiom for comparative probability orders [5, 6].

If ⪰ is an order on P_{k}[n] which satisfies the IES, then, for all j in the range 1 ≤ j ≤ k − 1, it induces an order ⪰_{j} on P_{j}[n], which also satisfies the IES. To define ⪰_{j} we take any W ∈ P_{k−j}[n], and then for any U, V ∈ P_{j}[n], we set

U ⪰_{j} V if and only if U ∪ W ⪰ V ∪ W.  (3)

By the IES, this will not depend on the choice of the particular multiset W. The orders ⪰_{j} will be called orders associated with ⪰. These orders, as it was proved in Lemma 1 of [20], satisfy the following property.

Lemma 1. Let ⪰ be an order on P_{k}[n] which satisfies the IES and ⪰_{i} be the corresponding order on P_{i}[n] for i = 1, …, k. Suppose that U, V ∈ P_{ℓ}[n], R, Q ∈ P_{h}[n], and U ⪰_{ℓ} V, R ⪰_{h} Q with ℓ+h ≤ k. Then U ∪R ⪰_{ℓ+h} V ∪Q.

In this paper, without loss of generality, we assume that ⪰ induces a linear order on [n] (which is naturally identified with P_{1}[n]), and that this linear order satisfies the condition

1 ≻_{1} 2 ≻_{1} 3 ≻_{1} … ≻_{1} n.  (4)

It is important that we rule out the possibility of indifferences here. This does not restrict our framework, since if j ∼ i for some j > i, then we may view the elements i, i+1, …, j as indistinguishable, and then we may simplify the framework by not making any distinction between these elements.

The next definition is technical but very important.

Definition 4. We say that an order ⪰ on P_{k}[n] satisfies the mth cancellation condition C_{m} if for no m distinct comparisons A_{i} ⪰ B_{i}, i = 1, 2, …, m, among which A_{i} ≻ B_{i} for at least one i, 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}} .  (5)

This is a complete analogue of the mth cancellation condition formulated by Kraft, Pratt and Seidenberg [11] for orders on the power set 2^{[n]}. As in [11, Theorem 2] it is easy to show that for an order ⪰ on P_{k}[n] to be representable it is necessary and sufficient that all cancellation conditions C_{2}, C_{3}, … are satisfied. This will become obvious later, when we reformulate this statement in vector form, in which the cancellation conditions look much more natural.

Example 2. The nonrepresentable linear order A_{4} on P_{2}[4] given by

\{1^{2}\} ≻ \{12\} ≻ \underline{\{13\} ≻ \{2^{2}\}} ≻ \underline{\{23\} ≻ \{14\}} ≻ \underline{\{24\} ≻ \{3^{2}\}} ≻ \{34\} ≻ \{4^{2}\}

and constructed in [19] does not satisfy the condition C_{3}, since it contains the following comparisons (underlined above):

{13} ≻ {2^{2}}, {23} ≻ {14}, {24} ≻ {3^{2}}.  (6)

Indeed, the union of the multisets on the right and the union of the multisets on the left are both equal to the multiset {12^{2}3^{2}4}. Thus C_{3} is violated with a_{1} = a_{2} = a_{3} = 1.

In order to convince the reader that the above cancellation conditions are natural, we note that the IES for ⪰ follows from C_{2}, since it cannot be true that A ∪ W_{1} ⪰ B ∪ W_{1} and B ∪ W_{2} ≻ A ∪ W_{2}. When W_{1} = W_{2} = ∅ we obtain also antisymmetry. It is also obvious that C_{2} follows from the IES and antisymmetry, and hence for antisymmetric orders, condition C_{2} and the IES are equivalent. Transitivity of ⪰ is implied by C_{3} as it is impossible to have simultaneously A ⪰ B, B ⪰ C, and C ≻ A.

It should be noted that, although transitivity follows from C_{3}, it is weaker than C_{3} (see Example 2). It is of special interest when the IES implies C_{3}, C_{4}, …, and hence representability of ⪰. For n = 3, Sertel and Slinko [19] showed that the IES implies C_{i} for all i ≥ 3, and hence all orders on P_{k}[3] which satisfy the IES are representable, for all k ≥ 1. This is no longer true for n > 3 as shown in the same paper. Nevertheless, sometimes something good can be said about ⪰ even when it is not representable.

Definition 5. We will say that an order ⪰ on P_{k}[n] is almost representable if there exist nonnegative real numbers u_{1}, …, u_{m} such that for all M_{1} = ([n], μ_{1}) and M_{2} = ([n], μ_{2}) belonging to P_{k}[n],

M_{1} ⪰ M_{2} ⟹ ∑_{i=1}^{n} μ_{1}(i)u_{i} ≥ ∑_{i=1}^{n} μ_{2}(i)u_{i}.  (7)

This is a complete analogue of the almost representability condition for comparative probability orders [11, 15].

Almost representable orders satisfying the IES need not be representable (see [20, Sect. 3]). Such linear orders may exist only when the representable order associated with utilities u_{1}, …, u_{m} is non-linear and some multisets are tied. There are also linear orders which satisfy the IES but still fail to be almost representable (see [20, Sect. 4]). More precisely, examples are given in [20] of a non-representable but almost representable linear order in P_{2}[4], and a linear order in P_{3}[4] that fails to be almost representable; both satisfy the IES but fail to satisfy C_{3}.

Thus it is clear that to secure representability, sometimes we have to assume more than the IES (or C_{2}, which is the same), and we may need also some of the conditions C_{3}, C_{4}, . . .. It is important to find out how far do we have to go, and how many cancellation conditions we need to assume before we can guarantee the representability of an order on P_{k}[n]. The current paper is devoted to this particular question. All results will be formulated in terms of the following two functions.

For n ≥ 3 and k ≥ 2, let f(n, k) be the smallest positive integer such that any linear order on P_{k}[n] which satisfies C_{2}, C_{3}, …, C_{f(n,k)} is representable. Similarly, let g(n, k) be the smallest positive integer such that any almost representable linear order on P_{k}[n] which satisfies C_{2}, C_{3}, …, C_{g(n,k)} is representable. Clearly, g(n, k) ≤ f(n, k) for all n and k. Sertel and Slinko [20] showed in this notation that f(3, k) = g(3, k) = 2 for all k ≥ 1.

In this paper we will completely describe the function g(n, k). Specifically, we will show that g(n, k) = n − 1 for all n ≥ 3 and k ≥ 2 apart from the pair (n, k) = (5, 2), for which g(5, 2) = 3. As for the function f(n, k), the best we can prove in general is that n − 1 ≤ f(n, k) ≤ n whenever (n, k) ≠ (5, 2). Computer-assisted calculations show that g(n, k) = f(n, k) for small values of n and k (namely, for (n, k) = (4, 2), (4, 3), (5, 2), (5, 3), (6, 2) and (7, 2)), and so we conjecture that this is true in general.

To obtain these results we take a geometric view of linear orders, and define discrete cones (similar to those defined by Fishburn [6] for comparative probability orders on a set). We will show that to every order ⪰ on P_{k}[n] satisfying the IES there corresponds a discrete cone C(⪰), and vice versa.

We are grateful to an anonymous referee and the action editor Jean-Paul Doignon for numerous valuable suggestions.

2 Discrete Cones

To define discrete cones we need the following notation. Let {e_{1}, …, e_{n}} be the standard basis of ℝ^{n}, let M_{k} = {−k, …, −1, 0, 1, …, k} and let M_{k}^{n} be the nth Cartesian product of M_{k}. Next, for x = (x_{1}, …, x_{n}) ∈ M_{k}^{n}, define

|x| = ∑_{i=1}^{n} |x_{i}|,
x^{+} = (v_{1}, …, v_{n}), where v_{i} = max(x_{i}, 0), and
x^{−} = (u_{1}, …, u_{n}), where u_{i} = min(x_{i}, 0),

so that x = x^{+} + x^{−} and |x| = |x^{+}| + |x^{−}|. Similarly, for any two vectors x = (x_{1}, …, x_{n}) ∈ M_{k}^{n} and y = (y_{1}, …, y_{n}) ∈ M_{k}^{n}, let

max(x, y) = (w_{1}, …, w_{n}), where w_{i} = max(x_{i}, y_{i}).

Finally, we define T_{k}^{n}, a set in which the cones associated with orders on P_{k}[n] will live, by

T_{k}^{n} = {x ∈ M_{k}^{n} | |x^{−}| = |x^{+}| ≤ k} .

This consists of all vectors in M_{k}^{n} which are orthogonal to the vector n = (1, 1, …, 1) and whose sum of positive entries is no greater than k.

Given a multiset M = ([n], μ) ∈ P_{k}[n], let χ(M) = (μ(1), …, μ(n)) be the characteristic function of M. Given an order ⪰ on P_{k}[n], for every comparison M ⪰ N we construct a vector χ(M, N) = χ(M) − χ(N) ∈ T_{k}^{n}. We can now define C(⪰) to be the set of all vectors χ(M, N) for all valid comparisons M ⪰ N, where M, N ∈ P_{k}[n]. Note that, if M ∩ N ≠ ∅, then for M′ = M \(M ∩N) and N′ = N \(M ∩N) we have χ(M, N) = χ(M′, N′). This means that for any order ⪰ which satisfies the IES, then C(⪰) is welldefined. Now we will give an abstract definition of this object.

Definition 6. A subset C ⊆ T_{k}^{n} is said to be a discrete cone (or simply, a cone) in T_{k}^{n} if the following conditions hold:

D1. e_{i} − e_{i+1} ∈ C \ (−C) for 1 ≤ i ≤ n − 1,
D2. 0 ∈ C, and for all x ∈ T_{k}^{n} \ {0} either x ∈ C or −x ∈ C (but not both),
D3. x + y ∈ C whenever x, y ∈ C and | max(−x^{−}, y^{+})| ≤ k.

We note that if m ≤ k and ⪰_{m} is the order on P_{m}[n] associated with ⪰, then C(⪰_{m}) ⊆ C(⪰). Furthermore:

Proposition 1. If a linear order ⪰ on P_{k}[n] satisfies (4) and the IES, then C(⪰) satisfies conditions D1 to D3 and so is a discrete cone. On the other hand, every discrete cone C ⊆ T_{k}^{n} defines a linear order ⪰ on P_{k}[n] which satisfies (4) and the IES, and in which A ⪰ B if and only if χ(A, B) ∈ C, for every two multisets A, B ∈ P_{k}[n].

Proof. Let ⪰ be a linear order on P_{k}[n] which satisfies (4) and the IES. Then (4) implies conditions D1 for C(⪰) and D2 obviously holds for C(⪰) since ⪰ is linear. Only D3 is not immediately clear.

So suppose that x = (x_{1}, …, x_{n}) = χ(A, B) ∈ C(⪰) and that y = (y_{1}, …, y_{n}) = χ(D, E) ∈ C(⪰), with | max(−x^{−}, y^{+})| ≤ k. We may choose such representations of x and y for which A ∩ B = ∅ and D ∩ E = ∅. In doing this, suppose that A and B have cardinality s, and D and E have cardinality t, where s ≤ k and t ≤ k. Then x^{+} = χ(A) and −x^{−} = χ(B) while y^{+} = χ(D) and −y^{−} = χ(E), and |x^{−}| = |x^{+}| = |A| = |B| = s while |y^{−}| = |y^{+}| = |D| = |E| = t.

This means that A, B ∈ P_{s}[n] and D, E ∈ P_{t}[n] with A ⪰_{s} B and D ⪰_{t} E, where ⪰_{s} and ⪰_{t} are the orders induced by ⪰ on P_{s}[n] and P_{t}[n], respectively. The fact that | max(−x^{−}, y^{+})| ≤ k implies that there exist two multisets F_{1} and F_{2} such that F_{1} ∪ B = F_{2} ∪ D, and the cardinality ℓ of this common union is not greater than k. By Lemma 1,

F_{1} ∪ A ⪰_{ℓ} F_{1} ∪ B = F_{2} ∪ D ⪰_{ℓ} F_{2} ∪ E,

and hence by transitivity, F_{1} ∪ A ⪰_{ℓ} F_{2} ∪ E. It now follows that

x + y = χ(A ∪ D, B ∪ E) = χ(A ∪ F_{2} ∪ D, B ∪ F_{2} ∪ E)
= χ(A ∪ F_{1} ∪ B, B ∪ F_{2} ∪ E) = χ(A ∪ F_{1}, F_{2} ∪ E) ∈ C(⪰).

For the second part, let C be any cone in T_{k}^{n}. We define an order on each of the sets P_{ℓ}[n] for ℓ ≤ k by setting for any two multisets A, B ∈ P_{ℓ}[n]

A ⪰_{ℓ} B whenever χ(A, B) ∈ C.

By its definition, the order ⪰_{k} (=⪰) on P_{k}[n] will satisfy the IES, but we need to prove its transitivity. So suppose A ⪰ B and B ⪰ D for some A, B, D ∈ P_{k}[n]. Let x = χ(A, B) and y = χ(B, D). Then | max(−x^{−}, y^{+})| ≤ k since each entry of both −x^{−} and y^{+} is bounded above by the corresponding entry of χ(B), and |χ(B)| = k, so χ(A, D) = χ(A)−χ(B)+χ(B)−χ(D) = x+y ∈ C, and therefore A ⪰ D.

Example 3. For the linear order ⪰ on P_{2}[4] from Example 2, the three vectors

x = (1, −2, 1, 0), y = (0, 1, −2, 1), z = (−1, 1, 1, −1)  (8)

belong to C(⪰), which is a cone in T_{2}^{4}. These vectors correspond to the three comparisons given in (6). Note that for each pair of distinct vectors u, v in the set {x, y, z} we have | max(u^{+}, v^{−})| = 3, and that explains why no sum of two vectors from this set belongs to C(⪰).

We can reformulate now the cancellation conditions as follows:

Proposition 2. An order ⪰ satisfies the mth cancellation condition if and only if for no m-subset {x_{1}, …, x_{m}} ⊆ 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.  (9)

Proof. If m distinct comparisons A_{i} ⪰ B_{i} exist as in Definition 4, then we take vectors x_{i} = χ(A_{i}, B_{i}) ∈ C(⪰) for 1 ≤ i ≤ m, and condition (5) implies that a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{m}x_{m} = 0. The converse is also clear.

Definition 7. Suppose for an order ⪰ on P_{k}[n] there exists a set of m vectors {x_{1}, …, x_{m}} ⊆ C(⪰) and positive integers a_{1}, …, a_{m} such that (9) holds. Then we say that the order ⪰ violates the mth cancellation condition for vectors x_{1}, …, x_{m} with multiplicities (a_{1}, …, a_{m}).

Example 4. The three vectors from C(⪰) given in Example 3 add up to the zero vector, hence the order ⪰ violates C_{3} with multiplicities (1, 1, 1), and is not representable.

Geometrically, what is happening is clear. An order ⪰ is representable provided there exists a positive-integer-valued vector w = (w_{1}, …, w_{n}) ∈ ℝ^{n} such that w_{1} > w_{2} > … > w_{n} and such that

x ∈ C(⪰) ⟺ (w, x) > 0 for every x ∈ T_{k}^{n} \ {0},  (10)

that is, all non-zero vectors in the cone C(⪰) lie in the open half-space H_{w} = {x ∈ ℝ^{n} | (w, x) > 0} determined by the hyperplane L_{w} with normal vector w. The cone C(⪰) in this case is a pointed cone.

Similarly, for any order ⪰ that is almost representable, there exists a nonnegative-integer-valued vector w = (w_{1}, …, w_{n}) ∈ ℝ^{n} such that both w_{1} ≥ w_{2} ≥ … ≥ w_{n} ≥ 0 and

x ∈ C(⪰) ⟹ (w, x) ≥ 0 for every x ∈ T_{k}^{n},  (11)

so that in this case the whole of the cone C(⪰) lies in the closed half-space \overline{H_{w}} = \{x ∈ ℝ^{n} | (w, x) ≥ 0\} = H_{w} ∪ L_{w}.

Note that in both cases, the vector w represents the vector of utilities.

3 Construction Theorem

Proposition 3. Let ⪰ be an almost representable order with a vector of utilities w. Suppose that the mth cancellation condition is violated for vectors x_{1}, …, x_{m} with multiplicities (a_{1}, …, a_{m}). Then all the vectors x_{1}, …, x_{m} lie in the hyperplane L_{w}.

Proof. First we note that (w, x) > 0 for all those x ∈ C(⪰) which do not belong to L_{w}. Next, condition (9) implies that

∑_{i=1}^{n} a_{i}(w, x_{i}) = 0,

and since a_{i} > 0 for 1 ≤ i ≤ n, this can hold only when all (w, x_{i}) = 0 for all i, and hence we find that x_{i} ∈ L_{w} for 1 ≤ i ≤ n.

Corollary 1. Any almost representable order on P_{k}[n] which satisfies C_{3}, C_{4}, …, C_{n−1} is representable.

Proof. Suppose that for some m, the mth cancellation condition is violated by vectors x_{1}, …, x_{m} ∈ C(⪰) with multiplicities (a_{1}, …, a_{m}), that is, with a_{1}x_{1} + ⋯ + a_{m}x_{m} = 0. Now since all the vectors x_{1}, …, x_{m} belong to the (n−2)-dimensional subspace L_{w} ∩ L_{n}, where L_{n} is the hyperplane with normal vector n = (1, 1, …, 1), we may use standard linear algebra to reduce the number of vectors in this linear combination to at most n − 1 vectors, while keeping all coefficients positive. We claim that if m ≥ n, then one of the vectors x_{1}, …, x_{m} can be excluded from the linear combination. Indeed in this case the set of vectors {x_{1}, …, x_{m−1}} is linearly dependent, and so there exist real numbers b_{1}, …, b_{m−1} with at least one b_{i} being positive, such that b_{1}x_{1} + ⋯ + b_{m−1}x_{m−1} = 0. Hence for all ϵ ∈ ℝ we have

(a_{1} − ϵb_{1})x_{1} + … + (a_{m} − ϵb_{m})x_{m} + a_{m}x_{m} = 0.

When ϵ = 0, all coefficients in this equation are positive. If we choose the smallest positive ϵ for which a_{i} − ϵb_{i} = 0 for some i, then the resulting linear combination will not contain x_{i}, and will still be nontrivial since a_{m} > 0. Hence we may suppose that m ≤ n − 1. Since ⪰ satisfies C_{4}, …, C_{n−1}, it follows that ⪰ is representable.

Proposition 4. g(n, k) ≤ n − 1 and f(n, k) ≤ n for all n and k.

Proof. The first inequality g(n, k) ≤ n − 1 follows from Corollary 1, and the second inequality f(n, k) ≤ n follows from a similar argument in the (n − 1)-dimensional subspace L_{n}.

The following theorem enables us to construct orderings that are almost representable but fail C_{m} for particular values of m.

Theorem 1 (Construction method). For m ≥ 3, let X = {x_{1}, …, x_{m}} be a system of m non-zero vectors from T_{k}^{n} satisfying the following conditions:

(a) ∑_{i=1}^{m} a_{i}x_{i} = 0 for some positive integers a_{1}, …, a_{m},

(b) | max(−x_{i}^{−}, x_{j}^{+})| > k for every pair {i, j} ⊂ {1, 2, …, m} with i ≠ j, and (c) no proper subsystem X′ ⊂ X is linearly dependent with positive coeffi-

cients.

Suppose further that the m × n matrix A whose rows are the given vectors x_{1}, …, x_{m} has the property that Aw = 0 for some positive-integer-valued vector w = (w_{1}, …, w_{n}) with w_{1} > w_{2} > … > w_{n} > 0, and that

L_{w} ∩ (T_{k}^{n} \ {0}) = {±x_{1}, …, ±x_{m}}.

Let ⪰ be the (nonlinear) order on P_{k}[n] with the vector of utilities w, and let C(⪰) = {x ∈ T_{k}^{n} | (x, w) ≥ 0} be the discrete cone associated with ⪰. Then the set

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

is a discrete cone that corresponds to an almost representable order on P_{k}[n] which satisfies C_{j} for all j < m, but does not satisfy C_{m}.

Proof. First we note that {±x_{1}, …, ±x_{m}} ⊆ L_{w} = {x ∈ ℝ^{n} | (w, x) = 0}. Next (e_{i}−e_{i+1}, w) = w_{i}−w_{i+1} > 0 for 1 ≤ i < n, 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′. Now let us prove D3. Suppose that y, z ∈ C′ and | max(−y^{−}, z^{+})| ≤ k, but y + z ∉ C′. Since the cone C(⪰) satisfies D3 we know that y + z ∈ C(⪰), so y + z ∈ C(⪰) \ C′, and hence y + z = −x_{i} for some i. Moreover, y, z ∈ L_{w}, since otherwise −(x_{i}, w) = (y + z, w) = (y, w) + (z, w) > 0. It follows from (c) that y = x_{j} for some j and z = x_{ℓ} for some ℓ. This contradicts hypothesis (b), however, since | max(−y^{−}, z^{+})| ≤ k. Thus D3 holds for C′.

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

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

with positive integers c_{1}, …, c_{j} and y_{i} ∈ C′ for 1 ≤ i ≤ j, where j < m. If (y_{i}, w) > 0 for some i, then 0 = (0, w) = (c_{1}y_{1} + c_{2}y_{2} + ⋯ + c_{j}y_{j}, w) = c_{1}(y_{1}, w) + c_{2}(y_{2}, w) + … + c_{j}(y_{j}, w) > 0, a contradiction, hence y_{i} ∈ L_{w} for all i, and therefore {y_{1}, …, y_{j}} ⊆ {x_{1}, …, x_{m}}, which contradicts (c). Finally, C_{m} fails by hypothesis (a).

4 Characterisation of g(n, k)

In this section we will use the construction method from the previous section and Proposition 4 to characterise the function g(n, k) as follows:

Theorem 2. For all n ≥ 3 and k ≥ 2,

g(n, k) = \{ \begin{matrix}n − 2 & if (n, k) = (5, 2), \\ n − 1 & otherwise. \end{matrix}

We prove this theorem partly by theoretical means and partly by direct calculations for small n and k (with the help of the computer algebra system Magma [1], using the same techniques of enumeration as described in [2]). We present the theoretical results first.

As was mentioned above, the case n = 3 of this theorem was proved in [20], so we need only consider cases where n ≥ 4. The proof of each case will consist of constructing a matrix A which satisfy conditions of Theorem 1. The rows of A will be denoted by v_{1}, v_{2}, …. We will use the following notation extensively: for any vector v, let the expression x_{i}(v) denote the ith co-ordinate entry of v.

4.1 Proof of Theorem 2 for n = 4.

Consider the vectors v_{1}, v_{2}, v_{3} that make up the rows of the 3 × 4 matrix

A = [ \begin{matrix}0 & −(k − 1) & k & −1 \\ 1 & −1 & −(k − 1) & k − 1 \\ −1 & k & −1 & −k + 2 \end{matrix} ] .  (12)

It is clear that v_{1} and v_{2} are linearly independent and v_{1} + v_{2} + v_{3} = 0. It can also be seen (by inspection of the first and fourth co-ordinates) that no linear combination y_{1}v_{1} +y_{2}v_{2} of v_{1} and v_{2} can be a vector of integers unless both y_{1} and y_{2} are integers. The row-space of A has a normal vector w = (k^{2} − k + 2, k + 1, k, 1), satisfying the requirement w_{1} > w_{2} > … > w_{n} > 0 of Theorem 1 since k^{2} − k + 1 > k for all k > 1. Similarly the given vectors v_{1}, v_{2}, v_{3} satisfy the requirement that | max(−v_{i}^{−}, v_{j}^{+})| > k for every two i and j, since 2k − 1 > k for all k > 1.

Next, because |v_{1}^{+}| = |v_{1}^{−}| = |v_{2}^{+}| = |v_{2}^{−}| = k, no proper multiple of v_{1} or v_{2} can lie in T_{k}^{4}, and hence any vector v in L_{w} ∩T_{k}^{4} other than 0, ±v_{1} or ±v_{2} must be of the form v = m_{1}v_{1} + m_{2}v_{2} with non-zero coefficients m_{1}, m_{2} ∈ ℤ. Now if m_{1} > 0 and m_{2} > 0, then since −k ≤ x_{2}(v) = −m_{1}(k − 1) − m_{2} < 0 we find that m_{1} = m_{2} = 1, giving v = (1, −k, 1, k − 2) = −v_{3}. Similarly, if m_{1} < 0 and m_{2} < 0, then inspection of x_{2}(v) gives m_{1} = m_{2} = −1 and v = v_{3}. On the other hand, if m_{1} > 0 > m_{2} or m_{1} < 0 < m_{2} then x_{3}(v) = m_{1}k−m_{2}(k−1) lies outside the acceptable range M_{k} for co-ordinates of vectors in T_{k}^{4}. Hence the only non-zero vectors in L_{w} ∩ T_{k}^{4} are ±v_{1}, ±v_{2} and ±v_{3}.

By Theorem 1, these vectors give rise to an almost representable order on P_{k}[4] which fails to satisfy C_{3}, and by Proposition 4 it follows that g(4, k) = 3 for all k ≥ 2.

4.2 Proof of Theorem 2 for n = 5 and k ≥ 4.

Consider the four vectors v_{1}, v_{2}, v_{3}, v_{4} forming the rows of the 4 × 5 matrix

A = [ \begin{matrix}1 & −(k − 1) & k − 3 & 2 & −1 \\ 0 & 1 & −k & k − 2 & 1 \\ 0 & 0 & 1 & −k & k − 1 \\ −1 & k − 2 & 2 & 0 & −(k − 1) \end{matrix} ] .

We note that v_{1} +v_{2} +v_{3} +v_{4} = 0, any three of the given vectors are linearly independent, and the vector w = (k^{3} − 3k^{2} + 6k − 3, k^{2} − k + 3, k + 1, 2, 1) is a normal vector to the row-space of A. Also the given vectors can easily be seen to satisfy the requirement that | max(−v_{i}^{−}, v_{j}^{+})| > k whenever i ≠ j. Next, we need the following:

Lemma 2. L_{w} ∩ T_{k}^{5} = {0, ±v_{1}, ±v_{2}, ±v_{3}, ±v_{4}}.

Proof. Clearly {v_{1}, v_{2}, v_{3}} is a basis for the 3-dimensional subspace L_{w} ∩L_{n}, so every vector v in L_{w} ∩T_{k}^{5} must be of the form v = y_{1}v_{1} +y_{2}v_{2} +y_{3}v_{3}, and moreover, from inspection of x_{1}(v), x_{2}(v) and x_{3}(v) it is obvious that y_{1}, y_{2} and y_{3} have to be integers. Without loss of generality (since −T_{k}^{5} = T_{k}^{5}), we may assume that y_{1} ≥ 0. We proceed case-by-case:

Case 1: Suppose y_{1} = 0. If y_{2} ≠ 0 then y_{2} and y_{3} must have the same sign (for otherwise x_{3}(v) = −y_{2}k + y_{3} lies outside M_{k}), and then inspection of x_{2}(v) + x_{5}(v) = 2y_{2} + (k − 1)y_{3} forces y_{3} = 0 (because membership of T_{k}^{5} requires |v^{−}| = |v^{+}| ≤ k). Hence either y_{2} = 0 or y_{3} = 0, giving v = 0, ±v_{2} or ±v_{3}.

Case 2: Suppose y_{1} > 0 and y_{2} = 0. Then inspection of x_{2}(v) = −y_{1}(k − 1) gives y_{1} = 1. Also if y_{3} ≠ 0 then y_{3} > 0 (for otherwise x_{4}(v) = 2y_{1}−y_{3}k > k), but then v^{−} = (0, −(k − 1), 0, 2 − y_{3}k, 0) so |v^{−}| = k − 3 + y_{3}k > k, a contradiction. Hence v = v_{1} in this case.

Case 3: Suppose y_{1} > 0, y_{2} ≠ 0 and y_{3} = 0. Then inspection of x_{3}(v) = y_{1}(k − 3) − y_{2}k gives y_{2} > 0, following which inspection of x_{4}(v) = 2y_{1} + y_{2}(k − 2) gives y_{1} = y_{2} = 1, but then v = v_{1} + v_{2} = (1, −(k − 2), −3, k, 0) so |v^{+}| = 1 + k > k, a contradiction. Hence no such v exists in this case.

Case 4: Suppose y_{1} > 0, y_{2} < 0 and y_{3} ≠ 0. Then since −k ≤ x_{2}(v) = −y_{1}(k − 1) + y_{2} < 0 we find that y_{1} = 1 and y_{2} = −1, and therefore v = (1, −k, 2k − 3 + y_{3}, 4 − k(1 + y_{3}), −2 + y_{3}(k − 1)). Now as x_{2}(v) = −k, no other co-ordinates of v can be negative, so 4 − k(1 + y_{3}) = x_{4}(v) ≥ 0 and −2 + y_{3}(k − 1) = x_{5}(v) ≥ 0. The first of these two inequalities gives y_{3} ≤ 0 but the second gives y_{3} > 0, a contradiction, so no such v exists in this case.

Case 5: Suppose y_{1} > 0, y_{2} > 0 and y_{3} ≠ 0. Then since k ≥ x_{4}(v) = 2y_{1} + y_{2}(k − 1) − y_{3}k we find y_{3} > 0, so all three coefficients are positive. If y_{1} = y_{2} = y_{3} = 1, then we have v = v_{1} + v_{2} + v_{3} = −v_{4}. Otherwise max(y_{1}, y_{2}, y_{3}) > 1. If y_{2} > y_{1} then x_{5}(v) = −y_{1}+y_{2}+y_{3}(k−1) ≥ 1+k−1 = k and then |v^{+}| ≥ x_{1}(v) + x_{5}(v) ≥ 1 + k > k, a contradiction, hence y_{2} ≤ y_{1}. Similarly if y_{3} = max(y_{1}, y_{2}, y_{3}) > 1, then x_{5}(v) = −y_{1} + y_{2} + y_{3}(k − 1) ≥ −y_{3}+1+y_{3}(k−1) = y_{3}(k−2)+1 ≥ 2(k−2)+1 = 2k−3 > k, a contradiction, and hence we may suppose that y_{1} = max(y_{1}, y_{2}, y_{3}) > 1. Now this implies −k ≤ x_{2}(v) = −y_{1}(k−1)+y_{2} ≤ −y_{1}(k−1)+y_{1} = (2−k)y_{1} ≤ (2−k)2 = 4−2k, and therefore k ≥ 4. In fact equality must occur, so y_{1} = y_{2} = 2, but then v = (2, −4, −6 + y_{3}, 8 − 4y_{3}, 3y_{3}), and requiring x_{3}(v) ≥ −k and x_{5}(v) ≤ k forces the contradictory inequalities y_{3} ≥ 2 and y_{3} ≤ 1.

As these five cases cover all possibilities, the proof is complete.

By Theorem 1, there exists an almost representable order on P_{k}[5] which fails C_{4}, and by Proposition 4 it follows that g(5, k) = 4 for all k ≥ 4.

4.3 Proof of Theorem 2 for n ≥ 6 and k ≥ 3.

The proof for this case is split into a number of observations and lemmata. Let us consider the following (n − 2) × n matrix:

A = [ \begin{matrix}1 & −(k−1) & k−3 & 1 & 0 & … & 0 & 0 & 0 & 1 & −1 \\ 0 & 1 & −k & k−2 & 1 & 0 & … & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & −k & k−2 & 1 & 0 & … & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & −k & k−2 & 1 & 0 & … & 0 & 0 \\ … & … & … & … & … & … & … & … & … & … & … \\ … & … & … & … & … & … & … & … & … & … & … \\ 0 & 0 & 0 & 0 & 0 & … & 0 & 1 & −k & k−2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & … & 0 & 1 & −k & k−1 \end{matrix} ] .

Let v_{i} be the ith row of A. Clearly the vectors v_{1}, v_{1}, …, v_{n−2} are linearly independent, and therefore span a subspace of ℝ^{n} of dimension n−2. Also it is easy to check that |v_{i}^{+}| = |v_{i}^{−}| = k for all i, and that | max(−v_{i}^{−}, v_{j}^{+})| > k whenever i ≠ j.

Let v = ∑_{i=1}^{n−2} y_{i}v_{i} be a linear combination of v_{1}, …, v_{n−2}. For later use, we note the following:

x_{1}(v) = y_{1},
x_{2}(v) = −y_{1}(k − 1) + y_{2},
x_{3}(v) = y_{1}(k − 3) − y_{2}k + y_{3},
x_{i}(v) = y_{i−3} + y_{i−2}(k − 2) − y_{i−1}k + y_{i} for 4 ≤ i ≤ n − 2,
x_{n−1}(v) = y_{1} + y_{n−4} + y_{n−3}(k − 2) − y_{n−2}k, and
x_{n}(v) = −y_{1} + y_{n−3} + y_{n−2}(k − 1).

In addition, we will use particular sums of these co-ordinates, including

x_{1}(v) + x_{3}(v) = y_{1}(k − 2) − y_{2}k + y_{3},
x_{2}(v) + x_{3}(v) = −2y_{1} − y_{2}(k − 1) + y_{3},
x_{1}(v) + x_{3}(v) + x_{4}(v) = y_{1}(k − 1) − 2y_{2} − y_{3}(k − 1) + y_{4},

and, for 4 ≤ i ≤ n−2, also the sums

x_{i}(v) + x_{i+1}(v) = y_{i−3} + y_{i−2}(k−1) − 2y_{i−1} − y_{i}(k−1) + y_{i+1},

x_{2}(v) + x_{3}(v) + x_{i}(v) = −2y_{1} − y_{2}(k−1) + y_{3} + y_{i−3} + y_{i−2}(k−2) − y_{i−1}k + y_{i},

x_{2}(v) + x_{3}(v) + … + x_{i}(v) = −y_{1} − y_{i−2} − y_{i−1}(k−1) + y_{i}.

All of these sums must lie in the interval M_{k} = {−k, …, −1, 0, 1, …, k}, irrespective of whether their terms x_{j}(v) are positive or negative (since, for example, if the sum exceeds k then the sub-sum of positive terms exceeds k).

Lemma 3. Suppose that some linear combination v = ∑_{i=1}^{n−2} y_{i}v_{i} of the v_{i} belongs to T_{k}^{n}. Then y_{i} ∈ ℤ for all i.

Proof. We have y_{1} = x_{1}(v) ∈ ℤ, and as −y_{1}(k − 1) + y_{2} = x_{2}(v) ∈ ℤ we find y_{2} ∈ ℤ. Clearly this argument can be repeated, to show y_{i} ∈ ℤ for all i.

Lemma 4. There is a vector w = (w_{1}, …, w_{n}) belonging to the null space of A such that w_{1} > w_{2} > … > w_{n} > 0.

Proof. The null space of A has dimension 2 (since v_{1}, …, v_{n−2} are linearly independent), and contains the vector n = (1, 1, …, 1). To construct another vector u = (u_{1}, …, u_{n}) in this null space, let us set u_{n} = 0 and u_{n−1} = 1. Then from orthogonality with the last row of A we see that u_{n−2} = k. We proceed by reverse induction to prove that u_{i} > 2u_{i+1} for 2 ≤ i ≤ n − 1. This is clearly true for i = n − 1, and for i = n − 2 since k > 2. Now let us assume that u_{i+1} ≥ 2u_{i+2} and u_{i+2} ≥ 2u_{i+3} for some i ≤ n − 3. Then by orthogonality with the ith row of A we have the inductive step

u_{i} = ku_{i+1} − (k − 2)u_{i+2} − u_{i+3}
= 2u_{i+1} + (k − 2)(u_{i+1} − u_{i+2}) − u_{i+3}
≥ 2u_{i+1} + (k − 2)u_{i+2} − u_{i+3}
≥ 2u_{i+1} + u_{i+2} − u_{i+3}
≥ 2u_{i+1},

as required. Similarly, orthogonality with the first row of A gives

u_{1} = (k − 1)u_{2} − (k − 3)u_{3} − u_{4} = 2u_{2} + (k − 3)(u_{2} − u_{3}) − u_{4}
≥ 2u_{2} + (k − 3)u_{3} − u_{4} ≥ 2u_{2} − u_{4} > u_{2} + u_{3} − u_{4} ≥ u_{2}.

Thus we have u_{1} > u_{2} > … > u_{n} = 0, and we can simply take w = u + n to satisfy the requirement that all co-ordinates of w are positive.

Lemma 5. L_{w} ∩ T_{k}^{n} = {0, ±v_{1}, ±v_{2}, …, ±v_{n−2}, ±v_{n−1}}, where v_{n−1} is the vector −(∑_{i=1}^{n−2} v_{i}) = (−1, k − 2, 2, 0, …, 0, −k + 1).

Proof. Clearly {v_{1}, v_{2}, …, v_{n−2}} is a basis for the (n − 2)-dimensional subspace L_{w} ∩ L_{n}, so every vector v in L_{w} ∩ T_{k}^{n} is of the form v = ∑_{i=1}^{n−2} y_{i}v_{i}, and by Lemma 3, all the y_{i} are integers. To find all possibilities for v, we may assume without loss of generality that y_{1} ≥ 0 (since −T_{k}^{n} = T_{k}^{n}). As before, we consider several cases:

Case 1: Suppose y_{1} = 0. If y_{i} = 0 for all i then v = 0. Otherwise let j be the smallest positive integer for which y_{j} ≠ 0. Then without loss of generality we may suppose that y_{j} ≥ 1. With these hypotheses, we will prove that v is one of v_{2}, v_{3}, …, v_{n−3} or v_{n−2}. To do so, assume the contrary, and further, suppose that ∑_{i=2}^{n−2} |y_{i}| is as small as possible.

Now assume also for the time being that y_{j} ≥ 2. If j = n − 2, then x_{n}(v) = −y_{1} + y_{n−3} + y_{n−2}(k − 1) = 0 + 0 + y_{n−2}(k − 1) ≥ 2(k − 1) > k, a contradiction, and so j ≤ n − 3. The requirement x_{j+1}(v) ≥ −k then gives y_{j+1} ≥ y_{j}k − k ≥ 2k − k = k ≥ 3. But now if y_{ℓ} ≥ 3 and y_{i} ≥ 2 whenever j ≤ i < ℓ, where 3 ≤ ℓ ≤ n−3, then x_{2}(v) + x_{3}(v) + … + x_{ℓ+1}(v) ≥ −k gives

y_{ℓ+1} ≥ −k + y_{1} + y_{ℓ−1} + y_{ℓ}(k − 1) ≥ −k + 0 + 2 + 3(k − 1) = 2k − 1 ≥ 3,

and hence by induction, y_{ℓ} ≥ 3 whenever j < ℓ ≤ n − 2. This, however, gives

x_{n}(v) = −y_{1} + y_{n−3} + y_{n−2}(k − 1) ≥ 0 + 2 + 3(k − 1) = 3k − 1 > k, another contradiction. Hence y_{j} = 1. Also j ≠ n − 2, since we have assumed v ≠ v_{n−2}, and therefore 2 ≤ j ≤ n − 3.

Next, because x_{j+1}(v) ≥ −k we have y_{j+1} ≥ y_{j}k − k ≥ k − k = 0. Assume for the time being that y_{j+1} ≥ 2. If j = n − 3, then we find x_{n}(v) = −y_{1} + y_{n−3} + y_{n−2}(k − 1) = 0 + 1 + y_{n−2}(k − 1) ≥ 1 + 2(k − 1) > k, a contradiction, and so j ≤ n − 4. Moreover, from x_{j+1}(v) + x_{j+2}(v) ≥ −k we find that y_{j+2} ≥ 2y_{j} + y_{j+1}(k − 1) − k ≥ 2 + 2(k − 1) − k = k ≥ 3, and by induction (as above), it follows that y_{ℓ} ≥ 3 whenever j + 1 < ℓ ≤ n − 2, and again x_{n}(v) = −y_{1} + y_{n−3} + y_{n−2}(k − 1) ≥ 0 + 2 + 3(k − 1) = 3k − 1 > k, a contradiction. Hence y_{j+1} = 0 or 1.

If y_{j+1} = 0, then x_{j}(v) = x_{j}(v_{j}) = 1 and x_{j+1}(v) = x_{j+1}(v_{j}) = −k, and these co-ordinates cancel each other when we take the difference u = v − v_{j}. Moreover, as |v| ≤ 2k and |v_{j}| = 2k we see that |u| = |v − v_{j}| ≤ (2k − (k + 1))+(2k−(k+1)) < 2k, and since u lies in L_{w} (so that |u^{+}| = |u^{−}|), it follows that u lies in T_{k}^{n}, and hence also in L_{w} ∩ T_{k}^{n}. But u = v − v_{j} = ∑_{i=j+2}^{n−2} y_{i}v_{i}, and as ∑_{i=j+2}^{n−2} |y_{i}| is smaller than ∑_{i=2}^{n−2} |y_{i}| we deduce that u = 0 or u = ±v_{i} for some i ≥ j +2, and hence v = v_{j} or v_{j} ±v_{i} for some i ≥ j +2. The former possibility has been ruled out already, and the latter possibility is easily ruled out since x_{j+1}(v_{j} + v_{i}) + x_{i+1}(v_{j} + v_{i}) ≤ −k + 1 − k = 1 − 2k < −k and x_{j+1}(v_{j} − v_{i}) + x_{i+2}(v_{j} − v_{i}) ≤ −k − (k − 2) = 2 − 2k < −k.

Similarly if y_{j+1} = 1, then x_{j}(v) = x_{j}(v_{j}) = 1 while x_{j+1}(v) = −(k − 1) and x_{j+1}(v_{j}) = −k, so that when we take the difference u = v − v_{j}, we find |u| = |v − v_{j}| ≤ (2k − k) + (2k − k) = 2k, and again u lies in L_{w} ∩ T_{k}^{n}, but u = v − v_{j} = ∑_{i=j+1}^{n−2} y_{i}v_{i}, with ∑_{i=j+1}^{n−2} |y_{i}| smaller than ∑_{i=2}^{n−2} |y_{i}|, so u = 0 or u = ±v_{i} for some i ≥ j + 1, and hence v = v_{j} or v_{j} ± v_{i} for some i ≥ j + 1. In fact because y_{j+1} = 1 we must have v = v_{j} + v_{j+1}, but then x_{j}(v) + x_{j+3}(v) + x_{j+4}(v)) = 1 + (k − 1) + 1 = k + 1 > k, another contradiction.

Hence there is no other such v; the only possibilities are v_{2}, v_{3}, …, v_{n−3} and v_{n−2}.

Case 2: Suppose y_{1} = 1 and y_{2} < 0. Then the requirement x_{2}(v) ≥ −k gives y_{2} = −1 and x_{2}(v) = −k, so that no other co-ordinates of v can be negative. Similarly, from x_{1}(v) + x_{3}(v) ≤ k we find that y_{3} ≤ k − y_{1}(k − 2) + y_{2}k ≤ k − (k − 2) − k = 2 − k ≤ −1, and from x_{1}(v) + x_{3}(v) + x_{4}(v) ≤ k we find that y_{4} ≤ k − y_{1}(k−1) + 2y_{2} + (k−1)y_{3} ≤ k − (k−1) − 2 − (k−1) = −k ≤ −3. It now follows by induction that y_{j} ≤ −3 for 4 ≤ j ≤ n − 2, for if y_{j} ≤ −3 and y_{i} ≤ −1 for 2 ≤ i < j, then from the requirement x_{2}(v) + x_{3}(v) + … + x_{j+1}(v) ≥ −k we find that

y_{j+1} ≤ k + y_{1} + y_{j−1} + y_{j}(k − 1) ≤ k + 1 − 1 − 3(k − 1) ≤ 3 − 2k ≤ −3.

This, however, gives

x_{n}(v) = −y_{1} + y_{n−3} + y_{n−2}(k − 1) ≤ −1 − 1 − 3(k − 1) = 1 − 3k < −k,

a contradiction. Hence this case is impossible.

Case 3: Suppose y_{1} = 1 and y_{2} = 0. As v and v_{1} then have the same first two co-ordinates, namely 1 and −(k − 1), these cancel each other when taking their difference u = v − v_{1}. Moreover, as |v| ≤ 2k and |v_{1}| = 2k we see that |u| = |v − v_{1}| ≤ (2k − k) + (2k − k) = 2k, and since u lies in L_{w} (so that |u^{+}| = |u^{−}|), it follows that u lies in T_{k}^{n}. By the argument in Case 1, we find that u = 0 or ±v_{i} for some i ≥ 3, and hence v = v_{1} or v_{1} ± v_{i} for some i ≥ 3. The latter possibility, however, is easily ruled out since x_{2}(v_{1} + v_{i}) + x_{i+1}(v_{1} + v_{i}) ≤ −(k − 1) + 1 − k = 2 − 2k < −k and x_{1}(v_{1} − v_{i}) + x_{i+1}(v_{1} − v_{i}) ≥ 1 + k > k. Hence we have only v = v_{1}.

Case 4: Suppose y_{1} = 1 and y_{2} > 0. Assuming y_{2} ≥ 2, then the requirement x_{2}(v)+x_{3}(v) ≥ −k gives y_{3} ≥ 2y_{1} +y_{2}(k −1)−k ≥ 2+2(k −1)−k = k ≥ 3. It then follows by induction that y_{j} ≥ 3 for 4 ≤ j ≤ n − 2, for if y_{i} ≥ 3 for 3 ≤ i ≤ j − 1, then from

x_{2}(v) + x_{3}(v) + … + x_{j}(v) ≥ −k we find that

y_{j} ≥ −k + y_{1} + y_{j−2} + y_{j−1}(k − 1) ≥ −k + 1 + 2 + 3(k − 1) ≥ 2k ≥ 3.

This, however, gives

x_{n}(v) = −y_{1} + y_{n−3} + y_{n−2}(k − 1) ≥ −1 + 3 + 3(k − 1) = 3k − 1 > k,

a contradiction. Thus y_{2} = 1.

If all y_{i} = 1 for all i then v = ∑_{i=1}^{n−2} v_{i} = −v_{n−1}. Otherwise suppose that j is the smallest positive integer for which y_{j} ≠ 1. If j = 3, then from x_{2}(v) + x_{3}(v) ≥ −k we find that y_{3} ≥ 2y_{1} + y_{2}(k − 1) − k = 1, and so y_{j} ≥ 2 in that case, while if 3 ≤ j ≤ n−2 then x_{2}(v) + x_{3}(v) + x_{j}(v) ≥ −k gives

y_{j} ≥ −k + 2y_{1} + y_{2}(k − 1) − y_{3} − y_{j−3} − y_{j−2}(k − 2) + y_{j−1}k
= −k + 2 + (k − 1) − 1 − 1 − (k − 2) + k = 1,

and so y_{j} ≥ 2 in that case also. But now if y_{ℓ} ≥ 2 and y_{i} ≥ 1 for all i < ℓ, where 3 ≤ ℓ ≤ n − 3, then x_{2}(v) + x_{3}(v) + … + x_{ℓ+1}(v) ≥ −k gives

y_{ℓ+1} ≥ −k + y_{1} + y_{ℓ−1} + y_{ℓ}(k − 1) ≥ −k + 1 + 1 + 2(k − 1) ≥ k ≥ 3,

and hence by induction, y_{ℓ} ≥ 2 whenever j ≤ ℓ ≤ n − 2. This, however, gives

x_{n}(v) = −y_{1} + y_{n−3} + y_{n−2}(k − 1) ≥ −1 + 1 + 2(k − 1) > k,

a contradiction. Hence no such j exists, and we have only v = −v_{n−1}.

Case 5: Suppose y_{1} ≥ 2. Then since x_{2}(v) ≥ −k we have y_{2} ≥ y_{1}(k−1)−k = (y_{1}−1)(k−1)−1 ≥ 2(y_{1}−1)−1 = 2y_{1}−3 ≥ 1, and since x_{2}(v)+x_{3}(v) ≥ −k we have y_{3} ≥ 2y_{1}+y_{2}(k−1)−k = 2y_{1}+(y_{2}−1)(k−1)−1 ≥ 2y_{1}−1 ≥ y_{1}+1 ≥ 3. It follows by induction that y_{j} ≥ y_{1} + 1 ≥ 3 for 4 ≤ j ≤ n − 2, for if y_{i} ≥ y_{1} + 1 ≥ 3 for 3 ≤ i ≤ j − 1, then from x_{2}(v) + x_{3}(v) + … + x_{j}(v) ≥ −k

we find that

y_{j} ≥ −k + y_{1} + y_{j−2} + y_{j−1}(k − 1) ≥ −k + y_{1} + 1 + 3(k − 1)
≥ y_{1} + 2(k − 1) ≥ y_{1} + 1 ≥ 3.

This, however, gives

x_{n}(v) = −y_{1} + y_{n−3} + y_{n−2}(k − 1) > 1 + 3(k − 1) = 3k − 2 > k,

a contradiction.

As these five cases cover all possibilities, the proof is complete.

4.4 Proof of Theorem 2 for n ≥ 8 and k = 2.

Consider the n−2 vectors v_{1}, …, v_{n−2} that make up the rows of the following (n−2) × n matrix:

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

Clearly these vectors are linearly independent, and so the row-space of A a subspace of ℝ^{n} of dimension n − 2. Also clearly |v_{i}^{+}| = |v_{i}^{−}| = 2 for all i, and it is easy to check that | max(−v_{i}^{−}, v_{j}^{+})| > 2 whenever i ≠ j.

In what follows, we use the Fibonacci sequence, that is, the sequence (f_{m}) of integers defined by f_{1} = f_{2} = 1 and f_{m+2} = f_{m+1} + f_{m} for all m ≥ 1.

Lemma 6. There is a vector w = (w_{1}, …, w_{n}) belonging to the null space of A such that w_{1} > w_{2} > … > w_{n} > 0. In fact, such a vector is given by

w_{1} = 2f_{n−1} − 2, w_{2} = 2f_{n−1} − f_{n−2} − 1, and w_{i} = f_{n−i+2} (13)

for 3 ≤ i ≤ n, where f_{m} is the mth term of the Fibonacci sequence.

Proof. Let us take w_{n} = f_{2} = 1 and w_{n−1} = f_{3} = 2. Then by orthogonality with v_{n−2} we have w_{n−2} = 2w_{n−2} − w_{n} = 3 = f_{4}. It follows by induction that w_{i} = f_{n−i+2} whenever 3 ≤ i ≤ n, for if this is true for all j such that i < j ≤ n, then by orthogonality with v_{i} we have

w_{i} = 2w_{i+1} − w_{i+3} = 2f_{n−(i+1)+2} − f_{n−(i+3)+2}
= 2f_{n−i+1} − (f_{n−i+1} − f_{n−i}) = f_{n−i+1} + f_{n−i}
= f_{n−i+2}.

Next, by orthogonality with v_{2} we have w_{1} = 2w_{3} − w_{n−1} = 2f_{n−1} − 2, and by orthogonality with v_{1} we have w_{2} = w_{1} −w_{4} +w_{n} = 2f_{n−1} −2−f_{n−2} +1 = 2f_{n−1} − f_{n−2} − 1 = f_{n−1} + f_{n−3} − 1. Finally, it is an easy exercise to verify that w_{1} > w_{2} > … > w_{n} > 0, because (f_{m}) is an increasing sequence of positive integers.

Lemma 7. L_{w} ∩ T_{2}^{n} = {0, ±v_{1}, ±v_{2}, …, ±v_{n−2}, ±v_{n−1}}, where v_{n−1} is the vector −(∑_{i=1}^{n−2} v_{i}) = (0, 1, −1, 0, −1, 0, …, 0, 1).

Proof. Let v be any non-zero vector in L_{w} ∩ T_{2}^{n}, and let i be the smallest positive integer such that x_{i}(v) ≠ 0. Without loss of generality we may assume that x_{i}(v) > 0, and therefore x_{i}(v) = 1 or 2. If x_{i}(v) = 2, however, then orthogonality of v with w must correspond to an equation of the form 2w_{i} − w_{r} − w_{s} = 0 with i < r < s or 2w_{i} − 2w_{r} with i < r, both of which are impossible since the co-ordinates of w are strictly decreasing. Thus x_{i}(v) = 1, and orthogonality of v with w must correspond to an equation of the form w_{i}−w_{r}−w_{s}+w_{t} with i < r < s < t, or w_{i}−2w_{r}+w_{t} = 0 with i < r < t. These two possibilities can be amalgamated into one by considering the equation as w_{i} − w_{r} − w_{s} + w_{t} with i < r ≤ s < t. Again we proceed case-by-case.

Case 1: Suppose i = 1. Then w_{1} = w_{r}+w_{s}−w_{t} < 2w_{r} so 2f_{n−1}−2 < 2f_{n−r+2} and therefore f_{n−1} < f_{n−r+2} + 1, which implies r ≤ 3. Next, if r = 3 then w_{1} = w_{3} + w_{s} − w_{t} < w_{3} + w_{s}, so 2f_{n−1} − 2 < f_{n−1} + f_{n−s+2} and therefore f_{n−s+2} > f_{n−1} − 2, which implies s ≤ 3 (because n ≥ 8), giving r = s = 3 and then w_{t} = 2w_{3} − w_{1} = 2f_{n−1} − 2f_{n−1} + 2 = 2, so t = n − 1 and v = (1, 0, −2, 0, …, 0, 1, 0) = v_{2}. Similarly, if r = 2 then we find that w_{1} = w_{2} + w_{s} − w_{t} < w_{2} + w_{s}, so 2f_{n−1} − 2 < 2f_{n−1} − f_{n−2} − 1 + f_{n−s+2} and therefore f_{n−s+2} > f_{n−2} −1, which implies s ≤ 4. If r = s = 2, however, then w_{t} = 2w_{2} − w_{1} = 2(2f_{n−1} − f_{n−2} − 1) − 2f_{n−1} + 2 = 2f_{n−1} − 2f_{n−2} = 2f_{n−3}, which is impossible (since 2f_{n−3} > f_{n−3} + f_{n−4} = f_{n−2} while also 2f_{n−3} < f_{n−3} + f_{n−2} = f_{n−1}). Similarly, if r = 2 and s = 3 then w_{t} = w_{2} + w_{3} − w_{1} = 2f_{n−1} − f_{n−2} − 1 + f_{n−1} − 2f_{n−1} + 2 = f_{n−1} − f_{n−2} + 1 = f_{n−3} + 1, which is also impossible (since n − 3 ≥ 5). Hence if r = 2 then s = 4, in which case w_{t} = w_{2} + w_{4} − w_{1} = 2f_{n−1} − f_{n−2} − 1 + f_{n−2} − 2f_{n−1} + 2 = 1, giving t = n and v = (1, −1, 0, −1, 0, …, 0, 1) = −v_{1}.

Case 2: Suppose i = 2. Then 2w_{r} > w_{r} + w_{s} − w_{t} = w_{2} so

2f_{n−r+2} > 2f_{n−1} − f_{n−2} − 1 = 2(f_{n−2} + f_{n−3}) − f_{n−2} − 1
= f_{n−2} + 2f_{n−3} − 1 > f_{n−2} + f_{n−3} + f_{n−4} = 2f_{n−2},

and therefore r ≤ 3, so r = 3, and

w_{s} − w_{t} = w_{2} − w_{3} = f_{n−1} − f_{n−2} − 1 = f_{n−3} − 1.

If s ≥ 6, then n − s + 2 < n − 3 and so w_{s} − w_{t} = f_{n−s+2} − f_{n−t+2} < f_{n−3} − 1, a contradiction, hence 3 ≤ s ≤ 5. If s = 5, then f_{n−3} − 1 = w_{s} − w_{t} = f_{n−s+2} − f_{n−t+2} = f_{n−3} − f_{n−t+2} so f_{n−t+2} = 1, giving t = n, and then v = (0, 1, −1, 0, −1, 0, …, 0, 1) = v_{n−1}. If s = 4, then f_{n−t+2} = w_{t} = w_{s} − f_{n−3} + 1 = f_{n−2} − f_{n−3} + 1 = f_{n−4} + 1, which is impossible since n ≥ 8. Finally (in the case where i = 2) if s = 3, then t ≥ 4 so w_{t} ≤ f_{n−2} and therefore w_{s} − w_{t} ≥ f_{n−1} − f_{n−2} = f_{n−3} > f_{n−3} − 1, another contradiction.

Case 3: Suppose i ≥ 3. If r ≥ i+2, then f_{n−s+2} = w_{s} > w_{s} −w_{t} = w_{i} −w_{r} ≥ w_{i} − w_{i+2} = f_{n−i+2} − f_{n−i} = f_{n−i+1}, which implies n − s + 2 > n − i + 1, so s < i + 1 < r, a contradiction. Thus r = i + 1, and w_{s} − w_{t} = w_{i} − w_{r} = f_{n−i+2} − f_{n−i+1} = f_{n−i}. In particular, f_{n−s+2} = w_{s} > w_{s} − w_{t} = f_{n−i}, so n − s + 2 > n − i, giving s < i + 2, and therefore r = s = i + 1. It follows that f_{n−t+2} = w_{t} = w_{r} + w_{s} − w_{i} = 2w_{i+1} − w_{i} = 2f_{n−i+1} − f_{n−i+2} = f_{n−i+1} + (f_{n−i+1} − f_{n−i+2}) = f_{n−i+1} − f_{n−i} = f_{n−i−1}, and thus either t = i + 3 (if i ≤ n − 3) or t = i + 2 = n (if i = n − 2), giving v = v_{i} in both cases.

Hence the only non-zero vectors in L_{w} ∩T_{2}^{n} are ±v_{1}, ±v_{2}, …, ±v_{n−1}.

By Theorem 1, we have g(n, 2) = n − 1 for all n ≥ 8.

4.5 Remaining cases

The results for the remaining cases were obtained with the help of the computer algebra system Magma [1], using the same techniques of enumeration as described by Fishburn in [6, Section 4], but also checking the results for both representability and almost representability (using techniques of linear programming) as in [2].

In the case where n = 5 and k = 2, we have found that there are precisely 286 orders on P_{2}[5] which satisfy the IES, of which 114 are representable and 172 are not, and that all of the latter fail C_{3}, and all but 40 are all almost representable. One example of an almost representable order that fails C_{3} is the following (in which ij denotes the obvious multiset of cardinality 2): 1^{2} ⪰ 12 ⪰ 13 ⪰ 14 ⪰ 2^{2} ⪰ 15 ⪰ 23 ⪰ 24 ⪰ 3^{2} ⪰ 34 ⪰ 25 ⪰ 35 ⪰ 4^{2} ⪰ 45 ⪰ 5^{2}; this is almost representable via the vector w = (6, 4, 3, 2, 1). Thus f(5, 2) = g(5, 2) = 3.

For n = 5 and k = 3, there are precisely 68820 orders on P_{3}[5] satisfying the IES, of which 6588 are representable and 62232 are not. Of those which are not representable, 62208 fail C_{3}, while 24 satisfy C_{3} but fail C_{4}. All of the latter 24 are almost representable, and one such example is given by 1^{3} ⪰ 1^{2}2 ⪰ 1^{2}3 ⪰ 1^{2}4 ⪰ 1^{2}5 ⪰ 12^{2} ⪰ 123 ⪰ 124 ⪰ 13^{2} ⪰ 125 ⪰ 134 ⪰ 2^{3} ⪰ 14^{2} ⪰ 135 ⪰ 2^{2}3 ⪰ 145 ⪰ 2^{2}4 ⪰ 23^{2} ⪰ 15^{2} ⪰ 2^{2}5 ⪰ 234 ⪰ 24^{2} ⪰ 3^{3} ⪰ 235 ⪰ 3^{2}4 ⪰ 245 ⪰ 34^{2} ⪰ 3^{2}5 ⪰ 25^{2} ⪰ 4^{3} ⪰ 345 ⪰ 4^{2}5 ⪰ 35^{2} ⪰ 45^{2} ⪰ 5^{3}; this is almost representable via w = (20, 10, 6, 4, 1). Thus f(5, 3) = g(5, 3) = 4.

For n = 6 and k = 2, there are precisely 33592 orders on P_{2}[6] which satisfy the IES, of which 2608 are representable and 30984 are not. Of those which are not representable, 30980 fail C_{3}, while the other four satisfy C_{3} and C_{4} but fail C_{5}. All of the latter four are almost representable, and one such example is 1^{2} ⪰ 12 ⪰ 13 ⪰ 14 ⪰ 15 ⪰ 2^{2} ⪰ 23 ⪰ 24 ⪰ 3^{2} ⪰ 34 ⪰ 16 ⪰ 25 ⪰ 4^{2} ⪰ 35 ⪰ 45 ⪰ 26 ⪰ 36 ⪰ 5^{2} ⪰ 46 ⪰ 56 ⪰ 6^{2}; this is almost representable via w = (12, 8, 7, 6, 4, 1). Thus f(6, 2) = g(6, 2) = 5.

For n = 7 and k = 2, there are 23178480 orders on P_{2}[7] which satisfy the IES, of which 107498 are representable and 23070982 are not. Of those which are not representable, 23069816 fail C_{3}, 1138 fail C_{5} but satisfy C_{3} and C_{4}, and 28 fail C_{6} but satisfy C_{3}, C_{4} and C_{5}. Also, of the 1138 that fail C_{5} but satisfy C_{3} and C_{4}, 1078 are almost representable, while the other 60 are not almost representable. Finally, all of the 28 that fail C_{6} but satisfy C_{3}, C_{4} and C_{5} are almost representable; one such example is 1^{2} ⪰ 12 ⪰ 13 ⪰ 14 ⪰ 15 ⪰ 16 ⪰ 2^{2} ⪰ 23 ⪰ 24 ⪰ 25 ⪰ 3^{2} ⪰ 34 ⪰ 17 ⪰ 35 ⪰ 4^{2} ⪰ 45 ⪰ 26 ⪰ 5^{2} ⪰ 36 ⪰ 46 ⪰ 56 ⪰ 27 ⪰ 37 ⪰ 47 ⪰ 6^{2} ⪰ 57 ⪰ 67 ⪰ 7^{2}; this is almost representable via w = (22, 14, 12, 11, 10, 6, 1). Thus f(7, 2) = g(7, 2) = 6.

This completes the proof of Theorem 2. It is interesting to note that for each of the cases (n, k) = (5, 2), (6, 2) and (7, 2), there are no orderings that fail C_{4} but satisfy C_{3}. We do not yet understand why that happens.

5 A Conjecture

The results of this paper give us reason to formulate the following:

Conjecture 1. f(n, k) = g(n, k) for all n ≥ 3 and k ≥ 1.

References

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

[2] Conder, M., Slinko, A.: A Counterexample to Fishburn’s Conjecture on Finite Linear Qualitative Probability. Journal of Mathematical Psychology 48(6), 425–431 (2004)

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

[4] Dershowitz,N. Termination of Rewriting. In: Proc. First Internat. Conf. on Rewriting Techniques and Applications, Lecture Notes in Computer Science, Vol 202 (Springer, Berlin, 180–224 (1985).

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

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

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

[8] Herstein, I.N., Milnor J.: An Axiomatic Approach to Measurable Utility. Econometrica 23, 291–297 (1953)

[9] Katzner, W.D.: Static Demand Theory. MacMillan, London (1970)

[10] Koopmans, T.C.: Representation of Preference Orderings with Independent Components of Consumption and Representation of Preference Orderings over Time. in: McGuire, C.B., Radner, R. (Eds.) Decision and Organization. pp. 57–100. North-Holland, Amsterdam, 1972.

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

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

[13] Marshak, J.: Rational Behavior, Uncertain Prospects, and Measurable Utility. Econometrica 18, 111–141 (1950)

[14] Martin,U. A Geometric Approach to Multiset Ordering, Theoretical Computer Science, 67, 37–54 (1989).

[15] Regoli, G.: Comparative probability orderings. In: Imprecise Probabilities Project. Documentation. http://www.sipta.org/documentation/comparative prob/regoli.pdf. Cited 19 Sept 2006 (2006)

[16] Robbiano, L.: Term orderings on the polynomial ring. In: EURO-CAL’85, Linz, 1985, vol. 2. Lecture Notes in Comput. Sci., vol. 204, Springer, Berlin, pp. 513–517.

[17] Savage,L.J. The Foundations of Statistics. New York, John Wiley and Sons, 1954.

[18] Sertel, M.R., Kalaycıoğlu, E.: Toward the Design of a New Electoral Method for Turkey (in Turkish) TÜSIAD, Istanbul (1995)

[19] Sertel, M., Slinko, A.: Ranking Committees, Words or Multisets. Nota di Laboro 50.2002. Center of Operation Research and Economics. The Fundazione Eni Enrico Mattei, Milan (2002)

[20] Sertel, M. and A. Slinko, A.: Ranking Committees, Income Streams or Multisets. Economic Theory, 30(2): 265–287 (2007)

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

[22] von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior, Section 3 and Appendix. Princeton University Press (1947)

[23] Wakker, P.P.: Additive Representations of Preferences. Kluwer (1989)