×

The nucleon of cooperative games and an algorithm for matching games. (English) Zbl 0920.90142

Summary: The nucleon is introduced as a new allocation concept for nonnegative cooperative \(n\)-person transferable utility games. The nucleon may be viewed as the multiplicative analogue of Schmeidler’s nucleolus. It is shown that the nucleon of (not necessarily bipartite) matching games can be computed in polynomial time.

MSC:

91A12 Cooperative games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] W.W. Bein, P. Brucker, J.K. Park and P.K. Pathak, ”A Monge property for thed-dimensional transportation problem,”Discrete Applied Mathematics 58 (1995) 97–109. · Zbl 0833.90083 · doi:10.1016/0166-218X(93)E0121-E
[2] G. Birkhoff,Lattice Theory, American Mathematical Society Colloquium Publications, Vol. 25 (American Mathematical Society, Providence, RI, 1967).
[3] R.E. Burkard, B. Klinz and R. Rudolf, ”Perspectives of Monge properties in optimization,”Discrete Applied Mathematics, to appear. · Zbl 0856.90091
[4] U. Derigs, O. Goecke and R. Schrader, ”Monge sequences and a simple assignment algorithm,”Discrete Applied Mathematics 15 (1986) 241–248. · Zbl 0646.90068 · doi:10.1016/0166-218X(86)90045-4
[5] J. Edmonds, ”Submodular functions, matroids and certain polyhedra,” in: R. Guy et al., eds.,Combinatorial Structures and their Applications (Gordon and Breach, New York, 1970) pp. 69–87. · Zbl 0268.05019
[6] J. Edmonds and R. Giles, ”A min-max relation for submodular functions on graphs,” in: P.L. Hammer, E.L. Johnson, B.H. Korte and G.L. Nemhauser, eds.,Studies in Integer Programming, Annals of Discrete Mathematics, Vol. 1 (North-Holland, Amsterdam 1977) pp. 185–204. · Zbl 0373.05040
[7] U. Faigle, ”Matroids in combinatorial optimization,” in: N. White, ed.,Combinatorial Geometries, Encyclopedia of Mathematics and its Applications, Vol. 29 (Cambridge University Press, Cambridge, 1987) pp. 161–210. · Zbl 0632.05018
[8] A. Frank and E. Tardos, ”Generalized polymatroids and submodular flows,”Mathematical Programming 42 (1988) 489–563. · Zbl 0665.90073 · doi:10.1007/BF01589418
[9] S. FujishigeSubmodular Functions and Optimization. Annals of Discrete Mathematics, Vol. 47 (North-Holland, Amsterdam, 1990).
[10] A.J. Hoffman, ”On simple linear programming problems,” in: V. Klee, ed.,Convexity, Proceedings of Symposia in Pure Mathematics, Vol. 7 (American Mathematical Society, Providence, RI, 1963) pp. 317–327.
[11] M. Queyranne, F. Spieksma and F. Tardella, ”A general class of greedily solvable linear program,” in: U. Faigle and C. Hoede, eds.,3rd Twente Workshop on Graphs and Combinatorial Optimization, Memorandum No. 1132 (Department of Applied Mathematics, University of Twente, Enschede, 1993). · Zbl 0924.90107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.