On computational complexity of membership test in flow games and linear production games

Shanfeng Zhu, Xiaotie Deng, Maocheng Cai and Qizhi Fang
Additional contact information
Shanfeng Zhu: Department of Computer Science, City University of Hong Kong, Hong Kong, P. R. China
Xiaotie Deng: Department of Computer Science, City University of Hong Kong, Hong Kong, P. R. China
Maocheng Cai: Institute of Systems Science, Chinese Academy of Sciences, Beijing 100080, P. R. China
Qizhi Fang: Department of Mathematics, Ocean University of Qingdao, Qingdao 266003, P. R. China

International Journal of Game Theory, 2002, vol. 31, issue 1, 39-45

Abstract: 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.

Keywords: Flow; game; ·; linear; production; game; · (search for similar items in EconPapers)
Date: 2002-10-02
Note: Received: October 2000/Final version: March 2002
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://link.springer.de/link/service/journals/00182/papers/2031001/20310039.pdf (application/pdf)
Access to the full text of the articles in this series is restricted

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:31:y:2002:i:1:p:39-45

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().