NDLI: The Complexity of the Nucleolus in Compact Games

Please wait, while we are loading the content...

The Complexity of the Nucleolus in Compact Games

Content Provider	ACM Digital Library
Author	Greco, Gianluigi Malizia, Enrico Palopoli, Luigi Scarcello, Francesco
Copyright Year	2015
Abstract	The nucleolus is a well-known solution concept for coalitional games to fairly distribute the total available worth among the players. The nucleolus is known to be $\textit{NP}-hard$ to compute over compact coalitional games, that is, over games whose functions specifying the worth associated with each coalition are encoded in terms of polynomially computable functions over combinatorial structures. In particular, hardness results have been exhibited over minimum spanning tree games, threshold games, and flow games. However, due to its intricate definition involving reasoning over exponentially many coalitions, a nontrivial upper bound on its complexity was missing in the literature and looked for. This article faces this question and precisely characterizes the complexity of the nucleolus, by exhibiting an upper bound that holds on any class of compact games, and by showing that this bound is tight even on the (structurally simple) class of graph games. The upper bound is established by proposing a variant of the standard linear-programming based algorithm for nucleolus computation and by studying a framework for reasoning about succinctly specified linear programs, which are contributions of interest in their own. The hardness result is based on an elaborate combinatorial reduction, which is conceptually relevant for it provides a “measure” of the computational cost to be paid for guaranteeing voluntary participation to the distribution process. In fact, the pre-nucleolus is known to be efficiently computable over graph games, with this solution concept being defined as the nucleolus but without guaranteeing that each player is granted with it at least the worth she can get alone, that is, without collaborating with the other players. Finally, this article identifies relevant tractable classes of coalitional games, based on the notion of type of a player. Indeed, in most applications where many players are involved, it is often the case that such players do belong in fact to a limited number of classes, which is known in advance and may be exploited for computing the nucleolus in a fast way.
Starting Page	1
Ending Page	52
Page Count	52
File Format	PDF
ISSN	19423454
e-ISSN	19423462
DOI	10.1145/2692372.2692374
Volume Number	7
Issue Number	1
Journal	ACM Transactions on Computation Theory (TOCT)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-01-13
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Game theory Coalitional games Compact representations Computational complexity Linear programming Nucleolus Solution concepts
Content Type	Text
Resource Type	Article
Subject	Computational Theory and Mathematics Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Computational Complexity of Nash Equilibria in Concisely Represented Games

On the computational complexity of the bargaining set and the kernel in compact coalitional games (810).

Path-Disruption Games: Bribery and a Probabilistic Model

Computing cooperative solution concepts in coalitional skill games.

Using Computational Intelligence Algorithms to Solve the Coalition Structure Generation Problem in Coalitional Skill Games

Compilability and compact representations of revision of Horn knowledge bases

On the Complexity of Succinct Zero-Sum Games

Solution Concepts in A-Loss Recall Games: Existence and Computational Complexity

On the computational complexity of coalitional resource games (2006).

The Complexity of the Nucleolus in Compact Games

Similar Documents

The Computational Complexity of Nash Equilibria in Concisely Represented Games

On the computational complexity of the bargaining set and the kernel in compact coalitional games (810).

Path-Disruption Games: Bribery and a Probabilistic Model

Computing cooperative solution concepts in coalitional skill games.

Using Computational Intelligence Algorithms to Solve the Coalition Structure Generation Problem in Coalitional Skill Games

Compilability and compact representations of revision of Horn knowledge bases

On the Complexity of Succinct Zero-Sum Games

Solution Concepts in A-Loss Recall Games: Existence and Computational Complexity

On the computational complexity of coalitional resource games (2006).

The Complexity of the Nucleolus in Compact Games