Research Article

Fast computation of the leastcore and prenucleolus of cooperative games

Joseph Frédéric Bonnans^a1 and Matthieu André^a2

Inria-Futurs and Centre de Mathématiques Appliquées, École Polytechnique, 91128 Palaiseau, France; Frederic.Bonnans@inria.fr

Direction Optimisation Amont-Aval Trading, EDF, 1 Place Pleyel, 93282 Saint-Denis Cedex, France; matthieu.andre@edfgdf.fr

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 2ⁿ - 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.

Résumé

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ⁿ - 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.

(Received November 7 2006)

(Accepted September 5 2007)

(Online publication August 20 2008)

Key Words:

• Cooperative games;
• coalitions;
• constraint generation;
• decomposition;
• convex production games;
• symmetric games;
• aggregate players;
• nucleolus.

Mathematics Subject Classification:

• 91A12;
• 90C05;
• 90C11;
• 91B32