Microsoft Word - 18MGUNG8.docx

2018 年 10 月 12 日

第

_{4 章 VCG メカニズム}

（

_{Vickrey-Clarke-Groves Mechanism）}

本章のテーマ

効率的な

社会的選択ルール

f

:

 

A

（総余剰最大化）

( ( ), )

( , )

i i i N i N

v f

 

v a



 







for all





and

a



A

をメカニズムデザインで

「表明原理（

Revelation Principle）」より

g

を効率的配分ルールとして

Direct Mechanism

( , )

g x

が Incentive compatible になるように

支払いルール

_x

を

うまくデザインすればよい

ここで 効率的配分ルール

g

:

 

A

とは余剰最大化のこと：

( ( ), )

( , )

i i i N i N

v g

 

v a



 







for all





and

a



A

正直表明によって効率的な社会的選択ルールが遂行

どのように支払いルール

_x

をデザインすればよいか？

Answer:

Design ‘VCG mechanism’!

さらには

プレーヤーの最低限の利得を保障するため

参加制約条件をつけると

……

Design ‘Pivot Mechanism’!

本章における大事な仮定：

Private Values

( , )

( , )

i i i

v a





v a



選好についての情報の非対称性 cf. 品質についての情報の非対称性 （なぜこの仮定が必要かについては後述）

本章の大定理

Private Values の仮定下では

任意の効率的社会的選択ルールについて

VCG メカニズムを定義することができて

しかも

“VCG メカニズムは Incentive Compatible in Dominant Strategy (DIC) である！”

つまり

Private Values においては、

常に優位戦略によって効率的配分が達成可能である

この定理のすごいところは

Private Values 以外になんら仮定を置かずに成立すること！

例：

_{私的財の配分： 複数種類の財、各々複数単位}

経済主体ごとに選好まちまち：

代替財？補完財？独立財？

スケールメリット？デメリット？

これらすべて買い手によってまちまちでもよい

cf.

コーヒーと紅茶

コーヒーと砂糖

砂糖と

PC

電波オークション（５

G）：

「私にとってライセンスA とライセンス B は補完財」 「あなたにとっては代替財」 「彼女にとっては独立財」 「私はライセンスがたくさんあるとスケールメリット」 「あなたにとってはデメリット」追加価値ダウン 公共財の配分問題もVCG で OK： 伝統的にはＶＣＧ研究の重要テーマだった

4.1. VCG Mechanism: Definition

Definition:

Direct mechanism ( , )

g x

is said to be a

VCG mechanism

if the allocation

rule

g

is

efficient

, i.e. for every



,

( ( ), )

( , )

i i i i i N i N

v g

 

v a



 







for all

a



A

,

and for every

i



N

, there exists a function

h

_i

:

  such that

_i

R

\{ }

( )

( ( ),

)

(

)

i

j

j

i

i

j N i

x



v g

 

h



_



 





↑この（一見わかりにくい）支払いルールの意味を理解することが

本章の目的！

VCG Mechanism の支払いルール

x

とはどんな意味？？

Message profile

m



M

 

がアナウンスされると ＣＰは各プレーヤー

i

_に対して \{ }

( ( ),

)

j j j N i

v g m m





円支払う。 さらにＣＰは各プレーヤー

i

から

(

)

i i

h m

_ 円徴収する よって、プレーヤー

i

の私的便益は

( ( ), )

( )

i i i

v g m





x m

\{ }

( ( ), )

( ( ),

)

(

)

i i j j i i j N i

v g m



v g m m

h m

_ 









になる

VCG メカニズムを理解するため、まず特殊ケースとして

「徴収なし」のケースを考えてみよう：

(

) 0

i i

h m

_



, that is,

\{ }

( )

( ( ),

)

i j j j N i

x m

v g m m



 



各プレーヤー

_i

は「私のタイプは

m

_i



_i 」とアナウンスする CP はそれを鵜呑みにするとしよう 「真の状態は

( )

_{i i N i} i N

m

m

_ 



  

だと信じよう。配分を

g m

( )

としよう。」 CP は社会的便益（総余剰）を _j

( ( ),

_j

)

j N

v g m m





と想定し、 各プレーヤー

i

の私的便益を

v g m m

_i

( ( ), )

_i と想定したことになる

「社会的便益と私的便益は乖離している」

⇒

「このままではうそをつかれる懸念あり」

そこで、ＣＰは

「内部化（

_{Internalization）」を企てる：}

社会的便益と私的便益は一致してないので

内部化によって一致させよう

VCG の支払いルールの含意は

「内部化」である！

「

VCG の支払いルールの本質は「内部化」にある」

CP は、各プレーヤー

i

