Extending Utility Functions on Arbitrary Sets

Suppose that a decision maker has a utility function $f\mathop{\!{}_{\!\!P}}$ defined on some subset $P$ of a Euclidean space ${\mathbb{R}}^{k}$ of alternatives. It is usually assumed that $f\mathop{\!{}_{\!\!P}}$ strictly increases in $k$ coordinates corresponding to particular criteria. Therefore, it is of interest to determine conditions under which this function can be extended in such a way as to provide a strictly increasing function on ${\mathbb{R}}^{k}$. In settings where all elements of ${\mathbb{R}}^{k}$ are theoretically feasible, these conditions can be considered as those of the consistency of $f\mathop{\!{}_{\!\!P}}$.

In this paper, we consider a more general problem where an arbitrary preordered set ${(X,\succcurlyeq)}$ is substituted for ${\mathbb{R}}^{k}$. We show that whenever preorder $\succcurlyeq$ enables a utility representation (in the form of a real-valued function strictly increasing w.r.t. $\succcurlyeq$ on $X$), a strictly increasing extension of $f\mathop{\!{}_{\!\!P}}$ to ${(X,\succcurlyeq)}$ exists if and only if $f\mathop{\!{}_{\!\!P}}$ is gap-safe increasing with respect to $\succcurlyeq$. Moreover, such an extension can be based on any utility representation of $\succcurlyeq$. The main object of this paper is the general class of extensions (11) involving an arbitrary $(0,1)$-utility representation $u\mathop{\!{}_{01}}$ of $\succcurlyeq$ and arbitrary real constants ${\alpha}$ and ${\beta}>{\alpha}.$

We also consider the case where the structure of subset $P$ restricts functions strictly increasing on $P$ to the minimum extent. This is the case where $P$ is a Pareto set; for such $P,$ the extension takes a simpler form.

Starting with the classical results of Eilenberg [15], Nachbin [34, 35], and Debreu [10, 11, 12], much of the work related to utility functions has been done under the continuity assumption [6, 16]. In some cases this assumption is made “for purposes of mathematical reasoning” [1]. On the other hand, this requirement is not always necessary. Moreover, there are threshold effects [23, 27] such as a shift from quantity to quality or disaster avoidance behavior that require utility jumps. In other situations, the feasible set of possible outcomes is a discrete or finite subset of the entire space, which may eliminate or relax the continuity constraints. Thus, utility functions that may not be continuous everywhere are useful or even necessary to model some real-world problems [18, 28, 19, 14, 38, 2, 4]. For a discussion of various versions of the continuity postulate in utility theory, we refer to [44].

In this paper, we study the problem of extending utility functions defined on arbitrary subsets of an arbitrary set $X$ equipped with a preorder $\succcurlyeq$, but not endowed with a topological structure, since we do not impose continuity requirements. However, some kind of continuity of an associated inverse mapping follows from the necessary and sufficient condition of extendability we establish.

Throughout the paper ${(X,\succcurlyeq)}$ is a preordered set, where $X$ is an arbitrary nonempty set and $\succcurlyeq$ is a preorder (i.e., a transitive and reflexive binary relation) defined on $X.$ We first formulate the problem under consideration and then provide the necessary definitions; the definitions of basic properties and classes of binary relations are given in Appendix 0.A.

Consider any subset $P\subset X$ and any real-valued function $f\mathop{\!{}_{\!\!P}}$ defined on $P$. The problem studied in this paper is: to find conditions under which $f\mathop{\!{}_{\!\!P}}$ can be extended to ${(X,\succcurlyeq)}$ yielding a strictly increasing function and to construct a fairly general class of such extensions when they exist.

The definitions of the relevant terms are as follows.

Given a preorder $\succcurlyeq$ on $X,$ the asymmetric $\succ$ and symmetric $\approx$ parts of $\succcurlyeq$ are the relations¹¹1The elements of $X$ are printed in bold (as is common for vectors in ${\mathbb{R}}^{k}$) to distinguish them from real numbers. $[\bm{x}\succ\bm{y}]\equiv[\bm{x}\succcurlyeq\bm{y}$ and not $\bm{y}\succcurlyeq\bm{x}$] and $[\bm{x}\approx\bm{y}]\equiv[\bm{x}\succcurlyeq\bm{y}$ and $\bm{y}\succcurlyeq\bm{x}$], respectively, where $\equiv$ means “identity by definition.” Relation $\succ$ is transitive and irreflexive (i.e., it is a strict partial order), whereas $\approx$ is transitive, reflexive, and symmetric (i.e., an equivalence relation).

