Open access peer-reviewed chapter

Infinite Supermodularity and Preferences

Written By

Alain Chateauneuf, Vassili Vergopoulos and Jianbo Zhang

Submitted: March 4th, 2018 Reviewed: May 28th, 2018 Published: September 26th, 2018

DOI: 10.5772/intechopen.79150

Chapter metrics overview

1,022 Chapter Downloads

View Full Metrics

Abstract

This chapter studies the ordinal content of supermodularity on lattices. This chapter is a generalization of the famous study of binary relations over finite Boolean algebras obtained by Wong, Yao and Lingras. We study the implications of various types of supermodularity for preferences over finite lattices. We prove that preferences on a finite lattice merely respecting the lattice order cannot disentangle these usual economic assumptions of supermodularity and infinite supermodularity. More precisely, the existence of a supermodular representation is equivalent to the existence of an infinitely supermodular representation. In addition, the strict increasingness of a complete preorder on a finite lattice is equivalent to the existence of a strictly increasing and infinitely supermodular representation. For wide classes of binary relations, the ordinal contents of quasisupermodularity, supermodularity and infinite supermodularity are exactly the same. In the end, we extend our results from finite lattices to infinite lattices.

Keywords

  • supermodularity
  • ∞-supermodularity
  • lattice
  • JEL Classifications: D11
  • D12
  • C65

1. Introduction

The aim of this chapter is mainly twofold. It intends first to emphasize that on finite lattices, preferences merely respecting the lattice order cannot disentangle the usual economic hypothesis of supermodularity representations from the much stronger supermodular representations. Thus, we complement the work of Chambers and Echenique [1, 2] who nicely prove under the assumption of weak monotonicity that supermodularity is equivalent to the notion of quasisupermodularity introduced by Milgrom and Shannon [3].

Second, we aim at offering simple constructive proofs for the existence of -supermodular representations on finite lattices, hence generalizing to finite lattice the characterization obtained on finite Boolean Algebras by Wong, Yao and Lingras [4] of complete preorders representable by belief functions.

It is well known that supermodularity is a concept widely used in relation with economies of scale. It indicates a synergy relationship of subsystems, so that the marginal returns to the marginal element are closely related to the size of the existing elements. This creates nonlinear expectations that could have wide potential applications in social sciences. For example, we might see their applications in nonlinear pricing models as well as product bundling models.

This chapter is organized as follows. Section 2 introduces several notions of supermodularity. Then we propose our main result Theorem 1 over -supermodularity representations and underline through Proposition 1 that, in a finite lattice, quasisupermodularity is a very weak assumption, since for weakly increasing preference relations which are complete preorders, it cannot be distinguished from weak quasisupermodularity but also from what we call strong quasisupermodularity. Section 3 finally shows that complete preorders merely requiring strong monotonicity for preferences lead to the existence of supermodular representations.

Advertisement

2. Infinite Supermodularity

2.1. supermodularity and preference

Definition 1 Let X be a finite lattice and a preference relation on X (i.e. a binary relation on X with asymmetric part and symmetric part ).

is said to be weakly increasing if x y x y .

is said to be strictly increasing if it is weakly increasing and x < y x y .

is said to be weakly quasisupermodular if x y y x y x .

is said to be quasisupermodular if x x y x y y and x x y x y y .

is said to be strongly quasisupermodular if x x y x z x y z .

Note that what we call strong quasisupermodularity is dual (with instead of ) of what Chambers and Echenique [1] called modularity, a property referred to as Generalized Kreps by Epstein and Marinacci [5].

Definition 2 A function u : X R is said to be quasisupermodular if, for any x , y X , u x u x y implies u x y u y and u x > u x y implies u x y > u y . It is said to be supermodular if, for any x , y X , u x y + u x y u x + u y .1

