A Teaching Note on a Theorem due to Kreps (1979)

Introduction

Often, in a two-period choice problem, ‘the first period choice is over pairs of the form (immediate payoff, opportunity set for the second period choice)’ (see Kreps 1979). An opportunity set is a non-empty subset of a non-empty finite set.

In this note we are concerned with a theorem in Kreps (1979) which goes thus: A reflexive, complete and transitive preference relation over a collection of intertemporal opportunities such that the available set of second period opportunity sets associated with each first period alternative is closed under unions can be represented as a sum of a finite number of indirect utility functions, if and only if two reasonably harmless properties are satisfied. This theorem is the second theorem in this note. An indirect utility function is a value function defined on collection of opportunities (opportunity = a first period alternative along with a non-empty subset of opportunity sets) of a constrained utility maximization problem, where the constraint set is an opportunity set associated with a first period alternative.

There is some difficulty in following the proof of the theorem that was originally indicated by Kreps and so in a later paper Modica (2002) indicated an alternative proof of the same theorem. Modica (2002) claims that this alternative proof is ‘an intuitively easier route to Kreps’ original result…’. Furthermore, the alternative proof is ‘essentially ready for use in a decision theory class’.

Perceptions of elegance and difficulty are extremely personal matters and so are best not debated. Also, the suitability of material from a pedagogic point of view depends on who comprises the audience and who is the instructor. Our contention here is that the core idea of the original proof due to Kreps (1979) is quite easy to understand and whatever difficulty there seems to arise concerns the numerical representation of the preference over opportunity sets, since it involves several functions. The core idea in the original proof is that given two assumptions, for every opportunity set, there is a uniquely largest set that contains it and is at the same time indifferent to it. What we provide here is an alternative numerical representation of the preference relation (utility function) when it is restricted to the class of these ‘largest opportunity sets’. We then define a negative valued function on the class of these ‘largest opportunity sets’, such that the utility of such a set is the sum of the negative values of the ‘largest opportunity sets’ that it contains. Thereafter the proof reverts back to the last few steps of the proof in Kreps (1979).

The targeted audience for this note is a graduate class in microeconomic theory, where if at all a course on choice theory based on Kreps (1979) could be thought of being taught. The contention of this note is that for such an audience, while the proof due to Modica (2002) may suffice, we have a better alternative based on the original proof by Kreps (1979) to offer.

Model

Almost as in Kreps (1979), there is a non-empty finite set X, representing possible first and second period consumption bundles. Let Ψ(X) be the set of all non-empty finite subsets of X. For each x ∈ X, there is a non-empty subset C(x) of Ψ(X) such that C(x) is closed under unions, that is, A, B ∈ C(x) implies A B ∈ C(x). C(x) is the set of second period opportunity sets that are available to the decision-maker if he chooses x in the first period. Let Ω = Each member of Ω is said to be an intertemporal opportunity and Ω is said to be the set of all intertemporal opportunities. The choice today is from a non-empty subset of Ω. It is assumed that the choice today can be represented by a complete and transitive binary relation ℜ on Ω. In what follows, we will refer to any complete binary relation over Ω whose asymmetric part is acyclic as a preference over intertemporal opportunities (PIO). We will denote the asymmetric part of a PIO ℜ by P(ℜ) and its asymmetric part by I(ℜ).

A PIO ℜ is said to satisfy monotonicity (M) if for all x ∈ X and A, B ∈ C(x): A ⊂ B implies (x, B)ℜ(x, A).

A transitive PIO ℜ on Ω is said to be an indirect utility (IU) if and only if there is a function U: X × X → ℝ such that for all (x, A), (y, B) ∈ Ω, (x, A)ℜ(y, B) if and only if ≥ .

A PIO ℜ is said to be justifiable (J) if and only if for x ∈ X and A, B ∈ C(x), (x, A)ℜ(x, B) implies (x, A)ℜ(x, A ∪ B).

The following result is easy to prove.

