Computing the Least-Core and Nucleolus for Threshold Cardinality Matching Games

Qizhi Fang; B. Li; Xiaoming Sun; Jia Zhang; Jialin Zhang

doi:10.1007/978-3-319-13129-0_42

Computing the Least-Core and Nucleolus for Threshold Cardinality Matching Games

Qizhi Fang, B. Li, Xiaoming Sun, Jia Zhang, Jialin Zhang

Research output: Journal article publication › Journal article › Academic research › peer-review

1 Citation (Scopus)

Abstract

In this paper, we study the algorithmic issues on the leastcore and nucleolus of threshold cardinality matching games (TCMG). 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. Next, based on Gallai-Edmonds Decomposition in matching theory, we give a concise formulation of the nucleolus for a typical case of TCMG which the threshold T equals 1. When the threshold T is relevant to the input size, we prove that the nucleolus can be obtained in polynomial time in bipartite graphs and graphs with a perfect matching.

Original language	English
Pages (from-to)	474-479
Number of pages	6
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8877
DOIs	https://doi.org/10.1007/978-3-319-13129-0_42
Publication status	Published - 2014
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

More information

10.1007/978-3-319-13129-0_42

Cite this

@article{82cda610dd34455bb16a3e6ced710d08,

title = "Computing the Least-Core and Nucleolus for Threshold Cardinality Matching Games",

abstract = "In this paper, we study the algorithmic issues on the leastcore and nucleolus of threshold cardinality matching games (TCMG). 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. Next, based on Gallai-Edmonds Decomposition in matching theory, we give a concise formulation of the nucleolus for a typical case of TCMG which the threshold T equals 1. When the threshold T is relevant to the input size, we prove that the nucleolus can be obtained in polynomial time in bipartite graphs and graphs with a perfect matching.",

author = "Qizhi Fang and B. Li and Xiaoming Sun and Jia Zhang and Jialin Zhang",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.",

year = "2014",

doi = "10.1007/978-3-319-13129-0_42",

language = "English",

volume = "8877",

pages = "474--479",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Verlag",

}

Computing the Least-Core and Nucleolus for Threshold Cardinality Matching Games. / Fang, Qizhi; Li, B.; Sun, Xiaoming et al.

In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 8877, 2014, p. 474-479.

Research output: Journal article publication › Journal article › Academic research › peer-review

TY - JOUR

T1 - Computing the Least-Core and Nucleolus for Threshold Cardinality Matching Games

AU - Fang, Qizhi

AU - Li, B.

AU - Sun, Xiaoming

AU - Zhang, Jia

AU - Zhang, Jialin

PY - 2014

Y1 - 2014

N2 - In this paper, we study the algorithmic issues on the leastcore and nucleolus of threshold cardinality matching games (TCMG). 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. Next, based on Gallai-Edmonds Decomposition in matching theory, we give a concise formulation of the nucleolus for a typical case of TCMG which the threshold T equals 1. When the threshold T is relevant to the input size, we prove that the nucleolus can be obtained in polynomial time in bipartite graphs and graphs with a perfect matching.

AB - In this paper, we study the algorithmic issues on the leastcore and nucleolus of threshold cardinality matching games (TCMG). 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. Next, based on Gallai-Edmonds Decomposition in matching theory, we give a concise formulation of the nucleolus for a typical case of TCMG which the threshold T equals 1. When the threshold T is relevant to the input size, we prove that the nucleolus can be obtained in polynomial time in bipartite graphs and graphs with a perfect matching.

UR - http://www.scopus.com/inward/record.url?scp=84914127396&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-13129-0_42

DO - 10.1007/978-3-319-13129-0_42

M3 - Journal article

AN - SCOPUS:84914127396

VL - 8877

SP - 474

EP - 479

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -

Computing the Least-Core and Nucleolus for Threshold Cardinality Matching Games

Abstract

ASJC Scopus subject areas

More information

Other files and links

Cite this