誘因両立機構(incentive compatible mechanisms)いろいろ
23 Nov, 1996

modified: 8,11,17 Dec 2002; 8 Oct 2003; 30 Jun, 3 Jul 2008.


目次

はじめに

経済学・ゲーム理論の分野でいわれる「インセンティブ・コンパチビリティ」 (誘因両立性などと訳される)あるいは「インプリメンテーション」(遂行などと訳される)とは、 グループ全体の利益になる選択を保証するため、ウソをつく誘因を排除し、各人 に本当のことをいわせるしかけ(=メカニズム)のことである。

おおざっぱに説明すると次のようなことだ。皆で何かを決めようとしている グループがあって、その内で各メンバーがウソを ついて自分の利益を誘導しようとするかもしれない状況を考える。例えば 公共財の供給(Clarke, 1971; Groves, 1973, 1976)、オークション(Vickrey, 1961)、 多事業部制の企業組織(Groves and Loeb, 1979)の例が古典的な例である。

このような状況で各 メンバーがゲーム理論にしたがって合理的にふるまうと仮定し、そのゲームの解が メンバーの本当のことをいうようにするしくみをこの分野では、 需要顕示機構(デマンド・リベレーション・メカニズム)とか、 誘因スキーム(インセンティブ・スキーム)、あるいは誘因メカニズムなど という(Maskin, 1985; Laffont and Maskin, 1982; Groves and Loeb, 1979)。

また、やや種類がちがうが、これらと密接に関わるメカニズムは投票のそれである(Farquharson, 1969; Moulin, 1979)。そこで用いられた「如才ない」投票手続きは、 後の非支配遂行・仮想遂行の先駆となった。(これらは 展開系ゲーム理論における完全性(や動的計画法における後方帰納)と同じ タイプの論法を用い、劣った戦略を反復消去するが、 これにより非単調なSCCを遂行した。)

当初、支配戦略の下で、公共選択分野への応用を中心に研究されたこの分野は、 ゲーム理論の発展と共に、近年までナッシュ均衡とそのの改良版による精緻な メカニズムの研究へと進展した。所謂、ナッシュ遂行理論は、1977年の 未公開論文でEric Maskinがナッシュ均衡の概念を用いて、より一般的な社会的選択 でのその可能性の条件を明らかにしたことがその端緒である(Maskin, 1999)。

最初の30年間位についての研究レビューはMaskin and Sjostrom(2002)や Palfrey(2002)にまとめられた。日本語の文献で西條・大和 (1997)はWEB上から読める。 また同サイトから、実験室的手法を含む最近の研究動向を知ることができる。

以下では文献を参考にその古典的ないくつかの例を、誘因両立機構(インセンティブ・コンパチブルなインセンティブメカニズムといった意味。手元の文献をいくつか当ったが、公式な呼び方ではないかもしれない。)としてまとめてみた。またPage(1988)に示唆されたように、遂行理論以外の分野で関連の深い、 主観確率理論や統計学的推論におけるメカニズム例を追加した。

ところで、この分野の文献は、現代では飛躍的に増え、応用分野も広がっている。その功績から メカニズムデザインの先駆者ハービッツ、マイヤーソン、マスキンの3人に対して、 2007年度ノーベル経済学賞が授与された。とくにハービッツは90歳で最高齢受賞者 でもあったが、2008年6月24日、ミネアポリスにて没。 誘因両立性やメカニズムデザインの理論的フレイムワークを築いたのが、 レオニード・ハービッツである。ハービッツは、MarschakらRadnerらと共に 市場や組織(あるいは計画経済)を並列分散的情報処理システムとして捉える 数理的アプローチを開拓したが、 なかんずくそれまで経済学者が素朴に信奉してきた価格メカニズムの根本的問題を明らかにした。 すなわち価格メカニズムのプロセスとして側面に光を当て、その情報効率性を数学的に 証明すると共に、そのインセンティブの問題を定式化し、困難を証明した (Hurwicz, 1960, 1972, 1973)。分権的情報システムとしての経済学的 メカニズムの数理にかんするその後の展開は、最近の本にまとめられている (Hurwicz and Reiter, 2006)。


ラムジー・ルール(Ramsey Rule)

