Fast computation of the leastcore and prenucleolus of cooperative games

Bonnans, Joseph Frédéric; André, Matthieu

doi:10.1051/ro:2008016

Bonnans, Joseph Frédéric ; André, Matthieu

RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 299-314.

Résumé
Abstract

Le calcul du leastcore et du prénucléole est une manière efficace d’allouer une ressource entre $n$ joueurs. L’inconvénient est qu’il suppose la résolution d’un programme linéaire avec $2^{n} - 2$ contraintes. Dans cet article nous montrons comment, dans le cas de jeux de production convexes, générer des contraintes en résolvant des programmes linéaires mixtes de petite taille. L’approche est étendue aux jeux avec symétries (joueurs identiques) et aux jeux avec coalitions partiellement continues. Nous étudions aussi le calcul du prénucléole, et donnons des résultats numériques prometteurs.

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 $2^{n} - 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.

MR Zbl

DOI : 10.1051/ro:2008016

Classification : 91A12, 90C05, 90C11, 91B32
Mots-clés : cooperative games, coalitions, constraint generation, decomposition, convex production games, symmetric games, aggregate players, nucleolus

@article{RO_2008__42_3_299_0,
     author = {Bonnans, Joseph Fr\'ed\'eric and Andr\'e, Matthieu},
     title = {Fast computation of the leastcore and prenucleolus of cooperative games},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {299--314},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {3},
     year = {2008},
     doi = {10.1051/ro:2008016},
     mrnumber = {2444489},
     zbl = {1154.91317},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro:2008016/}
}

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 - Recherche Opérationnelle
PY  - 2008
SP  - 299
EP  - 314
VL  - 42
IS  - 3
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro:2008016/
DO  - 10.1051/ro:2008016
LA  - en
ID  - RO_2008__42_3_299_0
ER  -

%0 Journal Article
%A Bonnans, Joseph Frédéric
%A André, Matthieu
%T Fast computation of the leastcore and prenucleolus of cooperative games
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2008
%P 299-314
%V 42
%N 3
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro:2008016/
%R 10.1051/ro:2008016
%G en
%F RO_2008__42_3_299_0

Bonnans, Joseph Frédéric; André, Matthieu. Fast computation of the leastcore and prenucleolus of cooperative games. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 299-314. doi : 10.1051/ro:2008016. https://www.numdam.org/articles/10.1051/ro:2008016/

Bibliographie
Cité par

[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. | Zbl

[3] P.E. Gill, W. Murray and M.H. Wright, Practical optimization. Academic Press, London (1981). | MR | Zbl

[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. | MR | Zbl

[5] D. Granot, A generalized linear production model: a unifying model. Math. Program. 34 (1986) 212-222. | MR | Zbl

[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. | MR | Zbl

[7] J.E. Kelley, The cutting plane method for solving convex programs. J. Soc. Indust. Appl. Math. 8 (1960) 703-712. | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[10] G. Owen, On the core of linear production games. Math. Program. 9 (1975) 358-370. | MR | Zbl

[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. | Numdam | MR | Zbl

[12] D. Schmeidler, The nucleolus of a characteristic function game. SIAM J. Appl. Math. 17 (1969) 1163-1170. | MR | Zbl

[13] L.S. Shapley, On balanced sets and cores. Nav. Res. Logist. Q. 14 (1967) 453-460.

Cité par Sources :