Teorema do ponto fixo de Kakutani

Na análise matemática , o teorema do ponto fixo de Kakutani é um teorema do ponto fixo que generaliza o de Brouwer para funções com valores definidos . Fornece condição suficiente para que tal função, definida sobre um compacto convexo de um espaço euclidiano , tenha um ponto fixo , isto é, neste contexto: um ponto que pertence à sua imagem por esta função.

Este teorema foi demonstrado por Shizuo Kakutani em 1941 e popularizado por John Forbes Nash , que o usou em sua descrição do equilíbrio de Nash . Desde então, teve muitas aplicações na teoria e economia dos jogos .

Estados

A declaração do teorema de Kakutani é a seguinte:

Seja S um compacto convexo nonempty um espaço euclidiano e S φ de aplicação nas inteiros 2 S partes do S . Se o gráfico de φ é fechado em S × S e se, para qualquer ponto x de S, φ ( x ) é um convexo não vazio, então φ tem um ponto fixo .

Nesta declaração, por definição:

o gráfico de φ é o conjunto de pares ( x , y ) de S × S tais que y ∈ φ ( x );
um ponto fixo de φ é um elemento x de S tal que x ∈ φ ( x ).

Declaração equivalente

Algumas fontes, incluindo o artigo original de Kakutani, trazem em jogo a noção de hemicontinuidade superior, definida por:

Uma aplicação φ: X → 2 Y é superiormente hegemônica se, para qualquer W aberto a Y , o conjunto de pontos x para os quais φ ( x ) está incluído em W for um X aberto .

O teorema pode então ser reformulado como:

Seja S um compacto convexo não vazio de um espaço euclidiano e φ: S → 2 S um mapa semicontínuo superior. Se, para qualquer ponto x de S, φ ( x ) é um convexo fechado não vazio, então φ tem um ponto fixo.

Esta variante é equivalente à afirmação anterior porque, de acordo com o teorema do gráfico fechado para funções com valores definidos , para qualquer Y compacto , o gráfico de um mapa φ: X → 2 Y é fechado se e somente se φ for superiormente semicontínuo e todos os φ ( x ) são fechados.

Exemplo e contra-exemplos

O S compacto convexo considerado aqui é o intervalo [0, 1].

Exemplo

A aplicação φ definida por φ ( x ) = [1 - x / 2, 1 - x / 4] satisfaz as hipóteses do teorema, portanto deve ter pontos fixos. Podemos verificar por resolução direta: 1 - x / 2 ≤ x ≤ 1 - x / 4 é equivalente a 2/3 ≤ x ≤ 4/5.

Contra-exemplo no caso não convexo

A suposição de que os φ ( x ) são convexos é essencial neste teorema: seja φ definido por

\ varphi (x) = {\ begin {cases} \ {3/4 \} & {\ text {si}} \ quad 0 \ leq x <1/2 \\\ {3 / 4,1 / 4 \} & {\ text {si}} \ quad x = 1/2 \\\ {1/4 \} & {\ text {si}} \ quad 1/2 <x \ leq 1. \ end {cases}}

Esta função não tem ponto fixo. Ele satisfaz todas as suposições do teorema, exceto a convexidade de φ (1/2).

Contra-exemplo no caso não fechado

O mapa φ definido por φ ( x ) = [ x / 3, 2 x / 3] se x > 0 e φ (0) =] 0, 1] não tem ponto fixo. É superiormente semicontínuo e com valores convexos não vazios, mas seu gráfico não é fechado porque φ (0) não é.

Formulários

Teoria do jogo

O matemático John Forbes Nash usou o teorema do ponto fixo de Kakutani para demonstrar um teorema principal da teoria dos jogos , uma consequência do qual é a existência de um equilíbrio de Nash em qualquer jogo de estratégia mista infinito , independentemente do número n de jogadores. Este trabalho rendeu-lhe o “ Prêmio Nobel de Economia ”.

