The Open Graph Theorem for Correspondences: A New Proof and Some Applications

Abstract

It is known that a correspondence from a topological space to a Euclidean space, with open and convex upper sections, has an open graph if and only if it is lower hemicontinuous. We refer to this result as the open graph theorem. We provide a new and simple proof of the open graph theorem. We also show that the open graph theorem leads to novel results on the existence of constant selections and fixed points for correspondences with non-compact and non-convex domain. Finally, we present an economic application of our results to a principal-agent model.

Share and Cite:

Impicciatore, G. and Ruscitti, F. (2012) The Open Graph Theorem for Correspondences: A New Proof and Some Applications. Theoretical Economics Letters, 2, 270-273. doi: 10.4236/tel.2012.23049.

1. Introduction

The closed graph theorem for correspondences asserts that a closed-valued correspondence with a compact Hausdorff range is upper hemicontinuous if and only if it has a closed graph. This result, especially when combined with Kakutani’s fixed point theorem, has many well-known applications in economics. A companion theorem, which perhaps is less-known, is the “open graph theorem” for correspondences established by Zhou [1]: a correspondence S from an arbitrary topological space to, with open and convex values, is lower hemicontinuous if and only if it has an open graph. Zhou and other authors have already used the open graph theorem to show the existence of fixed points for a correspondence, when X is convex and compact. These results have then been exploited to establish the existence of equilibria in abstract economies (see, e.g., Theorem 7 in Zhou [1]).

In this paper we first provide a new proof of the open graph theorem. Unlike the original proof of Zhou, which is based on the geometric properties of the unit ball in, our proof relies on basic separation properties of convex sets. We underscore that our proof hinges on a lemma which is relevant for dynamic programming applications. Moreover, such a lemma also enables us to strengthen a theorem on correspondences reported in Moore [2].

Then, we demonstrate that the open graph theorem can be employed to obtain a new and simple result on the existence of fixed points and constant selections for a correspondence S whose domain X is simply a connected subset of. Note that we assume neither convexity nor compactness of X. Next, we prove, as a corollary, a quite surprising property of continuous correspondences defined on connected topological spaces. In a nutshell, under additional assumptions such correspondences must be constant. Finally, we develop an economic application of our corollary that concerns contract theory.

The lay-out of the paper is as follows: In Section 2 we remind the reader the open graph theorem and we offer a new proof. To this end, we first prove an instrumental lemma which is interesting in its own right. In Section 3 we show how the open graph theorem leads to the existence of constant selections and fixed points. As a corollary, in Section 4 we provide sufficient conditions for constant correspondences. In Subsection 4.1 we discuss an economic application of our result about constant correspondences. Specifically, we focus on an abstract but fairly general principal-agent model.

2. The Open Graph Theorem

The concepts concerning correspondences, used hereafter, should already be familiar. At any rate, we refer the reader to Aliprantis et al. [3], or Border [4]. In Section 4.1 we shall make use of the following result, reported in Moore [2] as Proposition 11.70.

Proposition 2.1. Let X be a topological space, and suppose that is a lower hemicontinuous correspondence with convex values. Then, the correspondence defined by

has open lower sections.1

The following theorem is due to Zhou ([1], Proposition 2).

Theorem 2.1. (The open graph theorem): Let X be a topological space, and suppose that is a correspondence with convex and open upper sections. Then, S is lower hemicontinuous if and only if it has an open graph.

Next we offer a novel proof of Theorem 2.1. Our proof hinges upon the following Lemma.

Lemma 2.1. Let be a lower hemicontinuous correspondence, where X is an arbitrary topological space. Suppose that S is convex-valued, and for some, is non-empty. Then, for any compact set, there exists a neighborhood of such that for all.

Proof. Suppose, by way of contradiction, that the claim is false. Then, there is a compact set K, with for some, a net in X such that, and a net such that but for each. By a standard result on separation of convex sets, the vectors can be separated from the sets. That is, there exists a net such that

for any (denotes the inner product in). Without loss of generality, we can assume that and that where (the proof works for any converging subnet of). Now, since the net lies in K, assume without loss of generality that. Since, there exists such that, where is the closed ball of radius around. Now let. For any, we have that

(2.1)

This is because

and.

On the other hand, , where. Therefore,. By lower hemicontinuity of S, there exists, with for each, such that. Thus,

We remark that in the special case in which X is finitedimensional, a proof of Lemma 2.1 can be derived from Proposition 4.15 and Theorem 5.9 in Rockafellar and Wets [5].2

