スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
【--/--/-- --:-- 】
| スポンサー広告 | コメント(-) | トラックバック(-) |
極大要素の存在: 美人ホールを求めて

(n+1) 個以上のモノを n 個の集合に入れると, 少なくともひとつの集合はそれらのモノを少なくとも2 個以上ふくむ.

これは数学や言語学でときどき出てくる原理です. (たとえば regular languages の理論の pumping lemma の証明などで使われる.) 「ひきだし論法」とか「部屋割り論法」とかも呼ばれるだって.「美人ホールの原理」とでも訳せば, すごくわかりやすいんですけどね.でも二つ以上(同時に)入れるのは困難か.

れ・イジュ, Pigeon-Hole Principle (鳩の巣の原理).

予告した「極大要素の存在: 消費者理論より簡単」からタイトルを変更した.「ベスト・エレメントの存在: 美人ホールを求めて」なども考えたがやめた.できれば締まりがいいほうがよいのだが,どれが締まりがいいだろう.

前回の記事「選好」では,日本語の文「その個人は選択肢 x を選択肢 y よりも好む」を xPy と記号化した.単に記号化しただけでは,もとの文の意味が抜け落ちてしまう.だから,意味を再現するために記号化されたものに改めて条件を課す必要が出て来る.選好 P にどんな条件を課せば,xPy という表現が「その個人は選択肢 x を選択肢 y よりも好む」という意味をじゅうぶん捉えることができるだろうか? 例として《推移性 (transitivity)》を考えてみる: 任意の選択肢 x, y, z について,「もし xPy と yPz が成り立てば,xPz が成り立つ」ことを要求するのだ.つまり「x が y より,そして y が z よりも好ましいのならば,x が z より好ましいと自動的に言えるよね」というわけだ.選好がたとえば推移的であると仮定するのは,たんに「より好む」という言葉の通常の意味を反映させることを超えて,その言葉の使い方をより限定・明確化しているとも言える.(「より好む」が推移性をみたさなくても平気でその言葉を使うひともいるだろうから.)「より好む」という言葉で x 対 y そして y 対 z を順序付けしておきながら x 対 z の順序付けができないことはその言葉の使い方としておかしいといっていることになるから.そうすることにより,その言葉を発する主体である個人の思考に一定のパタンを想定しているともいえる.

他の条件をふたつ挙げよう.たとえばある選択肢 x について,xPx が成立することを許せば「x を x よりも好む」ということになり,日本語の「よりも」という意味に反する.よって通常は「どんな選択肢 x についても,xPx は成り立たない」という《非反射性 (irreflexivity)》を仮定する.また,「どんな選択肢 x, y についても,xPy と yPx の両方が成り立つことはない」という《非対称性 (asymmetry)》を仮定することも多い.

だがここでは,推移性よりも弱い《非循環性 (acyclicity)》という条件を考えたい.これは「サイクルを作らない」という意味だ.たとえば選択肢 x, y, z があって xPy, yPz, zPx となっているとき,選択肢列 (x, y, z) は《サイクル》であるという.x が y より好きで y が z より好きなのに,z が x より好きと言っているわけで,いわば「より好き」の矢印が巡り巡ってもとに戻って来ているわけだ (円周上に x, y, z が並んで,x→y→z→x の矢印が連なっているのをイメージせよ).一般的には,P における《サイクル》とは (ある有限な数) k 個の選択肢の列 (x1, x2, ..., xk) であって,x1Px2, x2Px3, ..., xk-1Pxk, かつ xkPx1 となるものと定義される.そして,選好 P がいかなるサイクルもふくまないとき,P は《非循環的》という.(テキストによっては,P がいかなるサイクルもふくまないとき,R を非循環的と定義する.ただし xRy とは not yPx のことである.)

べつの言い方をすると,選好 P が《非循環的》であるとは,任意の選択肢 x1, x2, ..., xk について,もし x1Px2, x2Px3, ..., xk-1Pxk ならば,not xkPx1 となることである. サイクルには同じ選択肢が2回以上現れてもいいとする.選好 P が非循環的なとき,P は非反射的かつ非対称的である (練習問題).選好 P が非循環的なとき,R は完備性をみたす.すなわち任意の x, y について,xRy or yRx となる (練習問題).