Neste caso, S é o conjunto de n -tuplas de estratégias que os n jogadores podem escolher e φ ( x ) é o conjunto de n- duplas de estratégias ótimas (não necessariamente únicas) para cada jogador, em resposta à escolha de outro jogadores em estratégia mista x . O equilíbrio de Nash de um jogo é um ponto fixo de φ , ou seja, um n -tuplo de estratégias em que cada componente é uma resposta ótima do jogador, correspondendo à escolha dos outros componentes pelos outros jogadores. O teorema de Kakutani assegura a existência de tal ponto fixo.

Equilíbrio geral

Na teoria econômica de equilíbrio geral , o teorema de Kakutani foi usado para demonstrar a existência de preços que correspondem à oferta e à demanda em todos os mercados de uma economia. A questão da existência de tais preços remontava pelo menos a Léon Walras . A primeira prova foi fornecida por Lionel McKenzie . O teorema de Kakutani é um fundamento essencial da “teoria do valor” de Gérard Debreu (economista franco-americano cujo trabalho recebeu o “ Prêmio Nobel de Economia ”).

Nesse caso, S é o conjunto de n tuplas de preços de commodities. A função φ é escolhida de forma que o resultado φ ( x ) difira do argumento x assim que o preço n- duplo x não iguala oferta e demanda em todos os lugares. O desafio aqui é construir um mapa φ verificando esta propriedade e as hipóteses do teorema de Kakutani. Tal φ , se existir, terá então um ponto fixo que, por construção, igualará a oferta com a demanda em todos os lugares.

Plano da prova

(Para outra prova, consulte a próxima seção.)

Caso de um segmento

A prova é muito mais simples quando S é um segmento da linha real, mas este caso particular é instrutivo porque sua estratégia geral se adapta a dimensões superiores.

Seja φ : [0, 1] → 2 [0, 1] um mapa que satisfaça as hipóteses do teorema.

Primeira etapa. Construímos em [0, 1] duas sequências adjacentes ( a i ), ( b i ) ( i = 0, 1, ...) tais que b i - a i ≤ 2 - i e tal que exista p i ∈ φ ( a i ) eq i ∈ φ ( b i ) satisfazendo: p i ≥ a i e q i ≤ b i . Esta construção é realizada por indução . Estabelecemos a 0 = 0, b 0 = 1, p 0 = qualquer ponto de φ (0) e q 0 = qualquer ponto de φ (1). Então, assumindo a k , b k , p k , q k já construídos, definimos m = ( a k + b k ) / 2 .
- Se existe um r ∈ φ ( m ) tal que r ≥ m , podemos escolher
  - $a_ {k + 1} = m, ~ b_ {k + 1} = b_ {k}, ~ p_ {k + 1} = r, ~ q_ {k + 1} = q_ {k}.$
- Caso contrário, como φ ( m ) não é vazio, existe necessariamente um s ∈ φ ( m ) tal que s ≤ m . Neste caso, nós escolhemos
  - $a_ {k + 1} = a_ {k}, ~ b_ {k + 1} = m, ~ p_ {k + 1} = p_ {k}, ~ q_ {k + 1} = s.$
Segundo passo. Focamos em um valor de adesão ( a, b, p, q ) desta sequência de quádruplos ( a i , b i , p i , q i ) (existem alguns, de acordo com o significado direto do teorema de Bolzano- Weierstrass , aplicado ao compacto [0, 1] 4 ). Por construção, temos q ≤ b = a ≤ p . Além disso ( como o gráfico de φ é fechado ), p ∈ φ ( a ) eq ∈ φ ( b ). Observando x o elemento a = b , podemos resumir a situação da seguinte forma:

q, p \ in \ varphi (x) \ quad {\ text {e}} \ quad q \ leq x \ leq p.

Pela convexidade de φ ( x ), deduzimos que x pertence a φ ( x ), ou seja, x é um ponto fixo de φ .

Caso de um simplex

Na dimensão n > 1, o método é essencialmente o mesmo se S for um n - simplex . A única adaptação está na primeira etapa:

