2014/09/21 by Qizhi Fang, Bo Li, Fang, Qizhi +7
Economics, Econometrics and Finance · Decision Sciences · #Game Theory and Voting Systems #Game Theory and Applications #Auction Theory and Applications
paper · pdf · doi:10.48550/arxiv.1409.5987
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 on 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. 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.