Computer Science – Computer Science and Game Theory
Scientific paper
2008-10-17
Computer Science
Computer Science and Game Theory
30 pages, 6 figures
Scientific paper
Coalitional games are mathematical models suited to analyze scenarios where players can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. A fundamental problem for coalitional games is to single out the most desirable outcomes in terms of appropriate notions of worth distributions, which are usually called solution concepts. Motivated by the fact that decisions taken by realistic players cannot involve unbounded resources, recent computer science literature reconsidered the definition of such concepts by advocating the relevance of assessing the amount of resources needed for their computation in terms of their computational complexity. By following this avenue of research, the paper provides a complete picture of the complexity issues arising with three prominent solution concepts for coalitional games with transferable utility, namely, the core, the kernel, and the bargaining set, whenever the game worth-function is represented in some reasonable compact form (otherwise, if the worths of all coalitions are explicitly listed, the input sizes are so large that complexity problems are---artificially---trivial). The starting investigation point is the setting of graph games, about which various open questions were stated in the literature. The paper gives an answer to these questions, and in addition provides new insights on the setting, by characterizing the computational complexity of the three concepts in some relevant generalizations and specializations.
Greco Gianluigi
Malizia Enrico
Palopoli Luigi
Scarcello Francesco
No associations
LandOfFree
On the Complexity of Core, Kernel, and Bargaining Set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Complexity of Core, Kernel, and Bargaining Set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Core, Kernel, and Bargaining Set will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-352284