em vez de cortar pela metade um intervalo pelo seu meio como na dimensão 1, usamos uma subdivisão baricêntrica (em) para cortar o simplex em sub-simplexes menores.
em vez dos argumentos elementares que permitiam, na dimensão 1, escolher um dos meios-intervalos de forma que os extremos formem duas sequências, uma crescente e outra decrescente, na dimensão superior é o lema de Sperner que garantirá a existência de um sub-simplex apropriado.

Caso Geral

Se S (não vazia) é um compacto dimensão de convexa n de espaço euclidiano, podemos assumir sempre que a dimensão do espaço é também N , e 0 é interior a S . Em seguida, escolhemos um n -simplex S ' contendo S , e estendemos o mapa φ: S → 2 S em um mapa φ': S ' → 2 S' , escolhendo φ ' radialmente constante no complemento do interior de S . Então, se ( S, φ ) satisfez as hipóteses do teorema de Kakutani, ( S ', φ' ) também as verificará, portanto (de acordo com o caso anterior aplicado ao simplexo S ' ) φ' terá um ponto fixo x ∈ φ ' ( x ). Mas como todas as imagens por φ ' estão incluídas em S , x então pertence a S , então φ' ( x ) = φ ( x ) e x é um ponto fixo para φ .

Generalizações em dimensão infinita

O teorema do ponto fixo de Kakutani foi estendido para separar espaços localmente convexos de dimensão infinita por Ky Fan e Irving Glicksberg.

O teorema Kakutani-Fan-Glicksberg pode ser afirmado da seguinte forma:

Seja S um convexo não vazio compacto de um espaço convexo localmente separado e φ: S → 2 S um mapa semicontínuo superior. Se, para qualquer ponto x de S, φ ( x ) é um convexo fechado não vazio, então φ tem um ponto fixo.

É uma generalização para funções multivaloradas do teorema do ponto fixo de Tychonoff, de acordo com o qual, para qualquer S convexo compacto não vazio de um espaço localmente convexo separado, qualquer mapa contínuo de S a S tem um ponto fixo. O caso de funções multivaloradas pode, como o das aplicações, ser deduzido do teorema do ponto fixo de Brouwer :

Demonstração

Para qualquer vizinhança convexa V de 0, um teorema de seleção aproximada fornece um subespaço vetorial de dimensão finita G V e um mapa contínuo f V : S → S ∩ G V tal que para qualquer ponto z de S , ( z , f V ( z ) ) pertence a Gr (φ) + ( V × V ). O teorema do ponto fixo Brouwer prova a existência em S ∩ L V de um ponto x V fixo f V . Seja x um valor de adesão em S da seqüência generalizada ( x V ). O par ( x , x ) é então aderente ao gráfico de φ, portanto pertence a ele, uma vez que este gráfico é fechado. Portanto, x é um ponto fixo de φ.

Como no caso euclidiano, uma formulação equivalente é:

Seja S um convexo compacto não vazio um espaço convexo localmente separadas e S φ de uma aplicação em duas S . Se o gráfico de φ for fechado e se, para qualquer ponto x de S, φ ( x ) for um convexo não vazio, então o conjunto (compacto) de pontos fixos de φ é não vazio.

ou :

Seja S um convexo não vazio compacto de um espaço convexo localmente separado E e φ: S → 2 E um mapa semicontínuo superior. Se, para qualquer ponto x de S, φ ( x ) é um convexo fechado encontrando S, então φ tem um ponto fixo.

Notas e referências

(pt) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado " Teorema do ponto fixo de Kakutani " ( veja a lista de autores ) .

