Teorema del punto fijo discreto

En matemáticas discretas , un punto fijo discreto es un punto fijo para funciones definidas en conjuntos finitos, típicamente subconjuntos de la cuadrícula entera.${\displaystyle \mathbb {Z} ^{n}}$.

Los teoremas de punto fijo discreto fueron desarrollados por Iimura, ^{[ 1 ]} Murota y Tamura, ^{[ 2 ]} Chen y Deng ^{[ 3 ]} y otros. Yang ^{[ 4 ]} proporciona una revisión.

Los teoremas de punto fijo continuo suelen requerir una función continua . Dado que la continuidad no tiene sentido para funciones en conjuntos discretos, se reemplaza por condiciones como la de una función que preserva la dirección . Estas condiciones implican que la función no cambia drásticamente al moverse entre puntos vecinos de la cuadrícula entera. Existen diversas condiciones de preservación de la dirección, según si los puntos vecinos se consideran puntos de un hipercubo (HGDP), de un simplex (SGDP), etc. Consulte la página sobre funciones que preservan la dirección para ver las definiciones.

Los teoremas de punto fijo continuos a menudo requieren un conjunto convexo . El análogo de esta propiedad para conjuntos discretos es un conjunto integralmente convexo .

Un punto fijo de una función discreta f se define exactamente igual que para las funciones continuas: es un punto x para el cual f ( x )= x .

Nos centramos en las funciones ${\displaystyle f:X\to \mathbb {R} ^{n}}$donde el dominio X es un subconjunto no vacío del espacio euclidiano${\displaystyle \mathbb {R} ^{n}}$. ch( X ) denota la envoltura convexa de X .

Teorema de Iimura-Murota-Tamura : ^{[ 2 ]} Si X es un subconjunto integralmente convexo finito de${\displaystyle \mathbb {Z} ^{n}}$, y${\displaystyle f:X\to {\text{ch}}(X)}$Si f es una función hipercúbica que conserva la dirección (HDP) , entonces f tiene un punto fijo.

Teorema de Chen-Deng : ^{[ 3 ]} Si X es un subconjunto finito de${\displaystyle \mathbb {R} ^{n}}$, y${\displaystyle f:X\to {\text{ch}}(X)}$Si f es simplicialmente direccionalmente preservada (SDP) , entonces f tiene un punto fijo.

Teoremas de Yang : ^{[ 4 ]}

• [3.6] Si X es un subconjunto finito integralmente convexo de${\displaystyle \mathbb {Z} ^{n}}$, ${\displaystyle f:X\to \mathbb {R} ^{n}}$es simplicialmente grueso preservando la dirección (SGDP) , y para todo x en X existe algún g ( x )>0 tal que${\displaystyle x+g(x)f(x)\in {\text{ch}}(X)}$, entonces f tiene un punto cero.
• [3.7] Si X es un subconjunto hipercúbico finito de${\displaystyle \mathbb {Z} ^{n}}$, con punto mínimo a y punto máximo b ,${\displaystyle f:X\to \mathbb {R} ^{n}}$es SGDP, y para cualquier x en X :${\displaystyle f_{i}(x_{1},\ldots ,x_{i-1},a_{i},x_{i+1},\ldots ,x_{n})\leq 0}$y${\displaystyle f_{i}(x_{1},\ldots ,x_{i-1},b_{i},x_{i+1},\ldots ,x_{n})\geq 0}$Entonces, f tiene un punto cero. Este es un análogo discreto del teorema de Poincaré-Miranda . Es una consecuencia del teorema anterior.
• [3.8] Si X es un subconjunto integralmente convexo finito de${\displaystyle \mathbb {Z} ^{n}}$, y${\displaystyle f:X\to {\text{ch}}(X)}$es tal que${\displaystyle f(x)-x}$es SGDP , entonces f tiene un punto fijo. ^{[ 5 ]} Este es un análogo discreto del teorema del punto fijo de Brouwer .
• [3.9] Si X =${\displaystyle \mathbb {Z} ^{n}}$, ${\displaystyle f:X\to \mathbb {R} ^{n}}$está delimitado y${\displaystyle f(x)-x}$es SGDP, entonces f tiene un punto fijo (esto se deduce fácilmente del teorema anterior tomando X como un subconjunto de${\displaystyle \mathbb {Z} ^{n}}$que limita f ).
• [3.10] Si X es un subconjunto finito integralmente convexo de${\displaystyle \mathbb {Z} ^{n}}$,${\displaystyle F:X\to 2^{X}}$una asignación de punto a conjunto , y para todo x en X :${\displaystyle F(x)={\text{ch}}(F(x))\cap \mathbb {Z} ^{n}}$y existe una función f tal que${\displaystyle f(x)\in {\text{ch}}(F(x))}$y ${\displaystyle f(x)-x}$es SGDP, entonces hay un punto y en X tal que${\displaystyle y\in F(y)}$. Este es un análogo discreto del teorema del punto fijo de Kakutani , y la función f es un análogo de una función de selección continua .
• [3.12] Supongamos que X es un subconjunto finito integralmente convexo de${\displaystyle \mathbb {Z} ^{n}}$y también es simétrico en el sentido de que x está en X si y solo si - x está en X.${\displaystyle f:X\to \mathbb {R} ^{n}}$es SGDP con respecto a una triangulación débilmente simétrica de ch( X ) (en el sentido de que si s es un simplex en el límite de la triangulación si y solo si - s lo es), y${\displaystyle f(x)\cdot f(-y)\leq 0}$para cada par de puntos conectados simplicialmente x , y en el límite de ch( X ), entonces f tiene un punto cero.
• Consulte la encuesta ^{[ 4 ]} para obtener más teoremas.

Los teoremas de punto fijo discretos están estrechamente relacionados con los teoremas de punto fijo para funciones discontinuas. Estos también utilizan la condición de conservación de la dirección en lugar de la continuidad.

Teorema del punto fijo de Herings-Laan-Talman-Yang : ^{[ 6 ]}

Sea X un subconjunto compacto convexo no vacío de${\displaystyle \mathbb {R} ^{n}}$. Sea f : X → X una función localmente gruesa que preserva la dirección (LGDP) : en cualquier punto x que no sea un punto fijo de f , la dirección de${\displaystyle f(x)-x}$se conserva en gran medida en algún entorno de x , en el sentido de que para cualesquiera dos puntos y , z en este entorno, su producto interno es no negativo, es decir:${\displaystyle (f(y)-y)\cdot (f(z)-z)\geq 0}$. Entonces f tiene un punto fijo en X .

El teorema se enuncia originalmente para politopos, pero Philippe Bich lo extiende a conjuntos compactos convexos. ^{[ 7 ] : Thm.3.7} Nótese que toda función continua es LGDP, pero una función LGDP puede ser discontinua. Una función LGDP incluso puede no ser ni semicontinua superior ni inferiormente . Además, existe un algoritmo constructivo para aproximar este punto fijo.

Los teoremas de punto fijo discreto se han utilizado para demostrar la existencia de un equilibrio de Nash en un juego discreto y la existencia de un equilibrio walrasiano en un mercado discreto. ^{[ 8 ]}