Article ID: | iaor1995684 |
Country: | United States |
Volume: | 19 |
Issue: | 2 |
Start Page Number: | 257 |
End Page Number: | 266 |
Publication Date: | May 1994 |
Journal: | Mathematics of Operations Research |
Authors: | Papadimitriou Christos H., Deng Xiaotie |
Keywords: | group decision making |
The authors study from a complexity theoretic standpoint the various solution concepts arising in cooperative game theory. They use as a vehicle for this study a game in which the players are nodes of a graph with weights on the edges, and the value of a coalition is determined by the total weight of the edges contained in it. The Shapley value is always easy to compute. The core is easy to characterize when the game is convex, and is intractable (NP-complete) otherwise. Similar results are shown for the kernel, the nucleolus, the