ある意味において、主観的確率と期待効用の理論そのものが、 以下で紹介される誘因両立メカニズムの先駆とみなせるだろう。 なぜなら、主観的確率や期待効用を、人間の被験者から引き出すための方法 がこの分野では開発されてきたが、そのために誘因両立性の条件 が応用されたからである。また、以下で紹介するClarke-Groves-Vickreyの 需要顕示機構を応用し、確率顕示機構(固有スコアリングルール)を 改良する試みもある(Page, 1988)。

主観的確率はクジの好み(期待効用)から計測される.

確実なaとbcがそれぞれ確率pと1−pで当たるクジが 無差別なら,

p=(ua−uc)/(ub−uc).

.:

ua=p・ub+(1−p)・uc

ua−uc=p・(ub−uc)

p=(ua−uc)/(ub−uc).


Brierの固有スコア規則(Proper Scoring Rule).

固有スコアルールは主観的期待効用理論をまとめたL.Savageが晩年取組んだ といわれるテーマである。以下ではPage(1988)を参考に、Brierによる メカニズムとPageによるPivot Mechanismによるその改良のアイディアについて 述べる。 天気予報官が明日の雨の確率を予想する.

予報官は主観確率pをもつが,それについての報告rは天気の実現 Xによって選ばれる転移関数tにしたがって報酬を受けとるものと する(i.e., スコア規則).ここではXは1(雨)または0(その 他)であり,1のとき報酬はF(r),0のときG(r)である. また予報官がp=rにおいてその期待報酬を最大にするとき,この スコア規則は(厳密に)プロパーであるという.

Brierのスコア規則.
F(r)=r(2−r),G(r)=(1−r)(1+r).

期待報酬=pF+(1−p)G

    =pr(2−r)+(1−p)(1−r)(1+r)

    =2pr−pr^{2}+1−r^2−p+pr^{2}

    =1+2pr−r^{2}−p

    =−(p−r)^{2}+p^{2}−p+1.

明らかにBrier規則はプロパーである.

Brierのスコア規則の問題点.r=.5と報告しても.75の報酬を受ける が,いっぽう正直報告はたしかに支配戦略ではあるけれども,成功と 失敗の報酬のリスクの点では,つねに0.5と答える虚偽戦略に劣る.

PSRのピボタル・メカニズムへの翻訳
各人が勝つ(w)か負ける(l)かはすべての参加者の報告 によって決まる.一方,報酬の大きさは,他者の報告r’にだけ依存する. 天気予報官の問題にピボット機構をあてはめると,他の人より過大に報告 したらt=1−r’(X=1のとき勝ち)またはt=r’(X=0のとき 負け),その他の場合はすべてt=0とする.

たとえば報告がr=0.3,r’=0.2で,結果がX=0だったとすると, あなたは勝ちで0.3のトランスファーを受け取る.相手は0ゆえ,両者の 差は0.3.一方Brier規則では,勝者が1-0.04=0.96,敗者が1-0.09=0.91 で,その差は0.05.


ピボタル・メカニズム(Pivotal Mechanism).

クラーク=グローブズのメカニズム(別名ピボタルメカニズム) (Clarke,1971)としてしられる公共財の支配戦略遂行メカニズム.

ピボタルメカニズムはつぎの2つのルールからなる.

(採否ルール)

各人から表明された純利得wiの合計が非負,  つまり$Σw_{i}$≧0ならプロジェクトを実施.それ以外のとき,見送り.

(課税ルール)

単独でプロジェクトの採否を覆えす,エージェントi (ピボタル・エージェントと呼ばれる)に対して,表4のように課税する.

つまり他の全員が実施したくない案が,一人の強硬な意見で採決された 場合,皆が得たであろう負の便益の合計をピボタル税としてこの一人に 対して課す.また他の全員が実施したい案が,一人の強硬な意見により 却下された場合,皆が得たであろう便益の合計をピボタル税としてこの 一人に対して課す.この結果,正直に各人の好みを表明することが支配 戦略均衡になり,パレート最適なプロジェクト選択を行える.ただし その結果もたらされる配分は初期状態よりも悪くなることがあり,個人 実行可能性を満たさない.

ピボタルメカニズムにおける課税ルール
Σwj(全員) Σwj≠i(i以外) ti
Σwj≧0(実施)  Σwj≠i≧0のとき

Σwj≠i<0のとき

|Σwj≠i|

Σwj<0(見送り)  Σwj≠i≧0のとき

