%Paper: ewp-game/9405002 %From: wilhelm@neuefeind.wustl.edu (Wilhelm Neuefeind) %Date: Tue, 17 May 94 10:22:33 CDT %&latex \documentstyle[12pt]{article} \textheight=20.7cm \textwidth=6in \oddsidemargin=.25in \evensidemargin=0mm \topmargin=0mm \sloppy \begin{document} \newcommand{\nat}{\mbox{$I\!\!N$}} \newcommand{\reals}{\mbox{$I\!\!R$}} \newcommand{\defeq}{\, \raisebox{1.3pt}{\scriptsize :} \!\!\!\: =} \def\qed{\hfill\rule[0mm]{2.5mm}{2.5mm}} \newtheorem{defi}{Definition} \begin{titlepage} \quad \vskip2cm \begin{center} Continuous Linear Representability of\\ Binary Relations*\\ \quad \\ {\sc Wilhelm Neuefeind} \\ {\it Washington University in Saint Louis}\\ {\sc Walter Trockel**}\\ {\it IMW, Universit\"{a}t Bielefeld}\\ \quad \\ \end{center}\vskip2cm \noindent {\bf Running title:} Representability of Relations \vskip1cm \noindent Send correspondence to:\\ Professor Wilhelm Neuefeind \\ Department of Economics, Box 1208\\ Washington University\\ St. Louis, MO 63130-4899 \vskip1cm \vfill * Thanks are due for helpful comments to Manfred Nermuth, David Schmeidler, Antonio Villar, and anonymous referees. ** Financial support from the DFG under Tr 120/4-2 is gratefully acknowledged. \end{titlepage} \newpage \noindent {\bf Summary:} A very general result on continuous linear representability of binary relations on topological vector spaces is presented. Applications of this result include individual decision making under uncertainty, i.e. expected utility theory and collective decision making, in particular, utilitaristic social welfare functions. \vskip.5cm \noindent {\it Journal of Economic Literature} Classification Numbers: D71, D81 \vskip.5cm \section{Introduction} \pagestyle{plain} This paper presents a very general result on continuous linear representability of binary relations on topological vector spaces. Important applications of this result include individual decision making under uncertainty (expected utility theory) and collective decision making (utilitaristic social welfare functions). In the latter area, the paper adds to known results on the existence of social welfare functionals; see e.g. Maskin [1978], Roberts [1980], or d'Aspremont [1985]. In addition to allowing for infinitely many individuals, it demonstrates the power of a translation-invariance assumption which allows to considerably weaken other assumptions, which are usually made in this context, as completeness, transitivity, and continuity of the social planner's preferences (or, in the expected utility case, the individual's). The result is in the spirit of Schmeidler's [1971] who derives completeness from strong continuity properties of partial transitive preferences. We use an assumption, to be called indifference-invariance, which is strictly weaker than transitivity.\footnote{The relation of that assumption to transitivity has been studied earlier by Rader [1963] and Sonnenschein [1965] for the case of complete preferences.} This assumption, together with the translation-invariance postulate, allows us to get completeness, transitivity, and continuous representability from much weaker assumptions on the relation. For the sake of clarity and ease of exposition, we postpone a more detailed discussion until we have presented the formal set-up and the Proposition. \section{Notation and basic definitions} Let $V$ be a topological vector space and $R$ be a binary relation on $V$. By $I$ and $P$ we denote the strict and the indifference relations, respectively, derived from $R$: \[\begin{array}{lcccl} \forall\ x,y\in V & : & x \ P\ y & :\Leftrightarrow & x \ R\ y \mbox{\ and not\ } y \ R\ x;\\ & & x \ I\ y & :\Leftrightarrow & x \ R\ y \mbox{\ and\ } y \ R\ x. \end{array}\] \newpage We shall employ the following notation for all $x\in V\!$: \[\begin{array}{lcll} R(x) & \defeq & \{y\in V\mid x\ R\ y\} & \mbox{\ lower contour set of $x$} ;\\ R^{-1}(x) & \defeq & \{ y\in V \mid y \ R\ x\} & \mbox{\ upper contour set of $x$} ;\\ P(x) & \defeq & \{ y\in V \mid x\ P\ y\} & \mbox{\ worse set of $x$} ;\\ P^{-1}(x) & \defeq & \{ y\in V \mid y\ P\ x\} & \mbox{\ better set of $x$} ;\\ I(x) & \defeq & \{ y \in V \mid x\ I\ y\} & \mbox{\ indifference set of $x$} . \end{array}\] By definition, $I$ is {\em symmetric}, i.e. $x\ I\ y$ implies $ y\ I\ x$ for all $x,y\in V$, and $P$ is {\em irreflexive}, i.e. $x\not\in P(x)$ for all $x \in V\!$. \begin{defi} A binary relation $R$ on $V$ is called {\em translation-invariant} iff $\, \forall\ y,z\in V\!: R(y) + z \subseteq R(y+z)$. \end{defi} \begin{defi} A binary relation $R$ on $V$ is called {\em indifference-invariant} iff $ \forall x,y \in V\!: x\ P\ y \Rightarrow I(x) \times I(y) \subseteq P^{-1}(y) \times P(x).$ \end{defi} Clearly, indifference-invariance of a relation is strictly weaker than its transitivity. Rader [1963] and Sonnenschein [1965] give conditions under which transitivity and indifference-invariance of $R$ are in fact equivalent. They use completeness, continuity, and connectedness assumptions on $R$ and one half of indifference-invariance, i.e.\quad $x\ P\ y \Rightarrow I(x) \subseteq P^{-1}(y)$ for all $ x,y \in V,\;$ to obtain that equivalence. In our set-up, a local continuity assumption on and translation-invariance of $R$ allow us to get an even stronger result. Note that, for translation-invariant relations $R$, indifference-invariance of $P$ is characterized by $P(0) + I(0) \subset P(0)$. We will use this fact later on without explicitly mentioning it. \begin{defi} A binary relation $R$ on $V$ is called {\em lower closed} (resp.~{\em lower open}) {\em at} $x\in V$ iff $R(x)$ is closed (resp.~$P(x)$ is open). It is {\em lower continuous at} $x\in V$ iff it is lower closed and lower open at $x\in V\!$. \end{defi} Upper continuity is defined symmetrically. Note that a relation is called {\it continuous} if it is lower continuous and upper continuous at all $x \in V\!$. \section{Result and Discussion} \noindent{\bf Proposition:} {\it Let $R$ be a translation- and indifference-invariant binary relation on $V$ which is lower continuous at some point of $V\!$. If $P \not= \phi$, then $R$ is a continuous complete preordering, representable by a continuous linear utility function.} \vskip.2cm In the case of expected utility theory, $V$ contains the set of lotteries available to an individual decision maker with a preference $R$. Here, our result asserts the existence of a continuous linear utility function for an {\em a priori} partial, locally continuous, and non-ordered preference on the set of lotteries. In contrast, earlier work as in Theorem 4.2.2 of Blackwell-Girshick [1954], in Theorem 2 of Grandmont [1972], and the results in Einy [1989], Trockel [1992], and Candeal-Indurain [1994] all require complete, transitive, and globally continuous preferences. Our result does not imply (nor is it implied by) Theorem 8 in Herstein-Milnor [1953]. They assume completeness and transitivity of the relation while we do not. Our set of alternatives is a linear topological space while theirs is a mixture set and may not have a topology. Our local continuity assumption plays the same r\^ole as their Archimedian axiom which amounts to a continuity assumption when the mixture set equals $\reals^n$. While, in general, the question of continuity of the utility may be meaningless in their setup, the utility may not be continuous even if the mixture set can be embedded in or is a linear topological space.\footnote{ To verify this and, thus, that our result does not imply theirs, observe that any linear topological space is a mixture set, in particular, any ${\cal{L}}^p$. It is well known (see e.g. Rudin [1991]) that, for $p \in (0,1)$, the latter spaces have only a trivial topological dual. Therefore, linear utility representations exist due to their result, but continuous do not.} In the case of the application of our Proposition to a social choice problem, the vector space $V$ is the space of utility allocations to the individuals making up society. The relation $R$ on $V$ is a social welfare ordering, i.e. a planner's preference on utility allocations. Our Proposition gives a very general utilitarianism result for the social welfare ordering $R$. In contrast to the set-up usually considered, it allows for infinitely many individuals in a society as well as for {\em a priori} partial, non-ordered preferences of the social planner. In particular, our indifference-invariant social relations do {\em a priori} not exclude cycles.\footnote{Indeed, indifference-invariance of $R$ is consistent with cycles. It would be quite a natural property of a non-transitive social preference relation because the ranking of two social alternatives could be influenced by a replacement of two socially indifferent substitutes.} They only require that, in choice situations between two utility alloca tions, either one of them can be replaced by an indifferent one without influencing the choice. Thus, no rationality assumptions are required for the planner's preference. The translation-invariance here represents cardinality and unit comparability with a fixed unit. It is the power of this assumption which allows us to deduce continuity from local semi-continuity and indifference-invariance, and even implies $R$ to be a linearly representable (thus transitive and complete) social welfare ordering. In this literature, a distinction is made between weak and strong utilitarianism results. The strong notion requires {\it representation} of the planner's preference $R$ by a linear functional, while the weak notion only requires $R$ to be {\it included} in the relation generated by the functional. The ``weak notion'' results (see e.g. d'Aspremont-Gevers [1977] and Roberts [1980]), usually rely on Theorem 4.3.1 in Blackwell-Girshick [1954] which does not require continuity assumptions (and does not yield continuity of the representation). Our Proposition, thus, does not strengthen these results. It, however, generalizes the version of this theorem, which includes semi-continuity as an assumption, on page 120 in Blackwell-Girshick [1954], and extends it to infinite dimensions. Therefore, our result allows the derivation of a more desirable strong utilitarianism result with a continuous social welfare functional. It is natural, to compare this result with that of Maskin [1978], whose approach is quite different. He starts with a product space of utility functions and assumptions on the social welfare functional and derives, with the help of the welfarism theorem (see d'Aspremont-Gevers [1977]), a social welfare ordering on the (finite-dimensional) space of utility allocations and proves its representability. We apply our Proposition directly to the latter space (allowing for infinite dimension). Maskin's assumption of {\em full comparability} is replaced by our assumption of {\em translation-invariance}. Neither one of these assumptions is implied by the other. This substitution, however, has the interesting and pleasant consequence that the strong separation property needed in Maskin's paper can be dispensed with and that (as already pointed out) continuity can be derived from local semi-continuity. In closing we note that, in view of Trockel's [1989] classification of Cobb-Douglas representable utility functions, our present result may be translated into one giving minimal requirements for a binary relation on $\reals^n_{++}$ to be representable by a Cobb-Douglas utility function. \section{ Proof of the Proposition} \noindent{\bf Proof:} (a) First we show that $I$ is transitive.\footnote{ Note that completeness of an indifference-invariant relation trivially implies this result. Here we show it without first showing the completeness of the relation.} \vskip.1cm \noindent By translation-invariance, $R(0) = -R^{-1}(0)$, $P(0) = -P^{-1}(0)$, $I(0)= - I(0)$, and $R(x) = x + R(0)$, $P(x) = x + P(0)$, $I(x) = x +I(0)$ for any $x\in V$. Hence, lower continuity at one point implies (global) continuity. There exists $\bar{x} \in P(0)$. We will show\footnote{This argument borrows from Schmeidler [1971].} that \begin{equation} V=P(0) \cup P^{-1}(\bar{x}) = R(0) \cup R^{-1}(\bar{x}). \end{equation} Because the middle term is open and non-empty and the last term is closed, equality of the two in fact implies that both terms equal the connected set $V$. To prove (1), let $y \in I(0) \cup I(\bar{x})$. If $y \in I(0)$, then $-y \in I(0)$ and indifference-invariance implies $\bar{x} - y \in P(0)$, i.e. $\bar{x} \in P(y)$, thus $y \in P^{-1}(\bar{x})$. If $y \in I(\bar{x})$, then $y- \bar{x} \in I(0)$ and, again by indifference-invariance, $y= \bar{x} +(y - \bar{x}) \in P(0)$. We will now show that $I$ is transitive, i.e. $I(0) + I(0) \subseteq I(0)$. \noindent Because of (1), $\frac{1}{2}\bar{x} \in P(0) \cup P^{-1}(\bar{x})$. We will show that $ \frac{1}{2}\bar{x} \in P(0)$, which is clear if $\frac{1}{2}\bar{x} \not\in P^{-1}(\bar{x})$. If $\frac{1}{2}\bar{x} \in P^{-1}(\bar{x}),$ i.e. $\bar{x} \in P(\frac{1}{2}\bar{x})$, then, by translation-invariance, $\frac{1}{2}\bar{x} \in P(0)$. Since (1) is true for any $z \in P(0)$, iterations of this argument show that $0 \in clP(0)$, where $cl$ denotes the closure operator in the topology of $V$. Next we will show that $R(0) = cl P(0)$. Because $R(0)$ is closed, we only have to show that $I(0) \subseteq cl P(0).$ To this end, let $z \in I(0)$. Then $z = 0 + z \in cl P(0) + I(0) \subseteq cl( P(0) + I(0)) \subseteq cl P(0)$, where the last inclusion holds because of indifference-invariance. This implies that $R(0) +I(0) = cl P(0) + I(0) \subseteq cl(P(0) +I(0)) \subseteq cl P(0) = R(0)$, hence, $I(0) + I(0) \subseteq R(0)$. By translation-invariance, we also have $R^{-1}(0) +I(0) \subseteq R^{-1}(0)$, whence $I(0) + I(0) \subseteq R^{-1}(0)$ and we are done. \vskip.4cm (b) Secondly, we show that $R$ is complete. \vskip.1cm \noindent Assume that this is not the case, i.e. there exists $x\in V$ not comparable to 0. By (1), this implies $x \in P^{-1}(\bar{x})$. This will allow us to prove\ \begin{equation} R(x) \cap R(0) = P(x) \cap P(0). \end{equation} In fact, if $z \in I(x) \cap P(0)$ or $z \in I(0) \cap P(x)$, then, by indifference-invariance, $x \in P(0)$ or $x \in P^{-1}(0)$, respectively -- a contradiction to our assumption. If $z \in I(x) \cap I(0)$, then transitivity of $I$ implies $x \in I(0)$ -- again a contradiction. Because the set described in (2) does not own $x$, it is closed, open, and not the whole space. Therefore it is empty, a contradiction to $\bar{x} \in P(0) \cap P(x)$. \vskip.4cm (c) Next we show that $I(0)$ is a closed linear subspace of $V$. \vskip.1cm \noindent In fact, let $x\ I\ 0$, $y \ I\ 0$. Translation-invariance of $R$ and transitivity of $I$ give us $0\ I\ -x$ and thus $-x+y \ I\ y$. Transitiviy of $I$ implies $-x+y\ I\ 0$, and $I(0)$ is a group. It is left to show that $ x \in I(0)$ implies $\lambda x \in I(0)$ for any $\lambda \in \reals_+$. We will show that $x \ I\ 0$ implies $\frac{1}{2} x \ I \ 0$. Assume not. Then by completeness, $\frac{1}{2} x \in P (0)$ or $\frac{1}{2} x\in P^{-1}(0)$; say $\frac{1}{2} x \in P(0)$. Translation-invariance yields $-x\ I\ 0$ , and indifference-invariance $-\frac{1}{2} x =\frac{1}{2} x -x \in P(0)$, i.e. $\frac{1}{2} x\in P^{-1}(0)$, a contradiction to the fact that $P$ is asymmetric. Iterations of this argument yield $\frac{1}{2^k} x\ I\ 0$ for all $k \in \nat$. The group property of $I(0)$ allows us to infer that $\frac{n}{2^k} x \in I(0)$ for all $n,k \in \nat $. Because the set of these points is dense in $\reals_+\cdot x$ and because $I(0)$ is closed as the intersection of the closed sets $R^{-1}(0)$ and $R(0)$, we are done. \vskip.4cm (d) Finally, we prove linear continuous representability. \vskip.1cm \noindent Let $W$ be an algebraic complement of $I(0)$, i.e. $W$ is a linear subspace of $V$ with $I(0) \cap W = \{0\}$, and $V = I(0) + W$. By non-triviality of $R$, $W \not = \left\{ 0 \right\}$. Then, $C \defeq W \setminus \left\{ 0 \right\}$ clearly is a subset of $P(0) \cup P^{-1}(0)$, and, thus, cannot be connected. However, if dim $W \geq 2$, then $C$ is connected as the union of finitely many connected sets with mutually non-empty intersections. Hence dim $W = 1$ and $I(0)$ is a hyperplane. Therefore, there exists a continuous linear functional $p$ with $p(\bar{x}) < 0$ and $H^p \defeq \mbox{Ker\ } p = I(0)$ (Robertson and Robertson, 1964, Chapter II). Let $H_-^p \defeq \{ y\in V \mid p(y) < 0 \}$ \break and $H_+^p \defeq -H_-^p$. Either one of these open halfspaces is non-empty and connected. Because $R$ is complete, $H_-^p = (H_-^p \cap P(0)) \cup (H_-^p \cap P^{-1}(0))$. Because $\bar{x} \in H_-^p \cap P(0)$ and the sets $P(0)$ and $P^{-1}(0)$ are open, $H_-^p\cap P^{-1}(0) = \emptyset$. Thus $H_-^p \subset P(0)$. By translation-invariance, this gives $H_+^p = -H_-^p \subset -P(0)= P^{-1}(0)$. Hence $( H_{\rule{0mm}{2mm}}^p,H_+^p,H_-^p)$ and $(I(0) , P^{-1}(0),P(0))$ both are partitions of $V$ with $H_+^p \subset P^{-1}(0)$ and $H_-^p \subset P(0)$, and $I(0) =H^p$. Therefore, these partitions are identical and $p$ is (up to multiplication by a positive scalar) the uniquely determined continuous linear functional representing $R$. In particular, $R$ must be transitive and continuous in addition to being complete. \qed \section*{References} %\art author | date | title | journal | vol | pp. \def\art#1 | #2 | #3 | #4 | #5 | #6. {#1: #3. #4 {\bf #5,} #6 (#2)} %\book author | date | title | city | press. \def\book#1 | #2 | #3 | #4 | #5. {#1: #3 #4: #5 #2} %vol author | date | title | in | eds | city | press. \def\vol#1 | #2 | #3 | #4 | #5 | #6 | #7. {#1: #3, in: #4. Eds.~#5, #6: #7 #2} \begingroup\advance\leftskip by \parindent \parindent-16pt \quad \vol d'Aspremont, C. | 1985 | Axioms for Social Welfare Orderings | Social Goals and Social Organization. Essays in memory of Elisha Pazner | Leonid Hurwicz, David Schmeidler, and Hugo Sonnenschein | New York | Cambridge University Press. \art d'Aspremont, C., L. Gevers | 1977 | Equity and the Informational Basis of Collective Choice | Review of Economic Studies | 44 | 199 -- 209. \book Blackwell, D., M.A. Girshick | 1954 | Theory of Games and Statistical Decisions. | New York | John Wiley \& Sons. \art Candeal-Haro, J.C., E. Indurain-Eraso | 1994 | A Note on Linear Utility | Economic Theory | 6 | forthcoming. \art Einy, E. | 1989 | On Preference Relations which Satisfy Weak Independence Property | Journal of Mathematical Economics | 18 | 291--300. \art Grandmont J.-M. | 1972 | Continuity Properties of a von Neumann-Morgenstern Utility | Journal of Economic Theory | 4 | 45 -- 57. \art Herstein, I.N., J. Milnor | 1953 | An Axiomatic Approach to Measurable Utility | Econometrica | 21 | 291 -- 297. \art Maskin, E. | 1978 | A Theorem on Utilitarianism | Review of Economic Studies | 45 | 93 -- 96. \art Rader, J. T. | 1963 | The Existence of a Utility Function to Represent Preferences | Review of Economic Studies | 31 | 229 -- 232. \art Roberts, K. W. S. | 1980 | Interpersonal Comparability and Social Choice Theory | Review of Economic Studies | 47 | 421 -- 439. \book Robertson, A.P. and W.J. Robertson | 1964 | Topological Vector Spaces. | New York | Cambridge University Press. \book Rudin W. | 1991 | Functional Analysis. | New York | McGraw-Hill. \art Schmeidler, D. | 1971 | A Condition for the Completeness of Partial Preference Relations | Econometrica | 39 | 403 -- 404. \art Sonnenschein, H. | 1965 | The Relationship between Transitive Preference and the Structure of the Choice Space | Econometrica | 33 | 624 -- 634. \art Trockel, W. | 1989 | Classification of Budget-Invariant Monotonic Preferences | Economic Letters | 30 | 7 -- 10. \art Trockel, W. | 1992 | An Alternative Proof for the Linear Utility Representation Theorem | Economic Theory | 2 | 298--302. \endgroup \end{document} \begin{description} \item[] d'Aspremont, C. (1985): ``Axioms for Social Welfare Orderings,'' in {\em Social Goals and Social Organization. Essays in memory of Elisha Pazner.} Eds. Leonid Hurwicz, David Schmeidler, and Hugo Sonnenschein. New York: Cambridge University Press. \item[] d'Aspremont, C. and L. Gevers (1977): ``Equity and the Informational Basis of Collective Choice,'' {\em Review of Economic Studies} {\it 44}, 199 -- 209. \item[] Blackwell, D. and M.A. Girshick (1954): {\it Theory of Games and Statistical Decisions.} New York: John Wiley \& Sons. \item[] Candeal-Haro, J.C. and E. Indurain-Eraso (1994): `` A Note on Linear Utility,'' {\em Economic Theory}, forthcoming \item[] Einy, E. (1989): `` On Preference Relations which Satisfy Weak Independence Property,'' {\em Journal of Mathematical Economics}, {\em 18,} 291--300. \item[] Grandmont J.-M. (1972): ``Continuity Properties of a von Neumann-Morgenstern Utility,'' {\em Journal of Economic Theory}, {\it 4}, 45 -- 57. \item[] Herstein, I.N. and J. Milnor (1953): ``An Axiomatic Approach to Measurable Utility,'' {\em Econometrica}, {\it 21}, 291 -- 297. \item[] Maskin, E. (1978): ``A Theorem on Utilitarianism,'' {\em Review of Economic Studies}, {\it 45}, 93 -- 96. \item[] Rader, J. T. (1963): ``The Existence of a Utility Function to Represent Preferences,'' {\em Review of Economic Studies}, {\it 31}, 229 -- 232. \item[] Roberts, K. W. S. (1980): ``Interpersonal Comparability and Social Choice Theory,'' {\em Review of Economic Studies}, {\it 47}, 421 -- 439. \item[] Robertson, A.P. and W.J. Robertson (1964): {\em Topological Vector Spaces.} Cambridge University Press. \item[] Rudin W. (1991): {\em Functional Analysis.} New York, McGraw-Hill. \item[] Schmeidler, D. (1971): ``A Condition for the Completeness of Partial Preference Relations,'' {\em Econometrica}, {\it 39}, 403 -- 404. \item[] Sonnenschein, H. (1965): ``The Relationship between Transitive Preference and the Structure of the Choice Space,'' {\em Econometrica}, {\it 33}, 624 -- 634. \item[] Trockel, W. (1989): ``Classification of Budget-Invariant Monotonic Preferences,'' {\em Economic Letters}, {\it 30}, 7 -- 10. \item[] Trockel, W. (1992): ``An Alternative Proof for the Linear Utility Representation Theorem,'' {\em Economic Theory}, {\it 2}, 298--302. \end{description} \end{document}