The converse relations corresponding to $\succcurlyeq$ and $\succ$ are $\preccurlyeq\,:[\bm{x}\preccurlyeq\bm{y}]\equiv[\bm{y}\succcurlyeq\bm{x}]$ and $\prec\,:[\bm{x}\prec\bm{y}]\equiv[\bm{y}\succ\bm{x}]$.

For any $P\subseteq X,$ $\succcurlyeq\!\mathop{\!{}_{P}}$ is the restriction of $\succcurlyeq$ to $P$.

$\bm{x}\in X$ is a maximal (minimal) element of ${(X,\succcurlyeq)}$ iff $\bm{x}^{\prime}\succ\bm{x}$ (resp., $\bm{x}\succ\bm{x}^{\prime}$) for no $\bm{x}^{\prime}\in X.$

Utility functions $f\mathop{\!{}_{\!\!P}}$ strictly increasing w.r.t. $\succcurlyeq$ can express the attitude, consistent with the preference preorder $\succcurlyeq$, of a decision maker towards the elements of $P$. Utility representations of preorders and partial orders have been studied since [35, 3, 36, 17].

It follows from Definition 1 that for any weakly increasing function $f\mathop{\!{}_{\!\!P}}$,

Using (1) we obtain the following simple lemma.

Indeed, (2) follows from Definition 1 using (1). Conversely, if (2) holds, then $[\hskip 1.1pt\bm{p}^{\prime}\succcurlyeq\bm{p}\>\Rightarrow f\mathop{\!{}_{\!\!P}}(\bm{p}^{\prime})\geq f\mathop{\!{}_{\!\!P}}(\bm{p})],$ since $\bm{p}^{\prime}\succcurlyeq\bm{p}$ implies $[\hskip 1.1pt\bm{p}^{\prime}\approx\bm{p}\mbox{ or }\bm{p}^{\prime}\succ\bm{p}]$ with the desired conclusion in either case, while the second condition is immediate.

In economics and decision making, alternatives are often identified with $k$-dimensional vectors of criteria values [41] or goods [1]. In such cases, $X={\mathbb{R}}^{k}.$ Thus, an important special case of the extendability problem is the problem of extending to ${\mathbb{R}}^{k}$ functions defined on $P\subset{\mathbb{R}}^{k}$ and strictly increasing w.r.t. the Pareto preorder on ${\mathbb{R}}^{k}$. The Pareto preorder $\succcurlyeq$ [13] is defined as follows: for any $\bm{x}=(x_{1},\ldots,x_{k})$ and $\bm{y}=(y_{1},\ldots,y_{k})$ that belong to ${\mathbb{R}}^{k},$ $[\bm{x}\succcurlyeq\bm{y}]\equiv[x\mathop{\!{}_{i}}\geq y\mathop{\!{}_{i}}$ for all $i\in\{1,\ldots,k\}]$.

Extensions of preorders and partial orders and their numerical representations have been studied since Szpilrajn’s theorem [39] according to which every partial order can be extended to a linear order.

Another basic result is that a preorder $\succcurlyeq$ has a utility representation whenever there exists a countable dense⁴⁴4$Y\subseteq X$ is $R$-dense in $X,$ where $R$ is a binary relation on $X$ [17], iff $\bm{x}^{\prime}R\bm{x}$ $\Rightarrow$ [$\bm{x}^{\prime}\in Y$ or $\bm{x}\in Y$ or [$\bm{x}^{\prime}R\bm{y}$ and $\bm{y}R\bm{x}$ for some $\bm{y}\in Y$]] for all $\bm{x},\bm{x}^{\prime}\in X$. (w.r.t. the induced partial order) subset in the factor set $X/\!\approx,$ where $\approx$ is the symmetric part of $\succcurlyeq$ [12, 37, 17]. This is not a necessary condition, however, for the subclass of weak orders (i.e., connected preorders), it is necessary.