Definition 3 is said to be supermodular if it allows a supermodular representation u : X R , i.e. there exists u : X R supermodular such that: for all x , y X , if x y then u x u y and if x y then u x > u y . Furthermore, the representation u is weakly increasing if x y u x u y .

Definition 4 Let X be a finite lattice then v : X R is said to be supermodular if

v k = 1 n x k I 1 n 1 I + 1 v x i i I , n 2 , x k X , k = 1 , , n

The following simple example illustrates that indeed supermodularity and supermodularity are two different notions for weakly increasing functions on a finite lattice X .

Example 5 let S = s 1 s 2 s 3 and consider X where X consists of the following partitions of S :

X = 0 { s 1 s 2 s 3 } x i = S \ s i s i i = 1,2,3 1 s 1 s 2 s 3

and is defined by x y if partition y is a refinement of partition x . It is straightforward to see that x i x j = 0 and x i x j = 1 for i j . Furthermore let u : X R be defined by u 0 = 0 , u x i = 1 , 1 i 3 and u 1 = 2 , clearly u is supermodular but not supermodular as just proved now. In actual fact, for a function v : X R defined by v 0 = 0 , v x i = 1 , i = 1,2,3 , then v is supermodular if and only if v 1 3 .

Chambers and Echenique [2] have shown that a preference relation on a lattice has a weakly increasing supermodular representation if and only if it has a weakly increasing and quasisupermodular representation. Now, we show that this is also equivalent to allowing a weakly increasing supermodular representation.

Theorem 1: A binary relation on X has a weakly increasing and quasisupermodular representation if and only if it has a weakly increasing and supermodular representation.

Proof. If part: Since an supermodular representation is always super modular, the if part is immediate.

Only if: This part of the proof is highly inspired by the paper of David Kreps, A representation theorem for preference for flexibility, and especially by the proof of Lemma 3, p.572.

From Theorem 1 of Chambers and Echenique [2], we know that there is a weakly increasing supermodular u : X R which represents .

Let R be the total preorder induced on X by u , i.e. xRy u x u y . Let P be the asymmetric part of R . Clearly, R agrees with , i.e. x y xRy and x y xPy . Therefore, the proof will be complete if one shows that R can be represented by a -supermodular function v which, by construction, will be necessarily weakly increasing.

Henceforth, to simplify the exposition, we will abuse of notation, letting R be denoted again by . Note that this new is again monotone, i.e. x y x y , since x y u x u y .

Let x denote the equivalence class of any x X . There is a finite number of equivalence classes, x n x 1 . Note that since u is supermodular: x x y x y y . This will be very useful later on. At last, for any x X , define x = y X y x . The following lemma will be crucial [8, 9].

Lemma 1. For any x X , there exists a unique x X such that x x = y X x y x .

Proof. Let us first show uniqueness. Suppose that x and y satisfy the property of Lemma 1. Then, x y and y x so x = y .

Since x is finite, there exists at least one minimal element for in x x , which is denoted by x . The proof will be completed if we show that x x = y X x y x .

Note that y X x   y   x x x . Actually, if y X and x y x , then weak increasingness of implies x y x , hence y x since x x .

It remains to prove that x x   y X x y x , or, equally, that y X , y x , y x implies y x . So let us show that if y X , y x , y x , then not( y x ) is impossible.

If not ( y x ), then x > x y . Actually, one has always x x y and y x y , so if x = x y , then we would get y x , a contradiction.

Let us see now that, from the definition of x , x > x y implies x x y . Actually, if x y x , since x x y and is monotone, it turns out that x x y x , which entails x y x . Therefore, x y x , but, since x > x y , this contradicts the fact that x is a minimal element of x for .

So x x y and, by supermodularity, x y y . But y x and x x , hence x y x . So, by monotonicity, x x y y x . Therefore, x x , a contradiction, which completes the proof of Lemma 1. ■

We can now turn to finishing the proof of Theorem 1. We intend to define, for any y X , n y R + in a consistent way such that the function v , defined by v x = y x n y for any x X , represents .

