Searching for the Core with Column Generation

Kael Stilp, (Ozlem Ergun) - A seminal theorem in coalitional game theory gives sufficient conditions, being balanced, for a general n person game to have a non-empty core, Herbert E. Scarf(1967).  The core of a game is a payoff method to players such that no subset of players will want to leave the game by forming their own coalition.  Generally, finding a core element of a balanced game is difficult, yet the proof that Scarf gives is essentially constructive.

It mirrors the Simplex method on a discrete approximation of the game using two interacting tableaus, alternately making pivots.  However, it is not an algorithm as it relies on taking limits on successive approximations of the game to find an element in the core of the original game.  We would like to explore linear programming techniques applied to this method, particularly column generation through exploitation of nice properties within it and a given game.  The goal would be to drive the method, in a local fashion, towards an element in the core rather than exploring all possible payoffs as in the proof.