Open access peer-reviewed chapter

Infinite Supermodularity and Preferences

By Alain Chateauneuf, Vassili Vergopoulos and Jianbo Zhang

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

DOI: 10.5772/intechopen.79150

Downloaded: 225

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.

2. Infinite Supermodularity

2.1. supermodularity and preference

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

is said to be weakly increasing if xyxy.

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

is said to be weakly quasisupermodular if xyyxyx.

is said to be quasisupermodular if xxyxyyand xxyxyy.

is said to be strongly quasisupermodular if xxyxzxyz.

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:XRis said to be quasisupermodular if, for any x,yX, uxuxyimplies uxyuyand ux>uxyimplies uxy>uy. It is said to be supermodular if, for any x,yX, uxy+uxyux+uy.1

Definition 3 is said to be supermodular if it allows a supermodular representation u:XR, i.e. there exists u:XRsupermodular such that: for all x,yX, if xythen uxuyand if xythen ux>uy. Furthermore, the representation uis weakly increasing if xyuxuy.

Definition 4 Let Xbe a finite lattice then v:XRis said to be supermodular if

vk=1nxkI1n1I+1vxiiI,n2,xkX,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=s1s2s3and consider Xwhere Xconsists of the following partitions of S:

X=0{s1s2s3}xi=S\sisii=1,2,31s1s2s3

and is defined by xyif partition yis a refinement of partition x.It is straightforward to see that xixj=0and xixj=1for ij.Furthermore let u:XRbe defined by u0=0,uxi=1,1i3and u1=2,clearly uis supermodular but not supermodular as just proved now. In actual fact, for a function v:XRdefined by v0=0,vxi=1,i=1,2,3, then vis supermodular if and only if v13.

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:XRwhich represents .

Let Rbe the total preorder induced on Xby u, i.e. xRyuxuy. Let Pbe the asymmetric part of R. Clearly, Ragrees with , i.e. xyxRyand xyxPy. Therefore, the proof will be complete if one shows that Rcan be represented by a -supermodular function vwhich, by construction, will be necessarily weakly increasing.

Henceforth, to simplify the exposition, we will abuse of notation, letting Rbe denoted again by . Note that this newis again monotone, i.e. xyxy, since xyuxuy.

Let xdenote the equivalence class of any xX.There is a finite number of equivalence classes, xnx1. Note that since uis supermodular: xxyxyy. This will be very useful later on. At last, for any xX, define x=yXyx. The following lemma will be crucial [8, 9].

Lemma 1. For any xX, there exists a unique xXsuch that xx=yXxyx.

Proof. Let us first show uniqueness. Suppose that xand ysatisfy the property of Lemma 1. Then, xyand yxso x=y.

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

Note that yXx y xxx. Actually, if yXand xyx, then weak increasingness of implies xyx, hence yxsince xx.

It remains to prove that xx yXxyx, or, equally, that yX, yx, yximplies yx. So let us show that if yX, yx, yx, then not(yx) is impossible.

If not (yx), then x>xy. Actually, one has always xxyand yxy, so if x=xy, then we would get yx, a contradiction.

Let us see now that, from the definition of x, x>xyimplies xxy. Actually, if xyx, since xxyand is monotone, it turns out that xxyx, which entails xyx. Therefore, xyx, but, since x>xy, this contradicts the fact that xis a minimal element of xfor .

So xxyand, by supermodularity, xyy. But yxand xx, hence xyx. So, by monotonicity, xxyyx. Therefore, xx, 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 yX, nyR+in a consistent way such that the function v, defined by vx=yxnyfor any xX, represents .

Let 0Xbe the minimal element of Xfor . Since x0Xfor any xXand x0Ximplies x0X, one has x1=0X. For any yx1, let ny=0. Therefore, for any xx1, vx=yxny=0.

Let us now show by induction that the ny‘s can be defined in such a way that there exists α1=0<α2<<αi<<αn, satisfying vx=αi, xxiand ny0yX, yxwhere xxi.

This is true for x1. Suppose that this has been done up to i1, 1i1n1and let us prove the result for index i.

Let xi=y1yjym. Let us first show that we can suitably obtain v(yj)=αi>αi1, for 1jm. Note that vyj=nyj+y<yjny.

Since by monotonicity y<yjimplies yyj, hence yxi, it comes from the definition of yjthat yxi. Therefore, at step i, y<yjnyis already defined, so since there is a finite number of yj‘s, one can choose αisuch that αi>αi1and such that n(yj)=αiy<yjnybe positive. For such an αi, we consequently get v(yj)=αi>αi1.

It thus remains to see that we can choose suitably the n.values of the remaining y‘s satisfying yxfor xxi. So for any given yj, j=1m, we need to show that it is possible to get v(yj)=αi, where v(yj)=yyjny. Let ybe such that yyj, then by monotonicity yyj. If yyj, then yjyyj, and if yyj, then necessarily y<yjand, therefore, by definition of yj, necessarily y<yj, indeed y<yjimplies y<yj. So {y, yyj}={y, y<yj}yj{y, yj<yyj}. Since any ysuch that yj<yyjhas not yet been attributed a value n., we can state ny=0for such y‘s. It comes that v(yj)=n(yj)+y<yjny, that is v(yj)=αi.

So finally we get nz‘s satisfying the required condition of representation: xyzxnzzynzwith nz0, zX. It remains to show that vdefined 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 xkX,k=1,,n, n2,and let us prove that

vk=1nxkI1n1I+1vxiiI

For xX,let Ix=k1knxxk, then:

I1n1I+1vxiiI==I1n1I+1xxiiInx=IxnxIIx1I+1=Ixnx1IIx1I1=Ixnx

But Ixnxxk1..mxknx=vk=1nxksince nx0xX.

Hence, vis an supermodular and weakly increasing by construction. ■

The following corollary shows that, as soon as the binary relation on Xis a complete preorder, that is, reflexive, transitive and complete (i.e. xyX2, xyor yxor 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 Xfor gives the result, taking into account the fact that by hypothesis is monotone, or, in other words, weakly increasing, and that quasisupermodular implies: xxyxyy. (iii) (ii) is immediate. (ii) (i): Let ube a weakly increasing and quasisupermodular representation of . Let xy, then uweakly increasing implies uxuyand urepresentation of the complete preorder implies xy, therefore is weakly increasing. It remains to prove that is quasisupermodular. Since is weakly increasing and since xxyand xyy, one gets xxyand xyyso indeed xxyxyy. Let us now show xxyxyy: xxyand urepresents implies ux>uxy, uquasisupermodular then implies uxy>uy, and urepresents the complete preorder finally implies xyy, which completes the proof of the corollary.■

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

Consider a finite set S=s1s2s3s4and the finite lattice X=PS. Let u:XRbe defined by u=0=uxif the cardinal of x, denoted x, equals 1, ux=16if x=2, ux=13if x=3and ux=1if x=4.

As proved in Chateauneuf and Jaffray [7] in Example 4, uis supermodular but not supermodular. Let be the complete preorder on Xdefined by xyuxuy. Clearly, uis 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, ny=0if y1,3,4and ny=16if y=2, defining vx=yxnydoes the job, since v=vx=0if x=1, vx=16if x=2, vx=36if x=3and vx=1if x=4. Hence, vis 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 Xbe 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 xyyxyx, x,yX.Suppose not, then by monotonicity, we must have xxy,quasisupermodularity implies xyy, a contradiction. (1) (3): Suppose xyx,we need to show that xzxyz.Since xxyxz,thus if xyx,then xyxyxz,hence xyxyxz. By weak quasisupermodularity, we have xyxzxz,i.e.xyzxz.(3) (2): We need to show that xxyxyyand xxyxyy.Since is weakly increasing it is clear that xxyxyyis always true. Now we prove the second statement: xxyxyy.First, is weakly increasing implies xyy,thus if it is not xyythen it must be the case that xyy=xyy,strong quasisupermodularity implies x=xyxxyyx=yx, which says xyxcontradicting xxy.

Thus, we have shown that, for a weakly increasing complete preorder over a finite lattice X, Weakquasisupermodularityquasisupermodularitystrongquasisupermodularity.

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

Definition 6 A function f:XRis strictly increasing if x<yfx<fy.

Theorem 2 below shows that if the preference relation on Xi a complete preorder, then strict monotonicity of is not only necessary but also sufficient in order to get a strictly increasing supermodular function urepresenting . 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 xdenote the equivalence class of xXfor , and let us consider the finite number of equivalence classes x1xixn. As in the proof of Theorem 1, it is enough to show that there exist nz0zXsuch that, setting ux=zxnzxX, one gets xyif and only if uxuy. Actually, such an uwill indeed represent and be supermodular. Moreover, since is strictly increasing, x<yimplies xyand we will get x<yimplies ux<uyso uwill be strictly increasing. So let us define inductively the nz‘s in order that the function udefined by ux=zxnzxXrepresents .

Let 0Xstands for the minimal element in X. Note that x1=0X. Actually, xX, x0X, so if x=0X, indeed x0Xby reflexivity of , and if x>0X, then x0Xsince is strictly increasing. It turns out that, letting n0X=α10(eventually α1>0), one gets ux=α1xx1.

Let us now consider x2. For any xX, z<ximplies zxby strict monotonicity of . So for any given xx2, one gets z<xif and only if z=0X. Actually: z<xzx2zx1z=0Xand, conversely, given 0Xx, 0X=xis impossible, and, since 0Xx, one gets 0X<x. Therefore, defining nx=β1>0xx2, one gets for xx2that ux=zxnz=α2>α1where α2=α1+β1.

Consider now x3. The same reasoning as before shows that for any xx3, {z, zx}=x{z, z<x}and z<ximplies zx3. Since the x‘s belonging to x3are finite, let x¯x3be such that z<x¯nz=maxxx3z<xnz. Note that this quantity is well defined since nzhas already been defined for zx3. Choose nx¯=βx¯>0sufficiently great in order that α3nx¯+z<x¯nz>α2. Choose now the remaining nx‘s where xx3such that nx+z<xnz=α3. Then, necessarily nxnx¯>0. So we get ux=zxnz=α3xx¯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<yux<uyxybecause urepresents the complete preorder. ■

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

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

Proof. Let ube a strictly increasing representation of and define the complete preorder Ron Xby xRyuxuy. Then, x>yux>uyxRyand not(yRx). Hence, Ris 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]. ■

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 01,μxthe std. Lebesgue measure, νxbe a distribution that with mass points on all the rational numbers of 01. We define an order on L to be x < y if μx<μyor μx=μy,andνx<νy.Clearlythis 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  onXis said to be lower finitely separable if there is a countable set C such that 1. Cxxyis finite for all yX,and2. xy,Czxzy.

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

