Fonction supermodulaire - Supermodular function

En mathématiques , une fonction

${\ displaystyle f \ colon \ mathbb {R} ^ {k} \ to \ mathbb {R}}$

est supermodulaire si

${\ Displaystyle f (x \ uparrow y) + f (x \ downarrow y) \ geq f (x) + f (y)}$

pour tous , où désigne le maximum et par composantes au minimum de par composantes et . ${\ displaystyle x}$${\ Displaystyle y \ in \ mathbb {R} ^ {k}}$${\ displaystyle x \ uparrow y}$${\ displaystyle x \ downarrow y}$${\ displaystyle x}$${\ displaystyle y}$

Si - f est supermodulaire alors f est appelé sous - modulaire , et si l'inégalité est changée en égalité, la fonction est modulaire .

Si f est deux fois continuellement différentiable, alors la supermodularité est équivalente à la condition

${\ displaystyle {\ frac {\ partial ^ {2} f} {\ partial z_ {i} \, \ partial z_ {j}}} \ geq 0 {\ mbox {for all}} i \ neq j.}$

Supermodularité en économie et théorie des jeux

Le concept de supermodularité est utilisé dans les sciences sociales pour analyser comment la décision d' un agent affecte les motivations des autres.

Considérons un jeu symétrique avec une fonction de paiement fluide définie sur les actions de deux joueurs ou plus . Supposons que l'espace d'action soit continu; pour simplifier, supposons que chaque action est choisi parmi un intervalle: . Dans ce contexte, la supermodularité de implique qu'une augmentation du choix du joueur augmente le gain marginal de l'action pour tous les autres joueurs . Autrement dit, si un joueur choisit un joueur supérieur , tous les autres joueurs sont également incités à augmenter leurs choix . Suivant la terminologie de Bulow, Geanakoplos et Klemperer (1985), les économistes appellent cette situation la complémentarité stratégique , car les stratégies des acteurs sont complémentaires les unes des autres. C'est la propriété de base sous-jacente aux exemples d' équilibres multiples dans les jeux de coordination . ${\ displaystyle \, f}$${\ displaystyle \, z_ {i}}$${\ displaystyle i \ in {1,2, \ dots, N}}$${\ displaystyle z_ {i} \ in [a, b]}$${\ displaystyle \, f}$${\ displaystyle \, i}$${\ displaystyle \, z_ {i}}$${\ displaystyle df / dz_ {j}}$${\ displaystyle \, z_ {j}}$${\ displaystyle \, j}$${\ displaystyle \, i}$${\ displaystyle \, z_ {i}}$${\ displaystyle \, j}$${\ displaystyle \, z_ {j}}$

Le cas contraire de la submodularité de correspond à la situation de substituabilité stratégique . Une augmentation de diminue le gain marginal pour tous les choix des autres joueurs , les stratégies sont donc des substituts. Autrement dit, si choisit un plus élevé , les autres joueurs sont incités à choisir un plus bas . ${\ displaystyle \, f}$${\ displaystyle \, z_ {i}}$${\ displaystyle \, z_ {j}}$${\ displaystyle \, i}$${\ displaystyle \, z_ {i}}$ ${\ displaystyle \, z_ {j}}$

Par exemple, Bulow et al. considérer les interactions de nombreuses entreprises imparfaitement compétitives . Lorsqu'une augmentation de la production d'une entreprise augmente les revenus marginaux des autres entreprises, les décisions de production sont des compléments stratégiques. Lorsqu'une augmentation de la production d'une entreprise abaisse les revenus marginaux des autres entreprises, les décisions de production sont des substituts stratégiques.

Une fonction d'utilité supermodulaire est souvent liée à des biens complémentaires . Cependant, ce point de vue est contesté.

Fonctions submodulaires des sous-ensembles

La supermodularité et la sous-modularité sont également définies pour les fonctions définies sur des sous-ensembles d'un plus grand ensemble. Intuitivement, une fonction sous-modulaire sur les sous-ensembles démontre des «rendements décroissants». Il existe des techniques spécialisées pour optimiser les fonctions sous-modulaires.

Soit S un ensemble fini. Une fonction est de sous - module si pour tout et , . Pour la supermodularité, l'inégalité est inversée. ${\ displaystyle f \ colon 2 ^ {S} \ to \ mathbb {R}}$${\ displaystyle A \ sous-ensemble B \ sous-ensemble S}$${\ displaystyle x \ in S \ setminus B}$${\ Displaystyle f (A \ cup \ {x \}) - f (A) \ geq f (B \ cup \ {x \}) - f (B)}$

La définition de la sous-modularité peut être formulée de manière équivalente comme

${\ Displaystyle f (A) + f (B) \ geq f (A \ cap B) + f (A \ cup B)}$

pour tous les sous - ensembles A et B de S .

La théorie et les algorithmes de dénombrement pour trouver les maxima (minima) locaux et globaux des fonctions submodulaires (supermodulaires) peuvent être trouvés dans B. Goldengorin. Journal européen de recherche opérationnelle 198 (1): 102-112, DOI: 10.1016 / j.ejor.2008.08.022

Voir également

• Fonction pseudo-booléenne
• Théorème de Topkis
• Fonction d'ensemble submodulaire
• Superadditif
• Fonctions d'utilité sur des biens indivisibles

Notes et références