Among the extensions of the Pareto preorder on ${\mathbb{R}}^{k}$ are all lexicographic linear orders [17] on ${\mathbb{R}}^{k}$. When $k>1$, these extensions lack utility representations [12], while a utility representation of the Pareto preorder is any function strictly increasing in all coordinates.

Any utility representation of a preorder $\succcurlyeq$ induces a weak order that extends $\succcurlyeq$. In turn, this weak order determines its utility representation up to an arbitrary strictly increasing transformation; for certain related results, see [17, 32, 33, 21, 6, 16]. As was seen on the example of the Pareto preorder, not all weak orders extending $\succcurlyeq$ correspond to utility representations of $\succcurlyeq$. However, this is true when $X$ is a vector space and the weak order has the Archimedean property, which ensures [17] the existence of a countable dense (w.r.t. this weak order) subset of $X$.

Theorem 6.1 below gives a necessary and sufficient condition for the strictly increasing extendability of a function defined on a subset of $X$ w.r.t. a preorder that has a utility representation. Moreover, this theorem introduces a class of extensions that depend on both the initial function and an arbitrary utility representation of the preorder.

We now introduce the notation used in Theorem 6.1 and present simple facts related to it.

Let $\widetilde{{\mathbb{R}}}$ be the extended real line:

with the ordinary $>$ relation supplemented by $+\infty>-\infty$ and $+\infty>x>-\infty$ for all $x\in{\mathbb{R}}$. Since the extended $>$ relation is a strict linear order, it determines unique smallest ($\min Q$) and largest ($\max Q$) elements in any nonempty finite $Q\subset\widetilde{{\mathbb{R}}}$.

Functions $\sup Q$ and $\inf Q$ are considered as maps from $2^{{\mathbb{R}}}$ to $\widetilde{{\mathbb{R}}}$ defined for $Q=\emptyset$ as follows: $\sup\emptyset=-\infty$ and $\inf\emptyset=+\infty$. This preserves inclusion monotonicity, i.e., the property that $\sup Q$ does not decrease and $\inf Q$ does not increase with the expansion of the set $Q$ (cf. [40, Section 4]). Throughout we assume $+\infty+x=+\infty$ and $-\infty-x=-\infty$ whenever $x>-\infty,$ while indeterminacies like $+\infty+(-\infty)$ never occur in our formulas.

For any $f\mathop{\!{}_{\!\!P}}\!:P\to{\mathbb{R}}$, where $P\subseteq X$, define two functions from $X$ to $\widetilde{{\mathbb{R}}}$:

By definition, the “lower supremum” $f_{\bm{\uparrow}_{\mathstrut}}^{P}(\bm{x})$ and “upper infimum” $f^{\bm{\downarrow}\mathstrut}_{\!P}(\bm{x})$ functions can take values $-\infty$ and $+\infty$ along with real values.

It follows from the transitivity of $\succcurlyeq$ and the inclusion monotonicity of the $\sup$ and $\inf$ functions that for any (not necessarily increasing) $f\mathop{\!{}_{\!\!P}},$ functions $f_{\bm{\uparrow}_{\mathstrut}}^{P}(\bm{x})$ and $f^{\bm{\downarrow}\mathstrut}_{\!P}(\bm{x})$ are weakly increasing with respect to $\succcurlyeq$:

Consequently,

Furthermore, since $\bm{p}\in P$ implies $\bm{p}\in P_{\bm{\uparrow}}\!\!(\bm{p})\cap P^{\bm{\downarrow}}(\bm{p}),$ it holds that

We will use the following characterizations of the class of weakly increasing functions $f\mathop{\!{}_{\!\!P}}$ in terms of $f_{\bm{\uparrow}_{\mathstrut}}^{P}$ and $f^{\bm{\downarrow}\mathstrut}_{\!P}.$

The proofs are given in Section 11.

In this section, we consider the class of gap-safe increasing functions $f\mathop{\!{}_{\!\!P}},$ which is not wider, but can be narrower for some $X$ and $P$ than the class of strictly increasing functions $P\to{\mathbb{R}}$ (see Proposition 2 and Example 1 below). We will show that this is precisely the class of functions that admit a strictly increasing extension to ${(X,\succcurlyeq)}$.