Σwj≠i<0のとき

|Σwj≠i|

補足:
真の需要の総和の符号によりプロジェクト選択x∈{0,1}を定める意思決定ルールは、真の需要θ[i]に対して、効用関数がu[i]=θ[i]・x−t[i]と書ける場合、もし明らかに全体問題での最適選択を与える。全員が正直に言えば、話は簡単だが、上記例題のように、工夫しないと、自発的に本当のことをいわない人たちが出てくる。ピボタル税は3人のパイオニアの独立の業績において共通に見出せるメカニズム構成要素であり、単独の名称で、あるいはVickrey-Groves-Clarkeのメカニズムなどと称される。このメカニズムは実行可能(feasible)だが、予算均衡(balance)条件は満たさない。つまりつねに税収合計が0以下(実行可能)だが、ぴったり0(バランス)ではなく負の値になりうる。ピボタル税で潤う個人がでてくる(Laffont and Maskin, 1982, p.60)。

またバランス条件は保証されないが、このモデルで、より一般的にピボタル税(つまりピボタルエージェントにだけ支払わせる税ないし支払われる補助金)が、需要顕示に成功するための必要十分条件は、以下のように書ける(ibid, Theorem 3.2)。

t[i](θ)= Σj=/=i {θ[i] + h[i](θ[-i])} if Σi θ[i]≧0;
= h[i](θ[-i]) if Σi θ[i]<0.

なお、驚くべきことにピボタル税は実行可能なクラスにおける絶対総税収の下界を与える(ibid Theorem 3.3)。また実行可能かつ個人合理的なスキームの非存在が示される(ibid Theorem 3.4)。


セカンド・プライス・オークション(Second Price Auction)

最高価格を付けた買い手が2番目に高かった付け値で購入する権利を得るという オークションルールの下では,理論的には各参加者は他の人がどんな作戦で付け 値してくるかあれこれ考えずに,ただ自分の本当の評価額を言えばいい. ただしもし最高価格が何人かによって同時に付けられたなら抽選で一人を選ぶ ことにする. この方式はヴィクレイによって提唱された(Vickrey,1961).クラーク =グローブズのメカニズムが考案された際にも,参考にされている.

定理(Vickrey, 1961).SPAにおいて正直報告は各参加者にとって弱い意味で支配戦略である.

証明

参加者i=1,2,…,N、それぞれの付け値s(i)、本当の評価値v(i)とする。
以下、ある参加者iの付け値戦略を考えるので、s=s(i)、v= v(i)と書く。
ここで i の付け値以外で最高の値を rとする。つまり、r =max{s(j)≠s, j=1,…,N}.
もし自分( i )が勝者になれば、純利益は u=v−r、そうでないときu= 0である。
正直報告のとき。s=vである。rの値によって2パタンに分かれる。
r>s=vのとき.勝者でない。u=0。
s=v≧rのとき.勝者になる(抽選かも)。u=v−r≧0となり純利益がある。
過大報告のとき。s>vである。さらにrの値によって3パタンに分かれる。
r>s>vのとき.勝者でない。u=0なので正直報告s=vでも同じ。
s≧r>vのとき.勝者になる(抽選かも)。だが純利益u=v−r<0となりマイナス。
s>v≧rのとき.勝者になる。u=v−r≧0となり純利益があるが正直報告しても同じ。
過小報告のとき。s<vである。上と同じく3パタンある。
r<s<vのとき.勝者になる。u=v−r>0だが正直報告しても同じ結果。
s≦r<vのとき.同点抽選以外で勝者になれない。当たったら損。またそれ以外はいずれにせよu=0で正直報告と同じ。
s<v≦rのとき.勝者になれず。正直報告すれば同点抽選で当たる可能性はあるがいずれにせよ純利益はu=0。
証明終わり.

表にまとめてみよう。各状態でuが正になるときの値はどの行動でも 同じであり、s=vが他の2案に劣ることはないので、 弱支配戦略であることがわかるだろう。

v>r v=r v<r
s>v u>0 u=0 u≦0
s=v u≧0 u=0 u=0
s<v u≧0 u=0 u=0


グローブズ=レッジャード・メカニズム(Groves=Ledyard Mechanism).

