I've been trying to understand Scarf's core theorem, which says that if a coalitional non-tranferable utility game is
balanced, then it has a non-empty core. In the context of transferable utility games, there is another definition of "balanced game" which should not be confused with the one for NTU games. Osborne and Rubinstein's book studies balanced TU games in some detail, but only briefly mentions balanced NTU games.
The definition (NTU case) uses the notion of a balanced set system, defined as follows...
Given a set
N, suppose that
C is a collection of subsets of
N, i.e.
C is a subset of 2
N. Let
C={
C1,...,
Cz}. We say that
C is balanced if there are non-negative real numbers α
i, one for each
Ci, such that, for every element of
N, the sum over all
Ci of their α values is 1.
The above definition is used in Scarf's 1967 paper.
The def can also be characterized as follows: Associate each member of
N with a coordinate in Euclidean space, in fact let's associate it with a point in space representing the unit vector pointing in the direction of that coordinate. More generally, associate any subset of
N with the average, or center of gravity, of the points corresponding to the members of that subset. An equivalent definition of "balanced collection of subsets of
N" says that the point corresponding to the entire set
N should be a convex combination of the points corresponding to these subsets of
N. (the equivalence is straightforward; it is pointed out in
this paper and probably quite a lot of others.)
There's an alternative definition that requires that the α
i should be positive, rather than just non-negative (e.g.
this paper). This is
not equivalent in terms of which set systems are balanced (but the definitions are indeed the same modulo their use in the definition of a balanced NTU game). Let's use the phrase "positively balanced" to refer to set systems where the α
i can all be positive. To see how they differ, suppose
N={1,2,3} and consider the subsets {1},{2,3},{3}. These subsets are balanced, using the α values 1,1,0 respectively. It is easy to see that {3} must be given the value 0, so that these sets are balanced but not positively balanced.
From a geometrical perspective, "positively balanced" seems rather unsatisfying since a set system that is balanced but not positively balanced, is from the perspective of the α
i, nevertheless arbitrarily close to being positively balanced. I am wondering if there is some nice alternative combinatorial characterization of positively balanced set systems. On the other hand, for set systems that are not balanced (under the original definition) the set of all non-negative weighted sums of their corresponding points in space, is presumably bounded away from the average of all the points. Maybe it's interesting to ask how close you can get? (My guess: for
N={1,2,...,
n}, take the
n-1 subsets
N-{1}, ...,
N-{n-1}; these are not balanced; but give each one α
i=1/(
n-2), so for each
i<
n you get a total of 1, and for
n you get a total of (
n-1)/(
n-2); pretty close to the all-ones vector.)