Values Of Non-Atomic Games

Carl Herpfer (1836-1897) was a German painter.

The topics are

\begin{equation}{\label{a}}\tag{A}\mbox{}\end{equation}

Preliminaries.

The player space is a measurable space $(I,{\cal I})$. A member of the $\sigma$-field ${\cal I}$ is called a coalition. A game is a real-valued set function $v$ defined on ${\cal I}$ such that $v(\emptyset )=0$. A game $v$ is monotonic when $T\subseteq S$ implies $v(T)\leq v(S)$. A set function is a function from ${\cal I}$ into a real Banach space.

The variation of a set function $v$ is the extended real-valued function $|v|$ defined by
\[|v|(S)=\sup\sum_{i=1}^{n}\parallel v(S_{i})-v(S_{i-1})\parallel\]
for $S\in {\cal I}$, where the supremum is taken over all finite nondecreasing sequences of coalitions of the form $S_{0}\subseteq S_{1}\subseteq\cdots\subseteq S_{n}=S$.
A set function $v$ is of bounded variation if and only if $|v|(I)<\infty$.

We denote by $BV$ the normed linear space of all games of bounded variation endowed with the operations of pointwise adition and (real) scalar multiplication with the variation norm $\parallel v\parallel_{BV}=|v|(I)$. The set of monotonic games span this space $BV$.
The subspace of $BV$ that consists of all finitely additive real-valued set function of bounded variation is denoted by $FA$. (Milchtaich \cite{mil98}).

A vector measure is a countably additive set function from ${\cal I}$ into a real Banach space. A vector measure is non-atomic when, for every $S\in {\cal I}$ with $\mu (S)\neq 0$, there is a subset $T\subseteq S$ such that $\mu (T)\neq 0$ and $\mu (S\setminus T)\neq 0$. The variation $|\mu |$ (also called the total variation measure) of a vector measure $\mu\in BV$ is a measure. We also see that $|\mu |$ is non-atomic if and only if $\mu$ is non-atomic. The subspace of $BV$ that consists of all non-atomic (finite, signed real-valued) measures is denoted by $NA$.

An ideal coalition (fuzzy coalition) is a measurable function $h:I\rightarrow [0,1]$. For a vector measure $\mu$ and an ideal coalition (or a linear combination of ideal coalitions) $h$, we define
\begin{equation}{\label{ga50}}\tag{1}
\mu (h)=\int hd\mu .
\end{equation}
(see Dunford and Schwartz \cite[Section IV.10]{dun} for a definition of integration with respect to a vector measure). We denote by ${\cal S}$ the set of all ideal coalitions. The set ${\cal S}$ is topologized by the $NA$-topology, which is defined as the smallest topology on ${\cal S}$ such that all functions of the form $\mu (\cdot)$ defined in (\ref{ga50}) with $\mu\in NA$ are continuous. The base for the neighborhood system of an ideal coalition $h$ can be taken as the collection of all open sets of the form shown below
\[\left\{g\in {\cal S}:\max_{1\leq i\leq k}|\mu_{i}(g-h)|<\epsilon\right\},\]
where $\epsilon >0$ and $\mu_{1},\cdots ,\mu_{k}\in NA$. The range of a vector measure $\mu$ is the set $\mu ({\cal I})$. We have the following observations.

If the range of $\mu$ (or, more precisely, the subspace it spans) is finite dimensional, then $\mu$ is automatically of bounded variation.
If $\mu$ is also non-atomic, then its range is compact and convex.

The range of a general non-atomic vector measure need not be compact nor convex. However, we have the following observations.