Let 0 X be the minimal element of X for . Since x 0 X for any x X and x 0 X implies x 0 X , one has x 1 = 0 X . For any y x 1 , let n y = 0 . Therefore, for any x x 1 , v x = y x n y = 0 .

Let us now show by induction that the n y ‘s can be defined in such a way that there exists α 1 = 0 < α 2 < < α i < < α n , satisfying v x = α i , x x i and n y 0 y X , y x where x x i .

This is true for x 1 . Suppose that this has been done up to i 1 , 1 i 1 n 1 and let us prove the result for index i .

Let x i = y 1 y j y m . Let us first show that we can suitably obtain v ( y j ) = α i > α i 1 , for 1 j m . Note that v y j = n y j + y < y j n y .

Since by monotonicity y < y j implies y y j , hence y x i , it comes from the definition of y j that y x i . Therefore, at step i , y < y j n y is already defined, so since there is a finite number of y j ‘s, one can choose α i such that α i > α i 1 and such that n ( y j ) = α i y < y j n y be positive. For such an α i , we consequently get v ( y j ) = α i > α i 1 .

It thus remains to see that we can choose suitably the n . values of the remaining y ‘s satisfying y x for x x i . So for any given y j , j = 1 m , we need to show that it is possible to get v ( y j ) = α i , where v ( y j ) = y y j n y . Let y be such that y y j , then by monotonicity y y j . If y y j , then y j y y j , and if y y j , then necessarily y < y j and, therefore, by definition of y j , necessarily y < y j , indeed y < y j implies y < y j . So { y , y y j } = { y , y < y j } y j { y , y j < y y j } . Since any y such that y j < y y j has not yet been attributed a value n . , we can state n y = 0 for such y ‘s. It comes that v ( y j ) = n ( y j ) + y < y j n y , that is v ( y j ) = α i .

So finally we get n z ‘s satisfying the required condition of representation: x y z x n z z y n z with n z 0 , z X . It remains to show that v defined this way is indeed -supermodular. While we might involve Möbius inversion as in the seminal book of Rota [6]), we choose for sake of self completion to propose the following direct proof. Let x k X , k = 1 , , n , n 2 , and let us prove that

v k = 1 n x k I 1 n 1 I + 1 v x i i I

For x X , let I x = k 1 k n x x k , then:

I 1 n 1 I + 1 v x i i I = = I 1 n 1 I + 1 x x i i I n x = I x n x I I x 1 I + 1 = I x n x 1 I I x 1 I 1 = I x n x

But I x n x x k 1 . . m x k n x = v k = 1 n x k since n x 0 x X .

Hence, v is an supermodular and weakly increasing by construction. ■

The following corollary shows that, as soon as the binary relation on X is a complete preorder, that is, reflexive, transitive and complete (i.e. x y X 2 , x y or y x or both), one can obtain a much more general result.

Corollary 1: For a complete preorder on a lattice X , the following assertions are equivalent:

  1. is weakly increasing and quasisupermodular.

  2. has a weakly increasing and quasisupermodular representation.

  3. has a weakly increasing and supermodular representation.

Proof. (i) (iii): Starting the proof of only if of Theorem 1 at the point where we were considering the finite equivalent classes of X for gives the result, taking into account the fact that by hypothesis is monotone, or, in other words, weakly increasing, and that quasisupermodular implies: x x y x y y . (iii) (ii) is immediate. (ii) (i): Let u be a weakly increasing and quasisupermodular representation of . Let x y , then u weakly increasing implies u x u y and u representation of the complete preorder implies x y , therefore is weakly increasing. It remains to prove that is quasisupermodular. Since is weakly increasing and since x x y and x y y , one gets x x y and x y y so indeed x x y x y y . Let us now show x x y x y y : x x y and u represents implies u x > u x y , u quasisupermodular then implies u x y > u y , and u represents the complete preorder finally implies x y y , which completes the proof of the corollary.■

