Bases and transforms of set functions

Michel Grabisch (1, 2)

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

The paper studies the vector space of set functions on a finite set X, which can be alternatively seen as pseudo-Boolean functions, and including as a special cases games. We present several bases (unanimity games, Walsh and parity functions) and make an emphasis on the Fourier transform. Then we establish the basic duality between bases and invertible linear transform (e.g., the Möbius transform, the Fourier transform and interaction transforms). We apply it to solve the well-known inverse problem in cooperative game theory (find all games with same Shapley value), and to find various equivalent expressions of the Choquet integral.

Nous étudions l'espace vectoriel des fonctions d'ensemble sur un espace fini X, qui peuvent être vues aussi comme des fonctions pseudo-booléennes, et incluent comme cas particulier les jeux. Nous présentons plusieurs bases (jeux unanimes, fonctions de Walsh, fonctions de parité) ainsi que la transformée de Fourier. Nous établissons la dualité fondamentale entre les bases et les transformées linéaires et inversibles (e.g., la transformée de Möbius, de Fourier et les transformées en interaction). Nous l'appliquons pour résoudre le problème inverse bien connu de la théorie des jeux coopératifs (trouver tous les jeux ayant la même valeur de Shapley), et pour trouver différentes expressions équivalentes pour l'intégrale de Choquet.

Mots clés: set function; basis; Walsh function; Fourier transform; game

Mots clés: fonction d'ensemble; base; fonction de Walsh; transformée de Fourier; jeu

Domaines: Economies et finances

Michel Grabisch. Bases and transforms of set functions. 2015. ⟨halshs-01169287⟩