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

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.