角谷の不動点定理
表示
数学の解析学の分野における角谷の不動点定理︵かくたにのふどうてんていり、英: Kakutani fixed-point theorem︶は、集合値函数に対する不動点定理である。ユークリッド空間のあるコンパクトな凸部分集合が不動点︵すなわちそれを含む集合へ写像される点︶を持つための十分条件を与える定理である。角谷の不動点定理は、ブラウワーの不動点定理の一般化である。ブラウワーの不動点定理は、ユークリッド空間のコンパクトな凸部分集合上で定義される連続函数の不動点の存在を示すものであった。角谷の定理はこれを集合値函数に拡張したものである。
この定理は角谷静夫によって1941年に証明され[1]、ジョン・ナッシュによりナッシュ均衡を表現するために用いられた[2]。その後、ゲーム理論や経済学における幅広い分野で応用されている[3]。
不動点を持たない函数
すべての xに対して φ(x) が凸であるという条件は、定理が成立する上で本質的に重要である。
[0,1] 上で定義される次の函数を考える‥
この函数は不動点を持たない。この函数は、角谷の定理の凸性以外の条件をすべて満たすが、x = 0.5 において凸ではない。
内容[編集]
角谷の定理の内容は次のようになる[4]‥ Sを、ユークリッド空間 Rnの空でないコンパクト凸部分集合とする。φ: S → 2S をS上の集合値函数で、閉グラフと次の性質を備えるものとする‥φ(x) は x ∈ Sに対して空でない凸集合である。このとき、φ は不動点を持つ。定義[編集]
集合値函数 集合 Xから集合 Yへの集合値函数 φ とは、Y 内の一つあるいはそれ以上の点を Xの各点に関連付けるある法則である。正式に言うと、それは Xから Yの冪集合への通常の函数で、φ: X→2Y と表現され、すべての に対して φ(x) は空とならないようなものである。各入力に対して出力を返す函数を表す上で、対応という語が好まれて用いられることもある。したがって、領域の各元は値域の一つあるいはそれ以上の元からなる部分集合と対応する。 閉グラフ 集合値函数 φ: X→2Y が閉グラフ︵closed graph︶を持つとは、集合 {(x,y)| y ∈ φ(x)} が積位相において X×Y の閉部分集合であることをいう。すなわち、すべての列 と で および かつすべての に対して を満たすようなものに対して、 が成り立つ。 不動点 φ: X→2X を集合値函数とする。このとき、a ∈ X が φ の不動点であるとは、a ∈ φ(a) が成り立つことをいう。例[編集]
f(x) は閉区間 [0, 1] 上で定義される集合値函数で、点 xを閉区間 [1 − x/2, 1 − x/4] に写すものとする。このとき、f(x) は角谷の定理のすべての仮定を満たすため、必ず不動点を持つ。例えば 0.72 ∈ [1 − 0.72/2, 1 − 0.72/4] なので x = 0.72 は不動点である。特にこの場合は無限個の不動点が存在する。例外[編集]
別の表現[編集]
角谷の原著論文を含むいくつかの文献では、上半連続性の概念を用いた次のような定理の表現も見られる‥ Sを、ユークリッド空間 Rnの空でないコンパクトな凸部分集合とする。φ: S→2S をS上の上半連続な集合値函数で次の性質を満たすものとする‥φ(x) はすべての x ∈ Sに対して空でなく、閉かつ凸である。このとき、φ は不動点を持つ。 この角谷の定理の内容は、本記事の始めに説明された内容と全く同じものである。 この定理は、コンパクトなハウスドルフ値域空間 Yに対して集合値函数 φ: X→2Y が閉グラフを持つための必要十分条件は、それが上半連続であり、すべての xに対して φ(x) が閉集合であることを述べた、集合値函数に対する閉グラフ定理を使うことで証明できる[5]。すべてのユークリッド空間は︵距離空間となって︶ハウスドルフであるため、角谷の定理のこの別の表現において φ は閉値であることが要求され、閉グラフ定理によって二つの主張は同値であることが従う。応用[編集]
「数理経済学」も参照
ゲーム理論[編集]
「ゲーム理論」も参照
角谷の不動点定理は、ゼロ和ゲームの理論におけるミニマックス定理を証明するために利用することが出来る。この応用は角谷の原著論文において具体的に議論されていた[1]。
数学者ジョン・ナッシュは、ゲーム理論における主要な結果を証明するために角谷の不動点定理を利用した[2]。平たく言うと、この定理は、任意のプレイヤー数で混合戦略のすべての有限ゲームにおいてナッシュ均衡が存在することを保証するものである。この業績により、彼は後にノーベル経済学賞を受賞した。
この場合、S はゲームの各プレイヤーによって選ばれる混合戦略のタプルの集合である。函数 φ(x) は、x における他のプレイヤーの戦略に対する各プレイヤーの最善の反応のタプルである。同程度に良い反応が複数存在することもあり得るため、φ は単一の値ではなく集合値である。このとき、ゲームのナッシュ均衡は φ の不動点、すなわち各プレイヤーの戦略が他のプレイヤーの戦略に対する最善の反応となっているような戦略のタプルである。角谷の定理は、この不動点の存在を保証するものである。
一般均衡[編集]
「一般均衡」も参照
経済学における一般均衡の理論において、角谷の定理は、すべての市場における需要と供給を同時に等しいものとする価格の集合の存在を示すために用いられる[6]。そのような価格の存在は、少なくともレオン・ワルラスの時代にはすでに経済学における未解決問題として知られていた。その最初の証明は、ライオネル・マッケンジーによって与えられた。
この場合、S は商品価格のタプルの集合である。φ(x) は、価格タプル xが至る所で需要と供給を等しいものとしない限り、その引数とは異なる結果をもたらす函数として選ばれる。ここでは、このような性質を持ちながら、同時に角谷の定理の条件を満たす φ を構成することを目指す。これが達成されれば、定理より φ は不動点を持つこととなる。この構成方法より、そのような不動点は需要と供給を至る所で等しいものとする価格タプルに対応する。
証明の概要[編集]
S = [0,1][編集]
角谷の定理は、実数直線の閉区間上で定義される集合値函数の場合に、最も容易に証明される。その証明方法は、高次元の場合にも同様に適用することが出来るため、非常に有用である。 φ: [0,1]→2[0,1] を閉区間 [0,1] 上の集合値函数で、角谷の不動点定理の条件を満たすものとする。 ●[0,1] を細分する、互いに反対の方向へ動く隣接点の列を構成する。 i = 0, 1, … に対して、次の性質を持つ列 (ai, bi, pi, qi) を構成する‥1. 1 ≥ bi > ai ≥ 0 2. (bi − ai) ≤ 2−i 3. pi ∈ φ(ai) 4. qi ∈ φ(bi) 5. pi ≥ ai 6. qi ≤ bi
このとき、閉区間 [ai, bi] は [0,1] の部分区間の列である。条件 (2) より、このような列は次第に小さくなることが分かる。また条件 (3)–(6) より、函数 φ は各部分区間の左端を右方向に、右端を左方向に写すものであることが分かる。
このような列は次の手順で構成される。a0 = 0 および b0 = 1 を定める。p0 を φ(0) 内の任意の点とし、q0 を φ(1) 内の任意の点とする。このとき、条件 (1)–(4) は直ちに満たされる。さらに、p0 ∈ φ(0) ⊂ [0,1] であるため、p0 ≥ 0 は必ず成立し、条件 (5) は満たされる。同様に、q0 に対して条件 (6) は満たされる。
今、ak, bk, pkおよび qkは条件 (1)–(6) を満たすものと仮定する。次を定める。
m = (ak+bk)/2.
すると、[0,1] は凸集合なので、m ∈ [0,1] が成り立つ。
r ≥ mを満たす r∈ φ(m) が存在するなら、次のように各数を定める。
ak+1 = m
bk+1 = bk
pk+1 = r
qk+1 = qk
もし存在しないなら、φ(m) は空でないので、s ≤ mを満たす s∈ φ(m) が必ず存在する。このときは、次のように各数を定める。
ak+1 = ak
bk+1 = m
pk+1 = pk
qk+1 = s.
いずれの場合でも、このように定められた ak+1, bk+1, pk+1 および qk+1 は条件 (1)–(6) を満たすことが容易に確かめられる。
●細分の極限点を見つける。
デカルト積 [0,1]×[0,1]×[0,1]×[0,1] は、チコノフの定理よりコンパクト集合である。列 (an, pn, bn, qn) はこのコンパクト集合に属するため、ボルツァーノ=ワイエルシュトラスの定理より必ず収束部分列を持つ。そのような部分列に着目し、その極限を (a*, p*,b*,q*) とする。φ のグラフは閉であるため、p* ∈ φ(a*) および q* ∈ φ(b*) が成り立つ。さらに、条件 (5) より p* ≥ a* が成り立ち、条件 (6) より q* ≤ b* が成り立つ。
ところが、条件 (2) より (bi − ai) ≤ 2−i であるため、
b* − a* = (lim bn) − (lim an) = lim (bn − an) = 0
となる。したがって b* と a* は等しい。x = b* = a* とすると、次が得られる。
q* ∈ φ(x) ≤ x≤ p* ∈ φ(x).
●極限点が不動点であることを示す。
p* = q* ならば、p* = x= q* である。この場合 p* ∈ φ(x) なので、x は φ の不動点である。
そうでない場合を考える。二つの点aとbの間の線分は (1-t)a + tb とパラメータ表現できることを思い出されたい。上述の手順で q<x<pが分かっているので、pとqの間の線分をxの函数として作ることが出来る︵以下の分数は単位区間上にあることに注意されたい︶。φ(x) は凸であり、
であることから、p* および q* と同様に xも φ(x) に必ず属す。したがって xは φ の不動点である。
S が n-単体の場合[編集]
次元が1よりも大きい場合、角谷の定理を証明する上で最も簡単な物体は n-単体である。平たく言うと、n-単体とは高次元における三角形である。ある単体上で定義される集合値函数に対して角谷の定理を証明することは、区間に対して証明することと本質的に変わりはない。高次元の場合ならではの証明の難しさは、領域をより細かい部分片に分ける第一段階に現れる。 ●一次元の場合では区間を中心で分けたが、単体をより小さい部分単体に分ける上では重心細分が用いられる。 ●一次元の場合は、端点が反対方向に動くという方法で初等的に半区間を選ぶことが出来たが、単体の場合はスペルナーの補題として知られる組合せ論の結果が、適切な部分単体の存在を保証するために用いられる。 第一段階でこれらの変更が加えられれば、極限点を見つけそれが不動点であることを示す第二、第三段階は、一次元の場合とほとんど変わらずに証明することが出来る。任意の S[編集]
n-単体に対する角谷の定理は、任意のコンパクトな凸集合 Sに対する定理の証明において用いることが出来る。ここでもまた、より細かい部分集合を作っていく手順は同じである。しかし、n-単体の場合に考えた直線的な辺を持つ三角形の代わりに、曲がった辺を持つ三角形を考えることになる。正式に言うと、S を覆う単体を見つけ、変位レトラクトを使うことで問題を Sからその単体に移す。すると、n-単体に対してすでに得られた結果を利用することが出来るのである。無限次元への一般化[編集]
角谷の不動点定理は、アービング・グリックスバーグ[7]とキー・ファン[8]によって無限次元の局所凸位相ベクトル空間へ拡張された。この場合における定理を説明するために、次の定義が必要となる‥ 上半連続性 集合値函数 φ: X→2Y が上半連続であるとは、すべての開集合 W ⊂ Y に対して、集合 {x| φ(x) ⊂ W} が Xにおいて開であることをいう[9]。 角谷写像 X と Yは位相ベクトル空間とし、φ: X→2Y は集合値函数とする。Y が凸であるとき、φ が角谷写像︵Kakutani map︶であるとは、すべての x ∈ X に対してそれが上半連続で φ(x) が空でなく、コンパクトかつ凸であることをいう[9]。 このとき、角谷=グリックスバーグ=ファンの定理は次の様なものである[9]‥ Sをある局所凸位相ベクトル空間の空でないコンパクト凸部分集合とする。φ: S→2S を角谷写像とすると、φ は不動点を持つ。 単価函数に対する対応する結果は、チコノフの不動点定理である。 函数の定義される空間が、局所凸のみならずハウスドルフであるなら、この定理の主張はユークリッド空間における場合と同様のものとなる[5]‥ Sを、局所凸ハウスドルフ空間の空でないコンパクト凸部分集合とする。φ: S→2S がS上の集合値函数で、すべての x ∈ Sに対して φ(x) が空でない凸集合であるなら、φ の不動点の集合は空でなく、コンパクトである。逸話[編集]
ケン・ビンモアは、ゲーム理論に関する自身の著書[10]の中で、研究集会の際になぜ彼の講演に多くの経済学者が参加するのか角谷に尋ねられたことを記している。ビンモアが、それはおそらく角谷の不動点定理のせいだろうと答えると、角谷は困惑してこのように答えたという。﹁角谷の不動点定理とは何だ?﹂。注釈[編集]
- ^ a b Kakutani, Shizuo (1941). “A generalization of Brouwer’s fixed point theorem”. Duke Mathematical Journal 8 (3): 457–459. doi:10.1215/S0012-7094-41-00838-4.
- ^ a b Nash, J.F., Jr. (1950). “Equilibrium Points in N-Person Games”. Proc. Nat. Acad. Sci. U.S.A. 36 (1): 48–49. doi:10.1073/pnas.36.1.48. PMC 1063129. PMID 16588946 .
- ^ Border, Kim C. (1989). Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press
- ^ Osborne, Martin J.; Rubinstein, Ariel (1994). A Course in Game Theory. Cambridge, MA: MIT
- ^ a b Aliprantis, Charlambos; Kim C. Border (1999). “Chapter 17”. Infinite Dimensional Analysis: A Hitchhiker's Guide (3rd ed.). Springer
- ^ Starr, Ross M. (1997). General Equilibrium Theory. Cambridge University Press. ISBN 978-0-521-56473-1
- ^ Glicksberg, I.L. (1952). “A Further Generalization of the Kakutani Fixed Point Theorem, with Application to Nash Equilibrium”. Proceedings of the American Mathematical Society 3 (1): 170–174. doi:10.2307/2032478. JSTOR 2032478.
- ^ Fan, Ky (1952). “Fixed-point and Minimax Theorems in Locally Convex Topological Linear Spaces”. Proc Natl Acad Sci U S A. 38 (2): 121–126. doi:10.1073/pnas.38.2.121. PMC 1063516. PMID 16589065 .
- ^ a b c Dugundji, James; Andrzej Granas (2003). “Chapter II, Section 8” (limited preview). Fixed Point Theory. Springer. ISBN 978-0-387-00173-9
- ^ Binmore, Ken (2007). “Chapter 8”. Playing for Real: A Text on Game Theory (1st ed.). Oxford