|
Organizers |
Minimal core generation
by
Alain Fougeres
University of Perpignan / GREQAM Marseille
Coauthors: Annick Truffert, Michel Ventou
Our objective is to characterize the core of a T.U.-game on the basis of a minimal number of coalitions and to compute optimally all its vertices. When the game v is normalized, the core allocations may be considered as the probabilities which majorize it . The core vertices are classically characterized as the allocations w of which the "contact set" { w=v} has a linear rank equal to n . The main question is thus:
"how to recognize the coalitions determining all the core vertices?"
Our approach consists to obtain the adequate coalitions via the characterization of any minimal game having the same core as the given game. To simplify our exposition, we consider without loss of generality a normalized game v with positive values for any non-empty coalition. We examine the generating properties of the graph of the exact game s associated with v , to reduce the game value of some coalition (in fact just as zero) without modifying the initial core. When it is possible to drop no more coalition value, the obtained game, denoted u , is a minimal lower bound for v among all the games having the same core as v . We call this game a v-minimal game.
The core will be obviously determined by the values of the contact coalitions between the v-minimal game and its vertices. These contact coalitions are exactly the active coalitions of u , i.e. the coalitions A such that the value is unchanged, i.e. uA=vA . The set of such ones coincides with the support of u , i.e. the set of the coalitions with positive values. Moreover the minimal game u coincide on its support with both the initial game v and the exact game s .
The underlying reason is geometrical: from some appropriate closure, the exact game graph is positively generated from any v-minimal game graph, as the same way as the core is obtained by convex closure from its vertices.
To point out the two only types of the active coalitions, we associate with any coalition A its contact core CA , i.e. the set of the allocations w such that wA=vA . Any active coalition is either a node or a v-leader, i.e. is a coalition N or L such that CN=C or dim CL=dim C-1 .
When the only node non-empty is S , there exists a lowest game u
minorizing v ; the support of u is then the set of all the v-leaders
(plus S). In the general case, the support of any v-minimal game is the union of a minimal balanced generating family of the
nodes set (plus S), and a v-leader lifting ,
obtained in picking up one and only one v-leader in any equivalence class
defined by
|
Date received: May 16, 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 # cafc-50.