Remark and example: The following example illustrates that indeed even a complete preorder on a finite lattice X may possess both a weakly increasing super modular representation which is not supermodular and also a weakly increasing supermodular representation.

Consider a finite set S = s 1 s 2 s 3 s 4 and the finite lattice X = P S . Let u : X R be defined by u = 0 = u x if the cardinal of x , denoted x , equals 1 , u x = 1 6 if x = 2 , u x = 1 3 if x = 3 and u x = 1 if x = 4 .

As proved in Chateauneuf and Jaffray [7] in Example 4, u is supermodular but not supermodular. Let be the complete preorder on X defined by x y u x u y . Clearly, u is a weakly increasing supermodular representation of which is not supermodular. Hence, has a weakly increasing and quasisupermodular representation, and therefore from Corollary 1 has a weakly increasing and supermodular representation.

For instance, setting n = 0 , n y = 0 if y 1,3,4 and n y = 1 6 if y = 2 , defining v x = y x n y does the job, since v = v x = 0 if x = 1 , v x = 1 6 if x = 2 , v x = 3 6 if x = 3 and v x = 1 if x = 4 . Hence, v is a weakly increasing and supermodular representation of .

2.2. Weak quasisupermodularity, quasisupermodularity and strong quasisupermodularity

Now we show, for a weakly increasing complete preorder on a finite lattice X , the equivalence of the different notions of quasisupermodularity defined in Definition 1.

Proposition 1: Let X be a finite lattice, if is a weakly increasing complete preorder, then the following statements are equivalent.

  1. ⪰ is weakly quasisupermodular.

  2. ⪰ is quasisupermodular.

  3. is strongly quasisupermodular.

Proof. (2) (1): We need to show x y y x y x ,   x , y X . Suppose not, then by monotonicity, we must have x x y , quasisupermodularity implies x y y , a contradiction. (1) (3): Suppose x y x , we need to show that x z x y z . Since x x y x z , thus if x y x , then x y x y x z , hence x y x y x z . By weak quasisupermodularity, we have x y x z x z , i.e. x y z x z . (3) (2): We need to show that x x y x y y and x x y x y y . Since is weakly increasing it is clear that x x y x y y is always true. Now we prove the second statement: x x y x y y . First, is weakly increasing implies x y y , thus if it is not x y y then it must be the case that x y y = x y y , strong quasisupermodularity implies x = x y x x y y x = y x , which says x y x contradicting x x y .

Thus, we have shown that, for a weakly increasing complete preorder over a finite lattice X , Weakquasisupermodularity quasisupermodularity strong quasi supermodularity.

Advertisement

3. -Supermodular representation for strictly monotone preference on a lattice

Definition 6 A function f : X R is strictly increasing if x < y f x < f y .

Theorem 2 below shows that if the preference relation on X i a complete preorder, then strict monotonicity of is not only necessary but also sufficient in order to get a strictly increasing supermodular function u representing . Moreover, the proof offers a simple constructive way to build such a representation.

Theorem 2: Let be a complete preorder on X , then the following statements are equivalent:

  1. is strictly increasing.

  2. has a strictly increasing and quasisupermodular representation.

  3. has a strictly increasing and supermodular representation.

Proof. (i) (iii): Let x denote the equivalence class of x X for , and let us consider the finite number of equivalence classes x 1 x i x n . As in the proof of Theorem 1, it is enough to show that there exist n z 0 z X such that, setting u x = z x n z x X , one gets x y if and only if u x u y . Actually, such an u will indeed represent and be supermodular. Moreover, since is strictly increasing, x < y implies x y and we will get x < y implies u x < u y so u will be strictly increasing. So let us define inductively the n z ‘s in order that the function u defined by u x = z x n z x X represents .

