Locally convex (concave) games
by
J. M. Bilbao
Applied Mathematics II, University of Seville
Coauthors: E. Algaba, N. Jiménez, J. J. López

The concept of convex game was introduced by Shapley ( Cores of convex games, Int. J. Game Theory 1 (1971) 11-26). Recall that a game ( N, v) is convex if and only if for each player i in N, the marginal returns function is nondecreasing, that is,

v( S \cup i) -v( S) <= v( T \cup i)-v( T)   whenever  S subset T subset N\i.

The rank function of a greedoid is nondecreasing and locally submodular as the following theorem states (see Korte, Lovász and Schrader (1991) Greedoids). A function r:2^N --> Z₊ is the rank function of a greedoid if and only if for all X, Y subset N and all x, y in N the following conditions hold:

1. r( \emptyset) = 0,
2. r( X) <= | X| ,
3. X subset Y implies r( X) <= r( Y) ,
4. r( X) = r( X \cup x) = r( X \cup y) implies r( X) = r( X \cup { x, y} ) .

A game (N, c) is locally concave if the function c is locally submodular, that is, for all coalitions S subset N and all players i, j in N\S, we have

c( S) = c( S \cup i) = c( S \cup j)   implies   c( S) = c( S \cup { i, j} ) .

A game (N, v) is locally convex if the function v is locally supermodular, that is, for all nonempty coalitions S subset N and all players i, j in S,

v( S) = v( S\i) = v( S\j)   implies   v( S) = v( S\{i, j} ) .

We obtain the following properties: Let ( N, c) be a nondecreasing concave (convex) game. Then ( N, c) is locally concave (convex).

If ( N, v) is a convex game and v( i) >= 0 for all i in N, then ( N, v) is locally convex. If (N, c) is a concave game and c( N\i) <= c(N) for all i in N, then (N, c) is locally concave.

Every rank function of a greedoid which is not a matroid is an example of locally concave game which is not concave. We introduce a class of games in order to study the equivalence of these concepts.

An integer game c:2^N --> Z has the unit marginal worth property if for all S subset N and i in N,    c( S \cup i)-c( S) in { 0, 1} .

Let c:2^N --> Z be an integer game which satisfies the unit marginal worth property. Then the following statements are equivalent:

1. ( N, c) is locally concave.
2. c is the rank function of the matroid M={S subset N:c( S) = | S| } .
3. ( N, c) is nondecreasing and concave.

Let v:2^N --> Z be an integer game which satisfies the unit marginal worth property. Then the following statements are equivalent:

1. ( N, v) is locally convex.
2. The function r^d( S) = | S| -v( S) is the rank function of the matroid
   

   Md={ S subset N:v( S) = 0} .

3. ( N, v) is nondecreasing and convex.

Let v:2^N --> { 0, 1} be a game which is nondecreasing (simple game). Then the following statements are equivalent:

1. ( N, v) is convex.
2. ( N, v) is locally convex.
3. The collection of winning coalitions W={ S subset N:v( S) = 1} is closed under intersection.
4. There exists a unique circuit of the matroid M^d.
5. v=u_T, where T is the unique circuit of the matroid M^d.

Note that the intersection of the winning coalitions is the minimal winning coalition of the convex simple game v, i.e., the unique circuit (minimal dependent set) of the matroid M^d.

http://www.esi.us.es/~mbilbao/

Date received: May 2, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caez-98.