Wednesday, July 22, 2009

Balanced set systems

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 2N. 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.)

No comments: