スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
【--/--/-- --:-- 】
| スポンサー広告 | コメント(-) | トラックバック(-) |
ソロモン王のジレンマはセカンドプライス・オークションで解決できるじゃないか!

ソロモン王のジレンマ (King Solomon's dilemma)」という非分割財配分の有名な問題にたいする最新の解決法を紹介する.(この文章のために敷かれた伏線を知りたい方は以前の記事から遡ってもらいたい.)

まず,問題を記述しよう.ある赤ん坊を自分の子供であると主張しているふたりの女がいる.ソロモン王は本物の母親にその子を渡したい.女たちはその子供にたいしてある「評価額」 (その子を獲得するためにぎりぎり払っていい値段) を持っており,真の母親による評価額の方がもう一方の女による評価額よりもすくなくともδ>0 だけ高い.この一定のギャップがあることはソロモンをふくめて皆の知るところだ.女たちは子供にたいする自分の評価額は知っているが,相手の評価額は知らない.しかし,じぶんが本当の母親であるかどうか---いいかえれば自分の評価額が相手のより高いかどうか---は知っている.

セカンドプライスであれなんであれ,オークションをやってその子を買ってもらうというやり方ではダメである.ソロモン王の目標は,お金の受け渡しをせずに真の母親に子供を渡すことにあるからだ.

何人かのメカニズム・デザイナーがこの問題を解決するメカニズム (「ゲームフォーム」とも呼ばれるルール・手順) を提示している.(ここでは女性たちは互いの評価額を知らないと仮定している.互いの評価額を知っていると仮定した初期の研究については,別記事最終段落を参照.) Perry and Reny (1999) は以前の記事に出て来た second-price all-pay auction をもとにしつつ,「やっぱりやめた」と降りることができる権利 (ex post option to quit) を獲得者に認めるというメカニズムを提示した.Olszewski (2003) はセカンドプライス・オークションをもとにしつつ,ソロモン側から両方の女性へ追加的な支払いをするメカニズムを提示した.(前述記事の意地悪セカンドプライス・オークションでは,相手の入札額を追加的に支払うようになっている.一方,Olszewski では,相手の入札額を追加的に受け取った上で一定の参加費を取られる.これによって,そのオークションは評価額の低い女性にとって有利になっている.ヘンなオークションであることに変わりはない.) おっと,そのオークションの前段階として,そのオークションを実際に行うかどうかを決めるステージもある.いずれもかなり洗練された,手の込んだメカニズムだ.ほかにもこの問題に限らず扱える,つぶしのきく一般的メカニズムもあるが,いずれもかなり複雑だ.

しかし,そんなに手の込んだ方法が必要だろうか? そんなにヘンなオークションにもとづいたメカニズムじゃないとうまくいかないのだろうか? 3000 年間人類を悩ませ続けてきた (わけじゃないだろうなあ,ソロモンは一瞬で答え出したし) この問題に,恐るべき単純な解決法を与えたのが H. Reiju Mihara の以下のワーキングペーパーだ:
The second-price auction solves King Solomon's dilemma.

ちなみに「三原麗珠」というこの著者の名前に心当たりのある読者は少なくないだろう.このブログのモデルのひとりと考えられているためだ.実際ボクがこの著者のことを一人称で語るのは構わないという協定があるので,過去そのように語ったことがあるし以下でもそう語る部分がある.なんのまちがいか,18世紀のコンドルセとボルダそして 20 世紀真ん中のアローとともに (もうだいぶ以前にある科学教育サイトで) 名前を挙げられたことのある投票理論家 Mihara だが,今回は紀元前 900 年代に活躍したソロモン王のジレンマにたいする解答を,3000 年の歴史を超えて与えてくれたわけだ.その解決法の凄さは,中国?千年の歴史を結実して生まれたというインスタント・ラーメンの凄さにも迫るものがある.

こんなふうに書くと,三原はだれからも注目されない 3000 年前のどうでもいいことの訓古学的研究をやっているつまらない学者と思うひねくれた読者もいるだろうが,それはボクの本意ではない.すくなくとも社会選択 (三原の専門分野) あるいはメカニズム・デザイン (今回のペーパーの分野) という分野は最新の政治理論やコンピュータ・サイエンスにも注目されている先端的研究分野であることは指摘しておく.

三原のメカニズムもセカンドプライス・オークションにもとづく.ただし各女性から一定の参加費 (participation fee, entry fee) である δ を取るというところがちがう.もちろんオークションに参加したくない女性は参加しなくていいが,その場合は子供はもらえない.これだけだ.(よってタイトルを "The second-price auction with an entry fee solves King Solomon's dilemma " とでもすればずっと正確だ.) (ヘンなオークション方式に依存している) 先行研究にみられたような巧妙さ (ingenuity) もなにもあったものではない.Lack of ingenuity こそが,このメカニズムの最大の特徴とも言える.どうしてこれでうまくいくのか説明してみよう

セカンドプライス・オークション (第二価格秘密入札) でこの問題を解こうとすればどうなるかを,まず考えてみよう.それぞれの女性は,その子供にたいする評価額をそのまま入札することになる.(そうするのが弱支配戦略---つまりつねに最適---であることは,第二価格秘密入札にかんする理論を参照.) 真の母親 i は偽母親 j の入札した「第二価格」vj だけを払えばいいので,自分の評価額 vi との差額である vi-vj が「余剰」となる.したがって,その余剰未満である δ だけをソロモンが吸い取っても (参加費として支払いを要求しても) 母親はオークションに参加しようとするだろう.一方,オークションで子供を獲得できる見込みのない偽の母親の方は,参加費を払わなければならないならオークションに参加しないことを望むだろう.けっきょく「参加費を取るぞ」と「脅し」を与えるだけで真の母親だけが参加表明をすることになり,実際はオークションをわざわざ実行するまでもなく子供を真の母親に渡すことができるわけだ.ここで効いているのは,自分が真の母親であるかどうかをそれぞれの女性が知っているという仮定であるのはいうまでもない.本当はだれがどれだけの情報を持っているかを明確にした注意深い議論が必要だが,いずれにせよ単純な論理であることは分かるだろう.

特に数理系の人間は,「なんだ,そんなんで論文になるのか? だから経済理論はレベルが低い」と思ってしまうかもしれない.じっさい,ボクもこの著者からこのアイディアをはじめて聞いたときは,このブログで披露すればじゅうぶんだと思っていた.著者自身,「これほど自明な結果を論文にするのは初めてだ」と言いつつ,過去最短の時間でペーパーにまとめたようだ.しかし,できあがった結果は論文としてじゅうぶん整った形になっているし,どうして Olszewski らのメカニズムでは満足できないかについてもかなり説得的な議論が展開されている.そしてもちろん最大の強みは提案されたメカニズムの単純さ,lack of ingenuity にある.「そんな単純なアイディアで論文になるのか?」という疑問に直接答える代わりに,「そんな単純なアイディアだから論文になる」とだけ宣言してはぐらかしておこう.(これが真の答になっていないことは,ボク自身気が狂いそうなほど複雑なアイディアで論文を書いたことがあるから分かっている.) あとはどこのジャーナルが論文として認めるかの問題だ.

ところで,大学キャンパスでの駐車場配分について,以前,以下のように書いたことがある:

「クルマを所有する大学職員を貧乏人扱いする必要はない.カネを使えよ! 大学周辺の駐車場の 1.1 倍くらいの値段にすれば,多くの申請者は脱落するはずだ.いや,0.7 倍くらいでもかなり脱落するだろう.オークション方式でもいいかもしれない.」

上記のメカニズムを複数の「子供」(駐車スペース) をあつかえるように拡張すれば使えるかもしれない.じっさい Mihara のペーパーでは,n 人の個人なかの k 人に k 個の同一オブジェクトを配分する一般化された問題をあつかっている.駐車スペースにたいする自分の評価額がどのあたりにランクされるかは最初のうちは分からないにせよ,数回試行を重ねればだいたい分かるようになるだろう. (じっさいは自分が上から k 位内に入るかどうかが分かればじゅうぶんなはずだ.上記ペーパーは先行論文につられて上位 k 人がだれであるかをすべての個人が知っていることを要求しているが,たぶんそこまで要求しなくてもいいはず.) ただしメカニズムをデザインする方にとって,駐車場を強く欲しているグループと弱く欲しているグループの評価額の間に,δにあたる適当なギャップを見つけることは簡単ではないかもしれない.参加費であるδが小さすぎると,弱グループの参加をじゅうぶん排除できないかもしれない.参加費が高すぎると,今度はそのメカニズムにたいする学内の反対が強まって導入がむずかしくなるだろう.しかしこのメカニズムが仮にうまくいかなかったとしても,結果はオークションが実行されるだけのことだ.もともと自分は価格をもちいた解決でいいと言ってきた.非獲得者が参加費を払わなければならないという詳細のちがいはあるが,自分としては「失敗」じゃないのだ.

いうまでもなく,この参加費δはこの方式の提案者に支払うのが自分的には最適だ.法経地ローのキャンパス (どうでもいいが,五十音順に「経地法ロー」としたほうがかっこいいぞ) で得た収入だからといって,それをそれらの学部 (プラス専門職大学院) に還元しようとするとまたインセンティブにゆがみが出て来るからだ.あるいは,得た収入を別キャンパスの駐車場整備に使うということでも,参加者にとって得るところはないのでうまくいく.そちらをお好みだろうか?

他にも駐車スペースの数 k は実際は固定されているわけではなく,あるていど柔軟性があるソフトなものであることなど,いろいろと検討すべき課題はあるだろう.ただ,現段階でひとつ判明したことがある.「香川大学ビジネススクール要覧」というパンフレットで語られた三原麗珠の抱負がウソではなかったということだ:

「今後は大学や企業をはじめとする組織で起こる身近な配分問題をヒントにした理論研究に着手したい.もちろん最新の学問水準を保ちながら (あるいは押し上げながら) 研究をすすめ,なによりも経済学の発展に貢献したい.ついでに実務上の問題解決にも少し貢献できたら言うことはない.」

この抱負はビジネススクールに参加する一員としての行儀の良さを装った冗談とばかり思っていた.研究を捨てたわけではないというのは理解できるとしても,「身近な」「実務上の」などの言葉を用いるのはやり過ぎだと考えていた.しかし三原自身は地道にまじめにその抱負を実行に移したようだ.ビジネススクールに参加する教員の模範といってよいだろう.香川大学栄誉賞でも贈呈してはどうだろう.賞品はソロモン王にちなんで多数の「オンナ」にするのが適当だ.もちろん「平凡助教授の高い評価を得た」というのが表彰理由であるべきであり,プレスリリースにこの記事へのリンクを入れるべきであることは当然である.

追記 (三原麗珠からの投稿, 9/6/2006).

さて,平凡助教授による大げさな宣伝があったためか,若干の反響があった.宣伝が宣伝だったので,もしかすると匿名掲示板あたりで叩かれているのかもしれないが,そちらはチェックしていない.ここでは yyasuda の指摘へのリプライを補足する.(それにしても引っ越しの最中で忙しいなかペーパーにコメントしてくれた yyasuda さんにせよ,ボクのコメントにコメントしてくれたふっひーとさんにせよ,はるばる米国から賢いひとたちが出て来てくれたもんだ.ところでボクはメカニズム・デザインはもとより,非協力ゲームでペーパーを発表するのははじめてなんですよ.ノビスなんで,お手柔らかに.あと,ボクはおふたりを指導する立場にあったことはないんで「先生」とよばれてもなあ~.ま,たしかに同僚でも「先生」と呼んで来ることはあるんで分かるけど,研究者同士だから「三原さん」「麗珠さん」でじゅうぶん!)

ひとつ目の指摘は予想内のものだった.ボクの提示したメカニズム (参加費用つき自由参加型セカンドプライスオークション) が,完備情報のケースの解決として提示された Moore らのメカニズムに似ているというものだ.これは「言われてみればたしかに自明だが,思いつくのはかならずしも自明ではない」例といえないだろうか.似ているとされたメカニズムが発表されたのは 1992 年とか 1989 年の話だ.その後不完備情報ケースの解決として Perry and Reny が出版されたのが 1999年で,Olszewski は 2003年だ.これらはいずれも Moore らのペーパーを参照している.もし Moore らのメカニズムを知っているひとのかなりがボクのメカニズムをすぐ思いつくくらい似ていたとしたら,Perry and Reny にせよ,Olszewski にせよ,なぜわざわざ複雑なメカニズムを提示するのか説明があってもよさそうだ (レフェリーも指摘するだろうし).「ひとつの解決法としてアホでも思いつく単純な《参加費用つき自由参加型セカンドプライスオークション》があって,われわれとおなじ遂行概念で行ける.しかし,それはこうこうこういった欠点を持つ.そこでここではその克服としてこうこうこういうメカニズムを提示したい.結果としてメカニズムは少々複雑になるがそこは我慢してくれ」と.しかし,その種の正当化は彼らのパーパーには見当たらない.自明すぎて見落とされていた可能性が高いと思って,敢えてペーパーにしてみた.

二つ目の指摘は予想外だった.Olszewski のメカニズムでボクが欠点とみなしたことが,見方を変えれば長所とみなせるというものだ.これは Olszewski のメカニズムとボクの提示したメカニズムを比較するセクションである Discussion に出て来る話だ.現バージョンのそのセクションには,「全体的に見てボクのメカニズムのほうが優れている」という結論は書かれていない (読めばそう思うだろうが主張はしていない).あくまでもいくつかの個別の側面について,それぞれのメカニズムの特徴を「客観的に」リストしたつもりだ.Olszewski のメカニズムに長所があるなら,また,ボクのメカニズムに短所があるなら,書くのはまったく問題ない.ただ,短所とされたことというのが,参加者から (明示されていない支払い能力を超えて) お金を取る可能性を排除していないことなのだ.明示していないんだから「支払い能力は制約にならないと仮定している」といえば済むかもしれない. [しかしそんな仮定をしなくても,(参加費が特に大きくない限り) 支払い能力を超えてお金を取られる可能性は「評価額」の解釈上ありえないというのがボクの立場だ.起こりえない問題だから書かないほうがいいと現段階では考えている.(この角括弧内の説明は「評価額と支払い能力にかんする基礎論: ハーヴィッツの呪い?」を参照.)] ただ,指摘自体は新たな視点から問題を考え直すことを示唆していておもしろい.

他分野のひとに言わせれば,ボクが社会選択で書いて来たペーパーはむずかしいと言われることが多かった.それは多くの読者になじみのない問題をあつかっているためであり,ボクの書き方が悪いためではないはずだ.(たとえば投稿して蹴られる場合,レフェリーに well-written と言われた上で蹴られることが多い.もっとも,それだと書き方は上手だが内容がないみたいに聞こえてしまうが.) 今回はわりと有名でやさしい問題をあつかったため (学部授業の副読本にでも使えるかも),すぐ読者が現れたうえ,ありがたいことにラィティングが悪いわけでないことを指摘してくれた.(光栄ですよ,yyasuda さん!)

「論文自体は簡潔で非常に読みやすく大変勉強になりました。本稿のように大きいテーマについて書かれた論文は読んでいても楽しいですね♪」(yyasuda)

参考文献

H. Reiju Mihara. The second-price auction solves King Solomon's dilemma. August 2006. [教材としてもバシバシご利用ください]

追記 (7/19/2011).

「あとはどこのジャーナルが論文として認めるかの問題だ」と書いたが,その解答が出た:

H. Reiju Mihara. The second-price auction solves King Solomon's dilemma. Japanese Economic Review, 2011, doi: 10.1111/j.1468-5876.2011.00543.x

より新しい無料バージョンがあるため,上記「参考文献」に挙げた古いバージョンは取り消し線で消した.

YouTube の解説ビデオもある.

スポンサーサイト
【2006/09/03 00:31 】
| 社会科学 | コメント(3) | トラックバック(5) |
| ホーム |
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。