Please see PDF version
JOURNAL OF MATHEMATICAL PSYCHOLOGY Vol. 11, No. 2, May 1974
Limit Properties of Luce's Choice Theory
J. MICHAEL STEELE
Department of Mathematics, Stanford University, Stanford, California 94305
Luce's Axiom is interpreted in terms of a sequence of measures on the unit interval, and their limit properties are discussed. In particular, all limit laws are found to be either absolutely continuous with density x~ for a c ( 1, oo) or else degenerate laws consisting of a point mass at 0 or 1. A close connection between Luce's choice theory and Karamata's theory of regularly varying functions is established and systematically used.
INTRODUCTION
A principal problem of choice theory is how preferences among a finite set of alternatives change as the set is enlarged. A model for this situation has often been given in terms of probability distributions on the set of alternatives. To describe these models let A,, A2 An denote a set of alternatives and suppose Pk 1 < k < n gives the probability of the kth alternative being chosen. Now if A,, A2 A,,, An+, is an increased collection of alternatives, the fundamental problem is to predict the probabilities Pk' 1 < k < n + 1 which describe the kth alternative being chosen from the increased collection.
In this situation Luce (1959) suggested an axiom which has considerable mathematical elegance. If we assume Pk 0 0 for 1 < k n then Luce's axiom implies that Pi'lPk' = AIPk for all j, k such that j < n and k n.
The range of validity of this assumption has been widely studied, and it seems justified in a variety of important contexts. We refer here to Luce (1959) and also Tversky (1972) where the instances that the assumption is justified or unjustified are well discussed.
The focus of this paper is on the analysis of sequences of probability distributions which satisfy Luce's Axiom. To facilitate the statement of results it is convenient to make the following definition. A sequence of probability distributions L, = (pn(l), p.(2),..., p.(n)) for n 2, 3.... is called a Luce process if for all j and k such that j < min(n, m) and k min(n, m) it follows that
p.(j)lp.(k) = p.(j)lp.(k).
It is further assumed that p,(k) :7~ 0 for n >, 2 and 1 < k n since in (*) this is tacitly required.
124
Copyright 0 1974 by Academic Press, Inc. All rights of reproduction in any, form reserved.
i
i
1
1
125 LIMIT PROPERTIES OF LUCE'S CHOICE THEORY
The first part of our program is to establish the existence of a large class of Luce processes and to obtain useful representations for them. This will then make it possible to give a complete statement of the limit questions which are investigated and which are the main results of this paper. As background for the solution of the limit problems, we set forth in Section 11 the results and notation which will be needed from the theory of regularly varying functions. The main results on the limit behavior of Luce processes are proved in Section III and then in the last section the meaning of these results is discussed.
1. ExiSTENCE AND REPRESENTATION OF LUCE PROCESSES
To construct a Luce process, let v be a function from the strictly positive integers to the strictly positive reals, and define the probabilities p,,(k) by p,,(k) = v(k)/(v(l) + v(2) + ... + v(n)) for 1 < k < n and for n = 2, 3,... . Now if j < min(n, m) and k < min(n, m) we have p.(j)lp,,(k) = v(j)lv(k) = p,,,(j)lp,,(k) This shows that the distributions L,, defined by p,,(k) do indeed form a Luce process.
An exceedingly convenient aspect of Luce processes is that any such process can be represented by some v in the manner just described. In proving this, we will examine the special role of p,,(n) which, as defined above, is the probability of chosing the nth alternative from the set of the first n alternatives. We show that the sequence p,,(n), n = 2, 3,..., uniquely determines the Luce process L = {LJ' 2 and then use this to establish the correspondence between the functions v and the processes L. In order to clean notation and to stress the relationship between v(n) and p,,(n) we define a function p on the positive integers by p(n) ~ p,,(n), and the function p defined in this way is said to be associated with L. We now proceed by a short sequence of propositions.
PROPOSITION 1. If p(n) is associated with Luce processes L and E, then L =L'.
Proof. For n = 2 we have L, = (p,(1), P2(2)) and L2' = (PA1), pJ(2)), and by h~pothesis P2(2) = p(2) = PA2). Hence we also have p,(1) ~ 1 p(2) ~ P2,0), and thus L,, = LJ. Now we proceed by induction, so assume L,, = L.'. Then just applying the definitions p,,(k) = v(k)l(v(l) + ... + v(n)) and p,,(n) = p(n) we have the following.
L,,+1 = (pn+l(l)y pn+1(2),. , p.+,(n + 1))
= Q1 p(n + 1)) p.(1),..., (1 p(n + 1)) p.(n), p(n + 1))
= Q1 p(n + 1)) p (1 p(n + 1)) p.'(n), p'+,(n + 1))
n
= (p'+1(1), p' 1(2),..., pn+l(n)~ P~+1(n + 1)) = L'
n n+ n+l
Hence we have L,, ~ L,,' for all n 2 and thus L = L' as claimed.
i
i
i
i
J. MICHAEL STEELE 126
Now denote by Z+ the strictly positive integers and R+ the strictly positive reals.
PROPOSITION 2. There is a one one correspondence between Luce processes and functions v : Z+ >. R+ such that v(l) = 1.
Proof. Let L be a Luce process, and let p be the associated function defined by p(n) = p,,(n). Since p,(n) ::A 0 it is possible to define v : Z+ > R+ inductively by v(l) = 1 and v(n) = p(n)(1 p(n)) 1 (v(l) + .. + v(n 1)). Now let L' be the Luce process defined by p,,'(k) v(k)l(v(l) + + v(n)) for 1 ~< k < n and n >, 2. In particular, calculating p,,'(n) we have
p.'(n) = v(n)/(v(l) + = p(n)(1 p(n)) 1 (v(1) + + v(n 1))/(v(1) + ... + v(n)) = p(n)(1 p(n)) 1/(1 p(n)) 1 = p(n).
This shows that L and L' have the same associated functions and hence, by Proposition 1, L = E. Further, since v represents L' it also represents L so all that remains to show is that v is uniquely determined. But since p is uniquely determined and since the conditions that v(l) = 1 and v(n)/v(l) + ... + v(n) = p(n) uniquely determine v, the one one correspondence is established.
PROPOSITION 3. If q(n) is a sequence of probabilities which are never 0 or 1, then there exists a unique Luce process L such that the associated function p of L satisfies p(n) = q(n).
Proof. If v is defined inductively by v(l) = 1 and v(n) = q(n)(1 q(n)) 1 (v(l) + + v(n 1)) then a Luce process L can be defined by v. Now on calculating the p function associated with L as in Proposition 2, we see that p(n) = q(n). This proves the existence asserted in the proposition, and the uniqueness is a consequence of Proposition 1.
The preceding propositions continue the ideas of Luce (1959), and they lay a foundation for the study of the limiting behavior of the distributions L,, ~
p,,(n)). To facilitate the study of this behavior, we will represent the distributions L,, by measures P,, on a fixed probability space. This is accomplished by defining measures P,, on [0, 1] by putting atoms of mass p,,(k) at the points kIn for 1 :~ k < n and n >, 2. The measures P,, defined in this way will be called the associated measures of the Luce process L.
The fundamental limit problems for Luce processes can now be put as follows.
(a) What are the possible limit laws? That is, which measures on [0, 1] can arise as the limit in distribution of the measures P,, associated with some L?
(b) Under what conditions on the representing function v or on the associate function p, do the measures P,, converge?
i
1
i
i i 1 i
127 LIMIT PROPERTIES OF LUCE'S CHOICE THEORY
These questions, and also other questions, are answered by the theorems of Section Ill. These theorems based on the theory of regularly varying functions and the essential results which will be used are presented in the next section.
II. BACKGROUND ON REGULARLY VARYING FUNCTIONS
The results summarized in this section are due to Karamata (1933) and recent expositions can be found in the books by Feller (1971) and deHaan (1970). First, we define a function U : R+ > R+ to be regularly varying of exponent a if lir t . U(tx)l U(t) = x. for all x c [0, co]. The applicability of this definition is further extended by the convention that the symbol x be interpreted as 00 for x > 1 and as 0 for x < 1. Likewise x is interpreted as oo or 0 according as x < 1 or x > 1, and the symbols x and x are left undefined for x = 1. We now state as lemmas some of the basic facts about the functions just defined.
LEMMA 1. Let U be a positive monotone function on [0, oo] such that limt_. U(tx)1U(x) = 0(x) < oo on a dense subset A of [0, co]. Then 0(x) = x01 where 00 < 0C ~< 00.
Proof. Feller (1971), p. 275, Lemma 1.
LEMMA 2. Suppose U: R+ >. R+ is an a varying function with a c [ 1, oo]. Then fo U(t) dt is et + 1 varying.
0
Proof. deHaan (1970), p. 13, Lemma 1.2.2.
lot LEMMA 3. Suppose U(x) ~ fo u(t) dt and u(t) is monotone. Then if U(x) is a
0
varying with ot > 0 then u(x) is a 1 varying.
Proof. Feller (1971), p. 446, Lemma to Theorem 4.
LEMMA 4. Suppose U: R+ R+ is Lebesgue summable on finite intervals. If
lim 0
xU(x)lfo U(t) dt = a with a c (0, oo) then U is a 1 varying.
Proof. deHaan (1970), p. 16, Theorem 1.2.1, part b.
LEMMA 5. Suppose V is a varying for a c oo, co) and that V(x) v(t) dt
0
where v(t) is monotone, then
lirn xv(x)IV(x) a
X~m
Proof. deHaan (1970), pp. 22 23, Corollary 1.2.1, part 8.
J. MICHAEL STEELE 128
Finally, in order to apply the preceding lemmas to the theory of Luce processes we extend the domain of definition of the functions v and p to R+. As usual we denote by [x] the greatest integer less than or equal to x. For x > 1 the functions v and p can be
extended by defining v(x) = v([x]) and p(x) = p([x]), and for x < 1 v and p can be given the arbitrary value 0 since these functions will never be used in this range.
III. THE LIMIT THEORY OF LuCE PROCESSES
The first theorem of this section shows that the limit laws which arise from Luce processes are of a remarkably simple type.
THEOREM 1. If the measures & associated with a Luce process L converge in distribu
tion to P then P[O, x] xa for 0 <, oo.
Proof. Let U(x) Y,~"'
2=1 V(i) if x >, 1 and U(x) = 0 if 0 < x < 1, where v is taken, as usual, to be the representing function for the process L. Further, we have
,., v(i)/yltl
U(xt)l U(t) Y"0" _i_l v(i) = P[,]([0, [xt]l[t]]) for t > 1. Now, since (xt 1)1t <,
[xt]l[t] < xtl(t 1) we have for x c (0, 1) and sufficiently large t that
PulA (xt W1 < U(XtYu(t) < Pullo, XtAt M. (1
P has at most countably many atoms so that for a dense subset A of [0, 1] the left and right expressions of (1) must have the same limit as t > oo. Letting 0(t) denote this common limit where it exists, we can write for x e A that lim, . U(xt)l U(t) = 0(t). But, now choose x > 1 such that I 1x e A. Then lim,_, U(t(x))JU(t) = 0(11x) so also limt ,, U(t)1U(tx) = 0(11x). Since A is dense in (0, 1) we have B = {x : I lx c A} is
dense in (1, oo). On B define 0 by the relation 0(x) = 110(11x) <, oo. This gives that
lim U(xt)JU(t) = 0(x) for xeAUB.
Lemma 1 is applicable since U is positive and monotone, so consequently lim, . U(xt)l U(t) = xa for oo < a oo and x e A U B. By (1) it is necessary that xa be bounded on [0, 1] and hence 0 c£ < oo. Also by (1) and the definition of A we have P[O, x] = xm for 0 < a < oo.
COROT.LARY 1. 1. If the measures P,, associated with a Luce process converge to P in distribution, then either P is absolutely continuous or else consists of a unit mass at 0 or 1.
Proof. This is just the qualitative distinction of the cases a c (0, 1), 0, and
= 00.
i
129 LIMIT PROPERTIES OF LUCE'S CHOICE THEORY
COROLLARY 1.2. If & are associated with a Luce process and if lim,, PJO, y] for some y e (0, 1), then P,,, converge in distribution to the measure P with distribution P[O, x] = xa where o£ = log P1logy if P 0 0 and a ~ oo if P = 0.
Proof. If we take any subsequence P,,, of the & then by Helley's selection theorem there is a subsequence P,,,, of P,,, which converge in distribution. But by Theorem 1 the limit P of the subsequence P,,,, must be such that P[O, x] = xQ and in particular a must be the same a as stated in this corollary. Since every subsequence of & has a subsequence which converges to P it follows that & converge to P.
The next two theorems give conditions under which & converge and show that this convergence is very closely connected with the regular variation of the representing function v and the associated function p.
THEOREM 2. Suppose measures P,, are associated with a Luce process which is represented by v. If v is regularly varying with exponent cc >, 1 then lim,, . PJO, x] = xol+1. Conversely, if v is ultimately monotone and PJ0, x] ~ xQ with a > 0 then v is regularly varying with exponent a 1.
Proof. First, define two functions V and U by V(x) f X v(t) dt and U(x) =
[X] 0
1j 1 v(i) with the understanding that U(x) = 0 for x e [0, 1). Since PJ0, x] = U(=)1U(n), the direct part of the theorem is proved if U is proved to be a + 1 regularly varying. Note that by Lemma 2 V is a + 1 varying so we proceed by comparing U and V.
For the moment, consider the case a :y~ oo. Choose a > 1, then for x > (a we have
1 < U(x)IV(x) < V(x + IflV(x) < V(ax)IV(x).
Hence, 1 sup V(x)l V(x) < &+' and by the arbitrariness of a, lim,, . sup
U(x)IV(x) 1. The same result holds for lim,, . inf U(x)IV(x), and thus U(x) and
V(x) are asymptotic provided a :7~ oo. This implies that U(x) is a + 1 varying and
completes the direct part of the proof in this case.
Now suppose a = oo and fix a, b c (0, 1). If x > 1 la(l b) we have U(abx) <, V(ax) and we always have V(x) < U(x) so
0 < Qabx)JU(x) < V(ax)IV(x). (2)
Since V is regularly varying of exponent a + 1 = oo the right hand side of (2) converges to 0 as x ). oo. This gives lim,, . PJO, ab] = 0, and since the product ab can equal any x e [0, 1] we have lim,, . PJO, xl ~ xl. That is, the measures & converge in distribution to a unit mass at x ~ 1.
For the converse, suppose that PJO, xl = xol for a c~ (0, oo). We then have that U(x) is regularly varying with exponent a. By essentially the same estimates as in the first part of the proof, this implies that V(x) is also regularly varying of exponent OC.
J. MICHAEL STEELE 130
But by Lemma 3 this says v is regularly varying with exponent a 1, so Theorem 2 is proved.
In Theorem 1 it was proved that any limit of a Luce process must be a law of the form P[O, x] ~ xl a e [0, col, and as a corollary of Theorem 2 we have the result (which can also be proved directly) that all such laws are possible.
COROLLARY 2. 1. If P [0, x] = xl for oc E [0, col, then there exist a Luce process L with associated measures P,, such that lim,, . RJ0, xl = P[O, xl = xl~.
Proof. Define a representing function v for L by v(x) = xl 1 for a e [0, oo] and v(x) = exp x for a ~ oo. Since these functions are respectively a 1 and oo varying Theorem 2 implies the corollary.
The next theorem accomplishes for the associated function p much the same thing as Theorem 2 does for the representing function v. The only difference is that the quantities involved are more intuitive and the use of regular variation is covert.
THEOREm 3. Suppose p is the associatedfunction of a Luce process. If lim,, ~, np(n) et for a c (0, oo) then lim,,_,, PJO, x] = xa. Conversely, if the representing function v(x) is monotone and lim,, . PJ0, x] ~ l& for a c [0, oo], then lim,, . np(n)
Proof. Define (p(n) by the equation
,n+l
(n + 1) v(n + I)/ v(i) = (p(n + 1)oc
and note that T(n + 1) > 1 by the hypothesis.
Now
v(n + I)/E v(i) = 9,(n + 1) .1(n + 1 ap(n + 1))
i 1
and since (p(n) > 1 we have lim. . v(n + I)/E'n v(i) = 0. This guarantees that fo v(t) dt and 7,1M1 v(i) are asymptotic. Hence
lim np(n) = lim [xl vQx])11 v(i) lim. xv(x) v(t) dt.
n,~ X W X1W 0
By Lemma 4 this implies that v(x) is oc 1 varying and thus by Theorem 2 we have
lim. PJ0, X] = xa. [03
For the converse, first note that lim. PJ0, x] = xa implies that U(x) E, , v(i)
is regularly varying with exponent et. As in Theorem 2 this implies that V(x) =
S" v(t) dt is a varying. But since a. e [0, ool and v is assumed to be monotone it follows
0
from Lemma 5 that lim,,_. xv(x)l V(x) We also know from the proof of Theorem 2
that U(x) and V(x) are asymptotic so lim,,_. xv(x)l U(x) = a. By the definition of p
this implies lim, . np(n) = (x.
1
1
131 LIMIT PROPERTIES OF LUCE'S CHOICE THEORY
IV. CONCLUDING REMARKS
Luce's Axiom is firmly rooted in the literature of choice theory, and as an elegant probabilistic model the questions concerning its limit behavior deserve to be answered. There is another good reason to look for limit laws: simplicity. It is often the case that complicated matters become simple in the limit and Theorem 1 is an example of this.
As the focus of this paper has been on limit laws, the results set forth in Section I were created to form a foundation for such work. Proposition 2 was motivated by Theorem 3 of Luce (1959), but it is not evident that either of these results implies the other. The motivation for emphasizing the importance of p(n) in defining a Luce process was provided by the powerful results of Karamata's we have called Lemmas 4 and 5.
Of the results in Section Ill, Theorem 1 and the converse part of Theorem 3 deserve particular consideration. Theorem 1 says, of course, that any limit of a Luce process is a power law, that is, has distribution xl. One could not hope for anything more strikingly simple.
Theorem 3 also allows for some discussion. The result is in a way very natural, since it says, basically, that for convergence of P,, to a nontrivial law that the nth alternative should be chosen with probability on the order of 1In. Another aspect of Theorem 3 is that its essential ingredients Lemmas 4 and 5 are also the essential ingredients of the fundamental representation theorem of Karamata. Indeed the close connection bectween Luce's model in choice theory and Karamata's theory of regular variation is the basic contribution of this paper.
ACKNOWLEDGMENT
I am grateful to David Blower of the Department of Psychology of Stanford University for many invaluable discussions covering the spectrum of mathematical psychology.
REFERENCES
FELLER, WILLIAM. An introduction to probability theory and its applications, Volume 2. New York:
Wiley, 1971.
i)EHAAN, L. On regular variation and its application to the weak convergence of sample extremes.
Amsterdam: Mathematisch Centrurn Amsterdam, 1970.
KARAmATA, J. Sur un mode de croissance r6guli~re. Th6or~rnes fondamentaux. Bull. Soc. Math.
France, 1933, 61, 55 62. LucE, R. D. Individual choice behavior: a theoretical analysis. New York: Wiley, 1959. TvERsKY, Amos. Choice by elimination. J. Mathematical Psychology, 1972, 9, 341 367.
RECEIVED: JUNE 20, 1973
Printed by the St Catherine Press Ltd., Tempelhof 37, Bruges, Belgium.