前出のピボ タル・メカニズムのクラーク(Clarke,1971)を始め、グローブズら(Groves, 1973; Groves and Ledyard, 1987)が、公共財の自発的供給でのナッシュ遂行 の先駆となった。これらのメカニズム設計事例ではエージェントの効用関数の 形状について、つぎのような特殊な仮定を置く。

プロジェクトの実施費用γ、その採否x(θ)=0または1、個人iの費 用負担mi(θ)、社会選択ルールf(θ)=(x(θ)、m(θ))、 実数θiに対して、効用関数がui=θix−miのように書けるとする。 このとき、いかなるn次元の実数ベクトルθについても、

 mi(θ)=x(θ)(γ−Σθj≠i)+hi(θ-i) 

  と書ける関数hiが各エージェントについて存在することは、支配戦略均 衡で正直に遂行できるための必要十分条件である。じっさい、以下のグロ ーブズ・メカニズム(Groves Mechanism)をゲーム形式として与えればよい。

(グローブズ・メカニズム)

 ルール1: 表明されたθiの和≧γのとき、x=1。それ以外は0。

 ルール2: 上式で計算したmi(θ)を税として各人から徴収する。


直接表明メカニズムと間接メカニズムの例.

本例および顕示原理の説明はRepullo(1985)による。   結果 A={a、b、c、d}のうちのいずれか。

  好み u1、u2。ただし、個人のタイプθに依存する。

              a、b、c、d

    u1(θ1) = (2、4、2、4)

      u1(θ1’)= (1、0、2、4)

      u2(θ2) = (2、2、4、4)

    u2(θ2’)= (1、2、0、4)

社会選択ルール(SCR)f
f(θ1,θ2)={a} f(θ1,θ2’)={b}
f(θ1’,θ2)={c} f(θ1’,θ2’)={d}
直接表明メカニズム(Direct Revelation Mechanism) h
h(s1=θ1,s2=θ2) h(s1=θ1,s2=θ2’)
h(s1=θ1’,s2=θ2) h(s1=θ1’,s2=θ2’)
この4つのゲームをそれぞれ対応する個人の利得の組みで 表わし直せば以下のようになる.  h(θ1、θ2):支配戦略なし 

2,2 4,2
2,4 4,4
 h(θ1、θ2’):支配戦略はθ2’

2,1 4,2
2,0 4,4
 h(θ1’、θ2):支配戦略はθ1’

1,2 0,2
2,4 4,4
 h(θ1’、θ2’):支配戦略均衡(θ1’、θ2’)

1,1 0,2
2,0 4,4

間接メカニズム(Indirect Mechanism) g
  1\2  s2 s2’s2”

  −−−−−−−−−−−−−−

  s1   a  b  b

  s1’  c  d  c

  s1”  c  b  a

 gは、hに各人1つの戦略(si”)を追加したもの。ポイントは、 h(θ1’、θ2’)の支配戦略を保ちつつ、その他のケースで正直 報告を引き立たせて、支配戦略にすること。もちろん追加された戦略 自身はけして支配戦略にならない。

 g1(θ1、θ2)        g1(θ1、θ2’)

       ▼                   ▼

  1\2  s2 s2’s2”   1\2  s2 s2’s2”

  −−−−−−−−−−−−−−   −−−−−−−−−−−−−−

 ▼s1   22 42 42   ▼s1   21 42 42

  s1’  24 44 24    s1’  20 44 20

  s1”  24 42 22    s1”  20 42 21

 g1(θ1’、θ2)       g1(θ1’、θ2’)

       ▼                   ▼

  1\2  s2 s2’s2”   1\2  s2 s2’s2”

  −−−−−−−−−−−−−−   −−−−−−−−−−−−−−

  s1   12 02 02    s1   11 02 02

 ▼s1’  24 44 24   ▼s1’  20 44 20

  s1”  24 02 12    s1”  20 02 11

 ▼印は、支配戦略。

 北西のゲームでは、d(θ1、θ2)=(4、4)もナッシュ均衡 であり、それゆえ、gは(じゅうぶんに)fをナッシュ遂行できない。 またd(θ1、θ2)>a(θ1、θ2)。


顕示原理(Revelation Principle).

あるいは表明原理とも訳される。

定理: 顕示原理(Dasgpta, Hammond and Maskin, 1979):

 支配遂行できる(間接)=>正直支配遂行できる(直接)

定理: 支配遂行できない(直接)=>ナッシュ遂行もベイズ遂行もできない(間接)

                    目標外の均衡の存在をふせげない。

