離散不動点定理

離散数学において、離散固定点とは、有限集合、通常は整数グリッドのサブセット上で定義された関数の固定点です。 ${\displaystyle \mathbb {Z} ^{n}}$

離散不動点定理は、飯村^[1]、室田と田村^[2] 、陳と鄧^[3]らによって開発されました。楊^[4]は概要を示しています。

連続不動点定理は、連続関数を必要とすることがよくあります。離散集合上の関数では連続性は意味をなさないため、方向保存関数などの条件で置き換えられます。このような条件は、整数グリッドの隣接点間を移動するときに関数があまり劇的に変化しないことを意味します。隣接点が超立方体の点 (HGDP) と見なされるか、単体の点 (SGDP) と見なされるかなどによって、さまざまな方向保存条件があります。定義については、 方向保存関数のページを参照してください。

連続不動点定理では、凸集合が必要になることがよくあります。離散集合の場合のこの性質の類似物は、積分凸集合です。

離散関数fの不動点は連続関数の場合とまったく同じように定義されます。つまり、 f ( x )= xとなる点xです。

ここでは関数に注目します 。ここで、ドメイン X はユークリッド空間の空でない部分集合です。ch( X ) はXの凸包を表します。 ${\displaystyle f:X\to \mathbb {R} ^{n}}$${\displaystyle \mathbb {R} ^{n}}$

飯村・室田・田村の定理: ^[2] Xがの有限の凸集合であり、が超三次方向保存(HDP)関数である場合、fは不動点を持つ。 ${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle f:X\to {\text{ch}}(X)}$

陳鄧定理: ^[3] Xがの有限部分集合であり、かつ単体方向保存(SDP)である 場合、fは不動点を持つ。 ${\displaystyle \mathbb {R} ^{n}}$${\displaystyle f:X\to {\text{ch}}(X)}$

ヤンの定理：^[4]

• [3.6] Xがの有限の整凸部分集合であり、 が単体的総方向保存(SGDP)であり、X内のすべてのxに対して、となるg ( x )>0が存在する場合、fは零点を持つ。${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle f:X\to \mathbb {R} ^{n}}$${\displaystyle x+g(x)f(x)\in {\text{ch}}(X)}$
• [3.7] Xが の有限超立方部分集合で、最小点aと最大点bを持つ場合、は SGDP であり、X内の任意のxに対して、かつである場合、f は零点を持つ。これはポアンカレ-ミランダの定理の離散類似物である。これは前の定理の帰結である。${\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] Xが の有限の整凸部分集合であり、がSGDPとなるような場合、fには不動点がある。^[5]これはBrouwer の不動点定理の離散類似である。${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle f:X\to {\text{ch}}(X)}$${\displaystyle f(x)-x}$
• [3.9] X = が有界でありSGDPである場合、 fは不動点を持ちます（これは、X をその有界fのサブセットとすることで、前の定理から簡単にわかります）。${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle f:X\to \mathbb {R} ^{n}}$${\displaystyle f(x)-x}$${\displaystyle \mathbb {Z} ^{n}}$
• [3.10] Xが の有限の整凸部分集合、点から集合への写像、X内のすべてのxに対して であり、かつ となる関数fが存在し、かつが SGDP である場合、 X内にとなる点yが存在する。これは角谷不動点定理の離散類似であり、関数f は連続選択関数の類似である。${\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] Xが の有限の整凸部分集合であり、xがXに含まれる場合とx がXに含まれる場合で対称であるとする。 がch( X ) の弱対称三角分割に関して SGDP である場合 ( s が三角分割の境界上の単体である場合とsが単体である場合で)、 ch( X )の境界内の単体連結点x、yのすべてのペアに対して、f は零点を持つ。${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle f:X\to \mathbb {R} ^{n}}$${\displaystyle f(x)\cdot f(-y)\leq 0}$
• さらなる定理については調査^[4]を参照してください。

離散不動点定理は、不連続関数の不動点定理と密接に関連しています。これらも、連続性の代わりに方向保存条件を使用します。

ヘリングス-ラン-タルマン-ヤンの不動点定理: ^[6]

X をの空でない凸コンパクト部分集合とします。f : X → X を局所的に大まかな方向保存 (LGDP)関数とします 。つまり、 fの固定点ではない任意の点xにおいて、 の方向はxの近傍で大まかに保存されます。つまり、この近傍の任意の 2 点y、zに対して、その内積が非負になります (つまり、 ) 。このとき、 f はX内に固定点を持ちます。 ${\displaystyle \mathbb {R} ^{n}}$${\displaystyle f(x)-x}$${\displaystyle (f(y)-y)\cdot (f(z)-z)\geq 0}$

この定理はもともと多面体に対して述べられたものですが、フィリップ・ビッチはそれを凸コンパクト集合に拡張しました。^{[7] : Thm.3.7}すべての連続関数はLGDPですが、LGDP関数は不連続になる可能性があることに注意します。LGDP関数は、上半連続でも下半連続でもない場合があります。さらに、この固定点を近似するための構成的アルゴリズムがあります。

離散不動点定理は、離散ゲームにおけるナッシュ均衡の存在や、離散市場におけるワルラス均衡の存在を証明するために使われてきた。 ^[8]