Diskret fixpunktssats

I diskret matematik är en diskret fixpunkt en fixpunkt för funktioner definierade på finita mängder, typiskt delmängder av heltalsrutnätet $\mathbb {Z} ^{n}$ .

Diskreta fixpunktssatser utvecklades av Iimura, Murota och Tamura, Chen och Deng och andra. Yang tillhandahåller en undersökning.

Grundläggande koncept

Kontinuerliga fixpunktssatser kräver ofta en kontinuerlig funktion . Eftersom kontinuitet inte är meningsfullt för funktioner på diskreta uppsättningar ersätts den av villkor som en riktningsbevarande funktion . Sådana förhållanden innebär att funktionen inte ändras för drastiskt när man förflyttar sig mellan angränsande punkter i heltalsrutnätet. Det finns olika riktningsbevarande villkor, beroende på om närliggande punkter betraktas som punkter i en hyperkub (HGDP), av en simplex (SGDP) etc. Se sidan om riktningsbevarande funktion för definitioner.

Kontinuerliga fixpunktssatser kräver ofta en konvex uppsättning . Analogen av denna egenskap för diskreta uppsättningar är en integrerat konvex uppsättning .

För funktioner på diskreta set

Vi fokuserar på funktionerna ${\displaystyle f:X\to \mathbb {R} ^{n}} ,$ där domänen X är en icke-tom delmängd av det euklidiska rummet $\mathbb {R } ^{n}$ . ch( X ) betecknar det konvexa skrovet på X .

Iimura-Murota-Tamura-satsen : Om X är en ändlig integralt-konvex delmängd av $\mathbb {Z} ^{n}$ och $f:X\to {\text{ch}}(X)$ är en hyperkubisk riktningsbevarande (HDP) funktion, då har f en fixpunkt.

Chen-Dengs sats : Om X är en ändlig delmängd av $\mathbb {R} ^{n}$ , och $f:X\to {\text{ch }}(X)$ är helt enkelt riktningsbevarande (SDP) , då har f en fixpunkt.

Yangs satser :

• [3.6] Om X är en finit integrerad konvex delmängd av $\mathbb {Z} ^{n}$ , $f:X\to \mathbb {R} ^{ n}$ är helt enkelt grov riktningsbevarande (SGDP) , och för alla x i X finns det några g ( x )>0 så att $x+g (x)f(x)\in {\text{ch}}(X)$ , då har f en nollpunkt.
• [3.7] Om X är en ändlig hyperkubisk delmängd av $\mathbb {Z} ^{n}$ , med minimipunkt a och maximal punkt b , $f:X\to \mathbb {R} ^{n}$ är SGDP, och för valfritt x i X : $f_{i}(x_{1},\ldots ,x_{i-1},a_{i},x_{i+1},\ldots,x_{n})\leq 0$ och $f_{i}(x_{1},\ldots ,x_{i-1},b_{i}, x_{i+1},\ldots ,x_{n})\geq 0$ , då har f en nollpunkt. Detta är en diskret analog till Poincaré-Miranda-satsen . Det är en konsekvens av föregående sats.
• [3.8] Om X är en finit integrerad konvex delmängd av $\mathbb {Z} ^{n}$ och $f:X\to {\text{ ch}}(X)$ är sådan att $f(x)-x$ är SGDP , då har f en fixpunkt. Detta är en diskret analog till Brouwers fixpunktssats .
• [3.9] Om X = $\mathbb {Z} ^{n}$ , $f:X\to \mathbb {R} ^{n}$ avgränsad och $f(x)-x$ är SGDP, då har f en fixpunkt (detta följer lätt av föregående sats genom att ta X som en delmängd av $\mathbb {Z } ^{n}$ som begränsar f ).
• [3.10] Om X är en ändlig integralt-konvex delmängd av $\mathbb {Z} ^{n}$ , $F:X\to 2^{X}$ a punkt-till-uppsättning mappning , och för alla x i X : $F(x)={\text{ch}}(F(x)) \cap \mathbb {Z} ^{n}$ , och det finns en funktion f så att $f(x)\in {\text{ch}}( F(x))$ och $f(x)-x$ är SGDP, då finns det en punkt y i X så att $y\in F( y)$ . Detta är en diskret analog till Kakutanis fixpunktsats , och funktionen f är en analog till en kontinuerlig urvalsfunktion .
• [3.12] Antag att X är en ändlig integralt-konvex delmängd av ${\displaystyle \mathbb {Z} ^{n}} ,$ och den är också symmetrisk i den meningen att x är i X om - x är i X . Om $f:X\to \mathbb {R} ^{n}$ är SGDP med en svagt symmetrisk triangulering av ch( X ) (i den meningen att om s är en simplex på gränsen för trianguleringen iff - s är), och $f(x)\cdot f(-y)\leq 0$ för varje par av enkelt sammankopplade punkter x , y i gränsen för ch( X ), då har f en nollpunkt.
• Se undersökningen för fler satser.

För diskontinuerliga funktioner på kontinuerliga uppsättningar

Diskreta fixpunktssatser är nära besläktade med fixpunktssatser om diskontinuerliga funktioner. Även dessa använder riktningsbevarande villkoret istället för kontinuitet.

Herings-Laan-Talman-Yang fixpunktssats :

Låt X vara en icke-tom konvex kompakt delmängd av $\mathbb {R} ^{n}$ . Låt f : X → X vara en lokalt grov riktningsbevarande (LGDP) funktion: vid vilken punkt x som helst som inte är en fixpunkt för f , är riktningen för $f(x)-x$ grovt bevarad i någon omgivning av x , i den meningen att för alla två punkter y , z i detta grannskap är dess inre produkt icke-negativ, dvs: $(f(y)-y)\cdot (f(z)-z)\geq 0$ . Då f en fixpunkt i X .

Satsen anges ursprungligen för polytoper, men Philippe Bich utvidgar den till konvexa kompakta mängder, jfr sats 3.7 i sin artikel "Some fixed point theorems for discontinuous mappings".

Observera att varje kontinuerlig funktion är LGDP, men en LGDP-funktion kan vara diskontinuerlig. En LGDP-funktion kan till och med vara varken övre eller nedre halvkontinuerlig . Dessutom finns det en konstruktiv algoritm för att approximera denna fixpunkt.

Ansökningar

Diskreta fixpunktsteorem har använts för att bevisa förekomsten av en Nash-jämvikt i ett diskret spel, och förekomsten av en Walrasian-jämvikt på en diskret marknad.