系(Repulo,1985):

 ナッシュあるいはベイズ遂行できる(間接)=> (正直)支配遂行できる(直接)

 系の内容そのものは、ナッシユ遂行の方がむずかしいだろうという直感に一致する. この相対的なむずかしさは目標外のナッシュ均衡を防ぐことのむずかしさに由来する. (いわばナッシュ均衡は、支配均衡より肌理が粗いので、砂金ばかりか砂利や小石も 濾してしまう。)

補足:
 なおRepullo(1985)は、顕示原理の意味を、ナッシュ遂行の概念と関連させながら証明し、上の例題を用いて説明した。すなわち、正直遂行は遂行とは全く異なる概念であり、元のゲームと比べて情報落ちがある。顕示原理に述べられたとおり、その社会選択規則が間接メカニズムで支配戦略遂行可能であれば、支配戦略でそれを「正直に」遂行する直接メカニズムを作ることは容易だが、その直接メカニズムをそのまま使っても、(情報落ちしているので)支配戦略でそれを遂行する直接メカニズムにはならない(定理2)。これは元のそれが直接メカニズムで支配遂行できるときは、それに対応する正直報告メカニズムのナッシュ対応が、元の直接メカニズムのナッシュ対応に含まれることから示される。


ギッバート=サタスウェイトの定理と独裁者.

1970年代に、ハービッツ(Hurwicz, 1972)、ギッバート(Gibbard,1973)、 サタスウェイト(Satterthwaite, 1975)によって、パレート最適性と個人合 理性を同時に、支配戦略均衡で正直に遂行することは不可能である(あるい は社会に独裁者が存在してしまう)ことが、数学的に証明された。因に、 その証明の重要なステップには、有名なアローの一般不可能性定理が用いら れた。

(ギッバート=サタスウェイトの定理)

   最低2人、3つ以上の選択肢、fが次の条件1と2を満たすものとする。

   (条件1)各人は、選択可能な対象についての好みを制限されない。

   (条件2)選択の対象にタブーはなく、どれも社会目標になりうる。

   このとき、好みについての正直報告がベスト(すなわち嘘偽の動機が無 い)ならば、社会の中に独裁者が存在する。ただし、ここでいう独裁者 とは、以下のような意味においてである。

  (独裁者)dictator

 社会選択ルールfが独裁的である(is dictatorial)というのは、 いかなる(≧、t)に対しても、f(≧、t)に含まれるxで、 あるi(独裁者)にとって、つねにベストであることを指す。 

いくつかのメカニズムが上の条件1を緩和して成功している。


マスキンの定理とナッシュ遂行

一般に、ナッシュ均衡戦略は支配戦略均衡よりも緩やかな概念であるので 遂行できるルールが増えるのではないかと期待される。ナッシュ遂行の一 般的条件として、この分野の開拓者である、Eric Maskinによって、ナッ シュ遂行の必要条件と十分条件が証明された(Maskin、1977/99、1985;Saijo, 1988)。

(マスキンの定理)

 以下の3条件を満足する社会選択ルールfはナッシュ遂行できる。

 (1)社会のメンバーが3人以上いること、

 (2)fが単調(monotonic)であること、

 (3)拒否権がないこと(No Veto Power)。

ただし、上の定理でいう「拒否権」とは、あるi以外のすべてのメンバー j≠iについて、他のあらゆるy∈Xにつき、x(≧、tj)y ならば、 xはf(≧、t)に含まれることをいう。つまり、他の全員がベストだと 思うxは、いかなるiも単独で覆えすことができないという条件である。

(観察) f0に拒否権がないことは、明らかである。

また、社会的選択ルールf:T→C(ただしC⊆X)が単調というのは、 次の意味においてである。

(マスキン単調性)Maskin Monotonicity

 f(≧、t)には含まれるが、f(≧、t’)の下では含まれない x∈Cがあったとしよう。このとき、少なくとも一人のiと、ある x’∈Cについて、下の関係が成り立つ。

  x(≧、ti)x’ かつ x’(>、ti’)x。

いいかえれば、xがf(≧、t)に含まれるとき、tの下では、だれにと っても別のx’より好まれていたxが、別の好みt’の下では、x’の方 がxより好ましいといった、好みの逆転をあるエージェントについて引き 起こす選択対象x’がない限りは、このxはf(≧、t’)にも含まれる というのが、マスキン単調性の意味である。

