Remarkable polyhedra related to set functions, games and capacities

Michel Grabisch (1, 2)

1 CES - Centre d'économie de la Sorbonne
2 PSE - Paris School of Economics

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, decicion making and com-binatorial optimization. This survey paper gives an overview of these notions and studies all these polyhedra.

Mots clés: pseudo-Boolean function; Möbius trans-form; nonadditive measure; capacity; core; multichoice game; supermodular game; p-additive game; TU-game

Domaines: Mathématique discrète [cs.DM]; Economies et finances

Michel Grabisch. Remarkable polyhedra related to set functions, games and capacities. TOP, 2016, 24 (2), pp.301-326. ⟨10.1007/s11750-016-0421-4⟩. ⟨hal-01372858⟩