Abstract
Assignment games with side payments are models of certain two-sided markets. It is known that prices which competitively balance supply and demand correspond to elements in the core. The nucleolus, lying in the lexicographic center of the nonempty core, has the additional property that it satisfies each coalition as much as possible. The corresponding prices favor neither the sellers nor the buyers, hence provide some stability for the market.
An algorithm is presented that determines the nucleolus of an assignment game. It generates a finite number of payoff vectors, monotone increasing on one side, and decreasing on the other. The decomposition of the payoff space and the lattice-type structure of the feasible set are utilized in associating a directed graph. Finding the next payoff is translated into determining the lengths of longest paths to the nodes, if the graph is acyclic, or otherwise, detecting the cycle(s). In an (m,n)-person assignment game withm = min(m,n) the nucleolus is found in at most 1/2·m(m + 3) steps, each one requiring at mostO(m·n) elementary operations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Balinski ML, Gomory RE (1964) A primal method for the assignment and transportation problems. Management Science 10: 578–593
Granot D, Granot F (1992) On some network flow games. Mathematics of Operations Research 17: 792–841
Kohlberg E (1972) The nucleolus as a solution of a minimization problem. SIAM Journal on Applied Mathematics 23: 34–39
Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2: 83–97
Maschler M, Peleg B, Shapley LS (1979) Geometric properties of the kernel, nucleolus, and related solution concepts. Mathematics of Operations Research 4: 303–338
Maschler M, Potters JAM, Tijs SH (1992) The general nucleolus and the reduced game property. International Journal of Game Theory 21: 85–106
Noltemeier H (1975) An algorithm for the determination of longest distances in a graph. Mathematical Programming 9: 350–357
Owen G (1974) A note on the nucleolus. International Journal of Game Theory 3: 101–103
Sankaran JK (1991) On finding the nucleolus of ann-person cooperative game. International Journal of Game Theory 19: 329–338
Schmeidler D (1969) The nucleolus of a characteristic function game. SIAM Journal on Applied Mathematics 17: 1163–1170
Shapley LS, Shubik M (1972) The assignment game I: The core. International Journal of Game Theory 1: 111–130
Thompson GL (1981) Auctions and market games. In: Essays in Game Theory and Mathematical Economics in Honor of Oskar Morgenstern. Aumann RJ et al (Eds) Bibliographisches Institut, Mannheim
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Solymosi, T., Raghavan, T.E.S. An algorithm for finding the nucleolus of assignment games. Int J Game Theory 23, 119–143 (1994). https://doi.org/10.1007/BF01240179
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01240179