に、他のプレーヤーの私的便益の総和 \{ }

( ( ),

)

j j j N i

v g m m





を支払ってやる すると、ＣＰが予想する各プレーヤー

_i

の利得は \{ }

( ( ), )

( ( ),

)

i i j j j N i

v g m m

v g m m







( ( ),

)

j j j N

v g m m







max

_j

( ,

_j

)

a A j N

v a m

 _





これは「社会状態

_m



の時の最大化総余剰」に一致している

一方、CP の予想でなく真の社会状態を





とすると、 各プレーヤー

_i

の「実際の」便益は、

v g m m

_i

( ( ), )

_i でなく

( ( ), )

i i

v g m



である。よって… 各プレーヤー

_i

の実際の利得は

\{ }

( ( ), )

( ( ),

)

i

i

j

j

j N i

v g m



v g m m







これは

「社会状態

( ,



_i

_m

_i

)



にて配分

g m

( )

が選ばれた場合の総余剰」

に一致している

配分が

_{g m}

( )



_A

でなく

g

( ,



_i

m

_i

)



A

ならば （つまり i

m

の代わりに



_i をアナウンスするならば） プレーヤー

_i

の利得は \{ }

( ( ,

), )

( ( ,

),

)

i i i i j i i j j N i

v g



m

_



v g



m

_

m







\{ }

max{ ( , )

_{i i j}

( ,

_j

)}

a A j N i

v a



v a m

 _







\{ }

( ( ), )

( ( ),

)

i i j j j N i

v g m



v g m m









これは「社会状態

( ,



_i

m

_i

)

の時の最大化総余剰」に一致！

相手のメッセージ

i

m

_

に関係なく正直にタイプ表明するのがベスト

∴

_{正直が優位戦略！}

VCG メカニズム

( , )

g x

：一般形

\{ }

( )

( ( ),

)

(

)

i j j i i j N i

x m

v g m m

h m

_ 

 





(

)

i i

h m

_

はどんな値でもＯＫ。

ただし

自身のメッセージ

_m

_i

から独立でないとだめ

（独立でない場合には うそをついて徴収額を低くする可能性があり正直がベストにならない）

(

)

i i

h m

_

の追加は CP にとってとても大事：これがないと

大赤字

各プレーヤー

_i

に \{ }

( ( ),

)

j j j N i

v g m m





支払っているので、トータルで \{ }

{

_j

( ( ),

_j

)} (

1)

_j

( ( ),

_j

)

i N j N i j N

v g m m

n

v g m m

  





 



つまり 総余剰

( ( ),

)

j j j N

v g m m





の

n



1

倍もＣＰは支払っていることになる

∴

_{ならば各プレーヤーから}

_{h m}

_i

(

_i

)

_{円を徴収しよう！}

定理

4-1：任意の VCG メカニズムにおいて、各プレーヤーにとって正直戦

略は優位戦略である。つまり、

VCG メカニズムは incentive compatibility

in dominant strategy (DIC) をみたす。

証明：

任意の

_{m M}



_{について i}

( ( ), )

_{i i}

( )

_i

( ( ), )

_{i j}

( ( ),

_j

)

_i

(

_i

)

j i

v g m



x m

v g m



v g m m

h m

_ 











max{ ( , )

_{i i j}

( ,

_j

)}

_i

(

_i

)

a A j i

v a



v a m

h m

_  _









_i

( ( ,

_{i i}

), )

_{i j}

( ( ,

_{i i}

),

_j

)

_i

(

_i

)

j i

v g



m

_



v g



m

_

m

h m

_ 









。 Q.E.D.

4.2. ピヴォット・メカニズム（Pivot Mechanism）

徴収額

_{h m}

_i

(

_i

)

_{を大きくすればするほどＣＰは儲かる。} しかし大きくしすぎるとプレーヤーが参加しなくなる恐れがある。

∴ プレーヤーの参加制約を考慮すべし！

以下、配分問題に参加しない場合の機会費用を「ゼロ」としよう

（ゼロじゃないケースの考察も重要：後述）

参加制約条件（

Participation Constraint, Individual Rationality）：

A direct

mechanism

( , )

g x

satisfies

participation constraint

if for every

i



N

,

( ( ), )

( ) 0

i i

参加制約をみたすVCG メカニズム

( ( ),

)

( )

( ( ),

)

(

) 0

i j i j j i i j N

v g

 

x



v g

 

h



_ 











for all





Pivot Mechanism とは？

参加制約をみたす

VCG メカニズムの中で

もっとも

CP の収入をたかめるメカニズムのこと

For every

i



N

and



_i

 

_i

,

(

) min

( ( ),

)

i i i i j j j N

h

v g