Let us extend $X$ in the same manner as ${\mathbb{R}}$ is extended by (3):

where $\bm{-\infty}$ and $\bm{+\infty}$ are two distinct elements that do not belong to $X.$ Preorder $\succcurlyeq\!\mathop{\!{}_{X}}\subseteq X\!\times\!X$ is extended to $\widetilde{X}$ as follows:

where $(\bm{+\infty},\bm{x})$ and $(\bm{x},\bm{-\infty})$ are pairs of elements of $\widetilde{X}.$

Functions $f_{\bm{\uparrow}_{\mathstrut}}^{P}$, $f^{\bm{\downarrow}\mathstrut}_{\!P}:$ $\widetilde{X}\to\widetilde{{\mathbb{R}}}$ are defined in the same way as in (4).

The term “gap-safe increasing” refers to the property of a function to orderly separate its values (${f^{\bm{\downarrow}\mathstrut}_{\!P}(\bm{x}^{\prime})>f_{\bm{\uparrow}_{\mathstrut}}^{P}(\bm{x})}$) when the corresponding sets of arguments are orderly separated (${\bm{x}^{\prime}\succ\bm{x}}$) in $X$; see also Remark 3. In [8], the term “separably increasing function” was proposed, clashing with topological separability, which means the existence of a countable dense subset.

It should be noted that there are functions $f\mathop{\!{}_{\!\!P}}$ that are strictly increasing, upper-bounded on all lower $P$-contours and lower-bounded on all upper $P$-contours, but are not gap-safe increasing.

Let $f\mathop{\!{}_{\!\!P}}$ defined on any $P\subseteq X$ be gap-safe increasing. Theorem 6.1 below states that this is a necessary and sufficient condition for the existence of strictly increasing extensions of $f\mathop{\!{}_{\!\!P}}$ to ${(X,\succcurlyeq)}$ provided that $\succcurlyeq$ enables utility representation. Furthermore, for any such a representation, the theorem provides an extension of a gap-safe increasing function $f\mathop{\!{}_{\!\!P}}$ that combines these two functions.

For any ${\alpha},{\beta}\in{\mathbb{R}}$ such that ${\alpha}<{\beta},$ let $u\mathop{\!{}_{{\alpha}{\beta}}}\!:X\to{\mathbb{R}}$ be a utility representation of $\succcurlyeq$ (i.e., a function strictly increasing w.r.t. $\succcurlyeq$) satisfying

For any (unbounded) utility representation of $\succcurlyeq,$ $u(\bm{x})$, such a function $u\mathop{\!{}_{{\alpha}{\beta}}}(\bm{x})$ can be obtained, for example, using transformation

In particular, consider the functions $u\mathop{\!{}_{01}}\!:X\to{\mathbb{R}}$ that satisfy

They are normalized versions of the above utilities $u\mathop{\!{}_{{\alpha}{\beta}}}$:

For any real ${\alpha}$ and ${\beta}>{\alpha}$ and any utility representations $u\mathop{\!{}_{01}}$ of $\succcurlyeq,$ we define

For an arbitrary gap-safe increasing $f\mathop{\!{}_{\!\!P}},$ function $f\!:X\to{\mathbb{R}}$ given by (11) is well defined as the two terms in the right-hand side are finite. This follows from item $(b)$ of Proposition 2. For preordered sets ${(X,\succcurlyeq)}$ that have minimal or maximal elements (see Example 2 in Section 9, where ${(X,\succcurlyeq)}$ has a maximal element), this is ensured by introducing the augmented sets $\widetilde{X}$ in the definition of a gap-safe increasing function. Indeed, since $f^{\bm{\downarrow}\mathstrut}_{\!P}(\bm{+\infty})=+\infty,$ ${f_{\bm{\uparrow}_{\mathstrut}}^{P}(\bm{-\infty})=-\infty,}$ and $\bm{+\infty}\succ\bm{x}\succ\bm{-\infty}$ for all $\bm{x}\in X,$ Definition 4 provides $f^{\bm{\downarrow}\mathstrut}_{\!P}(\bm{+\infty})>f_{\bm{\uparrow}_{\mathstrut}}^{P}(\bm{x})$ and $f^{\bm{\downarrow}\mathstrut}_{\!P}(\bm{x})>f_{\bm{\uparrow}_{\mathstrut}}^{P}(\bm{-\infty}),$ hence $+\infty>f_{\bm{\uparrow}_{\mathstrut}}^{P}(\bm{x})$ and ${f^{\bm{\downarrow}\mathstrut}_{\!P}(\bm{x})>-\infty,}$ i.e., $f\mathop{\!{}_{\!\!P}}$ is upper-bounded on all lower $P$-contours and lower-bounded on all upper $P$-contours, ensuring the correctness of definition (11). If ${(X,\succcurlyeq)}$ has neither minimal nor maximal elements (like the Pareto preorder on ${\mathbb{R}}^{k}$), then the replacement of $\widetilde{X}$ with $X$ in Definition 4 does not alter the class of gap-safe increasing functions.

