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 publicationJournal articleAcademic researchpeer-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 languageEnglish
Pages (from-to)474-479
Number of pages6
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8877
DOIs
Publication statusPublished - 2014
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this