(em) Shizuo Kakutani , " Uma generalização do teorema do ponto fixo de Brouwer " , Duke Math. J. , vol. 8, n o 3, 1941, p. 457-459 ( DOI 10.1215 / S0012-7094-41-00838-4 ).
(in) JF Nash, Jr. , " Equilibrium Pontos em N-Person Games " , PNAS , vol. 36, n o 1,1950, p. 48-49 ( PMID 16588946 , DOI 10.1073 / pnas.36.1.48 ).
(in) Kim C. Border , Teoremas de Ponto Fixo com Aplicações à Economia e Teoria dos Jogos , UPC ,1989, 129 p. ( ISBN 978-0-521-38808-5 , leitura online ) , cap. 15 ("Teoremas de ponto fixo para correspondências")Referência padrão na teoria do ponto fixo para economistas. Inclui uma prova do teorema de Kakutani p. 71 e s. .
(em) Martin J. Osborne e Ariel Rubinstein , A Course in Game Theory , Cambridge, MA, MIT ,1994( leia online ) , p. 20.
(en) James Dugundji e Andrzej Granas, Teoria do Ponto Fixo , Springer ,2003, 690 p. ( ISBN 978-0-387-00173-9 , leitura online ) , "II, § 7" - Tratamento matemático completo e de alto nível da teoria do ponto fixo, incluindo os análogos em dimensão infinita do teorema de Kakutani.
(em) Ross M. Starr (em) , General Equilibrium Theory: An Introduction , CUP, 1997, 250 p. ( ISBN 978-0-521-56473-1 , leia online ).
(in) Mutiara Sondjaja , Sperner's Lemma Implies Kakutani's Fixed Point Theoreem , Claremont, Harvey Mud College , Thesis,2008( leia online ).
(em) Ky Fan , " Fixed-point and Minimax Theorems in Locally Convex Linear Topological Spaces " , PNAS , vol. 38, n o 2 1952, p. 121-126 ( PMID 16589065 , DOI 10.1073 / pnas.38.2.121 ).
(in) IT Glicksberg , " Uma nova generalização de topo do teorema do ponto fixo de Kakutani com implementação no ponto de equilíbrio de Nash " , Proc. Amargo. Matemática. Soc. , vol. 3, n o 1,1952, p. 170-174 ( ler online ).
(in) Charalambos D. Aliprantis e Kim C. Border Análise Dimensional Infinita: Um Guia do Mochileiro Springer2007, 3 e ed. ( 1 st ed. 1999) ( li on-line ) , p. 583.
Teorema 4 (em) Felix E. Browder , " A teoria de ponto fixo de mapeamentos multivalorados em espaços vetoriais topológicos " , Math. Ann. , vol. 177,1968, p. 283-301 ( ler online )fornece a mesma conclusão sob hipóteses mais fracas e sua prova - ao contrário das de Fan e Glicksberg - não se baseia no teorema de Kakutani, que então se torna um corolário .

Veja também

Bibliografia

(en) Kenneth J. Arrow e FH Hahn , General Competitive Analysis , Holden-Day,1971Referência padrão na teoria do equilíbrio geral . O Capítulo 5 usa o teorema de Kakutani para provar a existência de preços de equilíbrio. O Apêndice C inclui uma prova do teorema de Kakutani e discute sua relação com outros resultados matemáticos usados em economia.
(pt) Felix E. Browder , " Em uma forma aguçada do teorema de ponto fixo de Schauder " , PNAS , vol. 74, n o 11,Novembro de 1977, p. 4749-4751 ( ler online )
(en) Efe A. Ok , Real Analysis with Economics Applications , Princeton University Press ,2007, 802 p. ( ISBN 978-0-691-11768-3 , leitura online ) , cap. E.5.1 (“Continuidade II - Teorema do Ponto Fixo de Kakutani”) , p. 331e [ leia online ] , cap. J.3.1 (“ Espaços lineares normados - Teorema do ponto fixo de Glicksberg-Fan”), p. 623
(pt) Peter Saveliev , “ Pontos fixos e seleções de mapas de valor definido em espaços com convexidade ” , Internat. J. Math. & Matemática. Sci. , vol. 24, n o 9,2000, p. 595-612 ( ler online )

Link externo

(pt) John Hillas, " Fixed Point Theorems " , na University of Auckland