TY - JOUR
T1 - Computing the least-core and nucleolus for threshold cardinality matching games
AU - Fang, Qizhi
AU - Li, Bo
AU - Sun, Xiaoming
AU - Zhang, Jia
AU - Zhang, Jialin
N1 - Funding Information:
The work is partially supported by National Natural Science Foundation of China (NSFC) (Nos. 61170062 , 61222202 , 61433014 , 61173009 , 11271341 ).
Publisher Copyright:
© 2015 Elsevier B.V.
PY - 2016/1/4
Y1 - 2016/1/4
N2 - Cooperative games provide a framework for fair and stable profit allocation in multi-agent systems. Core, least-core and nucleolus are such solution concepts that characterize stability of cooperation. In this paper, we study the algorithmic issues of the least-core and nucleolus of threshold cardinality matching games (TCMG). A TCMG is defined on a graph G=(V, E) and a threshold T, in which the player set is V and the profit of a coalition S⊆. V is 1 if the size of a maximum matching in G[S] meets or exceeds T, and 0 otherwise. We first show that for a TCMG, the problems of computing least-core value, finding and verifying least-core payoff are all polynomial-time solvable. We also provide a general characterization of the least-core for a large class of TCMG (cf. Theorem 2). Next, based on Gallai-Edmonds Decomposition in matching theory, we establish a concise formulation of the nucleolus for a special case of TCMG (when the threshold T equals 1). For arbitrary T, we prove that the nucleolus of TCMG can be obtained in polynomial time for bipartite graphs and graphs with a perfect matching.
AB - Cooperative games provide a framework for fair and stable profit allocation in multi-agent systems. Core, least-core and nucleolus are such solution concepts that characterize stability of cooperation. In this paper, we study the algorithmic issues of the least-core and nucleolus of threshold cardinality matching games (TCMG). A TCMG is defined on a graph G=(V, E) and a threshold T, in which the player set is V and the profit of a coalition S⊆. V is 1 if the size of a maximum matching in G[S] meets or exceeds T, and 0 otherwise. We first show that for a TCMG, the problems of computing least-core value, finding and verifying least-core payoff are all polynomial-time solvable. We also provide a general characterization of the least-core for a large class of TCMG (cf. Theorem 2). Next, based on Gallai-Edmonds Decomposition in matching theory, we establish a concise formulation of the nucleolus for a special case of TCMG (when the threshold T equals 1). For arbitrary T, we prove that the nucleolus of TCMG can be obtained in polynomial time for bipartite graphs and graphs with a perfect matching.
KW - Game theory
KW - Least-core
KW - Linear programming
KW - Matching
KW - Nucleolus
UR - http://www.scopus.com/inward/record.url?scp=84951309955&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2015.11.015
DO - 10.1016/j.tcs.2015.11.015
M3 - Journal article
AN - SCOPUS:84951309955
VL - 609
SP - 500
EP - 510
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -