Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T11:10:22.907Z Has data issue: false hasContentIssue false
  • English
  • Français

Fast computation of the leastcoreand prenucleolus of cooperative games

Published online by Cambridge University Press:  20 August 2008

Joseph Frédéric Bonnans  and
Matthieu André
Joseph Frédéric Bonnans
Affiliation:
Inria-Futurs and Centre de Mathématiques Appliquées, École Polytechnique, 91128 Palaiseau, France; [email protected]
Matthieu André
Affiliation:
Direction Optimisation Amont-Aval Trading, EDF, 1 Place Pleyel, 93282 Saint-Denis Cedex, France; [email protected]
Get access

Abstract

The computation of leastcore and prenucleolus is an efficient way ofallocating a common resource among n players. It has, however,the drawback being a linear programming problem with2n - 2 constraints. In this paper we showhow, in the case of convex production games, generate constraints by solving small sizelinear programming problems,with both continuous and integer variables. The approach is extended to games with symmetries (identical players), and to games with partially continuous coalitions. We also study thecomputation of prenucleolus, and display encouraging numerical results.

Keywords

Cooperative gamescoalitionsconstraint generationdecompositionconvex production gamessymmetric gamesaggregate playersnucleolus.
Type
Research Article
Information
RAIRO - Operations Research , Volume 42 , Issue 3 , July 2008 , pp. 299 - 314
Copyright
© EDP Sciences, ROADEF, SMAI, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

M. Boyer, M. Moreau and M. Truchon, Partage des coût et tarification des infrastuctures. Les méthodes de partage de coût. Un survol. Technical Report RP-18, Cirano (2002).
Fromen, B., Reducing the number of linear programs needed for solving the nucleolus problem of n-person game theory. Eur. J. Oper. Res. 98 (1997) 626–636. CrossRef
P.E. Gill, W. Murray and M.H. Wright, Practical optimization. Academic Press, London (1981).
A.J. Goldman and A.W. Tucker, Polyhedral convex cones. In H.W. Kuhn and A.W. Tucker, editors, Linear inequalities and related systems, Princeton, 1956. Princeton University Press 19–40.
Granot, D., A generalized linear production model: a unifying model. Math. Program. 34 (1986) 212–222. CrossRef
Hallefjord, A., Helming, R. and Jörnstein, K., Computing the nucleolus when the characteristic function is given implicitly: a constraint generation approach. Int. J. Game Theor. 24 (1995) 357–372. CrossRef
Kelley, J.E., The cutting plane method for solving convex programs. J. Soc. Indust. Appl. Math. 8 (1960) 703–712. CrossRef
Maschler, M., Potters, J.A.M. and Tijs, S.H., The general nucleolus and the reduced game property. Int. J. Game Theor. 21 (1992) 85–106. CrossRef
Jörg Oswald, Jean Derks and Hans Peters, Prenucleolus and nucleolus of a cooperative game: characterizations by tight coalitions. In 3rd International Conference on Approximation and Optimization in the Caribbean (Puebla, 1995), Aportaciones Mat. Comun. vol. 24, Soc. Mat. Mexicana, México (1998) 197–216.
Owen, G., On the core of linear production games. Math. Program. 9 (1975) 358–370. CrossRef
Preux, N., Bendali, F., Mailfert, J., and Quilliot, A.. Cœur et nucléolus des jeux de recouvrement. RAIRO-Oper. Res. 34 (2000) 363–383. CrossRef
Schmeidler, D., The nucleolus of a characteristic function game. SIAM J. Appl. Math. 17 (1969) 1163–1170. CrossRef
Shapley, L.S., On balanced sets and cores. Nav. Res. Logist. Q. 14 (1967) 453–460. CrossRef