Fast computation of the leastcore and prenucleolus of cooperative games

Joseph Frédéric Bonnans; Matthieu André

RAIRO - Operations Research (2008)

  • Volume: 42, Issue: 3, page 299-314
  • ISSN: 0399-0559

Abstract

top
The computation of leastcore and prenucleolus is an efficient way of allocating a common resource among n players. It has, however, the drawback being a linear programming problem with 2n - 2 constraints. In this paper we show how, in the case of convex production games, generate constraints by solving small size linear 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 the computation of prenucleolus, and display encouraging numerical results.

How to cite

top

Bonnans, Joseph Frédéric, and André, Matthieu. "Fast computation of the leastcore and prenucleolus of cooperative games." RAIRO - Operations Research 42.3 (2008): 299-314. <http://eudml.org/doc/250422>.

@article{Bonnans2008,
abstract = { The computation of leastcore and prenucleolus is an efficient way of allocating a common resource among n players. It has, however, the drawback being a linear programming problem with 2n - 2 constraints. In this paper we show how, in the case of convex production games, generate constraints by solving small size linear 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 the computation of prenucleolus, and display encouraging numerical results. },
author = {Bonnans, Joseph Frédéric, André, Matthieu},
journal = {RAIRO - Operations Research},
keywords = {Cooperative games; coalitions; constraint generation; decomposition; convex production games; symmetric games; aggregate players; nucleolus.; cooperative games; convex production games; nucleolus},
language = {eng},
month = {8},
number = {3},
pages = {299-314},
publisher = {EDP Sciences},
title = {Fast computation of the leastcore and prenucleolus of cooperative games},
url = {http://eudml.org/doc/250422},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Bonnans, Joseph Frédéric
AU - André, Matthieu
TI - Fast computation of the leastcore and prenucleolus of cooperative games
JO - RAIRO - Operations Research
DA - 2008/8//
PB - EDP Sciences
VL - 42
IS - 3
SP - 299
EP - 314
AB - The computation of leastcore and prenucleolus is an efficient way of allocating a common resource among n players. It has, however, the drawback being a linear programming problem with 2n - 2 constraints. In this paper we show how, in the case of convex production games, generate constraints by solving small size linear 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 the computation of prenucleolus, and display encouraging numerical results.
LA - eng
KW - Cooperative games; coalitions; constraint generation; decomposition; convex production games; symmetric games; aggregate players; nucleolus.; cooperative games; convex production games; nucleolus
UR - http://eudml.org/doc/250422
ER -

References

top
  1. 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).  
  2. B. Fromen, 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.  
  3. P.E. Gill, W. Murray and M.H. Wright, Practical optimization. Academic Press, London (1981).  
  4. 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.  
  5. D. Granot, A generalized linear production model: a unifying model. Math. Program.34 (1986) 212–222.  
  6. A. Hallefjord, R. Helming and K. Jörnstein, Computing the nucleolus when the characteristic function is given implicitly: a constraint generation approach. Int. J. Game Theor.24 (1995) 357–372.  
  7. J.E. Kelley, The cutting plane method for solving convex programs. J. Soc. Indust. Appl. Math.8 (1960) 703–712.  
  8. M. Maschler, J.A.M. Potters and S.H. Tijs, The general nucleolus and the reduced game property. Int. J. Game Theor.21 (1992) 85–106.  
  9. 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.  
  10. G. Owen, On the core of linear production games. Math. Program.9 (1975) 358–370.  
  11. N. Preux, F. Bendali, J. Mailfert, and A. Quilliot. Cœur et nucléolus des jeux de recouvrement. RAIRO-Oper. Res.34 (2000) 363–383.  
  12. D. Schmeidler, The nucleolus of a characteristic function game. SIAM J. Appl. Math.17 (1969) 1163–1170.  
  13. L.S. Shapley, On balanced sets and cores. Nav. Res. Logist. Q.14 (1967) 453–460.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.