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 de enteros . ${\displaystyle \mathbb {Z} ^{n}}$

Los teoremas del punto fijo discreto fueron desarrollados por Iimura, ^[1] Murota y Tamura, ^[2] Chen y Deng ^[3] y otros. Yang ^[4] proporciona una encuesta.

Conceptos básicos

Los teoremas de punto fijo continuo a menudo requieren una función continua . Dado que la continuidad no es significativa para funciones en conjuntos discretos, se reemplaza por condiciones como una función que preserva la dirección . Tales condiciones implican que la función no cambia demasiado drásticamente cuando se mueve entre puntos vecinos de la cuadrícula entera. Existen varias condiciones de preservación de dirección, dependiendo de si los puntos vecinos se consideran puntos de un hipercubo (HGDP), de un simplex (SGDP), etc. Consulte la página sobre la función de preservación de dirección para obtener definiciones.

Los teoremas del punto fijo continuo 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 como para las funciones continuas: es un punto x para el cual f ( x ) = x .

Para funciones en conjuntos discretos

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

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

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

Teoremas de Yang : ^[4]

• [3.6] Si X es un subconjunto finito integralmente convexo de , preserva simplemente la dirección bruta (PIBD) , y para todo x en X existe algún g ( x )>0 tal que , entonces f tiene un punto cero. ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle f:X\to \mathbb {R} ^{n}}$ ${\displaystyle x+g(x)f(x)\in {\text{ch}}(X)}$
• [3.7] Si X es un subconjunto hipercúbico finito de , con punto mínimo a y punto máximo b , es PIBD, y para cualquier x en X : y , entonces f tiene un punto cero. Este es un análogo discreto del teorema de Poincaré-Miranda . Es consecuencia del teorema anterior. ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle f:X\to \mathbb {R} ^{n}}$ ${\displaystyle f_{i}(x_{1},\ldots ,x_{i-1},a_{i},x_{i+1},\ldots ,x_{n})\leq 0}$ ${\displaystyle f_{i}(x_{1},\ldots ,x_{i-1},b_{i},x_{i+1},\ldots ,x_{n})\geq 0}$
• [3.8] Si X es un subconjunto finito integralmente convexo de , y es tal que es SGDP , entonces f tiene un punto fijo. ^[5] Este es un análogo discreto del teorema del punto fijo de Brouwer . ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle f:X\to {\text{ch}}(X)}$ ${\displaystyle f(x)-x}$
• [3.9] Si X = , está acotado y es SGDP, entonces f tiene un punto fijo (esto se desprende fácilmente del teorema anterior al tomar X como un subconjunto de esos límites f ). ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle f:X\to \mathbb {R} ^{n}}$ ${\displaystyle f(x)-x}$ ${\displaystyle \mathbb {Z} ^{n}}$
• [3.10] Si X es un subconjunto finito integralmente convexo de , un mapeo punto a conjunto , y para todo x en X : , y hay una función f tal que y es SGDP, entonces hay un punto y en X tal que . 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 . ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle F:X\to 2^{X}}$ ${\displaystyle F(x)={\text{ch}}(F(x))\cap \mathbb {Z} ^{n}}$ ${\displaystyle f(x)\in {\text{ch}}(F(x))}$ ${\displaystyle f(x)-x}$ ${\displaystyle y\in F(y)}$
• [3.12] Supongamos que X es un subconjunto finito integralmente convexo de , y también es simétrico en el sentido de que x está en X si - x está en X . Si el SGDP es una triangulación débilmente simétrica de ch( X ) (en el sentido de que si s es un símplex en el límite de la triangulación si - s es), y para cada par de puntos x , y conectados de manera simple en el límite de ch( X ), entonces f tiene un punto cero. ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle f:X\to \mathbb {R} ^{n}}$ ${\displaystyle f(x)\cdot f(-y)\leq 0}$
• Consulte la encuesta ^[4] para obtener más teoremas.

Para funciones discontinuas en conjuntos continuos

Los teoremas de punto fijo discretos están estrechamente relacionados con los teoremas de punto fijo sobre funciones discontinuas. Éstos también utilizan la condición de preservació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 . Sea f : X → X una función que preserva la dirección localmente bruta (LGDP) : en cualquier punto x que no sea un punto fijo de f , la dirección de se conserva groseramente en alguna vecindad de x , en el sentido de que para dos puntos cualesquiera y , z en esta vecindad, su producto interno no es negativo, es decir: . Entonces f tiene un punto fijo en X . ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle f(x)-x}$ ${\displaystyle (f(y)-y)\cdot (f(z)-z)\geq 0}$

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

Aplicaciones

Se han utilizado teoremas discretos del punto fijo 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]

Referencias

1. Iimura, Takuya (1 de septiembre de 2003). "Un teorema del punto fijo discreto y sus aplicaciones". Revista de Economía Matemática . 39 (7): 725–742. doi :10.1016/S0304-4068(03)00007-7. ISSN  0304-4068.
2. Iimura, Takuya; Murota, Kazuo; Tamura, Akihisa (1 de diciembre de 2005). "Reconsideración del teorema del punto fijo discreto". Revista de Economía Matemática . 41 (8): 1030–1036. doi :10.1016/j.jmateco.2005.03.001. ISSN  0304-4068.
3. Chen, Xi; Deng, Xiaotie (2006). "Un enfoque simple para teoremas de punto fijo discreto". En Chen, Danny Z.; Lee, DT (eds.). Computación y Combinatoria . Apuntes de conferencias sobre informática. vol. 4112. Berlín, Heidelberg: Springer. págs. 3–12. doi :10.1007/11809678_3. ISBN 978-3-540-36926-4.
4. Yang, Zaifu (1 de diciembre de 2009) [2004 (documento de trabajo n.º 210 de Logística de Amazon, Universidad Nacional de Yokohama)]. "Análisis discreto de punto fijo y sus aplicaciones". Revista de teoría y aplicaciones del punto fijo . 6 (2): 351–371. doi :10.1007/s11784-009-0130-9. ISSN  1661-7746. S2CID  122640338.
5. Yang, Zaifu (1 de noviembre de 2008). "Sobre las soluciones de complementariedad no lineal discreta y problemas relacionados". Matemáticas de la Investigación de Operaciones . 33 (4): 976–990. doi :10.1287/moor.1080.0343. ISSN  0364-765X.
6. Jean-Jacques Herings, P.; van der Laan, Gerard; Talman, Dolf; Yang, Zaifu (1 de enero de 2008). "Un teorema del punto fijo para funciones discontinuas". Cartas de investigación operativa . 36 (1): 89–93. doi :10.1016/j.orl.2007.03.008. hdl : 10419/86189 . ISSN  0167-6377. S2CID  14117444.
7. Bich, Philippe (2006). "Algunos teoremas de punto fijo para asignaciones discontinuas". Cahiers de la Maison des Sciences Économiques .
8. Iimura, Takuya; Yang, Zaifu (1 de diciembre de 2009). "Un estudio sobre las correspondencias de demanda y respuesta ante la presencia de indivisibilidades". Revista de teoría y aplicaciones del punto fijo . 6 (2): 333–349. doi :10.1007/s11784-009-0131-8. ISSN  1661-7746. S2CID  121519442.