_

 

 _





Pivot Mechanism においては、 for every i and N _i  _i,

( ( ),

)

( )

( ( ),

)

(

) 0

i j i j j i i j N

v g

 

x



v g

 

h



_ 











for all



_i



_i, where the equality holds for some



_i



_i

さらに追加仮定として…

( , ) 0

i i

v a





for all

i



N

,

a



A

, and



_i



_i

および

There exists



_i



_i such that

( , ) 0

i i

v a





for all

a



A

配分に関心ないタイプ



_i が存在する（オークションでは財評価ゼロのタイプ：



_i



0

） この追加仮定下では

ピヴォット・メカニズムにおける徴収額

_{h m}

_i

₍

_i

₎

_は

\{ }

(

) max

( ,

)

i i j j a A j N i

h



_

v a



 _





「プレーヤー

i

抜きでの最大化総余剰」に一致

追加仮定下では ピヴォット・ＶＣＧメカニズムにおける支払いルールは \{ } /{ }

( )

( ( ),

) max

( ,

)

i j j j j a A j N i j N i

x m

v g m m

v a m

  

 







となる 「自分がいなかった時の他のプレーヤーの最大便益： \{ }

max

_j

( ,

_j

)

a A j N i

v a m

 _



」 ―「自分がいる場合の他のプレーヤーの便益： \{ }

( ( ),

)

j j j N i

v g m m





」

＝

「自分がいることによって被る他のプレーヤーの損失分」

を

CP に支払うことになる

Marginal Contribution（限界的貢献度）

ピヴォット・メカニズムにおいて、各プレーヤーの利得は \{ }

( ( ), )

( )

( ( ),

) max

( ,

)

i i i j j j j a A j N j N i

v g

 

x



v g

 

v a



  











\{ }

max

_j

( ,

_j

) max

_j

( ,

_j

)

a A a A j N j N i

v a



v a



 _  _









となる。これはつまり

Marginal Contribution（限界的貢献度）！

「自分がいることによって総余剰がどのくらい高まるか」

が利得になっている！

4.3. 二位価格入札は Pivot Mechanism である

Pivot Mechanism:

\{ } \{ }

( )

( ( ),

) max

( ,

)

i j j j j a A j N i j N i

x m

v g m m

v a m

  

 







0 max

_j

max

_j j i



j i



  



if

g m

( )



i

（落札）

max

_j

max

_j

0

j i



j i



 





if

g m

( )



i

（非落札） ∴ 二位価格入札はピヴォット・メカニズム！

＊

_{二位価格入札のコペルニクス的発想転換}

価格の決まり方（いくら？高い安い？）

⇒ 配分の効率性：二位価格を支払う（自分がいることで失う他者の便益） ⇒ ピヴォット・メカニズムへ一般化！

ＶＣＧメカニズムはすごいメカニズムデザイン！

１）

State Space に"connectedness"という数学的条件が備わっていると、VCG 以外

には、効率的

incentive compatible mechanism in dominant strategy は存在しない。

（

Green-Laffont-Holmstrom Theorem）

Theorem 7-2 (Uniqueness)：

Suppose that for any



: A



R

and any i



N

, there

exists



_i

 such that

_i

v

_i

( ,





_i

)





. Then, VCG mechanisms are only direct

mechanisms satisfying DIC.

２）優位戦略を

_{BNE に置き換えても、Pivot mechanism より高収入を CP にもた}

らす

_{incentive compatible mechanism in BNE (with participation constraint) は存在}

しない。

（後述する「収入同値定理（

_{Revenue Equivalence Theorem）」から導かれ}

る）

しかし、

VCG メカニズムにも問題点がある

１）Private Values の仮定が必要 Interdependent Values の場合には嘘をつくインセンティブ考えられる \{ } \{ }

( ( ), )

( ( ), )

( (

,

), )

( (

,

),

,

)

i j i i i j i i i i j N i j N i

v g

 

v g

 

v g m



_



v

g m



_

m



_  











となる

_m

_i





_i が存在しうる ２）談合（カルテル）が成立しやすい（後述） ３）収支均衡しない ４）機会費用＝０とは限らない場合、CP の赤字が解消されない（後述） ５）Cognitive complexity: 正直が優位戦略にもかかわらずわかりにくい 二位価格ですら現実にあまりつかわれていない 反論： せり上げ入札： すごく現実に使われている 二位価格入札と論理的に同じ（後述） ６）Computational Complexity 複雑な配分問題になると効率的配分の算出が難しい

Algorithmic Game Theory: New Field of Game Theory

宿題４（第４章まとめ）：一週間後の午前中までに教務に提出すること

https://sites.google.com/view/2018uteconmd/