Let 0 X stands for the minimal element in X . Note that x 1 = 0 X . Actually, x X , x 0 X , so if x = 0 X , indeed x 0 X by reflexivity of , and if x > 0 X , then x 0 X since is strictly increasing. It turns out that, letting n 0 X = α 1 0 (eventually α 1 > 0 ), one gets u x = α 1 x x 1 .

Let us now consider x 2 . For any x X , z < x implies z x by strict monotonicity of . So for any given x x 2 , one gets z < x if and only if z = 0 X . Actually: z < x z x 2 z x 1 z = 0 X and, conversely, given 0 X x , 0 X = x is impossible, and, since 0 X x , one gets 0 X < x . Therefore, defining n x = β 1 > 0 x x 2 , one gets for x x 2 that u x = z x n z = α 2 > α 1 where α 2 = α 1 + β 1 .

Consider now x 3 . The same reasoning as before shows that for any x x 3 , { z , z x } = x { z , z < x } and z < x implies z x 3 . Since the x ‘s belonging to x 3 are finite, let x ¯ x 3 be such that z < x ¯ n z = max x x 3 z < x n z . Note that this quantity is well defined since n z has already been defined for z x 3 . Choose n x ¯ = β x ¯ > 0 sufficiently great in order that α 3 n x ¯ + z < x ¯ n z > α 2 . Choose now the remaining n x ‘s where x x 3 such that n x + z < x n z = α 3 . Then, necessarily n x n x ¯ > 0 . So we get u x = z x n z = α 3 x x ¯ 3 .

Indeed, this process applies step by step along increasing rank of the classes, and thus gives the searched for result.

(iii) (ii) is immediate. (ii) (i) is immediate since x < y u x < u y x y because u represents the complete preorder. ■

As an immediate consequence, we obtain a stronger form of Corollary 5 of Chambers and Echenique [2].

Corollary 2 Let X be a finite lattice. If a binary relation on X has a strictly increasing representation, then it has a strictly increasing supermodular representation and even a strictly increasing supermodular representation.

Proof. Let u be a strictly increasing representation of and define the complete preorder R on X by xRy u x u y . Then, x > y u x > u y xRy and not( yRx ). Hence, R is a strictly increasing complete preorder on X . From Theorem 2, R , hence , has a strictly increasing supermodular representation and, therefore, has a strictly increasing supermodular representation. This indeed implies that has a supermodular representation as it is proved in Corollary 5 of Chambers and Echenique [2]. ■

Advertisement

4. Extensions to infinite lattices

We shall extend our major result to infinite lattices.

First it should noted that when we consider infinite lattices, we would need a separability in order represent the given preference. The following is a counter example.

Example 7 Let L be the standard Borel σ algebra on 0 1 , μ x the std. Lebesgue measure, ν x be a distribution that with mass points on all the rational numbers of 0 1 . We define an order on L to be x < y if μ x < μ y or μ x = μ y , and ν x < ν y . Clearly this is the induced lexicographic order on L. It is well known that the lexicographic order is not separable and does not allow a representation, thus the defined order would not allow any representation.

Definition 8 A preference   on X is said to be lower finitely separable if there is a countable set C such that 1. C x x y is finite for all y X , and 2. x y , C z x z y .

A differential operator on a ordered lattice can be introduced in the following manner.

Definition 9 The difference operator on lattice X is defined recursively as 0 f x = f x ,

a 1 f x = f x f x a 1 , , a 1 , , a k f x = a k a 1 , , a k 1 f x = f x f x a i + , , + 1 k f x a 1 a k .

The following proposition is well known for supermodular functions on finite lattices, one can see for example the work by J. P. Barthelemy (2000) p. 199–200.

Proposition 10 an increasing function is -supermodular if and only if a 1 , , a k f x 0 , a 1 , a k , k = 1 , 2 , . X 2 .

Now we are ready to extend our result that strictly increasing preference must allow strictly increasing -supermodular representation on any infinite lattices with lower finite separability.

