Thursday, 13 June 2013

On the number of blocks required to access the core

The following review has been written for Mathematical Reviews on the paper written by +Sylvain Béal, Eric Rémila, and Philippe Solal.

A payoff vector belongs to the core if (1) it distributes no more than the total value generated by all the players and no subset of players gets less than the value generated by this set. While the core may be empty, it remains one of the most popular solution concepts. Due to its definition, once a core imputation is proposed it is never rejected as no subset of players has a justified dissatisfaction. If such an imputation is seen as an agreement the question that naturally arises is whether such an agreement can be formed assuming that there is a status quo that does not belong to the core. [MR2065932 +László Kóczy  ; Luc Lauwers. The coalition structure core is accessible. Games Econom. Behav. 48 (2004), no. 1, 86--93] have shown that the core can be accessed by a bounded number of block, that is, coalitional improvements, but the presented bound was very high. Several papers (cited in this work) have improved on this bound, the current paper brings it down to n(n-1)/2.

The proof of this bound is based on the construction of a particular path, that at each non-core imputation looks for the smallest blocking coalition and among blocking coalitions with equal size the one with the maximal excess, that is, with the largest gain from blocking is selected. When this coalition blocks, its total payoff increases. Unlike in earlier models, here the authors try to provide the targeted, core payoff for as many players as possible. The method either reduces the set N_k of players with payoffs different from the target or else no new unsatisfied coalitions are generated.  In the latter case the set N_k can be reduced in at most |N_k| steps. Taking this worst case gives the aforementioned limit.

The idea of fixing some players' payoffs and studying the rest only suggests a link with reduced games, which is elaborated in the paper. At last the authors provide a comparison with alternative methods to access core imputations in some detail.

No comments:

Post a Comment