Remark 2.1. When the compact set K is a singleton, Lemma 2.1 implies the following property of S: If, then there exists a neighborhood of such that for all. In a finitedimensional setting, this property has been exploited by Stokey et al. [6] and Kim [7], without proof, to establish the differentiability of the value function in dynamic programming. In Benveniste and Scheinkman [8], this property follows at once from the assumptions on the technology set and the initial behavior of the optimal path. Aliprantis et al. [9] basically assume it.

We are now ready to present a new proof of Theorem 2.1. In what follows, gphs denotes the graph of correspondence S.

Proof of Theorem 2.1. If gphs is open, then S has open lower sections, and therefore S is lower hemicontinuous (Lemma 17.12 in Aliprantis and Border [3]). Now let. Then, and since S has open upper sections, by Lemma 2.1 there exist open neighborhoods and, of x and y respectively, such that for all. Therefore, and thus gphs is open in.

Remark 2.2. We stress that the above Proposition 2.1 is reported in Moore [2] without proof. However, notice that using Lemma 2.1 above it is easy to show that, defined in Proposition 2.1, is lower hemicontinuous. Thus, by Theorem 2.1, has open graph. Because open graph implies open lower sections, we obtain a result stronger than Moore’s.

3. Existence of Fixed Points and Constant Selections

We now use the open graph theorem to establish the existence of fixed points for a correspondence, where X is simply a connected subset of. The following result doesn’t require compactness or convexity of X. The idea of using connectedness as a substitute for convexity was suggested by Horvath [10]. However, our result neither implies nor is implied by his results. Recall that a topological space X is connected if the only clopen (simultaneously closed and open) subsets of X are and X. A subset of a topological space is a connected set if it is a connected space with its relative topology. The following result is an immediate corollary of Theorem 2.1.

Theorem 3.1. Let X be a connected topological space. Assume that is lower hemicontinuous, convex-valued, and with upper sections open in. Suppose there exists and such that is closed in X. Then, for all. In particular, if, then has a fixed point.

Proof. By assumption, the set is closed in X. Also, by the open graph theorem is open in X.3 Since is both open and closed in X, is clearly non-empty by assumption, and X is connected, we must have that, and we are done.

Remark 3.1. Note that Theorem 3.1 actually establishes the existence of a constant selection.4 Note, also, that on one hand Theorem 3.1 requires more conditions on S than convexity and lower hemicontinuity needed for fixed point theorems in. On the other hand, our theorem does not impose any compactness or convexity assumptions on X.

4. Constant Correspondences

Theorem 3.1 implies that the full continuity of a correspondence with open and convex upper section is restrictive, as the following surprising corollary illustrates.

Corollary 4.1. Let X be a connected topological space. If is a nonempty-valued continuous correspondence with convex and open upper sections, then S is constant on X.

Proof. The upper hemicontinuity of S implies that for any and any, is closed in X (Lemma 17.4 in [3]). It then follows from Theorem 3.1 that for any and, for all. Hence, S is constant on X.

Remark 4.1. It should be clear from the above proof that Corollary 4.1 still holds true if one replaces upper hemicontinuity with the weaker assumption that S has closed lower sections.

Principal-Agent Models

To illustrate the usefulness of Corollary 4.1, we shall outline an application to contract theory. For the main concepts and basic results about the principal-agent model we refer the reader to Grossman and Hart [11].

There is one principal and one risk-averse agent; let be the set of the agent’s feasible actions; let be the set of verifiable performance measures.5 Let be a function that maps any feasible action to a (non-atomic) Borel probability measure on. is equipped with the weak* topology. Notice that with these primitives the support6 gives rise to a well-defined correspondence supp from to. Let be such a correspondence. Finally, consider the composition .

Following [12], let’s say that the model exhibits shifting support if the latter changes with the action. With shifting support, it is known that basically no hidden action problem exists. Furthermore, there are actions (which are not least-costly to the agent) that can be implemented by the principal at the full-information cost (see [11,12]). Therefore, the case of a shifting support is in this sense trivial. Thus, to the best of our knowledge, in the principal-agent literature a shifting support is assumed away. In contrast, here we want to provide sufficient conditions, on the fundamentals of the model, in order that the support be independent of the actions. In other words, we seek conditions that result in the correspondence S being constant. To this end, let be the correspondence defined by.7 Let. It will suffice to show that is constant.

Assumption 4.1.1. is a connected topological space, is continuous, and is a set of Borel probability measures with support which is convex and that has non-empty interior. Moreover, has closed lower sections.

