Abstract
In this paper, we study the algorithmic issues on the least-core 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.
The work is partially supported by National Natural Science Foundation of China (NSFC) (NO. 61170062, 61222202, 61433014, 61173009, 11271341). Full version can be seen at: http://arxiv.org/abs/1409.5987.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aziz, H., Brandt, F., Harrenstein, P.: Monotone cooperative games and their threshold versions. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, vol. 1, pp. 1107–1114 (2010)
Biró, P., Kern, W., Paulusma, D.: Computing solutions for matching games. International Journal of Game Theory 41(1), 75–90 (2012)
Chen, N., Lu, P., Zhang, H.: Computing the nucleolus of matching, cover and clique games. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence (2012)
Deng, X., Fang, Q., Sun, X.: Finding nucleolus of flow game. Journal of Combinatorial Optimization 18(1), 64–86 (2009)
Deng, X., Papadimitriou, C.H.: On the complexity of cooperative solution concepts. Mathematics of Operations Research 19(2), 257–266 (1994)
Elkind, E., Goldberg, L.A., Goldberg, P.W., Wooldridge, M.: Computational complexity of weighted threshold games. In: Proceedings of the National Conference on Artificial Intelligence, vol. 22, p. 718 (2007)
Kern, W., Paulusma, D.: Matching games: the least-core and the nucleolus. Mathematics of Operations Research 28(2), 294–308 (2003)
Kopelowitz, A.: Computation of the kernels of simple games and the nucleolus of n-person games. Technical report, DTIC Document (1967)
Megiddo, N.: Computational complexity of the game theory approach to cost allocation for a tree. Mathematics of Operations Research 3(3), 189–196 (1978)
Plummer, M.D., Lovász, L.: Matching theory. Access Online via Elsevier (1986)
Schmeidler, D.: The nucleolus of a characteristic function game. SIAM Journal on Applied Mathematics 17(6), 1163–1170 (1969)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Fang, Q., Li, B., Sun, X., Zhang, J., Zhang, J. (2014). Computing the Least-Core and Nucleolus for Threshold Cardinality Matching Games. In: Liu, TY., Qi, Q., Ye, Y. (eds) Web and Internet Economics. WINE 2014. Lecture Notes in Computer Science, vol 8877. Springer, Cham. https://doi.org/10.1007/978-3-319-13129-0_42
Download citation
DOI: https://doi.org/10.1007/978-3-319-13129-0_42
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13128-3
Online ISBN: 978-3-319-13129-0
eBook Packages: Computer ScienceComputer Science (R0)