(観察1) 弱パレート効率集合は単調である。

(観察2) 一人以上にとってベストな結果を選ぶルールは単調である。

またマスキン単調性は、ナッシュ遂行の必要条件である。

(レマ1) fがナッシュ遂行可能ならば、単調である。

f(≧、t)には含まれるが、f(≧、t’)の下では含まれないx∈C があったとする。すなわち、ゲーム<G、(≧、t)>の下でx=g(a) はナッシュ均衡であるが、<G、(≧、t’)>の下ではナッシュ均衡で はないような、戦略組aが存在する。したがって、少なくとも一人のiと、 あるai’について、

  g(a)(≧、ti)g(a/ai’) かつ 

  g(a/ai’)(>、ti’)g(a)。

したがって単調でない社会選択ルールfは、ナッシュ遂行できない。すな わち、どんな(戦略型)ゲームを設計しても、虚偽ナッシュ均衡にはなる が、f(t)から外れるものが存在する。

ナッシュ遂行の十分条件の証明では、以下のメカニズムが用いられた。

(fをナッシュ遂行するゲーム)

G=<N、(Ai)、g>

 

   これらのルールの直観的解釈を試みよう。ルール1は現状把握がすでに 共通認識に達しており、それゆえ選択対象についても異論がないケースだ。 ルール2はこの合意からの、逸脱を試みるエージェントは、彼を除くすべて のメンバーから見て、我を張るよりも皆と歩調を合わせればいいのにと思わ れる場合に限って、言うことを聞いてあげ、それ以外では彼のいったことを 無視する。

ルール3は、いわば独裁者のクジ引きだが、公平なクジというより、「言っ たもの勝ち」の様相である。このケースでは、どのエージェントも表明操作 によって、自分を独裁者にしようとする(ジャンケンで相手の手を見てから 出すようなもの)ので、結局、純粋戦略ではナッシュ均衡になりえない。つ まり、2人以上の意見の食い違いを、選択結果に反映させないための工夫で ある。そこで、実数メッセージ各miの上限を外し、ルール3の代わりに、

 声の大きいものが勝つルール: k=argmax(mi)

としてもよい(これによって混合戦略均衡の場合を回避できる)。

また表明空間のサイズは、pi=(pi[i]、pi[i+1])、つまり自分 と隣人の好みのペアにまで、縮小できる(Saijo, 1988)。

ちなみにエージェントの数が2人の場合も含めたナッシュ遂行定理の証明は、 ムーアとリピュロ(Moore and Repullo, 1990)によって与えられた。

ナッシュ遂行が成功した一因は、社会選択ルールを、関数(一価)から対応 (多価)に拡張したことである。

(観察6)

最低2人、3つ以上の選択肢のとき、単調で拒否権なしの社会選択関数 (つまり一価の場合)fは独裁的である。

また直接表明メカニズム(Direct Revelation Mechanism)では、表明戦略が エージェント自身の「好み」に限られており、かつ正直報告に固執するため、 結局、支配戦略均衡の下での遂行と等価であり、不可能性定理から免れない わけであった。しかしナッシュ遂行におけるマスキンの表明メカニズムでは, 個人の戦略空間に、自分の好み以外の成分がとり入れられて(その分えらく 大きく)拡張された。つまりナッシュ遂行の場合、ディセプティブな均衡が 望ましくないなら、戦略空間を追加することによって、それらを消去する工 夫がある程度可能である。ある程度というのは、単調性が損なわ れたならば、ナッシュ遂行できないからである。


ナッシュ遂行の基本定理.