選択肢の集合 S の「ベストな要素」とはなにか,きちんと定義しよう.ある選択肢の集合 S に属する選択肢 x が選好 P についての S の《極大要素》であるとは,yPx となるような S に属する選択肢 y が存在しないこと (言い換えれば,S の任意の要素 y にたいして,not yPx がなりたつ,すなわち xRy となること) である.x より好ましいものが存在しないというわけだ.x が P について (S の) 極大要素のとき,x は R について《最大要素》と言える; その理由は明らかだろう.

だいぶ前置きが長くなってしまった.アジェンダ S とは選択肢集合 X の任意の「有限な」部分集合だった.任意のアジェンダが「ベスト」な選択肢 (選好にかんする極大要素) を持つかどうかがわれわれの関心だった.じつは,「任意のアジェンダ S が P について極大要素を持つための必要十分条件は,P が非循環的なことである」という定理が成立する.

P が推移的で非対称的ならば,非循環的である (練習問題).したがって,P が推移的かつ非対称的であることは,任意のアジェンダ S が P について極大要素を持つための十分条件であるのがこの定理から分かる.

消費者理論における最大化の基礎を理解する (トポロジーの概念の理解が要求される) のにくらべれば,この定理の証明は簡単だ.アジェンダは選択対象を有限個しかもたないためだ.詳しくは説明しないが,「穴」(あるいは「巣箱」) に「豆」(あるいは「鳩」) を入れて行く,あの「鳩の巣原理」が暗躍しているのだ.

まず P の非循環性が必要条件であること,つまり「どんなアジェンダ S でも極大要素を持つならば,P が非循環的である」ことを,対偶である「P が非循環的でなければ,あるアジェンダ S は極大要素を持たない」を示すことにより証明しよう.P がサイクル (x1, x2, ..., xk) を持つとする.すると,x1Px2, x2Px3, ..., xk-1Pxk から,x1 だけが極大要素の候補として残る.ところが xkPx1 から,x1 も極大要素になり得ない.よって,集合 S={x1, x2, ..., xk} 上に極大要素は存在しない.

次に P の非循環性が十分条件であること,つまり「P が非循環的なら,かならず S は極大要素を持つ」ことの証明をスケッチしてみよう.これも対偶「ある S が極大要素を持たないならば,P は非循環的ではない」をしめすことにより証明する.S が極大要素を持たないとする.つまり,S のどんな要素 x にたいしても x より好ましい (S の) べつの要素 y が存在する (yPx となる).いま任意の要素 x1を固定すると,それより好ましい x2,さらにそれより好ましい x3,……という具合にずっと S に属する選択肢の列が続くはずである.ところが S には有限個しか選択肢がないので,これらのいくつかは重複しているはずだ.たとえば x3= x7 といった具合に.(S の要素それぞれにたいしてひとつづつ「穴」が用意されているとする.[少なくとも 3 つの「穴」をすぐ思いついてイメージが定まらない読者は,自分のいちばん好きな「穴」一種類だけをイメージせよ.] 1日目,2日目,3日目……とより美しい要素を求めつつ,ある「パイプ」をそれらの穴に毎日ひと「穴」づつ突っ込んで行くと考えれば,「美人ホールの原理」そのものだ! 何日目かのある日,じぶんが以前突っ込んだ穴に再び突っ込んでいるのに気づくはずだ.もし「以前」というのが第一日目であれば,まるで「しあわせの青い鳥」ではないか!) もしそうであるなら,(x6, x5, x4, x3) がサイクルになるため,P は非循環的ではない.

上記の証明を声に出し図に描き AV (オーディオ・ビジュアル) 化してみるといい.「ある有限集合上で極大要素が存在しないこと」と「選好がサイクルをふくむこと」との同値関係を直観的にイメージできるようになればしめたものである.もしどうしてもそれができなければ,社会選択理論を証明レベルまで理解する資質はなさそうだ.大学院レベルの経済理論を理解するのは,もっとたいへんかもしれない.

【2006/09/25 02:34 】
| 社会科学 | コメント(1) | トラックバック(0) |
<<社会選択における極大要素 | ホーム | 選好>>
コメント
トラックバックの替わり
「非循環性なしの社会選択理論が出現!」を参照:
http://theorist.blog6.fc2.com/blog-entry-169.html

【2008/11/25 16:34】
| URL | 平凡助教授 #-[ 編集] |
コメントの投稿











管理者にだけ表示を許可する

トラックバック
トラックバックURL
http://theorist.blog6.fc2.com/tb.php/87-c72d3469
| ホーム |
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。