On computational complexity of membership test in flow games and linear production games
Let \equiv(N,v) be a cooperative game with the player set N and characteristic function v: 2N ->R. An imputation of the game is in the core if no subset of players could gain advantage by splitting from the grand coalition of all players. It is well known that, for the flow game (and equivalently, for the linear production game), the core is always non-empty and a solution in the core can be found in polynomial time. In this paper, we show that, given an imputation x, it is NP-complete to decide x is not a member of the core, for the flow game. And because of the specific reduction we constructed, the result also holds for the linear production game.
Volume (Year): 31 (2002)
Issue (Month): 1 ()
|Note:||Received: October 2000/Final version: March 2002|
|Contact details of provider:|| Web page: http://link.springer.de/link/service/journals/00182/index.htm|
|Order Information:||Web: http://link.springer.de/orders.htm|
When requesting a correction, please mention this item's handle: RePEc:spr:jogath:v:31:y:2002:i:1:p:39-45. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Guenther Eichhorn)or (Christopher F Baum)
If references are entirely missing, you can add them using this form.