以下に(完全情報下の)ナッシュ遂行についての主な結果をまとめておく。 o Maskin(1977/99)の得た先駆的な定理は次のようである。
o 3人以上の場合、ナッシュ遂行のための必要条件は、SCCの単調性である。 (Maskin単調性。)
o 3人以上では、誰も他の全員が最善と考える案を拒否できないこと、すなわちNVP(拒否権なし)の下で、単調性は必要十分条件である。
o 3人以上では、Maskin(とVind)のメカニズムを用いれば、単調かつNVPであるSCCをナッシュ遂行できる。
o しかし単調性だけは十分ではなく、また拒否権は必要条件ではない。より一般に、 2人のケースを含めた必要十分条件は、DuttaとSen(1991)、およびMooreとRepullo(1990)によって1990年代初めに解かれた。 非制限領域(とその強選好部分)についての必要十分条件は、Danilov(1992)によって示された。また彼らはその条件を満たす任意のSCCを遂行するメカニズムを設計した。
o その他、これまでに多くのナッシュ遂行の改良モデルが開発された。例えば、ナッシュ均衡では単独の逸脱のみ防げるが、結託した逸脱を許す強ナッシュ遂行についても解決済である。また仮想的遂行(および厳密遂行)と呼ばれる巧妙なメカニズムを用いれば、単調性にかかわらず任意のSCCを遂行できる。 非制限領域における必要十分条件
o 非制限領域はすべての可能な選好組からなる。ここでは非制限領域あるいはその強選好部分におけるナッシュ遂行の必要十分条件を述べる。ただし正式な定義ではなく、直観的な意味を説明する。より一般に制限領域でのMoore-Repulloらの条件もこれと類似した条件からなるが、正式な定義と定理は文献に譲る。
o 3人以上での必要十分条件は「本質的単調性」であり、制限領域でも十分条件であり、また非制限領域あるいは条件Dを満たす制限領域では必要条件となる(Danilov,1992; Yamato, 1992)。2人の場合、これに「個人合理性」および「MR特性」を加えた3条件である。後の2つは、「ブロック関係」を用いて定義される。
o 「本質的単調性」はMaskinによる単調性を強めた条件である。つまり、あるSCCの結果が別の状態でSCCから外れてよいのは、選好逆転を起こす別のSCC結果があって、かつそれは元のSCC結果の劣位集合の本質的要素であった場合に限られる。
o 「ブロック関係」はおおむね次のように定義される。エージェント?の選好R?があって、そのとき他のエージェントたちの選好組に関わらず、代替案の集合Xが社会選択対応と交わらないとき、エージェント?は集合Xをブロックするという。(NVPは全員がφのみブロックできることと等価である。)
o 「個人合理性」とは、誰かにブロックされるであろう劣った代替案を含まないこと。つまり個人合理的なSCC結果は、各エージェント自身のその劣位集合をブロックしない。
o 「MR特性」とは、両者がそれぞれブロックできないペアXとYの共通部分に共通最善案となるSCC結果があること。


番外.ランダマイズド・リスポンス:きわどい質問についてのアンケート方式.

個人のプライバシーにかかわるようなことはたとえアンケート用紙 に書き込むだけでも人はためらうものである.たとえば「あなたは 麻薬を使ったことがあるか?」といった質問項目を直接聞いたとこ ろで,DK(知らない・分からない)やNA(回答なし)が増えること は目に見えている.

そこで,とある統計屋さんが考えたのが次のような工夫である(Warner,1965).

100人の被アンケート者が集まったとする.

クマさんカードとゾウさんカードをそれぞれA枚と100−A枚(A≠50!) 用意する.これらをシャフルする.

各自にカード1枚を,自分以外に(もちろんアンケート者にも) 見られないように,引いてもらう.

そして,次のように指示する.

 「質問項目に対する答えが"Yes"で,クマさんカードを おもちの方は1番をマークして下さい.」

 「質問項目に対する答えが"Yes"で,キリンさんカードを おもちの方は2番をマークして下さい.」

 「質問項目に対する答えが"No"で,クマさんカードを おもちの方は2番をマークして下さい.」

 「質問項目に対する答えが"No"で,キリンさんカードを おもちの方は1番をマークして下さい.」

こうすれば,1番あるいは2番を答えを聞いただけでは,元のきわ どい質問への各自の回答が{Yes,No}のいずれであったのかは分 からないようになっている.

しかし100人分を集計すれば,次のように元の質問へのYesの回答 者の比率が,プライバシーを保ったまま明らかになる.

いま,A=30枚とし,答えが「1番」の人がm=40人だったとすると,

 40=30π+70(1−π)

  π=3/4

  X=75(人)

と推定される.より一般には,

  π=(m−N+A)÷(2A−N)

が不偏推定量となる.

        Yes     No       計

   −−−−−−−−−−−−−−−−−−−−−

   クマ   πA   (1−π)A   A

       (1番)   (2番)

   ゾウ   πB   (1−π)B   B=100−A

       (2番)   (1番)

   −−−−−−−−−−−−−−−−−−−−−

   計   100π  100(1−π) 100