We now formulate the main result.

The class of extensions introduced by Theorem 6.1 allows alternative representations that clarify its properties. They are given by Propositions 3–5.

The order of proofs in Section 11 is as follows. Verification of the second statement of Proposition 3 is straightforward and is omitted. This statement is used to prove Proposition 5, which implies Proposition 4, and they both are used in the proof of Theorem 6.1, which in turn implies the first statement of Proposition 3.

To simplify (12), we partition $X\setminus P$ into four regions determined by $\succcurlyeq$ and $P$:

Clearly these regions are pairwise disjoint and $X=P\cup A\cup L\cup U\cup N$.

Proposition 4 highlights the role of $u\mathop{\!{}_{{\alpha}{\beta}}}$ in (12). Function $f$ reduces to $f\mathop{\!{}_{\!\!P}}$ on $P$ and to $u\mathop{\!{}_{{\alpha}{\beta}}}$ on $N$ whose elements are $\succcurlyeq$-incomparable with those of $P$. Moreover, $f(\bm{x})=u\mathop{\!{}_{{\alpha}{\beta}}}(\bm{x})$ on the part of $L$ where $f^{\bm{\downarrow}\mathstrut}_{\!P}(\bm{x})\geq{\beta}$ and on the part of $U$ where $f_{\bm{\uparrow}_{\mathstrut}}^{P}(\bm{x})\leq{\alpha}.$ On the complement parts of $L$ and $U$, $f(\bm{x})=f^{\bm{\downarrow}\mathstrut}_{\!P}(\bm{x})+(u\mathop{\!{}_{{\alpha}{\beta}}}(\bm{x})-{\beta})$ and $f(\bm{x})=f_{\bm{\uparrow}_{\mathstrut}}^{P}(\bm{x})+(u\mathop{\!{}_{{\alpha}{\beta}}}(\bm{x})-{\alpha}),$ respectively. On $A,$ (12) is not simplified. This fact and the ambiguity on $L$ and $U$ prompt us to make another partition of $X.$

Consider four regions that depend on $\succcurlyeq,$ $P,$ $f\mathop{\!{}_{\!\!P}},$ ${\alpha},$ and ${\beta}$:

It is easily seen that $X=S_{1}\cup S_{2}\cup S_{3}\cup S_{4},$ whereas the $S_{i}$-regions are not disjoint. This decomposition allows us to express $f(\bm{x})$ without $\min$ and $\max$.

Thus, on $S_{1},$ $f(\bm{x})$ is a convex combination of $f^{\bm{\downarrow}}_{\!P}(\bm{x})$ and $f_{\bm{\uparrow}}^{P}\!\!(\bm{x})$ with coefficients $u\mathop{\!{}_{01}}(\bm{x})$ and $(1-u\mathop{\!{}_{01}}(\bm{x})),$ respectively. The regions $S_{1},S_{2},S_{3},$ and $S_{4}$ intersect on some parts of the border sets ${f^{\bm{\downarrow}\mathstrut}_{\!P}(\bm{x})-f_{\bm{\uparrow}_{\mathstrut}}^{P}(\bm{x})}={\beta}-{\alpha}$, $f_{\bm{\uparrow}_{\mathstrut}}^{P}(\bm{x})={\alpha}$, and $f^{\bm{\downarrow}\mathstrut}_{\!P}(\bm{x})={\beta}$. Accordingly, the expressions of $f$ given by Proposition 5 are concordant on these intersections.

