15MGUNG13

2015 年 10 月 6 日
4.3. 参加制約（個人合理性）と VCG メカニズム
配分問題に参加しない場合：機会費用＝ゼロ
（一般的には機会費用Vi ( ) ：状態  に依存しうる）
参加制約条件（Participation Constraint, Individual Rationality）
：A direct mechanism
satisfies participation Constraint if for every i  N , ,
vi ( g ( ),  )  xi ( )  0
for all
( g , x)
 .
参加制約条件がみたされれば
正直戦略プロファイルがプレイされる場合には
任意の状態   について必ず利得ゼロ（機会費用）以上が保証される
1
参加制約をみたすグローブス・メカニズムは
vi ( g ( ),  j )  xi ( )   v j ( g ( ),  j )  hi ( i )  0 for all
 
jN
参加制約をみたすグローブス・メカニズムの中で
もっとも収入をたかめるメカニズムはなに？
ＶＣＧメカ二ズム
（Vickrey-Clarke-Groves Mechanism, Pivot Mechanism）
For every i  N and  i ,
hi ( i )  min  v j ( g ( ),  j )
i i
jN
と定める。この時
 v ( g ( ), )  h (
jN
∴
j
j
i
i
)  0 for some
i  i
これ以上徴収すると参加制約みたされない
2
追加の仮定：
vi (a, i )  0 for all i  N , a  A, and i  i
および
there exists i such that
vi (a, i )  0
for all
a A
各プレーヤー i には配分に関心がないタイプi が存在する：
（メロン問題では i  0 に対応）
3
追加仮定下では、ＶＣＧメカニズムにおける徴収額 hi (m i ) は
hi ( i )  min  v j ( g ( ),  j )  max
i i
jN
aA

jN \{i }
v j ( a,  j )
「プレーヤー i 抜きでの最大化総余剰」
に一致
∴
xi (m)  
ＶＣＧメカニズムにおける支払いルールは

jN \{i}
v j ( g (m), m j )  max  v j (a, m j )
aA
jN
各プレーヤー i は
「自分がいなかった時の他のプレーヤーの最大便益： max
aA
―「自分がいる場合の他のプレーヤーの便益：

jN \{i }
 v ( a, m ) 」
jN
j
j
v j ( g (m), m j ) 」
＝「自分がいることによって被る他のプレーヤーの損失分」
を支払わされる。
4
Marginal Contribution（限界的貢献度）
ＶＣＧメカニズムにおいて、各プレーヤーの利得は
vi ( g ( ), i )  xi ( )   v j ( g ( ),  j )  max
aA
jN
 max  v j (a,  j )  max
aA
jN
aA

jN \{i }

jN \{i}
v j ( a,  j )
v j ( a,  j )
Marginal Contribution（限界的貢献度）
「自分がいることによって総余剰がどのくらい高まるか」
に一致！
5
4.4. VCG メカニズム（あるいはグローブスメカニズム）の Relevancy
＊
現実に使われているメカニズム（オークションルール）は
ＶＣＧメカニズムになっている？
＊
＊
ＶＣＧメカニズムは現実には使われていない？
現実に使われているメカニズムはＶＣＧメカニズム（そのものではないが）に
深く関連している？
6
4.4.1. 二位価格入札
メロン問題（メロン一単位を売却）
xi (m)  

jN \{i }
v j ( g (m), m j )  max  v j (a, m j )
aA
jN
 0  max  j  max  j （二位価格）
if g ( m)  i （落札）
  max  j  max  j  0
if g ( m)  i （非落札）
j i
j i
∴
j i
j i
ＶＣＧメカニズムは二位価格入札と同じ！
（続く）
7

Download Report