Proposition 11 Let X be a lattice with lower finite separability then the following two statements are equivalent.

  1. is a strictly increasing preference relation.

  2. There exists an strictly increasing supermodular f representing .

Proof. Recall that a subset C is said to separate if x y , c C such that x c y .

Let C = c 0 c 1 c m be a chain relative to separating the preference , since is strictly increasing, we know that C will also separate the lattice order . Denote x the maximal element of c C c x . It is well defined due to lower finiteness.

Given any weight function assigned to the separating chain w : C R , Denote x y w c dc = x c y w c , if x y , and = 0 otherwise.

Clearly given any positive function w c : C R + + , the function f x = c 0 x w c dc represents .

Now we claim that we can properly choose w c in such a way that f x = c 0 x w c dc is infinitely supermodular.

Actually, we choose w c 0 > 0 , and w c 2 X w c 0 + c 0 c w s ds , note this this is possible because X is a finite lattice.

We claim if we choose w c as in above then f x = c 0 x w c dc will infinitely supermodular.

In fact, the first difference: y f x = f x f x y = x y x w c dc > 0 if x y x , and = 0 otherwise.

y , z f x = f x f x y f x z f x z y = x y x w c dc x y z x z w c dc > 0

if y x x or z x x by our choice of w c , and = 0 otherwise.

It can be easily checked that if there is some a i x x , a 1 , . . , a k f x = 0 , if not, then a i x x i = 1 , 2 , . . , k

a 1 , . . a k f x = f x i f x a i + .. + 1 k f x a 1 .. a m w x 2 X c 0 x w c dc 0

This completes the proof. ■

Advertisement

5. Conclusion

In this chapter, we have explored the ordinal content of supermodularity on lattices. We studied the implications of various types of supermodularity for preferences over lattices. Especially we show that preferences on a lattice merely respecting the lattice order cannot disentangle these usual economic assumptions of supermodularity and infinite supermodularity. In addition, the strict increasingness of a complete preorder on a lattice is equivalent to the existence of a strictly increasing and infinitely supermodular representation. For wide classes of binary relations, the ordinal contents of quasisupermodularity, supermodularity and infinite supermodularity are exactly the same.

References

  1. 1. Chambers C, Echenique F. Ordinal notions of submodularity. Journal of Mathematical Economics. 2008;44:1243-1245
  2. 2. Chambers C, Echenique F. Supermodularity and preferences. Journal of Economic Theory. 2009;144:1004-1014
  3. 3. Milgrom P, Shannon C. Monotone comparative statics. Econometrica. 1994;62(1):157-180
  4. 4. Wong SKM, Yao YY, Lingras P. Comparative beliefs. In: Advances in the Dempster-Shafer Theory of Evidence. Wiley; 1994. pp. 115-132
  5. 5. Epstein LG, Marinacci M. Mutual absolute continuity of multiple priors. Journal of Economic Theory. 2007;137:716-720
  6. 6. Rota GC. On the foundations of combinatorial theory I: Theory of Mobius Mobius functions. Zeischrift fur Wahrscheinlichkeit Theorie. 2;4:340-368
  7. 7. Chateauneuf A, Jaffray J-Y. Some characterizations of lower probabilities and other monotone capacities through the use of Möbis inversion. Mathematical Social Science. 1989;17:263-283
  8. 8. Chateauneuf A, Vergopoulos V, Zhang J. Infinite Supermodularity and preferences. Economic Theory. 2017;63(1):99-109
  9. 9. Kreps DM. A representation theorem for preference for flexibility. Econometrica. 1979;47(3):565-578

Notes

  • Clearly, u supermodular implies u quasisupermodular.

Written By

Alain Chateauneuf, Vassili Vergopoulos and Jianbo Zhang

Submitted: March 4th, 2018 Reviewed: May 28th, 2018 Published: September 26th, 2018