Computing the least-core and nucleolus for threshold cardinality matching games

Qizhi Fang, Bo Li, Xiaoming Sun, Jia Zhang, Jialin Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)500-510
Number of pages11
JournalTheoretical Computer Science
Volume609
DOIs
Publication statusPublished - 4 Jan 2016
Externally publishedYes

Keywords

  • Game theory
  • Least-core
  • Linear programming
  • Matching
  • Nucleolus

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this