Remarkable polyhedra related to set functions, games and capacities
Résumé
Set functions are widely used in many domains of Operations Research (cooperative game theory, decision under risk and uncertainty, combinatorial optimization) under different names (TU-game, capacity, nonadditive measure, pseudo-Boolean function, etc…). Remarkable families of set functions form polyhedra, e.g., the polytope of capacities, the polytope of p-additive capacities, the cone of supermodular games, etc…. Also, the core of a set function, defined as the set of additive set functions dominating that set function, is a polyhedron which is of fundamental importance in game theory, decision making and combinatorial optimization. This survey paper gives an overview of these notions and studies all these polyhedra.
Les fonctions d'ensemble sont couramment utilisées dans de nombreux domaines de la Recherche Opérationnelle (théorie des jeux coopératifs, décision dans le risque et l'incertain, optimisation combinatoire) sous des noms différents (jeux TU, capacités, mesures non-additives, fonctions pseudo-booléennes, etc…). Les familles remarquables de fonctions d'ensemble forment des polyèdres, par exemple le polytope des capacités, des capacités p-additives, le cône des jeux sur-modulaires, etc…. D'autre part, le coeur d'une fonction d'ensemble, défini comme l'ensemble des fonctions d'ensemble additives dominant cette fonction d'ensemble est un polyèdre qui est d'une importance fondamentale en théorie des jeux, en décision et en optimisation combinatoire. Cet article de synthèse fait un survol de ces notions et étudie tous ces polyèdres.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...