Supermodulär funktion

I matematik , en funktion

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

är supermodulär om

f(x\uparrow y)+f(x\downarrow y)\geq f(x)+f( y)

för alla $x$ , $y\in \mathbb {R} ^{k}$ , där $x\uparrow y$ anger det komponentmässiga maximum och $x\downarrow y$ komponentmässigt minimum av $x$ och $y$ .

Om − f är supermodulär kallas f submodulär , och om olikheten ändras till en likhet är funktionen modulär .

Om f är två gånger kontinuerligt differentierbar, är supermodularitet ekvivalent med villkoret

{\frac {\partial ^{2}f}{\partial z_{i}\,\partial z_{j}}}\geq 0{\mbox{ för alla }}i\neq j.

Supermodularitet i ekonomi och spelteori

Begreppet supermodularitet används inom samhällsvetenskapen för att analysera hur en agents beslut påverkar andras incitament.

Tänk på ett symmetriskt spel med en jämn utdelningsfunktion $\,f$ definierad över åtgärder $\,z_{i}$ för två eller flera spelare $i \i {1,2,\dots ,N}$ . Antag att handlingsutrymmet är kontinuerligt; För enkelhetens skull, anta att varje åtgärd är vald från ett intervall: $z_{i}\in [a,b]$ . I detta sammanhang innebär supermodularitet av ${\displaystyle \,f} att en ökning av spelaren$ $\,i$ s val $\,z_{i}$ ökar den marginella vinsten $df/dz_{j}$ av action $\,z_{j}$ för alla andra spelare $\,j$ . Det vill säga, om någon spelare $\,i$ väljer en högre ${\displaystyle \,z_{i}}, har$ alla andra spelare $\,j$ ett incitament att höja sina val $\,z_{j}$ också. Efter terminologin i Bulow, Geanakoplos och Klemperer (1985) kallar ekonomer denna situation för strategisk komplementaritet , eftersom spelarnas strategier är komplement till varandra. Detta är den grundläggande egenskapen bakom exemplen på multipla jämvikter i koordinationsspel .

Det motsatta fallet av supermodularitet av ${\displaystyle \,f} ,$ kallad submodularitet, motsvarar situationen med strategisk utbytbarhet . En ökning av $\,z_{i}$ sänker den marginella vinsten till alla andra spelares val $\,z_{j}$ , så strategier är substitut. Det vill säga, om $\,i$ väljer en högre $\,z_{i}$ , har andra spelare ett incitament att välja en lägre $\,z_{j}$ .

Till exempel har Bulow et al. överväga samspelet mellan många ofullständigt konkurrenskraftiga företag. När en ökning av produktionen från ett företag höjer de andra företagens marginella intäkter, är produktionsbeslut strategiska komplement. När en ökning av produktionen av ett företag sänker marginalintäkterna för de andra företagen, är produktionsbeslut strategiska substitut.

En supermodulär nyttofunktion är ofta relaterad till kompletterande varor . Denna uppfattning är dock omtvistad.

Submodulära funktioner för delmängder

Supermodularitet och submodularitet definieras också för funktioner som definieras över delmängder av en större uppsättning. Intuitivt visar en submodulär funktion över delmängderna "minskande avkastning". Det finns specialiserade tekniker för att optimera submodulära funktioner.

Låt S vara en ändlig mängd. En funktion $f\colon 2^{S}\to \mathbb {R}$ är submodulär om för någon $A\subset B\subset S$ och $x\in S\setminus B$ , $f(A\ kopp \{x\})-f(A)\geq f(B\kopp \{x\})-f(B)$ . För supermodularitet är ojämlikheten omvänd.

Definitionen av submodularitet kan på motsvarande sätt formuleras som

f(A)+f(B)\geq f(A\cap B)+f(A\cup B)

för alla delmängder A och B av S .

Teori och uppräkningsalgoritmer för att hitta lokala och globala maxima (minima) för submodulära (supermodulära) funktioner finns i B. Goldengorin. European Journal of Operational Research 198(1):102-112, DOI: 10.1016/j.ejor.2008.08.022

Se även

Anteckningar och referenser