Función supermodular

En matemáticas, una función supermodular es una función en un retículo que, informalmente, tiene la propiedad de estar caracterizada por "diferencias crecientes". Vista desde el punto de vista de las funciones de conjunto , esto también puede verse como una relación de "rendimientos crecientes", donde agregar más elementos a un subconjunto aumenta su valoración. En economía , las funciones supermodulares se utilizan a menudo como una expresión formal de complementariedad en las preferencias entre bienes. Las funciones supermodulares se estudian y tienen aplicaciones en la teoría de juegos , la economía , la teoría de retículos , la optimización combinatoria y el aprendizaje automático .

Sea una red . Una función de valor real se llama supermodular si ${\displaystyle (X,\preceq)}$${\displaystyle f:X\rightarrow \mathbb {R}}$${\displaystyle f(x\vee y)+f(x\wedge y)\geq f(x)+f(y)}$

para todos ^[1] . ${\displaystyle x,y\en X}$

Si la desigualdad es estricta, entonces es estrictamente supermodular en . Si es (estrictamente) supermodular entonces f se llama ( estrictamente) submodular . Una función que es tanto submodular como supermodular se llama modular . Esto corresponde a que la desigualdad se transforme en una igualdad. ${\estilo de visualización f}$${\estilo de visualización X}$${\estilo de visualización -f}$

También podemos definir funciones supermodulares donde la red subyacente es el espacio vectorial . Entonces la función es supermodular si ${\displaystyle \mathbb {R} ^{n}}$${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$

${\displaystyle f(x\flecha arriba y)+f(x\flecha abajo y)\geq f(x)+f(y)}$

para todos , , donde denota el máximo por componentes y el mínimo por componentes de y . ${\estilo de visualización x}$${\displaystyle y\in \mathbb {R} ^{n}}$${\displaystyle x\flecha arriba y}$${\displaystyle x\flecha abajo y}$${\estilo de visualización x}$${\estilo de visualización y}$

Si f es dos veces continuamente diferenciable, entonces la supermodularidad es equivalente a la condición ^[2]

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

El concepto de supermodularidad se utiliza en las ciencias sociales para analizar cómo la decisión de un agente afecta los incentivos de los demás.

Consideremos un juego simétrico con una función de pago suave definida sobre las acciones de dos o más jugadores . Supongamos que el espacio de acciones es continuo; para simplificar, supongamos que cada acción se elige de un intervalo: . En este contexto, la supermodularidad de implica que un aumento en la elección del jugador aumenta el pago marginal de la acción para todos los demás jugadores . Es decir, si cualquier jugador elige un mayor , todos los demás jugadores tienen un incentivo para aumentar también sus elecciones. Siguiendo la terminología de Bulow, Geanakoplos y Klemperer (1985), los economistas llaman a esta situación complementariedad estratégica , porque las estrategias de los jugadores son complementarias entre sí. ^[3] Esta es la propiedad básica que subyace a los ejemplos de equilibrios múltiples en juegos de coordinación . ^[4]${\estilo de visualización \,f}$${\displaystyle \,z_{i}}$${\displaystyle i\in {1,2,\puntos ,N}}$${\displaystyle z_{i}\en [a,b]}$${\estilo de visualización \,f}$${\estilo de visualización \,i}$${\displaystyle \,z_{i}}$$Estilo de visualización: df/dz_{j}$${\estilo de visualización \,z_{j}}$${\estilo de visualización \,j}$${\estilo de visualización \,i}$${\displaystyle \,z_{i}}$${\estilo de visualización \,j}$${\estilo de visualización \,z_{j}}$

El caso opuesto de supermodularidad de , llamado submodularidad, corresponde a la situación de sustituibilidad estratégica . Un aumento de , reduce la recompensa marginal de todas las elecciones de los demás jugadores , por lo que las estrategias son sustitutivas. Es decir, si elige una , los demás jugadores tienen un incentivo para elegir una . ${\estilo de visualización \,f}$${\displaystyle \,z_{i}}$${\estilo de visualización \,z_{j}}$${\estilo de visualización \,i}$${\displaystyle \,z_{i}}$ ${\estilo de visualización \,z_{j}}$

Por ejemplo, Bulow et al. consideran las interacciones de muchas empresas imperfectamente competitivas . Cuando un aumento de la producción de una empresa eleva los ingresos marginales de las otras, las decisiones de producción son complementos estratégicos. Cuando un aumento de la producción de una empresa reduce los ingresos marginales de las otras, las decisiones de producción son sustitutos estratégicos.

Una función de utilidad supermodular suele estar relacionada con bienes complementarios . Sin embargo, esta visión es controvertida. ^[5]

La supermodularidad también se puede definir para funciones de conjunto , que son funciones definidas sobre subconjuntos de un conjunto mayor. Muchas propiedades de las funciones de conjunto submodulares se pueden reformular para aplicarlas a funciones de conjunto supermodulares.

Intuitivamente, una función supermodular sobre un conjunto de subconjuntos demuestra "rendimientos crecientes". Esto significa que si a cada subconjunto se le asigna un número real que corresponde a su valor, el valor de un subconjunto siempre será menor que el valor de un subconjunto mayor que lo contenga. Alternativamente, esto significa que a medida que agregamos elementos a un conjunto, aumentamos su valor.

Sea un conjunto finito. Una función de conjunto es supermodular si satisface las siguientes condiciones (equivalentes) ^[6] : ${\estilo de visualización S}$${\displaystyle f:2^{S}\to \mathbb {R} }$

1. ${\displaystyle f(A)+f(B)\leq f(A\cap B)+f(A\cup B)}$Para todos .${\displaystyle A,B\subseteq S}$
2. ${\displaystyle f(A\cup \{v\})-f(A)\leq f(B\cup \{v\})-f(B)}$para todos , donde .${\displaystyle A\subconjunto B\subconjunto V}$${\displaystyle v\notin B}$

Una función de conjunto es submodular si es supermodular, y modular si es a la vez supermodular y submodular. ${\estilo de visualización f}$${\estilo de visualización -f}$

• Si es modular y es submodular, entonces es una función supermodular.${\estilo de visualización f}$${\estilo de visualización g}$${\estilo de visualización fg}$
• Una función supermodular no negativa también es una función superaditiva.

Existen técnicas especializadas para optimizar funciones submodulares. La teoría y los algoritmos de enumeración para encontrar máximos (mínimos) locales y globales de funciones submodulares (supermodulares) se pueden encontrar en "Maximización de funciones submodulares: teoría y algoritmos de enumeración", B. Goldengorin. ^[7]

• Función pseudo-booleana
• Teorema de Topkis
• Función de conjunto submodular
• Superaditivo
• Funciones de utilidad sobre bienes indivisibles