DOCUMENTS DE TREBALL 
DE LA DIVISIÓ DE CIÈNCIES JURÍDIQUES 
ECONÒMIQUES I SOCIALS 
 
Col·lecció d’Economia 
 
 
A Note on Shapley’s Convex Measure Games 
 
 
F. Javier Martínez-de-Albéniz 
Carles Rafels* 
 
 
 
 
 
 
 
 
Adreça correspondència: 
Dep. Matemàtica Econòmica, Financera i Actuarial and CREB 
Facultat de Ciències Econòmiques i Empresarials 
Universitat de Barcelona 
Av. Diagonal 690, 08034 Barcelona, Spain 
e-mail:  albeniz@eco.ub.es /  rafels@eco.ub.es 
 
 
 
Novembre 2002  
                                                           
* Institutional support from research grants SGR2001-0029 and PB98-0867 and from University of Barcelona 
(Div. II) are gratefully acknowledged. 
A Note on Shapley’s Convex Measure Games
Abstract
L. S. Shapley, in his paper ‘Cores of Convex Games’, introduces
Convex Measure Games, those that are induced by a convex function
on R, acting over a measure on the coalitions. But in a note he states
that if this function is a function of several variables, then convexity
for the function does not imply convexity of the game or even super-
additivity. We prove that if the function is directionally convex, the
game is convex, and conversely, any convex game can be induced by a
directionally convex function acting over measures on the coalitions,
with as many measures as players.
Keywords: Convex cooperative games, directional convexity, super-
modularity, multilinear extension.
JEL Classification: C71
Resumen
L. S. Shapley introduce el concepto de Convex Measure Games en
su art´ ‘Cores of Convex Games’. Se trata de los juegos inducidos
por una funci´ convexa definida sobre R, y que act´ sobre una medi-
da en las coaliciones. Sin embargo, en una nota a pie de p´ a se˜ a
que si esta funci´ es una funci´ de varias variables entonces la con-
vexidad de la funci´ no implica la convexidad del juego ni siquiera
la superaditividad. Aqu´ se prueba que si la funci´ es direccional-
mente convexa, el juego es convexo, y que tambi´n cualquier juego
convexo puede ser inducido por una funci´ direccionalmente convexa
que act´ sobre medidas sobre las coaliciones, con, como m´ mo,
tantas medidas como jugadores.
1 Introduction
Shapley (1971) introduced the notion of convex game in his seminal paper.
This kind of games present several appealing regularity properties. They
are based in [what Shapley calls] convex set functions, or in other contexts,
such as Combinatorial Optimization or Integer Programming, supermodular
functions, what intuitively means that the incentives for joining a coalition
increase as the coalition grows. That is, a game that presents increasing
returns along with the coalition’s size or increasing differences in the evalua-
tion of the characteristic function. In his paper, Shapley introduces Convex
Measure Games, as those that are induced by a convex function on R, which
acts over a measure on the coalitions. In an economic situation, this measure
could be the initial distribution of a resource, for any player, and any coali-
tion gets the sum of the resources of its members. This function could, then,
be interpreted as a production function. He shows that not all convex games
are convex measure games, nor are equivalent to such games. The question
we want to solve is the note Shapley states in his paper, that if this function
is a function of several variables, then convexity for the function does not
imply convexity of the game or even superadditivity. The appropiate tool
will be directionally convex functions, and the main result of this paper is
to prove that any convex cooperative game can be represented as a measure
game, by using as many measures (resources) as the number of players and
combining them by a directionally convex production function.
2 Preliminaries and Notation
A T.U.-Cooperative Game in coalitional form is a pair (N,v), where N =
{1,2,...,n} is the set of players (we are assuming it is finite) and v : 2N -arrowrightR
is a function defined over the subsets of N (coalitions), 2N, such that v(emptyset) = 0.
We use the notation eS element RN to indicate the incidence vector ( 01-
vector) to the coalition S reflexsubset N, i.e., (eS)i = 1 if i element S, and 0 otherwise. If
S = {i}, we will denote by ei the corresponding e{i}.
Convex games were introduced by L. S. Shapley (1971). This class of
games is very interesting because of their properties with regard to stable
sets, solution concepts, core properties and inheriting properties.
A game (N,v) is convex if v(S) + v(T) <=< v(S union T) + v(S intersection T), for all
S,T element 2N. This is equivalent to the “snowballing” or “bandwagon” effect:
v(S union{i})-v(S) <=< v(T union{i})-v(T), for all i element N and all S propersubset T reflexsubset N\{i}.
On the other side, a lattice X is a set with a partial order relation (a
poset) such that every two elements, x and xprime have a least upper bound
1
(their join, x logicalor xprime) and a greatest lower bound (their meet, x logicaland xprime).
The real function f(x) defined on a lattice (X,logicalor,logicaland) is supermodular (see
Topkis, 1998) if
f(xprime) + f(xprimeprime) <=< f(xprime logicalor xprimeprime) + f(xprime logicaland xprimeprime) for all xprime,xprimeprime element X.
Notice that supermodularity is, for cooperative games, just the definition
of convex game, assuming the lattice of coalitions parenleftbig2Nparenrightbig , where the maximum
of two coalitions S and T is its union (SunionT), and minimum is its intersection
(S intersection T).
Convex measure games were introduced by Shapley (1971) in the following
way:
Consider the game (N,v) defined by
v (S) = f (µ(S)) , for all S reflexsubset N,
where µ is a measure over the coalitions, and f a real function such that
f(0) = 0. Recall that a measure µ is an additive (with respect to the union of
disjoint sets) positive real-valued function, such that µ(emptyset) = 0. This measure
µ may be interpreted as the initial distribution of one resource among the
players, and f as a production function that gives the net worth that can be
achieved with the resources.
For the case of one-variable production function, Shapley notes that con-
vexity on f implies the convexity of the game v, but not all convex games
can be described in this way with convenient function f and measure µ.
Moreover, Shapley points out in a note:
“Curiously, if f is a function of several variables and µ is a
vector of measures, then convexity of f does not imply convexity
of v, or even superadditivity.”
At this point, we can add that supermodularity of function f does not
imply convexity of the game v. This is easy to see for a one-variable pro-
duction function, since it is well known that any function of one variable is
supermodular. For more than one variable we have the following example:
Example 1 Consider the supermodular function f(x,y) = -x2 - y2, and
consider two players: 1 with endowment (2,1), and 2 with endowment (1,2).
Then the game associated to this function is: v(emptyset) = 0, v({1}) = -5,
v({2}) = -5, v({1,2}) = -18, and it is not a convex game.
Therefore it remains open which should be the right concept on the pro-
duction function that gives convexity on the class of cooperative measure
games. By the previous comments, it has to be a generalization of convexity
for one-variable functions, and we will introduce it in the next section.
2
3 Directional convexity
Let <=< denote the usual order in Rm, which makes componentwise compar-
isons: for x,y element Rm, x <=< y if xi <=< yi for i = 1,2,...,m. With this order
Rm forms a lattice (which is the product of m chains), and in this lattice we
have:
x logicaland y := (min {x1,y1},min {x2,y2},...,min {xm,ym}) ,
and
x logicalor y := (max {x1,y1},max {x2,y2},...,max {xm,ym}) .
Definition 2 A function f : S reflexsubset Rm -arrowright R is directionally convex if for
any x,y,z,t element S such that x+ y = z+ t,with z <=< x <=< t, and z <=< y <=< t, it
happens that
f (x) + f (y) <=< f (z) + f (t) .
Notice that in this definition x and y can be equal, and it is not necessary
that the sum x + y belongs to S.
The concept of directionally convex function is introduced and used in
Shaked and Shanthikumar (1990), Meester and Shanthikumar (1993, 1999),
and recently by M¨ and Scarsini (2001) or M¨ r (2001). It has arised in
the field of multivariate stochastic orders. Moreover, for twice differentiable
functions, as Shaked and Shanthikumar (1990) prove, directional convexity
is equivalent to the nonnegativity of all second partial derivatives:
partialdiff2f
partialdiffxipartialdiffxj (x) greaterequal 0, for all i,j element {1,2,... ,m} .
Therefore, for m > 1, directional convexity over Rm neither implies, nor
is implied by classical convexity.
For m = 1, it is obvious that directional convexity is equivalent to increas-
ing first differences, what is called Wright-convexity (Roberts and Varberg,
1973), but this is not equivalent to convexity as is incorrectly assumed, for
example, in Shaked and Shanthikumar (1990). The well-known construction
of an additive function on the real line that is nowhere continuous (Hardy,
Littlewood and P´ a, 1952) is an example, because convex functions are
continuous in the relative interior of its domain. Then, it is easy to prove
that convexity on f implies directional convexity of f. Adding continuity, the
converse will also be true.
Now it is time to see that directional convexity is the concept we need to
check convexity in the associated cooperative game:
3
Theorem 3 Let f : Rm+ -arrowrightR be a directionally convex function, such that
f(0) = 0, and µ1,µ2,... ,µm be measures over 2N. Then, the game (N,v)
defined as
v (S) = f (µ1 (S) ,µ2 (S) ,... ,µm (S)) , for all S reflexsubset N,
is a convex game.
Proof. For any measure µ, µ(emptyset) = 0, and µ(S) + µ(T) = µ(S intersection T) +
µ(S union T) , for all S,T reflexsubset N; moreover µ(S intersection T) <=< µ(S) ,µ(T) <=< µ(S union T) .
Then convexity of v is obvious.
4 Directionally convex measure games
In this section we will analyze the converse part of the above results. In
fact we will show that any convex cooperative game can be expressed as
a measure game for a suitable directionally convex function. Moreover, in
our representation, we will need only as many measures as players. To this
end, we consider any game (N,v) as a function defined on the unit cube: v
: {0,1}N -arrowright R, with v (0) = 0, identifying each coalition S reflexsubset N with its
incidence vector eS element RN. We will need to extend this initial discrete function
over the extreme points of the unit cube to the whole space Rn+ in such a
way that if the original function is supermodular, then the extended function
should be directionally convex.
Recall that for a given cooperative game v : {0,1}N -arrowrightR, with v (0) = 0,
it can be expressed in terms of the unanimity basis, where the coefficients
are the unanimity cooordinates:
v =
summationdisplay
Selement2N\emptyset
lambdaS uS.
The basis is formed by the unanimity games i.e. uT (S) =
braceleftbigg 1 T reflexsubset S
0 otherwise ,
with T reflexsubset N,T negationslash= emptyset, and the coordinates or Harsanyi dividends are:
lambdaS =
summationdisplay
TreflexsubsetS
(-1)|S|-|T| v(T).
Moreover, Owen’s multilinear extension (MLE)(Owen, 1995), extended to
the nonnegative orthant,
fo : RN+ -arrowrightR,
4
is defined, for all x element RN+ by:
fvo (x) = fvo (x1,x2,... ,xn) =
summationdisplay
SreflexsubsetN
braceleftBiggproductdisplay
ielementS
xi
productdisplay
i/S
(1 -xi)
bracerightBigg
v(S) =
=
summationdisplay
SreflexsubsetN
braceleftBiggproductdisplay
ielementS
xi
bracerightBigg
lambdaS. (1)
In Rafels and Ybern (1995) it is proved that fvo is supermodular on
the unit cube, the lattice
parenleftBig
[0,1]N ,<=<
parenrightBig
, if and only if the game v is con-
vex (v supermodular). But Owen’s Multilinear Extension does not pre-
serve supermodularity, if we consider this extension in RN+ instead of the
unit cube. As an example, consider the following 3-player convex cooper-
ative game defined by v(S) = 0 for |S| = 1, v(S) = 2 for |S| = 2, and
v(N) = 4. Its MLE is fo(x1,x2,x3) = 2x1x2 + 2x1x3 + 2x2x3 -2x1x2x3, and
partialdiff2fo
partialdiffx1partialdiffx2 (x1,x2,x3) = 2 -2x3, which is not positive for x element R
3
+, if x3 greaterequal 1.
As a consequence, the above example shows that Owen’s multilinear ex-
tension, considered in RN+, it is not directionally convex on the class of convex
cooperative games, and it cannot be used for our central result. As the reader
may suspect, the problem in the above example arises from the negativity of
a unanimity coordinate in the original convex game, lambdavN = -2.
For a convex game where all of its unanimity coordinates are nonnegative,
expression (1) will give us a positive answer. And in fact, Owen’s MLE can
be considered a “good” directionally convex extension of the original game
only for this class of games, as the next theorem shows:
Theorem 4 Let (N,v) be a cooperative game. Owen’s multilinear extension
(MLE),
fvo : RN+ -arrowrightR,
defined, for all x element RN+ by:
fvo (x) = fo(x1,x2,... ,xn) =
summationdisplay
SreflexsubsetN
braceleftBiggproductdisplay
ielementS
xi
productdisplay
i/S
(1 -xi)
bracerightBigg
v(S),
is a directionally convex extension of v, if and only if all unanimity coordi-
nates of coalitions of size greater or equal than 2 are nonnegative, i.e. lambdaS greaterequal 0
for all |S| greaterequal 2.
5
Proof. If all unanimity coordinates of coalitions of size greater or equal
than 2 are nonnegative, i.e. lambdaS greaterequal 0 for all |S| greaterequal 2 in the game (N,v) , by
using expression (1) we obtain:
partialdiff2fvo
partialdiffxipartialdiffxj (x) =
bracelefttp
braceleftmid
braceleftbt
0 if i = j,
summationtext
SreflexsubsetN\{i,j}
braceleftbiggproducttext
kelementS
xk
bracerightbigg
lambdaSunion{i,j} if i negationslash= j,
where a product over the empty set of indices is taken to be equal to 1.
Then we have obtained partialdiff2fvopartialdiffxipartialdiffxj (x) greaterequal 0 for all x element RN+ and all i,j element
{1,2,... ,m} , what is equivalent to directional convexity for twice differen-
tiable functions.
To see the ’only if’ part, suppose that there is some coalition(s) of size
greater or equal than 2 with negative coordinate, and pick a minimal size
coalition Sprime reflexsubset N with |Sprime| greaterequal 2 and lambdaSprime < 0. Consider two different players
in Sprime : i,j element Sprime, i negationslash= j, and take a vector ˆ element RN+ defined by ˆk = t if k element Sprime
and ˆk = 0 if k / Sprime. It is easy to check that
partialdiff2fvo
partialdiffxipartialdiffxj (ˆx) =
summationdisplay
SreflexsubsetSprime\{i,j}
t|S| lambdaSunion{i,j},
which is a polynomial in t, with a negative coefficient of maximum degree
(which is lambdaSprime < 0) and all other coefficients nonnegative, because if S notsubsetoreql
Sprime\ {i,j} , then lambdaSunion{i,j} greaterequal 0. It is enough to take t as large as necessary to
get a negative valuation for partialdiff2fvopartialdiffxipartialdiffxj (ˆ).
The above proof shows that supermodularity of Owen’s multilinear ex-
tension in the whole space RN+ is a characterization of nonnegativeness of all
unanimity coordinates associated to coalitions of size greater or equal than
2 of the game.
Theorem 4 solves the converse problem that we want to analyze for this
specific subclass of convex games.
Theorem 5 Any convex cooperative game (N,v) with lambdaS greaterequal 0 for all |S| greaterequal 2
is a directionally convex measure game.
Proof. Consider v : {0,1}N -arrowright R, with v (0) = 0, and, for i =
1,2,... ,n, define µi (S) = 1 if i element S, and 0 otherwise. Then for any S reflexsubset N,
(µ1(S),µ2(S),... ,µn(S)) = eS element RN+.
If we take Owen’s MLE: fvo : RN+ -arrowright R, we obtain that v parenleftbigeSparenrightbig =
fvo (µ1(S),µ2(S),... ,µn(S)) , and by theorem 4, fvo is a directionally con-
vex function. Therefore, v is a directionally convex measure game.
6
As we know, a cooperative game can be convex without having all of its
unanimity coordinates of size greater than two nonnegative, and therefore, a
representation theorem remains open for the whole class of convex games. As
the reader may suspect, we will need other kind of extension for cooperative
games, and we will proceed in two steps. First we will analyze an extension
procedure from {0,1}N to NN, and, second, from NN to RN+. The result of
the combination of both will be a general extension from {0,1}N to RN+ in
such a way that, if the original cooperative game is convex (supermodular
function), its extension to RN+ will be a directionally convex function.
In order to reach these results, we will need to use some characterizations
of nondifferentiable directionally convex functions defined in spaces NN and
RN+, that are developed in the appendix of this paper.
Lemma 6 Let v : {0,1}N -arrowright R be a real-valued function defined on the
vertices of the unit cube, with v (0) = 0, such that v is supermodular in the
lattice
parenleftBig
{0,1}N ,<=<
parenrightBig
. Then, there is a directionally convex function
fv : NN -arrowrightR,
with fv (0) = 0, which is an extension of v.
Proof. For each n element NN, we will denote S (n) = {i element N ; ni > 0} .
Define, for any n element NN,
fv (n) =
parenlefttp
parenleftbt productdisplay
jelementS(n)
nj
parenrighttp
parenrightbt
bracketlefttp
bracketleftbtv parenleftbigeS(n)parenrightbig - summationdisplay
jelementS(n)
v parenleftbigejparenrightbig
bracketrighttp
bracketrightbt + summationdisplay
jelementS(n)
njv parenleftbigejparenrightbig ,
where the product over the empty set equals 1, and summation over the
empty set equals 0.
This is an extension of the original function, because any vector eS is a
01 vector, and fv parenleftbigeSparenrightbig = v parenleftbigeSparenrightbig .
This function is directionally convex. To see it, we first calculate deltaifv(n) =
fv(n + ei) -fv(n), and two cases must be distinguished:
If ni = 0, then S (n + ei) = S (n) union {i} , and
deltaifv(n) =
parenlefttp
parenleftbt productdisplay
jelementS(n)
nj
parenrighttp
parenrightbt
bracketleftBig
v
parenleftBig
eS(n+ei)
parenrightBig
-v parenleftbigeS(n)parenrightbig -v parenleftbigeiparenrightbig
bracketrightBig
+ v parenleftbigeiparenrightbig .
7
If ni > 0, then S (n + ei) = S (n) , and
deltaifv(n) =
parenlefttp
parenleftexparenleftex
parenleftbt
productdisplay
jelementS(n)
jnegationslash=i
nj
parenrighttp
parenrightexparenrightex
parenrightbt
bracketlefttp
bracketleftbtv parenleftbigeS(n)parenrightbig - summationdisplay
jelementS(n)
v parenleftbigejparenrightbig
bracketrighttp
bracketrightbt + v parenleftbigeiparenrightbig .
Now, to prove that fv is directionally convex, for all n,nprime element NN with
n <=< nprime, and all i element N, we will check that deltaifv(n) <=< deltaifv(nprime). For these
vectors, nk <=< nprimek, for all k element N, and S (n) reflexsubset S (nprime) . We must distinguish also
several cases:
If ni > 0, then nprimei > 0, and being v supermodular, v parenleftbigeS(n)parenrightbig+summationtextjelementS(nprime)primereverseS(n) v (ej) <=<
v parenleftbigeS(nprime)parenrightbig . Then:
deltaifv(n) =
parenlefttp
parenleftexparenleftex
parenleftbt
productdisplay
jelementS(n)
jnegationslash=i
nj
parenrighttp
parenrightexparenrightex
parenrightbt
bracketlefttp
bracketleftbtv parenleftbigeS(n)parenrightbig - summationdisplay
jelementS(n)
v parenleftbigejparenrightbig
bracketrighttp
bracketrightbt + v parenleftbigeiparenrightbig
<=<
parenlefttp
parenleftexparenleftex
parenleftbt
productdisplay
jelementS(nprime)
jnegationslash=i
nprimej
parenrighttp
parenrightexparenrightex
parenrightbt
bracketlefttp
bracketleftbtv parenleftbigeS(n)parenrightbig - summationdisplay
jelementS(n)
v parenleftbigejparenrightbig
bracketrighttp
bracketrightbt + v parenleftbigeiparenrightbig
<=<
parenlefttp
parenleftexparenleftex
parenleftbt
productdisplay
jelementS(nprime)
jnegationslash=i
nprimej
parenrighttp
parenrightexparenrightex
parenrightbt
bracketlefttp
bracketleftbtv
parenleftBig
eS(nprime)
parenrightBig
-
summationdisplay
jelementS(nprime)
v parenleftbigejparenrightbig
bracketrighttp
bracketrightbt + v parenleftbigeiparenrightbig
= deltaifv(nprime).
If ni = 0, and nprimei = 0 then S (n + ei) = S (n)union{i} , and S (nprime + ei) = S (nprime)union
{i} . By the supermodularity of v,
v
parenleftBig
eS(n+ei)
parenrightBig
-v parenleftbigeS(n)parenrightbig <=< v
parenleftBig
eS(nprime+ei)
parenrightBig
-v
parenleftBig
eS(nprime)
parenrightBig
,
8
and we get:
deltaifv(n) =
parenlefttp
parenleftbt productdisplay
jelementS(n)
nj
parenrighttp
parenrightbtbracketleftBigv parenleftBigeS(n+ei)parenrightBig -v parenleftbigeS(n)parenrightbig -v parenleftbigeiparenrightbigbracketrightBig + v parenleftbigeiparenrightbig
<=<
parenlefttp
parenleftbt productdisplay
jelementS(nprime)
nprimej
parenrighttp
parenrightbtbracketleftBigv parenleftBigeS(n+ei)parenrightBig -v parenleftbigeS(n)parenrightbig -v parenleftbigeiparenrightbigbracketrightBig + v parenleftbigeiparenrightbig
<=<
parenlefttp
parenleftbt productdisplay
jelementS(nprime)
nprimej
parenrighttp
parenrightbtbracketleftBigv parenleftBigeS(nprime+ei)parenrightBig -v parenleftBigeS(nprime)parenrightBig -v parenleftbigeiparenrightbigbracketrightBig + v parenleftbigeiparenrightbig
= deltaifv(nprime).
If ni = 0, and nprimei > 0 then S (n + ei) = S (n) union {i} , and i element S (nprime + ei) =
S (nprime) . The following inequalities hold:
v
parenleftBig
eS(n+ei)
parenrightBig
+
summationdisplay
jelementS(nprime)primereverseS(n+ei)
v parenleftbigejparenrightbig <=< v
parenleftBig
eS(nprime)
parenrightBig
and
summationdisplay
jelementS(n)
v parenleftbigejparenrightbig <=< v parenleftbigeS(n)parenrightbig ,
which lead to:
deltaifv(n) =
parenlefttp
parenleftbt productdisplay
jelementS(n)
nj
parenrighttp
parenrightbt
bracketleftBig
v
parenleftBig
eS(n+ei)
parenrightBig
-v parenleftbigeS(n)parenrightbig -v parenleftbigeiparenrightbig
bracketrightBig
+ v parenleftbigeiparenrightbig
<=<
parenlefttp
parenleftexparenleftex
parenleftbt
productdisplay
jelementS(nprime)
jnegationslash=i
nprimej
parenrighttp
parenrightexparenrightex
parenrightbt
bracketleftBig
v
parenleftBig
eS(n+ei)
parenrightBig
-v parenleftbigeS(n)parenrightbig -v parenleftbigeiparenrightbig
bracketrightBig
+ v parenleftbigeiparenrightbig
<=<
parenlefttp
parenleftexparenleftex
parenleftbt
productdisplay
jelementS(nprime)
jnegationslash=i
nprimej
parenrighttp
parenrightexparenrightex
parenrightbt
bracketlefttp
bracketleftbtv parenleftBigeS(nprime)parenrightBig - summationdisplay
jelementS(nprime)
v parenleftbigejparenrightbig
bracketrighttp
bracketrightbt + v parenleftbigeiparenrightbig
= deltaifv(nprime).
And from the characterization of directionally convex functions (see
appendix), the statement is proved.
9
Now we will proceed to extend a directionally convex function on NN to
RN+. The procedure will be done by extending the discrete function by cells
or “blocks”, and for this reason several notions will be introduced.
Consider, for z0 <=< z1, z0,z1 element NN the following set, which is called a
discrete rectangle:
R bracketleftbigz0,z1bracketrightbig = braceleftbigz element NN | z0 <=< z <=< z1bracerightbig.
When bardblz1 -z0bardblinfinity = supielementN{|z1i -z0i |} <=< 1, the convex hull of R [z0,z1]
is called a cell D in RN+, and its infimum is z0. Notice that, for any cell D,
all the points in D intersection NN are the extreme points of D. They will be denoted
by extD.
Any point x in RN+ is contained in some cell, but it can be in the inter-
section of two or more cells. The intersection of two cells is either empty or
another cell.
For each x element RN+, we define the discrete neighbourhood (Miller, 1971) of
x :
N (x) = braceleftbigz element NN | bardblz -xbardblinfinity < 1bracerightbig.
Note that if x itself is in NN, then N (x) = {x} . The set N (x) has 2m
elements, where m is the number of coordinates of x that are not integers.
The convex hull of N (x) is a cell, precisely, the intersection of all cells that
contain x. Moreover, its minimal element x0 element N (x) is
x0 = floorleftxfloorright = (floorleftx1floorright,floorleftx2floorright,... ,floorleftxnfloorright) ,
where floorlefttfloorright is the integer part of t (the largest integer smaller than or equal to
t).
To extend a directionally convex function we will use the concept of
weighted function, defined by Miller (1971) in the following way: a func-
tion f : D -arrowright R (where D reflexsubset RN) is weighted if D is the convex hull of
a discrete rectangle S, and for x element D, f (x) = summationtextzelementN(x) wz (x) f (z) where
wz (x) are called the weights and satisfy the conditions summationtextzelementN(x) wz (x) = 1
and wz (x) greaterequal 0.
Now we can obtain the extension lemma:
Lemma 7 (Extension of a directionally convex function on NN to RN+)
Let f : NN -arrowrightR, with f (0) = 0, be a directionally convex function on NN.
There is a continuous directionally convex function ˜ : RN+ -arrowright R, which is
an extension of f.
10
Proof. Let f : NN -arrowright R, with f (0) = 0, be a function on NN. We are
going to define a function ˜ : RN+ -arrowrightR, which is an extension of f.
Define the following weighted function, for any x element RN+,
˜f(x) = summationdisplay
zelementN(x)
wz (x) f (z) ,
where wz (x) = producttext
ielementR(z)
¯i producttext
i/R(z)
(1 - ¯i) with ¯i = xi - x0i for all i element N ,
and R(z) = {i element N | zi -x0i = 1} , and x0 is the minimal element of the cell
N (x) .
The function ˜ is well defined, and these coefficients wz (x) , z element N (x)
are nonnegative, and add up to 1. Moreover, function ˜ coincides with f on
NN, since N (x) = {x} if x element NN.
Notice that the value on an arbitrary point x element RN+ is obtained as the
corresponding multilinear (linear in each variable) interpolation on N (x) , in
the spirit of Owen’s multilinear extension. We claim that the function ˜ has
the following properties:
1. ˜should be defined independently of the cell we want to use for a given
vector x element RN+. Formally, if C is an arbitrary cell, and x element C, then
˜f(x) = summationdisplay
zelementextC
wz (x) f (z) ,
where wz (x) = producttext
ielementR(z)
¯i producttext
i/R(z)
(1 - ¯i) with ¯i = xi - z0i for all i element N ,
and R(z) = {i element N | zi -z0i = 1} , and z0 is the minimal element of
the cell C.
Observe that if z element extC but z / N (x) , the coefficient of f (z) is zero,
because in this case there is some index k element N such that |zk -xk| = 1.
Then, z0k = xk if zk = z0k + 1, or z0k = xk -1 if zk = z0k. In the first case
¯k = xk-z0k = 0, and k element R(z), and in the second case ¯k = xk-z0k = 1,
and k / R(z). In each case, the coefficient of f (z) is zero.
2. ˜ is continuous in RN+. Indeed, the function ˜ is continuous in each cell
C of RN+, and each neighborhood of a vector x element RN+ can be partitioned
in a finite number of neighborhoods, one in each cell x belongs to.
3. ˜is linear in each coordinate inside a cell C. Formally: if C is a cell, and
x1,x2 element C with x1i = x2i for all i element N, i negationslash= k, then ˜(alphax1+(1 -alpha) x2) =
alpha ˜(x1) + (1 -alpha) ˜(x2) for any alpha element [0,1] .
11
4. If C is a cell, i element N and x, x + epsilonei element C, then deltaepsiloni ˜(x) = ˜(x+epsilonei) -
˜f(x) = epsilondelta1i ˜f(x{i}), where xS is defined as xSj = xj if j /element S, and
xSj = floorleftxjfloorright if j element S. It is a direct consequence of 3.
5. If C is a cell, i,j element N and x, x + epsilonei + epsilonprimeej element C, then deltaepsilonprimej deltaepsiloni ˜(x) =
epsilonprimeepsilondelta1jdelta1i ˜(x{i,j}). It is obtained by applying 4. twice.
6. For any x element RN+, epsilon,delta element R with 0 <=< delta <=< epsilon and i element N, deltaepsiloni ˜(x) =
deltaepsilon-deltai ˜(x+deltaei)+deltadeltai ˜(x). It follows directly from the definition of deltaepsiloni ˜(x).
7. For any x element RN+ and i element N, delta1i ˜(x) = summationtext
zelementN(x)
wz (x) delta1i f (z) . It is a
consequence of the following identities: N (x + ei) = N (x) + {ei} and
wz+ei (x + ei) = wz (x) .
8. For any x element RN+, k element N and i element N, deltaki ˜(x) = summationtext
zelementN(x)
wz (x) deltaki f (z) . It
can be obtained by iterative application of 7.
9. For any x element RN+ and i,j element N, delta1jdelta1i ˜(x) = summationtext
zelementN(x)
wz (x) delta1jdelta1i f (z) .
Similar to 7.
10. For any x element RN+, k,kprime element N and i,j element N, deltakprimej deltaki ˜(x) = summationtext
zelementN(x)
wz (x) deltakprimej deltaki f (z) .
Similar to 8.
We must show now that ˜ is directionally convex.
For any x element RN+, i,j element N, and k,kprime element N, by property 10, and directional
convexity of f (see appendix), deltakprimej deltaki ˜(x) greaterequal 0.
For any x element RN+, i,j element N, and alpha,beta element R, alpha,beta > 0, define the integer part
of alpha and beta : a = floorleftalphafloorright and b = floorleftbetafloorright, and the rest alphaprime = alpha -a, betaprime = beta -b, with
0 <=< alphaprime,betaprime < 1. Since alpha = a + alphaprime and beta = b + betaprime, and applying 6 iteratively,
we have:
deltabetaj deltaalphai ˜(x) = deltabjdeltaai ˜(x) +
deltabjdeltaalphaprimei ˜(x + aei) +
deltabetaprimej deltaai ˜(x + bej) +
deltabetaprimej deltaalphaprimei ˜(x + aei + bej).
The first sumand is positive, as we have just seen. For the second, if
x + aei and x + aei + alphaprimeei do not belong to the same cell, there is a number
deltaprime element R with 0 <=< deltaprime <=< alphaprime such that x+aei and x+aei+deltaprimeei belong to the same
12
cell, and so do x+aei +deltaprimeei and x+aei +alphaprimeei . Then if we apply properties
6, 4, 9 and 10, and directional convexity of f, this sumand is positive.
For the third and the latter just repeat the previous procedure.
We have proved that for any x element RN+, i,j element N, and alpha,beta element R, alpha,beta > 0,
deltabetaj deltaalphai ˜(x) greaterequal 0, and by the characterization of directionally convex functions,
given in the appendix, ˜ is directionally convex.
If we apply the preceding lemmas, we can state the main result of this
paper:
Theorem 8 Let (N,v) be a convex game. Then, there is a directionally
convex function f : Rn+ -arrowright R, such that f(0) = 0, and measures over
2N : µ1,µ2,...,µn such that:
v (S) = f (µ1 (S) ,µ2 (S) ,... ,µn (S)) , for all S reflexsubset N.
Proof. Define, for i = 1,2,... ,n, µi (S) = 1 if i element S, and 0 otherwise
(each player has the control of one resource). Then (µ1 (S) ,µ2 (S) ,... ,µn (S)) =
eS element RN+.
Define f(eS) = v(S). This gives a function defined on the vertices of
the unit cube. If v is a convex game, this is equivalent to function f being
supermodular in the vertices of the unit cube. Apply now lemma 6 and
lemma 7, and the result is proved.
As an illustration, look at an economic example quoted by Rosenm¨
(1981), and assume there are two factors, labor and land. There are n players
and each player i element N owns li units of labor force and ci units of land. There
is a function g : R+ -arrowrightR+,g(0) = 0 that gives the amount of crops per unit
of land that can be harvested.
The production function is, then
v(S) = c(S) · g(l(S))
assuming that c(S) = summationtextielementS ci, and l(S) = summationtextielementS li. If we define the production
function f : R2+ -arrowrightR+ by f(s,t) = sg(t), the game is convex if the function
g is convex. Notice that in this case f is directionally convex.
References
[1] Hardy, GH, Littlewood, JE, P´lya G (1952) Inequalities (2nd ed), Cam-
bridge University Press, London New York.
13
[2] Marshall, AE, Olkin, I (1979) Inequalities: Theory of majorization and
its applications, Academic Press, San Diego, CA.
[3] Meester, LE, Shanthikumar, JG (1993) Regularity of stochastic pro-
cesses. Probability in the Engineering and Informational Sciences, 7:
343–360.
[4] Meester, LE, Shanthikumar, JG (1999) Stochastic convexity on general
spaces. Mathematics of Operations Research, 24(2): 472–494.
[5] Miller, BL (1971) On minimizing nonseparable functions defined on the
integers with an inventory application. SIAM Journal on Applied Math-
ematics, 21(1):166–185.
[6] M¨ r, A (2001) Stochastic orders generated by generalized convex func-
tions. In: Hadjisavas,N, Martinez Legaz, JE, Penot, J-P (eds) Gen-
eralized Convexity and Generalized Monotonicity, Proceedings of the
6th International Symposium on Generalized Convexity/Monotonicity
(Samos, September 1999), Springer Verlag, Berlin Heidelberg, pp 264–
278.
[7] M¨ r, A, Scarsini, M (2001) Stochastic comparison of random vectors
with a common copula. Mathematics of Operations Research, 26(4):723–
740.
[8] Owen, G (1995) Game Theory (Third Edition), Academic Press, San
Diego, CA.
[9] Rafels, C, Ybern, N (1995) Even and odd marginal worth vectors,
Owen’s multilinear extension and convex games. International Journal
of Game Theory 24:113–126.
[10] Roberts, AW, Varberg, DE (1973) Convex functions, Academic Press,
New York.
[11] Rosenm¨ J (1981) The theory of games and markets, North Holland,
Amsterdam.
[12] Shaked, M, Shanthikumar, JG (1990) Parametric stochastic convexity
and concavity of stochastic processes. Annals of the Institute of Statis-
tical Mathematics 42:509–531.
[13] Shapley, LS (1971) Cores of Convex Games. International Journal of
Game Theory 1:11–26.
14
[14] Topkis, DM (1998) Supermodularity and Complementarity, Princeton
University Press, Princeton, NJ.
5 Appendix
For one-variable functions the usual definition of convex function defined over
a convex subset (an extended interval) S propersubset R is the following one: a function
f : S propersubset R -arrowrightR is convex if for any x,y element S and any lambda element [0,1],
f(lambdax + (1 -lambda)y) <=< lambdaf(x) + (1 -lambda)f(y).
If S is not an extended interval, but another subset of R, one should require
this condition for lambda element [0,1], and such that lambdax + (1 -lambda)y element S. For a function
defined on an extended interval of the integer set, that is, S = (a,b) intersection Z, f
is convex if and only if f has nonnegative second differences (Marshall and
Olkin, 1979), i.e.,
f(x + 2) -2f(x + 1) + f(x) greaterequal 0,
for all x element Z such that a < x,x + 2 < b.
To give a characterization of directionally convex functions, let us define
the difference operator:
Definition 9 For a function f : S reflexsubset Rm -arrowrightR define the difference opera-
tor deltaepsilonif(x) := f(x+epsilonei) -f(x), for all i element {1,2,... ,m} and all x element S such
that x+epsilonei element S, where ei is the i-th unit vector and epsilon element R+.
We will use deltaif(x) instead of delta1i f(x), if no confusion arises.
Theorem 10 Let f : Nm -arrowrightR be a real-valued function. Then the following
statements are equivalent:
(i) f is directionally convex.
(ii) For all x1,x2 element Nm with x1 <=< x2 and all y elementNm,
f (x1+y) -f (x1) <=< f (x2+y) -f (x2) .
(iii) For all x1,x2 element Nm with x1 <=< x2, and for all i element {1,2,... ,m} ,
deltaif(x1) <=< deltaif(x2).
15
(iv) For all x element Nm, and for all i,j element {1,2,...m} ,
deltajdeltaif(x) greaterequal 0.
(v) For all x element Nm, for all k,kprime element N, and for all i,j element {1,2,...m} ,
deltakprimej deltaki f(x) greaterequal 0.
(vi) f is supermodular and convex in each coordinate over N, all other co-
ordinates held fixed.
Proof. See Shaked and Shanthikumar (1990), Proposition 2.1. Equiva-
lence of (i) and (ii) is immediate, and also equivalence of (ii), (iii), (iv) and
(v) by repeated iteration. But (ii) implies supermodularity, because for any
z and t, consider z logicalor t and z logicaland t, and then take x1 = z logicaland t, x2 = t and
y = z-(z logicaland t) greaterequal 0. And the convexity in each coordinate results immedi-
ately if x1and x2 differ only in the i-th coordinate. To see that (vi) implies
(iii), we can consider two cases: if x1 and x2 have the same i- th coordi-
nate, it is obvious applying supermodularity to x1 + ei and x2. If they do
not have the same i- th coordinate, consider the auxiliary vector ˆ1, defined
by (ˆ1)k = (x1)k if k negationslash= i and (ˆ1)i = (x2)i , and first apply convexity in
coordinate i for x1 and ˆ1, and then the previous case with ˆ1 and x2.
We can state also equivalent characterizations for functions defined on
another subset of Rm that we use: Rm+.
Theorem 11 Let f : Rm+ -arrowrightR be a real-valued function. Then the following
statements are equivalent:
(i) f is directionally convex.
(ii) For all x1,x2 element Rm+ with x1 <=< x2 and all y elementRm+,
f (x1+y) -f (x1) <=< f (x2+y) -f (x2) .
(iii) For all x1,x2 element Rm+ with x1 <=< x2, for all epsilon element R, epsilon > 0 and for all
i element {1,2,... ,m} ,
deltaepsilonif(x1) <=< deltaepsilonif(x2).
(iv) For all x element Rm+, for all epsilon,epsilonprime element R, epsilon,epsilonprime > 0 and for all i,j element {1,2,...m} ,
deltaepsilonprimej deltaepsilonif(x) greaterequal 0.
Proof. Immediate following the lines of the previous proof.
16