文献.

  1. Clarke, E. (1971). Multipart pricing of public goods. Public Choice 11: 17-33.
  2. Danilov, V. (1992). Implementation via Nash equilibria. Econometrica 60(1): 43-56.
  3. Dutta, B. and A. Sen(1991). A necessary and sufficient condition for two-person Nash implementation. Review of Economic Studies 58:121-8.
  4. Farquharson, R. (1969). Theory of Voting. Yale University Press.
  5. Laffont, J.-J. and E. Maskin (1982). The theory of incentives: an overview. In Advances in Economic Theory. Cambridge University Press. pp.31-94
  6. Groves, T. (1973). Incentives in teams. Econometrica 41: 617-31.
  7. Groves, T. (1976). Incentive compatible control of decentralized organizations. In Y. Ho and S. Mitters (eds.), Directions in Large Scale Systems: Many-Person Optimization and Decentralized Control.
  8. Groves, T. and M. Loeb (1979). Incentives in a divisionalized firm. Management Science 25(3): 221-230.
  9. Groves, T. (1982). On theories of incentive compatibel choice with compensation. In Advances in Economic Theory. Cambridge University Press. pp.1-29
  10. Hurwicz, L. (1960). Optimality and informational efficiency in resource allocation processes, In K. Arrow et al. (eds.), Mathematical Methods in the Social Sciences. Stanford University Press, pp. .
  11. Hurwicz, L. (1972). On informationally decentralized systems, In C. B. McGuire and R. Radner (eds.), Decision and Organization, A Volume in Honor of Jacob Marschak, North-Holland, 297-336 (Second edition by the University of Minesota Press, 1986).
  12. Hurwicz, L. (1973). The design of mechanisms for resource allocation, American Economic Review, 63: 1-30.
  13. Hurwicz, L. and Reiter, S. (2006). Designing Economic Mechanisms. Cambridge University Press.
  14. Maskin, E. (1985). The theory of implementation in Nash equilibrium: a survey. In L.Hurwicz, D. Schmeidler, and H.Sonnenchein(eds.), Social Goals and Social Organization: Essays in Memory of Elisha Pozner, Cambridge University Press, pp.173-204.
  15. Maskin, E. (1999). Nash equilibrium and welfare optimality. Review of Economic Studies 66:23-38.
  16. Maskin, E. and T. Sjostrom(2002). Implementation theory. In K. Arrow, A. Sen, and K. Suzumura (eds.), Handbook of Social Choice and Welfare, Vol. 1, North-Holland, pp.237-288.
  17. Moore, J. (1993). Implementation, contracts, and renegotiation in environments with complete information. In J.-J. Laffont (ed.), Advances in Economic Theory, Cambridge University Press. pp.182-282.
  18. Moore, J. and R. Repullo(1990). Nash implementation: a full charaterization. Econometrica 58(5):1083-99.
  19. Moulin, H. (1979). Dominance solvable voting schemes. Econometerica 47: 1337-1351.
  20. Page, T. (1988). Pivot mechanism as a link between probability and preference revelation. Journal of Economic Theory 44: 43-62.
  21. Repullo, R. (1985). Implementation in dominant strategies under complete and incomplete information. Review of Economic Studies 42: 223-229.
  22. Saijo, T. (1988). Strategy space reduction in Maskins theorem: sufficient conditions for Nash implementation. Econometrica 56(3): 693-700.
  23. Palfrey, T.R. (2002). Implementation Theory. In R.J. Aumann and S. Hart (eds.), Handbook of Game Theory, Volume 3. Elsevier Science B.V., pp.2271-2326.
  24. Vickrey, W. (1961). Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance 16: 8-37.
  25. Warner, S. (1965). Randomized response: a survey technique for eliminating evasive answer bias. Journal of American Statistical Association 60: 63-69.
  26. Yamato, T. (1992). On Nash implementation of social choice correspondences. Games and Economic Behavior 4:484-92.
  27. 川又邦雄 (1991). 『市場機構と経済厚生』創文社.
  28. 西條・大和 (1997).「経済環境における社会的選択の分権化」mimeo. http://www.iser.osaka-u.ac.jp/~saijo/wed/97/saijo-yamato-survey.doc