Proposition 4.1.1. Under Assumption 4.1.1, is constant on A.

Proof. By Theorem 17.14 in [3], is lower hemicontinuous. As the restriction of to is convex-valued by assumption, it follows from Proposition 2.1 above that the restriction of to is lower hemicontinuous as well. Thus, is lower hemicontinuous. Clearly, it is non-empty-valued and has convex and open upper sections. Hence, by Corollary 4.1 and Remark 4.1, is constant on.

5. Conclusion

In this work we have presented a new proof of the open graph theorem. Then we have employed the latter to show the existence of fixed points and constant selections for correspondences defined on a connected domain. As a corollary, we have provided sufficient conditions for a correspondence to be constant. Finally, we have developed an economic application of constant correspondences that deals with contract theory. Our new proof is based on a lemma that utilizes basic separating hyperplane theorems and that, therefore, employes standard techniques in mainstream economic theory. We have argued that from the mathematics standpoint such lemma may be of some interest in its own right, and moreover it sheds light on some classic proofs of the differentiability of the value function in deterministic dynamic programming. Our result on the existence of fixed points might be useful when compactness and convexity of the domain is not guaranteed but the correspondence at hand satisfies specific properties in addition to lower hemicontinuity and convexity of its upper sections. Whether it can be applied to general equilibrium models or in game theory is something that remains to be seen. Regarding the significance of our economic application, Proposition 4.1.1 provides “guidelines” to construct principal-agent models that give rise to a probability distribution, over the observable outcomes, with support that does not change with the agent’s unobservable action. One does not have to assume from the outset that the support is constant.

NOTES

2We thank A. Bagh for pointing this out to us.

3Recall that open graph implies open lower sections.

4For economic applications of constant selections, see Horvath [10].

5This framework is general for it encompasses multi-tasks and multioutcomes models.

6We borrow the notion of support from Aliprantis and Border ([3], p. 441). Also, for any we denote the support of by supp.

7We have required the measure to be non-atomic (see above) to rule out point mass probability measures. Indeed, the latter measures admit a support with empty interior.

Conflicts of Interest

The authors declare no conflicts of interest.

 [1] J. Zhou, “On the Existence of Equilibrium for Abstract Economies,” Journal of Mathematical Analysis and Applications, Vol. 193, No. 3, 1995, pp. 839-858. doi:10.1006/jmaa.1995.1271 [2] J. C. Moore, “Mathematical Methods for Economic Theory 2,” Studies in Economic Theory, Springer-Verlag, Berlin, Vol. 10, 1999. [3] C. D. Aliprantis and K. C. Border, “ Infinite Dimensional Analysis A Hitchhiker’s Guide,” 3rd Edition, Springer-Verlag, Berlin, 2006. [4] K. Border, “Fixed Point Theorems with Applications to Economics and Game Theory,” Cambridge University Press, Cambridge, 1985. doi:10.1017/CBO9780511625756 [5] R. T. Rockafellar and R. Wets, “Variational Analysis,” 3rd Edition, A Series of Comprehensive Studies in Mathematics, Springer, Berlin, Vol. 317, 2009. [6] N. Stokey, R. E. Lucas and E. Prescott, “Recursive Methods in Economic Dynamics,” Harvard University Press, Cambridge, 1989. [7] T. Kim, “Differentiability of the Value Function: A New Characterization,” Seoul Journal of Economics, Vol. 6, No. 3,1993, pp. 257-265. [8] L. M. Benveniste and J. A. Scheinkman, “On the Differentiability of the Value Function in Dynamic Models of Economics,” Econometrica, Vol. 47, No. 3, 1979, pp. 727-732. doi:10.2307/1910417 [9] C. D. Aliprantis, G. Camera and F. Ruscitti, “Monetary Equilibrium and the Differentiability of the Value Function,” Journal of Economic Dynamics and Control, Vol. 33, No. 2, 2009, pp. 454-462. doi:10.1016/j.jedc.2008.06.010 [10] C. D. Horvath, “On the Existence of Constant Selections,” Topology and Its Applications, Vol. 104, No. 1-3, 2000, pp. 119-139. doi:10.1016/S0166-8641(99)00022-X [11] S. J. Grossman and O. D. Hart, “An Analysis of the Principal-Agent Problem,” Econometrica, Vol. 51, No. 1, 1983, pp. 7-45. doi:10.2307/1912246 [12] B. Caillaud and B. E. Hermalin, “Hidden Action and Incentives,” 2000. http://faculty.haas.berkeley.edu/hermalin/agencyread.pdf