Theorem 1 (Kreps (1979)

A binary relation ℜ on Ω is a transitive PIO and satisfies M and J, if and only if it is an IU.

The Theorem That We Are Really Interested In Here.

The following example is a dynamic variant of an example in Kreps (1990).

Consider a person who has to choose between chicken (Ch) and fish (Fi) at both lunch and dinner. He packs either Ch or Fi for lunch and goes to work. He has his lunch at work. In the evening he dines out. In the evening he has a choice between three restaurants: one which serves only Ch, another which serves only Fi and a third which serves both. For reasons of health he prefers to have Fi at both meals. However, if he chooses to have Fi at lunch and dines at the restaurant which serves both Ch and Fi, then he becomes a victim of his temptation and chooses Ch over Fi.

In order to give the story an interesting twist, suppose that the ‘only Fi’ restaurant is out of bounds in the evening for those who have Ch during lunch.

Let X = {Ch, Fi}, C(Fi) = {{Ch}, {Ch, Fi}, {Fi}} and C(Ch) = {{Ch, Fi}, {Ch}}. Thus, Ω = ({Ch} × C(Ch)) ∪ ({Fi} × C(Fi)).

Let ℜ be a transitive PIO with I(ℜ) denoting its symmetric part and P(ℜ) denoting its asymmetric part. Suppose, (Fi, {Fi})P(ℜ)(Fi,{Ch, Fi})P(ℜ)(Ch, {Ch, Fi})P(ℜ)(Fi,{Ch})P(ℜ)(Ch,{Ch}). Clearly, ℜ violates the property J (since (Fi, {Fi})P(ℜ)(Fi, {Ch}) and yet it is not the case that (Fi, {Fi})I(ℜ)(Fi, {Ch, Fi})).

A PIO ℜ is said to satisfy Kreps (K) if for all x ∈ X and A, B, D ∈ C(x) with A ⊂ B: (x, A)I(ℜ)(x, B) implying (x, (A ∪ D))I(ℜ)(x, (B ∪ D)).

Note that the PIO in the above example does not violate the property K.

Theorem 2 (Kreps (1979)

A binary relation ℜ on Ω is a transitive PIO and satisfies M and K, if and only if there exists a non-empty finite set S and a real valued function U: X × X × S → ℝ such that for all (y, A) and (z, B)∈ Ω: (y, A)ℜ(z, B) if and only if ≥ .

Proof.

It is easily observed that if there exists a non-empty finite set S and a real-valued function U: X × X × S → ℝ such that for all (y, A) and (z, B) ∈ Ω: (y, A)ℜ(z, B) if and only if ≥ , then R is a transitive PIO and satisfies M and K. Thus, let us prove the converse. Hence, assume that R is a transitive PIO and satisfies M and K.

For each x ∈ X and A ∈ C(x), let F(x, A) = {B ∈ C(x)|A ⊂ B and (x, A)I(ℜ)(x, B)}. Since A ∈ F(x, A), F(x, A) ≠ φ. Let B, D ∈ F(x, A). Then (x, A)I(ℜ)(x, B) and (x, A)I(ℜ)(x, D). Since A ⊂ B and A ⊂ D, by the property K, (x, A ∪ D)I(ℜ)(x, B ∪ D) and thus by the transitivity of ℜ, we have (x, A)I(ℜ)(x, B ∪ D). Thus, B ∪ D ∈ F(x, A).

Let f(x, A) = . By the repeated use of the argument above, we obtain (x, A)I(ℜ)(x, f(x, A)). Since, A ⊂ f(A), we have A ∪ f(x, A) = f(x, A).

Observation 1: For all x ∈ X and A, B ∈ C(x), (x, A)I(ℜ)(x, A ∪ B) if and only if B ⊂ f(x, A).

By the property M, (x, A ∪ B)ℜ(x, A).

If B ⊂ f(x, A), then by the property M, (x, f(x, A))ℜ(x, A ∪ B). But (x, A)I(ℜ)(x, f(x, A)). Thus, by the use of transitivity, we obtain (x, A)ℜ(x, A ∪ B). This combined with (x, A ∪ B)ℜ(x, A) implies (x, A)I(ℜ)(x, A ∪ B).

Conversely, if (x, A)I(ℜ)(x, A ∪ B), then A ∪ B ∈ F(x, A) and so A ∪ B ⊂ f(x, A). Thus, B ⊂ f(x, A).

For x ∈ X, let S(x) = {B ∈ C(x)| B = f(x, B)}.

Observation 2: For all x∈X, A∈C(x) and B∈S(x): A⊂ B if and only if f(A,x) ⊂ B.

If f(A,x) ⊂ B, then clearly A ⊂ B.

On the other hand, if A ⊂ B, then (x,A)(ℜ)(x,f(x,A)) and the property K yields (x, B ∪ A)I(ℜ)(x, B ∪ f(x, A)). Thus, A ⊂ B implies (x, B)I(ℜ)(x, B f (x, A)) and so by Observation 1, f(x, A) B ⊂ f(x, B). However, B ∈ S implies f(x, B) = B. Thus, f(x, A) B ⊂ B, which implies f(x, A) ⊂ B.

Observation 3: For all x ∈ X and A, B ∈ C(x), (x, A)R(x, B) if and only if (x, f(x, A))ℜ(x, f(x, B)).

Follows from (x, f(A))I(R)(x, A)R(x, B)I(R)(x, f(B)) and the transitivity of R.

Observation 4: For all x ∈ X and A ∈ C(x), f(x, f(x, A)) = f(x, A).

(x, A)I(R)(x, f(x, A))I(R)(x, f(x, f(x, A)) and the transitivity of R implies (x, A)I(R)(x, f(x, f(x, A))). Since A ⊂ f(x, A) ⊂ f(x, f(x, A)), f(x, f(x, A)) ∈ F(A). Thus, f(x, f(x, A)) ⊂ f(x, A). This combined with f(x, A) ⊂ f(x, f(x, A)) gives f(x, A) = f(x, f(x, A)).

Let R0 be the restriction of R to S = . Clearly, R0 is complete (i.e., reflexive and total). By the property M of R, for all x ∈ X and A, B ∈ S(x) with A ⊂ B implies (x, B)R0(x, A).

Now, suppose for some x ∈ X and A, B ∈ S(x), we have A ⊂⊂ B (i.e., A ⊂ B and A ≠ B). Suppose A = f(x, A1) and B = f(x, B1) for some A1, B1 ∈ C(X). Thus, (x, A1)I(R)(x, A) and (x, B1) I(R)(x, B). If (x, A)I(R)(x, B), then by transitivity of R, we obtain (x, A1) I(R)(x, B). But this is not possible since B A = f(x, A1). Thus, (x, B)P(R0)(x, A).

Given a non-empty finite subset T of Ω, let M(T, P(R0)) = {(x, A) ∈ T|, and there does not exist (y, A’) ∈ T satisfying (y, A’)P(R0)(x, A)}.

Let S1 = M(S, P(R0)). Having defined Sk for k ≥ 1, stop if S = If S ≠ ,; then let Sk + 1 = M(S\, P(R0)). Since S is a finite set, there exists a least positive integer L, such that S =

Note that if (x, A) ∈ Sk, (x, B) ∈ S and A ⊂⊂ B, then (x, B) ∈ Sj for some j < k.

We want negative real numbers wk for k = 1, …, L, such that for all j, k ∈{1, …, L}: j k if and only if wj ≥ wk. Thus, wk can be thought of as the utility associated with the indifference class Sk, for k ∈ {1, …, L}. Furthermore, we also want a function v: X × S → , such that (a) v(x, A) < 0 for all (x, A) ∈ S and (b) for all k ∈ {1, …, L} and (x, A) ∈ Sk, v(x, A) + = = wk.

Let q denote the cardinality of Ω.

Define functions v: X × S → and the real numbers wk for k ∈{1,…,L} inductively as follows:

For all (x, A) ∈ S1, let v(x, A) = –1 and w1= –1.

Having defined v on , and negative real numbers w1,…, wk for k ≥ 1, stop if = L. If k < L, then let wk + 1 = – and for (x, A) ∈ Sk + 1, let v(x, A) = wk + 1– . Note that for all (x, A) ∈ Sk + 1, v(x, A) is an integer in the interval [wk + 1, wk + 1 – qwk], where wk + 1 – qwk = –1.

Thus, v(x, A) < 0 for all (x, A) ∈ S.

Let U: X × X × S → be defined as follows. For all x, z ∈ X and (y, B) ∈ S, let U(x, z, (y, B)) = 0 if either x ≠ y or x ∉ B and U(x, z, (y, B)) = v(y, B) if x = y ∈ B.

Let V: Ω → be defined as follows. For all (x, A) ∈ Ω, V(x, A) =

For all (x, A) ∈ Ω and (y, B) ∈ S, max_z∈AU(x,z,(y,B)) = 0, if either x ≠ y or A\B ≠ φ and max_z∈AU(x,z,(y,B)) = v(y, B), if x = y and A ⊂ B.

Thus, V(x, A) = for all (x, A)∈Ω. However, from Observation 2, we obtain that for all x∈ X, A ∈ C(x) and B ∈ S(x), A ⊂ B if and only if f(x, A) ⊂ B.

Thus, V(x, A) = V(x, f(x, A)) = = wk(x, f(x, A)), where (x, f(x, A)) ∈ Sk(x, f(x, A)).

For all (x, A), (y, A’) ∈ Ω: (x, A)R(y, A’) if and only if (x, f(x, A))R(y, f(y, A’)). But (x, f(x, A))R(y, f(y, A’)) if and only if wk(x, f(x, A)) ≥ wk(y, f(y, A’)), that is, V(x, f(x, A)) ≥ V(y, f(y, A’)).

Thus, for all (x, A), (y, A’) ∈ Ω: (x, A)R(y, A’) if and only if V(x, A) = ≥ = V(y, A’). Q.E.D.

Acknowledgements

There are many reasons behind this teaching note. During the latter half of 2014 professional obligations awakened me to the fact that I had to revisit the Kreps (1979) result. Subsequently there were lively exchanges and animated discussions with Simon Grant, Lin Hsieh, Meng-Yu Liang and Arkaadii Slinko on related issues. All this convinced me that I had yet to comprehend fully the significance of the Kreps (1979) paper. Perhaps that is true even today. This led me to prepare this teaching note, the earliest version of which is available on https://groups.google.com/forum/#!forum/decision_theory_forum. I am very grateful to Anirban Ghatak for pointing out howlers in an earlier version of this note and for suggesting improvements. I would also like to thank Clemens Puppe for his comments on the issue. The latest version resulted after Nick Baigent took charge and advised me to include an example, without which he thought the paper would be incomprehensible. Thank you very much Nick for your help and guidance all along and in particular for this note. Ratul Lahkar endorsed Nick's views and I thank him for the same. I would also like to thank an anonymous referee of this journal for comments on this paper. A word of caution: Although I claim that this is a teaching note (since the contribution here is too thin to pass off as anything else, in spite of any pedagogic value that it may otherwise possess) due to unavoidable circumstances it has never been used in a classroom.