For every vector measure $\mu$ the set $\mu ({\cal S})=\{\mu (h):h\in {\cal S}\}$ is convex and weakly compact (ref. Diestel and Uhl \cite [p.263]{die}).
The set $\mu ({\cal S})$ coincides with the closed convex hull of $\mu ({\cal I})$, i.e., $\mu ({\cal S})=\overline{\mbox{co}}(\mu ({\cal I})$.
If $\mu$ is non-atomic, then $\mu ({\cal S})$ is the weak closure of $\mu ({\cal I})$.

We call $\mu ({\cal I})$ the {\bf extended range} of $\mu$.

Example. (Milchtaich \cite[p.28]{mil98}). Let $m$ be a probability measure on $(I,{\cal I})$, and define $\mu :{\cal I}\rightarrow L_{1}(m)$ by $\mu (S)=\chi_{S}$. Then $\mu$ is a vector measure of bounded variation whose variation is $m$. Therefore, $\mu$ is non-atomic if and only if $m$ is non-atomic. The range of $\mu$ consists of all (equivalence classes of) characteristic fucntions of measurable subsets of $I$. This is a closed, but not convex, subset of $L_{1}(m)$, and if $m$ is non-atomic then it is also not comapct. The extended range of $\mu$ is the set of all (equivalence classes of) measurable functions from $I$ into the unit interval. Indeed, for every $h\in {\cal S}$, $\mu (h)=h$. Note that in this example the weak compactness of the extended range of $\mu$ follows immediately from Alaoglu’s theorem and from the fact that the relative weak topology on this set coincides with the relative weak-star topology on it when seen as a subset of $L_{\infty}(m)$. $\sharp$

We shall say that a real-valued function $f$ defined on a convex subset $C$ of a Banach space $X$ is differentiable at $x\in C$ if and only if there exists a continuous linear functional $Df(x)\in Y^{*}$, where $Y$ is the subspace of $X$ spanned by $C-C=\{y-z:y,z\in C\}$ and $Y^{*}$ is its dual space, such that for every $y\in C$
\[f(x+\theta (y-x))=f(x)+\theta\langle y-x,Df(x)\rangle +o(\theta )\]
as $\theta\rightarrow 0+$. This continuous linear functional, which is necessarily unique, will be called the derivative of $f$ at $x$. The function $f$ is (resp. weakly) continuously differentiable at $x$ if and only if it is differentiable in a (resp. weak) neighborhood of $x$ in $C$ and the derivative $Df$ is (resp. weakly) continuous at $x$. The function $f$ is (resp. weakly) continuously differentiable if and only if it is (resp. weakly) continuously differentiable in the whole domain. The restriction of a (resp. weakly) continuously differentiable function to a convex subset of its domain is (resp. weakly) continuously differentiable. Continuous differentiability and weak continuous differentiability are equivalent for functions with compact domain. This follows from the fact that the relativization of the weak topology to a compact subset of a Banach space coincides with the relative norm topology (because every set which is closed, and hence compact, with respect to the relative norm topology is compact, and hence closed, also with respect to the relative weak topology). A real-valued function $f$ defined on a bounded convex subset $C$ of a Banach space $X$ is (resp. weakly) continuous at every point $x$ at which it is (resp. weakly) continuously differentiable. If $X$ is a Euclidean space and $C$ is compact then $f$ is continuously differentiable if and only if it can be extended to a continuous function on $X$ with continuous first-order partial derivatives (Milchtaich \cite{mil98}).

The closed linear subspace of $BV$ that is generated by all powers (with respect to pointwise muliplication) of non-atomic probability measures is denoted by $pNA$. There exists a unique continuous linear operator $\phi :pNA\rightarrow FA$ that satisfies $\phi (\mu^{k})=\mu$ for every non-atomic probability measure and positive integer $k$, called the Aumann-Shapley value on $pNA$. For a game $v$, we define
\[\parallel v\parallel_{\infty}=\inf\left\{\mu (I):\mu\in NA\mbox{ and $latex |v(S)-v(T)|
\leq\mu (S\setminus T)$ for every $S,T\in {\cal I}, T\subseteq S$}\right\}\]
(where $\inf\emptyset =\infty$). The collection of all games $v$ such that $\parallel v\parallel_{\infty}<\infty$ is a linear subspace of $BV$, which is denoted $AC_{\infty}$ and $\parallel\cdot\parallel_{\infty}$ is a norm on the space $AC_{\infty}$. The $\parallel\cdot\parallel_{\infty}$-closed linear subspace of $AC_{\infty}$ that is generated by all powers of non-atomic probability measures is denoted $pNA_{\infty}$, which is a proper subset of $pNA$. (Milchtaich \cite[p.29]{mil98}).

\begin{equation}{\label{b}}\tag{B}\mbox{}\end{equation}

Vector Measure Games.

Consider non-atomic games which are defined by finitely many nonnegative measures, i.e., games of $v$ of the form $v=f\circ (\mu_{1},\cdots ,\mu_{n})$, where $(\mu_{1},\cdots ,\mu_{n})$ is a vector of non-atomic nonnegative measures and $f$ is a real-valued function defined on the range of $(\mu_{1},\cdots ,\mu_{n})$. A game of this form is usually called vector measure game. It is a well known fact that in all cases studied, the value of such game $v$ turns out always to a linear combination of the measures $\mu_{1},\cdots ,\mu_{n}$. Can this “fact” be proved in general? That is, is it a consequence of the axioms defining the value (ref. Aumann and Shapley \cite{aum74b})? We will show here that the answer is negative. Formally, let $Q$ be a space of non-atomic games (all notations and definitions follow Aumann and Shapley \cite{aum74b}), and let $\phi :Q\rightarrow FA$ be a value on $Q$. The property we discuss is

(P1). Let $\mu_{1},\cdots ,\mu_{n}$ be $n$ non-atomic nonnegative measures, and $f$ a real-valued function defined on the range of $(\mu_{1},\cdots ,\mu_{n})$. If $v=f\circ (\mu_{1},\cdots ,\mu_{n})$ belongs to $Q$, then there exist real numbers $a_{1},\cdots ,a_{n}$ such that $\phi (v)=\sum_{i=1}^{n}a_{i}\mu_{i}$.

Note that (P1) holds when $n=1$. We can construct a number of examples, each one consisting of a space of games $Q$ together with an appropriate value $\phi$ on it, such that (P1) is violated. Of course, there might well be other values on the same space $Q$ which do satisfy (P1). (Hart and Neyman \cite{har88}).

A list of axioms, adapted from those which uniquely characterize the Shapley value for finite-player cooperative games, determines a unique value on certain classes of non-atomic cooperative games — games involving an infinite number of players, each of which is individually insignificant (ref. Aumann and Shapley \cite{aum74b}). Concrete criteria for identifying a given non-atomic game as belonging to such a class of games, and a formula for computing the value, are known for certain kinds of vector measure games (ref. Aumann and Shapley \cite{aum74b}). In a vector measure game, the worth of a coalition $S$ depends only on the value that a particular vector measure on the space of players takes in $S$. Here, the term “vector measure” usually refers to an $\mathbb{R}^{n}$-valued measure. However, certain non-atomic games are more naturally described in terms of measures that take values in an infinite dimensional Banach space.

Consider, for example, a (transferable utility) market game $v$, where the worth of a coalition $S$ is given by
\begin{equation}{\label{mil98eq1}}\tag{2}
v(S)=\max\left\{\int_{S}u(x(i),i)dm(i):\int_{S}x(i)dm(i)=\int_{S}a(i)dm(i)\right\},
\end{equation}
the maximum aggregate utility that $S$ can guarantee to itself by an allocation $x$ of its aggregate endowment $\int_{S}adm$ among its members (ref. Aumann \cite{aum64}. In this formula, $u(\xi ,i)$ is the utility that player $i$ gets from the bundle $\xi$ and $m$, the population measure, is a non-atomic probability measure.) Since $v(S)$ depends on $S$ only through certain integrals over $S$, if $m(S\setminus T)=m(T\setminus S)=0$ then $v(S)=v(T)$. Thus $v(S)$ can be expressed as a function of the characteristic function $\chi_{S}$ of the coalition $S$, seen as an element of $L_{1}(m)$. The market game under consideration can therefore be viewed as a vector measure game based on the $L_{1}(m)$-valued vector measure defined by $S\mapsto\chi_{S}$.

Sroka \cite{sro93} studied games based on vector measure of bounded variation with values in a relatively compact subset of a Banach space with a shrinking Schauder basis. The vector measure considered above in connection with the marker game is not of this kind: its range is not a relatively compact subset of $L_{1}(m)$, and $L_{1}(m)$ itself does not have a shrinking Schauder basis. (Only a separable Banach space with a separable dual space can have such a basis. Considering the range of measure in question to be subset of $L_{2}$, say, rather than $L_{1}$, would not help, for the measure would not then be of bounded variation. Note that if the range space were taken to be $L_{\infty}$ then the above set function would not even be a measure; specifically, it would not be countably additive.) These limitations on the range of the vector measure and on the space in which it lies are dispensed with here in our discussion. Thus, the results of Aumann and Shapley are generalized to a much larger class of vector measure games.

As the above market game example demonstrates, the present interpretation of “vector measure games” is broad enough to include all games in which the worth of a coalition is not affected by the addition or subtraction of a set of players of measure zero — the measure in question being a fixed non-atomic scalar measure on the space of palyers. All the games that belong to one of the spaces of games on which Aumann and Shapley have proved the existence of a unique value have this property, and can therefore be interpreted as vector measure games. This representation is, however, not unique. It is therefore desirable to reformulate the condition for a vector measure game to belong to one of these spaces in a language that does not make an explicit reference to vector measures. Such an alternative formulation is also preseted in our discussion, where the above conditions are stated as differentiability and continuity conditions on a suitable extension of the game, an ideal games, that assigns a worth to every ideal, or “fuzzy”, coalition, in which some players are only partial members (Milchtaich \cite{mil98}).

Given a measurable player space $(I,{\cal I})$ and a non-atomic vector measure $\mu$ from ${\cal I}$ into a real Banach space, let $f$ be a real-valued function defined on $\mu ({\cal I})$ such that $f(\theta )=0$ and let $v=f\circ\mu$ be the composition of $f$ and $\mu$. Then, we call $(I,{\cal I},v)$ a vector measure game. Aumann and Shapley \cite{aum74b} proved that if the range of $\mu$ is finite dimensional then a sufficient condition for a vector measure game $f\circ\mu$ to be in $pNA$ (actually in $pNA_{\infty}$) is that $f$ be continuously differentiable. Sroka \cite{sro93} generalized the result to the case where the range of $\mu$ is a relatively compact subset of a Banach space with a shrinking Schauder basis. These results are generalized further in the following theorem (Milchtaich \cite[p.30]{mil98}).

\begin{equation}{\label{mil98t1}}\tag{3}\mbox{}\end{equation}

Theorem \ref{mil98t1}. (Milchtaich \cite[p.30]{mil98}). Let $\mu$ be a non-atomic vector measure of bounded variation with values
in a Banach space $X$. If $f$ is a weakly continuously differentiable real-valued function defined on the extended range $\mu ({\cal I})$ of $\mu$ such that $f(0)=0$, then $f\circ\mu$ is in $pNA_{\infty}$ and its value is given by the $($diagonal$)$ formula
\begin{equation}{\label{mil98eq2}}\tag{4}
\phi (f\circ\mu )(S)=\int_{0}^{1}\langle\mu (S),Df(t\mu (I))\rangle dt
\end{equation}
for $S\in {\cal I}$. If $X$ is finite dimensional then the converse is also true; that is, a vector measure game $f\circ\mu$ is in $pNA_{\infty}$ only if $f$ is continuously differentiable on the range of $\mu$. $\sharp$

Note that if the range of $\mu$ is relatively compact (this is automatically the case if $X$ is a reflexive space or a separable dual space.) then by Mazur theorem (ref. Dunford and Schwartz \cite [p.416]{dun}) the extended range of $\mu$ is compact. Therefore, in such a case $f$ is weakly continuously differentiable if and only if it is continuously differentiable. If a vector measure game $f\circ\mu$ is monotonic, then for it to be in $pNA$ it suffices that $f$ be continuous, rather than differentiable, at $\theta$ and $\mu (I)$.

Proposition. (Milchtaich \cite{mil98}). Let $\mu$ be a non-atomic vector measure of bounded variation with values in a Banach space $X$, and let $f$ be weakly continuously differentiable real-valued function defined on $\mu (\{h\in {\cal S}:0<|\mu |(h)<|\mu |(I)\})$ and continuous at $\theta$ and at $\mu (I)$. If $(I,{\cal I},f\circ\mu )$ is a monotonic game, then it is in $pNA$ and its value is given by (\ref{mil98eq2}). $\sharp$

\begin{equation}{\label{mil98l1}}\tag{5}\mbox{}\end{equation}

Proposition \ref{mil98l1}. (Milchtaich \cite{mil98}). Let $\mu$ be a non-atomic vector measure of bounded with values in a Banach space $X$, and let $f$ be a real-valued function defined on $\mu ({\cal S})$. We define $\widehat{\mu}:{\cal I}\rightarrow L_{1}(|\mu |)$ by $\widehat{\mu}(S)=\chi_{S}$. $($Note that $|\widehat{\mu}|=|\mu |.)$ Then, the following statements hold true.

(i) There exists a unique real-valued function $\widehat{f}$ defined on $\widehat{\mu}({\cal S})$ satisfying $\widehat{f}(\widehat{\mu}(h))=f(\mu (h))$ for $h\in {\cal S}$.

(ii) For every $h\in {\cal S}$, if $f$ is $($resp. weakly$)$ continuous at $\mu (h)$, then $\widehat{f}$ is $($resp. weakly$)$ continuous
at $\widehat{\mu}(h)$.

(iii) If $f$ is weakly continuously differentiable at $\mu (h)$, then $\widehat{f}$ is weakly continuously differentiable at $\widehat{\mu}(h)$ and $D\widehat{f}(\widehat{\mu}(h))$ satisfies $\langle\widehat{\mu}(g),D\widehat{f}(\widehat{\mu}(h))\rangle =\langle\mu (g), Df(\mu (h))\rangle$ for $g\in {\cal S}$. $\sharp$

It follows from Proposition \ref{mil98l1} that, conceptually, there is only one kind of vector measures that needs to be considered in the present context, namely, vector measures that map coalitions into their characteristic functions. One may thus wonder whether vector measures need to be considered at all. An alternative approach might be to express the above conditions for a game to be in $pNA_{\infty}$ or in $pNA$ directly in terms of a particular “extension” of the game into a function on ${\cal S}$.

\begin{equation}{\label{c}}\tag{C}\mbox{}\end{equation}

Differentiable Ideal Games.

An {\bf ideal game} (fuzzy game) is a real-valued function on ${\cal S}$ that vanishes at (the constant function) $0$. We shall say that an ideal game $v^{*}$ is {\bf monotonic} if and only if $h\leq g$ implies $v^{*}(h)\leq v^{*}(g)$. The ideal game $v^{*}$ is said to be differentiable at $h\in {\cal S}$ if and only if there exists a (necessarily unique) non-atomic measure, denoted by $Dv^{*}(h)$ and called the derivative of $v^{*}$ at $h$, such that for every $g\in {\cal S}$
\[v^{*}(h+\theta (g-h))=v^{*}(h)+\theta Dv^{*}(h)(g-h)+o(\theta )\]
as $\theta\rightarrow 0+$. An ideal game is differentiable if and only if it is differentiable at every point in ${\cal S}$. An ideal game $v^{*}$ is a continuous extension of $v$ if and only if $v^{*}(\chi_{S})=v(S)$ for every $S\in {\cal I}$ and $v^{*}$ is continuous with respect to the $NA$-topology. Aumann and Shapley \cite [Proposition 22.16]{aum74b} showed that a continuous extension is always unique, and that a sufficient condition for a game to have such an extension is that there exists a sequence in $pNA$ that converges to that game in the supremum norm $\parallel v\parallel^{\prime}=\sup_{S\in {\cal I}}|v(S)|$. The set of all games that satisfy this condition
is closed under pointwise addition and scalar multiplication, and is denoted by $pNA’$.

\begin{equation}{\label{mil98t2}}\tag{6}\mbox{}\end{equation}

Theorem \ref{mil98t2}. (Milchtaich \cite[p.32]{mil98}). An ideal game $v^{*}$ is the continuous extension of some game $v$ in $pNA_{\infty}$ if and only if there is a non-atomic probability measure $m$ such that, for every $h\in {\cal S}$, the derivative $Dv^{*}(h)$ exists and is absolutely continuous with respect to $m$, $d(Dv^{*}(h))/dm$ is essentially bounded, and $d(Dv^{*}(\cdot))/dm$ is continuous at $h$ as a function into $L_{\infty}(m)$. The value of $v$ is then given by
\begin{equation}{\label{mil98eq5}}\tag{7}
\phi (v)(S)=\int_{0}^{1}Dv^{*}(t)(S)dt
\end{equation}
for $S\in {\cal I}$. $\sharp$

The necessary and sufficient condition for an ideal game $v^{*}$ to be the continuous extension of a game in $pNA_{\infty}$ that is given in Theorem \ref{mil98t2} is apparently stronger than the sufficient condition obtained by Hart and Monderer \cite{har97}. In fact, Hart and Monderer’s condition is equivalent to the requirement that $d(Dv^{*}(\cdot))/dm$ be continuous as a function into $L_{1}(m)$. The above condition is equivalent to the requirement that there is a representation of the game as a vector measure game that satisfies the conditions of Theorem \ref{mil98t1}. Thus, we have the following result.

Proposition. (Milchtaich \cite[p.32]{mil98}). We have the following properties.

(i) A game $v$ can be represented as a vector measure game $f\circ\mu$ with $f$ weakly continuously differentiable on the extended range $\mu ({\cal I})$ of $\mu$ if and only if $v\in pNA_{\infty}$.

(ii) A game $v$ can be represented as a vector measure game $f\circ\mu$ with $f$ weakly continuous on the extended range $\mu ({\cal I})$ of $\mu$ if and only if $v\in pNA’$. $\sharp$

Proposition. (Milchtaich \cite[p.32]{mil98}). Suppose that $v^{*}$ is a monotonic ideal game such that the following
conditions are satisfied:

$\lim_{t\rightarrow 0+}v^{*}(t)=0$ and $\lim_{t\rightarrow 1-}v^{*}(t)=v^{*}(1)$;
there exists a non-atomic probability measure $m$ such that, for every $h\in {\cal S}$ with $0<m(h)<1$ the following conditions are satisfied:

(a) the derivative $Dv^{*}(h)$ exists and is absolutely continuous with respect to $m$;

(b) $d(Dv^{*}(h))/dm$ is essentially bounded;

Then the game $v$ defined by $v(S)=v^{*}(\chi_{S})$ is in $pNA$ and its value is given by $(\ref{mil98eq5})$. $\sharp$

Theorem. (Milchtaich \cite[p.38]{mil98})(Market Games). Suppose that $(I,{\cal I})=([0,1],\mbox{the Borel sets})$. Let $m$ be a non-atomic probability measure (the population measure), a positive integer $k$ (the number of different goods), a $m$-integrable function $($the endowment$)$ from $I$ into the inetrior of the $k$-dimensional nonnegative orthant $\mathbb{R}_{+}^{k}$, and a real-valued function $u$ (the utility function) that is defined on $\mathbb{R}_{+}^{k}\times I$ and satisfies the following assumptions:

for every $\mbox{\boldmath $latex \xi$}\in\mathbb{R}_{+}^{k}$, $u(\mbox{\boldmath $latex \xi$},\cdot)$ is a measurable function on $I$;
for every $i\in I$, $u(\cdot,i)$ is a continuous function on $\mathbb{R}_{+}^{k}$;
for every $i\in I$, $u(\cdot,i)$ is strictly increasing (in each component separately), and $u({\bf 0},i)=0$;
for every $i\in I$ and $j$, $\partial u(\mbox{\boldmath $latex \xi$},i)/\partial\xi_{j}$ exists and is continuous at each $\mbox{\boldmath $latex \xi$}\in\mathbb{R}_{+}^{k}$ for which $\xi_{j}>0$; and $u(\mbox{\boldmath $latex \xi$},i)=o(\sum_{j}\xi_{j})$ as $\sum_{j}\xi_{j}\rightarrow\infty$, integrably in $i$, that is, for every $\epsilon >0$ there is an $m$-integrable function $\gamma :I\rightarrow\mathbb{R}$ such that, for every $\mbox{\boldmath $latex \xi$}\in\mathbb{R}_{+}^{k}$ nd $i\in I$, $\sum_{j}\xi_{j}\geq\gamma (i)$ implies $u(\mbox{\boldmath $latex \xi$},i)\leq\epsilon\cdot\sum_{j}\xi_{j}$.

Then, for every coalition $S$, the maximum in $(\ref{mil98eq1})$ is attained, and the market game $v$ defined by this equation is in $pNA$. The value of this game coincides with the unique competitive payoff distribution of the (transferable utility) market. $\sharp$