Definition 9 The difference operator on lattice Xis defined recursively as 0fx=fx,

a1fx=fxfxa1,,a1,,akfx=aka1,,ak1fx=fxfxai+,,+1kfxa1ak.

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 a1,,akfx0,a1,ak,k=1,2,.X2.

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 Xbe 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 frepresenting .

Proof. Recall that a subset Cis said to separate if xy,cCsuch that xcy.

Let C=c0c1cmbe a chain relative to separating the preference ,since is strictly increasing, we know that C will also separate the lattice order .Denote xthe maximal element of cCcx.It is well defined due to lower finiteness.

Given any weight function assigned to the separating chain w:CR,Denote xywcdc=xcywc,if xy,and =0otherwise.

Clearly given any positive function wc:CR++,the function fx=c0xwcdcrepresents .

Now we claim that we can properly choose wcin such a way that fx=c0xwcdcis infinitely supermodular.

Actually, we choose wc0>0,and wc2Xwc0+c0cwsds,note this this is possible because Xis a finite lattice.

We claim if we choose wcas in above then fx=c0xwcdcwill infinitely supermodular.

In fact, the first difference: yfx=fxfxy=xyxwcdc>0if xyx,and =0otherwise.

y,zfx=fxfxyfxzfxzy=xyxwcdcxyzxzwcdc>0

if yxxor zxxby our choice of wc,and =0otherwise.

It can be easily checked that if there is some aixx,a1,..,akfx=0,if not, then aixxi=1,2,..,k

a1,..akfx=fxifxai+..+1kfxa1..amwx2Xc0xwcdc0

This completes the proof. ■

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.

Notes

  • Clearly, u supermodular implies u quasisupermodular.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Alain Chateauneuf, Vassili Vergopoulos and Jianbo Zhang (September 26th 2018). Infinite Supermodularity and Preferences, Game Theory - Applications in Logistics and Economy, Danijela Tuljak-Suban, IntechOpen, DOI: 10.5772/intechopen.79150. Available from:

chapter statistics

225total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Coordination Concerns: Concealing the Free Rider Problem

By Adriana Alventosa and Penélope Hernández

Related Book

First chapter

The Neumann-Morgenstern Project – Game Theory as a Formal Language for the Social Sciences

By Hardy Hanappi

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us