Consider the case where $P$ is a Pareto set. Such a set comprises elements that are mutually undominated.

For functions defined on Pareto sets $P$, the necessary and sufficient condition of extendability to ${(X,\succcurlyeq)}$ given by Theorem 6.1 reduces to the boundedness on all $P$-contours (which appeared in Proposition 2) supplemented by condition (1): $\big{[}\hskip 1.1pt\bm{p},\,\bm{p}^{\prime}\in P\mbox{ and\, }\bm{p}^{\prime}\approx\bm{p}\hskip 1.1pt\big{]}\,\Rightarrow f\mathop{\!{}_{\!\!P}}(\bm{p}^{\prime})=f\mathop{\!{}_{\!\!P}}(\bm{p})$.

By the transitivity of $\succcurlyeq$, for any Pareto set $P,$ the sets $P\cup A$ and $S_{1}$ have a simple structure described in the following lemma.

Lemmas 2 and 3, Propositions 4 and 5, and Corollary 1 provide the following special case of Theorem 6.1 for Pareto sets.

It follows from Corollary 2 that for a Pareto set $P$, functions $f\mathop{\!{}_{\!\!P}}$ and $u\mathop{\!{}_{{\alpha}{\beta}}}$ influence $f$ almost symmetrically: $f$ reduces to $f\mathop{\!{}_{\!\!P}}$ on $P\cup A=S_{1},$ to $u\mathop{\!{}_{{\alpha}{\beta}}}$ on $S_{4}$, and is determined by the sum $f^{\bm{\downarrow}\mathstrut}_{\!P}(\bm{x})+u\mathop{\!{}_{{\alpha}{\beta}}}(\bm{x})$ or $f_{\bm{\uparrow}_{\mathstrut}}^{P^{\mathstrut}}(\bm{x})+u\mathop{\!{}_{{\alpha}{\beta}}}(\bm{x})$ on $S_{2}\cup S_{3}.$

Results related to Theorem 6.1 and Corollary 2 were used in [7, 9] to construct implicit forms of scoring procedures for preference aggregation and evaluation of the centrality of nodes. More specifically, theorems of this type allow us to move from axioms that determine a positive impact of the comparative results of objects on their functional scores to the conclusion that the scores satisfy a system of equations determined by a strictly increasing function.

Problems of extending real-valued functions while preserving monotonnicity (sometimes called lifting problems) have been considered primarily in topology. Therefore, continuity was usually a property to be preserved. This strand of literature started with the following theorem of general topology.

For metric spaces, a counterpart of this theorem was proved by Tietze [42].

Nachbin [35] obtained extension theorems for functions defined on preordered spaces. In his terminology, a topological space $(X,\tau,\succcurlyeq)$ equipped with a preorder $\succcurlyeq$ is normally preordered if for any two disjoint closed sets $F_{0},\,F_{1}\subset X,$ $F_{0}$ being decreasing (i.e., with every $\bm{x}\in F_{0}$ containing all $\bm{y}\in X$ such that $\bm{y}\preccurlyeq\bm{x}$) and $F_{1}$ increasing (with every $\bm{x}\in F_{1}$ containing all $\bm{y}\in X$ such that $\bm{y}\succcurlyeq\bm{x}$), there exist disjoint open sets $V_{0}$ and $V_{1},$ decreasing and increasing respectively, such that $F_{0}\subseteq V_{0}$ and $F_{1}\subseteq V_{1}.$ The space is normally ordered if, in addition, its preorder $\succcurlyeq$ is antisymmetric (i.e., is a partial order).

An analogous theorem for more general normally preordered spaces is [31, Theorem 3.4]. Sufficient conditions for $(X,\tau,\succcurlyeq)$ to be normally preordered are: (a) compactness of $X$ and belonging of $\succcurlyeq$ to the class of closed partial orders [35, Theorem 4 in Chapter 1] (this result was strengthened in [31]); (b) connectedness and closedness of $\succcurlyeq$ [30].