メカニズムデザイン・宿題解答 utgame2017 solution05 revised

メカニズムデザイン 宿題 5

奥村 恭平

^∗†‡

November 17, 2017

今回の宿題は難しかったと思います．順序統計量や条件付き期待値等，オークション理論で頻出す る概念に慣れるためにも，十分に復習するようにしてください．

(1) Virtual valuation

_を求めよ

N :

= {

1, . . . , n

}

, ωi ^i.i.d.

^∼

U

[

0, 1

]

とする．pi

⁽

^ωi

^{) =}

1, Pi

⁽

^ωi

^{) =}

^ωi

⁽

^ωi

^{∈ [}

0, 1

])

に注意すると，Virtual valuationは，

MRi

⁽

i, ωi

^{) =}

^ωi

⁻

¹

−

Pi

⁽

^ωi

⁾

pi

⁽

^ωi

⁾

=

^ω_i

− (

1

−

^ω_i

) =

2ωi

⁻

1 となることがわかる．これは^ω_iについて単調増加である．

補足コメント^:

オークションにおいて，virtual valuationが単調増加であるための十分条件としては，「hazard rateが 単調増加である」 i.e.

λ

₍

ω_i

₎

_:

₌

^pi

⁽

^ωi

⁾

1

−

P_i

(

^ω_i

)

と定義したときの^λが^ω_iについて単調増加である というものが有名です．Hazard rateは，直感的に は，分布関数P

(

t

)

を「ある時点tまでに死ぬ確率」と考えると，「ある時点tまで生き延びてきたという 条件のもとで，時点tに死ぬ確率(密度)」と解釈することができるような概念であり，これが増加する というのは，「だんだん壊れやすくなる」といった状況に対応していると解釈できます．オークション理 論ではhazard rateがしばしば登場します．

例えば

[

0, 1

]

区間上の一様分布の場合は

λ

₍

ω_i

_{) =}

^pi

⁽

^ωi

⁾

1

−

Pi

⁽

^ωi

⁾

=

¹

1

−

^ω_i となるので，この条件が満たされます．

Hazard rateの大小は，stochastic dominanceという概念と密接に関係しており，確率変数間の期 待値の大小を比較するのに役立ちます．興味のある方は，Krishna (2009)のAppendixを読んでみて下 さい．

(2)

留保価格付き SPA が収入を最大化することを示し，また，そのときの期待収入を示せ

コメント

まず，収入同値定理より，売り手が最大化すべきは，

max

g∈Gb ^E

[

∑

i∈N

MRi

⁽

g

(

^ω

)

, ω

)

]

(1)

∗first-year master student at Graduate School of Economics, the University of Tokyo

†E-mail: utgame2017@gmail.com

‡誤り等見つけた場合は教えて頂ければ幸いです．質問がある場合も上のメールアドレスまでご連絡ください．

, where bG is the collection of all allocation rules that satisfy BIC and IIR with proper payment rules.¹ となります．しかし，G^bそのものを特定するのは一般に困難であるため，「全ての配分ルールの集合をG とした上で，まず，

maxg∈G ^E

[

∑

i∈N

MRi

⁽

g

(

^ω

)

, ω

)

]

(2)

の最適解g^∗を求め，それがBIC (と

∀

i : y^∗_i

(

0

) =

0)を満たすことを期待する」という方針(期待収入最 大化メカニズムを求めるときの常套手段)でいきます．²

答

Reserve priceを1/2にした上で二位価格入札を行えばよい．その際の期待収入は，

(

n

−

1

+

2⁻ⁿ

)

/

(

n

+

1

)

． 解⁾

(2-1)

留保価格付き二位価格オークションが，期待収入最大化メカニズムであることを示せ．

∵ ₎

Step 1:_緩和問題(2)_を解く

MRi

⁽

a, ωi

^{) =}

{MRi

⁽

i, ωi

⁾

if a

=

i

0 o.w.

と，virtual valuationの単調増加性に注意すると，(2)の最適解gは， g

(

^ω

)

:

=

{arg maxi∈NMRi

⁽

i, ωi

⁾

if

∃

i

∈

N; MRi

⁽

i, ωi

^{) ≥}

0

∅

_o.w.

=

{i if ωi

^≥

yi

⁽

^ω−i

⁾

∅

_if

_∀

_{i; ωi}

<

_yi

₍

ω_−i

₎

, where yi

⁽

^ω−i

⁾

:

=

inf

{

^ω_i

|

MRi

⁽

i, ωi

^{) ≥}

0,

∀

j

̸=

i; MRi

⁽

i, ωi

^{) ≥}

MRj

⁽

j, ωj

^)}

期待支払い同値定理(スライド11,ページ13の一番下の式)より，gがBICを満たすためには，対応 する支払いルールxは，

E

[

xi

⁽

^ω

^{)] =}

E

[

vi

⁽

g

(

^ω

)

, ω

)] −

E [_{∫ ω}

i

0 ^vi2

⁽

^g

⁽

ω^′

i^{, ω−i}

⁾

^,

⁽

^ωi^{′, ω−i}

⁾⁾

^dωi^′

]

−

y^∗_i

(

0

)

を満たす必要がある．このためには例えば，

xi

⁽

^ω

^{) =}

vi

⁽

g

(

^ω

)

, ω

) −

∫ ω_i 0 ^vi2

⁽

^g

⁽

ω^′

i^{, ω−}i

⁾

,

(

^ω′_i, ω−i

⁾⁾

dω^′_i とすればよく，

vi

⁽

g

(

^ω_i^′, ω−i

⁾

,

(

^ω_i^′, ω−i

^{)) =}

{ω^′

i ^{if ω′}i

^≥

^yi

⁽

^ω−i

⁾

0 o.w.

vi2

⁽

g

(

^ω_i^′, ω−i

⁾

,

(

^ω_i^′, ω−i

^{)) =}

{1 if ω^′_i

≥

yi

⁽

^ω−i

⁾

0 o.w. に注意すると，

xi

⁽

^ω

^{) =}

{ω_i

_{− (}

ω_i

₋

_yi

₍

ω_−i

_{)) =}

_yi

₍

ω_−i

₎

_{if ωi}

_≥

_yi

₍

ω_−i

₎

0 o.w.

1タイプゼロの時が評価最低なので，IIRの条件は，BICと∀i : y^∗_i(0) =0が満たされていれば自動的に満たされます． 2このように，「まず，考える解の集合を簡単な集合にしたときの解きやすい最適化問題（緩和問題）を解いた上で，その解 を基に，元の最適化問題を解くことを試みる．」という方策は，複雑な最適化問題を解く時にしばしば用いられます．

となることがわかる．Virtual valuationの単調増加性と分布の対称性より，

MRi

⁽

i, ωi

^{) ≥}

MRj

⁽

j, ωj

^{) ⇐⇒}

^ωi

^≥

^ωj (3) となるので，(3)より，

yi

⁽

^ω−i

^{) =}

max

{

MR⁻_i ¹

(

0

)

, max

j̸=i

ω_j

_}

となるが，これは，reserve priceをMR⁻_i ¹

(

0

)

としたときの二位価格入札の支払いルールと一致してい る．³この問題の場合は，MR⁻_i ¹

(

0

) =

1/2なので，reserve priceを1/2として二位価格入札を行った ときの支払いルールがこれにあたる．gも，reserve price付き二位価格入札の配分ルールになっている ことが確認できる．

Step 2: BIC_と

∀

i : y^∗_i

(

0

) =

0_{のチェック}

Step 1で求めたdirect mechanism(reserve price付きの二位価格入札)

(

g, x

)

が，BICと

∀

i : y^∗_i

(

0

) =

0 を満たすことを確認できれば，

(

g, x

)

がBIC, IIRを満たす期待収入最大化メカニズムであることがわか る．詳細は省略する．（各自確認されたし．）⁴

以上より，reserve priceを1/2と設定したときの二位価格入札は，BIC, IICを満たす期待収入最大 化直接メカニズムになっていることがわかる．

(2-2)

_{期待収入を求めよ}

まず，期待収入Rは

R

=

E

[

max

{

MR1

(

1, ω1

)

, . . . , MRn

(

n, ωn

)

, 0

}]

となることが確認できる．最大のvirtual valuationを表す確率変数を

Y1:

=

max

{

MR1

(

1, ω1

)

, . . . , MRn

(

n, ωn

)} =

max

i∈N

⁽

^2ωi

⁻

¹

⁾

と定義し，Y1^{の分布関数を}FY1^{,密度関数を f}Y1^{とすると，}

FY₁

⁽

y

) =

P

(

Y1

^≤

y

) =

P

(

max

i∈N

⁽

^2ωi

⁻

¹

^{) ≤}

^y

^{) =}

^P

^(∀

^{i; 2ωi}

⁻

¹

^≤

^y

⁾

= [

P

(

2ωi

⁻

1

≤

y

)]

ⁿ

=

[

P (

ω_i

_≤

^y

⁺

¹ 2

)]n

=

(y

+

1 2

)n

(

y

∈ [−

1, 1

])

fY1

⁽

^y

^{) =}

d

dy^FY1

⁽

^y

⁾

=

(1

2 )n

n

(

y

+

1

)

ⁿ⁻¹

(

y

∈ [−

1, 1

])

となることがわかる．よって，期待収入は

R

=

E

[

max

{

Y1, 0

}] =

∫ ₁

−1^max

^{

^{y, 0}

^}

^fY1

⁽

^y

⁾

^dy

=

∫ ₀

−1⁰

^·

^fY1

⁽

^y

⁾

^dy

⁺

∫ ₁

0 ^{y fY1}

⁽

^y

⁾

^dy

=

∫ ₁

0 ^y

^·

(1 2

)n

n

(

y

+

1

)

ⁿ⁻¹dy

=

(1

2 )n

n

∫ ₁

0 ^y

⁽

^y

⁺

¹

⁾

n−1_dy

=

ⁿ

⁻

¹

⁺

²

−n

n

+

1

3_{この記法は若干sloppyです．MRd}

i^(ωi^):=MRi^{(i, ω}i^{)として，MRd}

−1

i ^{(0)と書くのが正確です．}

4実は，このようなオークションの利得関数形の下では，gが^ω_iについて増加であることから，BICがすぐに従うことが言 えます．(授業では，より一般的な利得関数形を扱っているので，必ずしもそうとは限りません．) Krishna (2009)の第５章に 分かりやすい解説があるので，興味のある方は読んでみて下さい．

となる．⁵

(3) コメント

Bulow and Klemperer (1996)の定理が成立することを，簡単な例について確認する問題でした．

この定理は現実問題に関して重要な含意があります:いま仮に自分が政策担当者で，なるべく政府の 収益を最大化するようにある一つの財を売りたいとします．限られた時間・予算の中で，どのように財 を売るべきでしょうか？

期待収入最大化メカニズムについて学んだ人は，「期待収入最大化メカニズム(この場合は留保価格 付き二位価格入札)を設計してやろう」と思うかもしれません．(もしくは，ある特定の数の企業に的を 絞った上で，時間をかけて交渉をし，高値で売ってやろうと思うかもしれません．)しかし，これには 一般的にかなりのコストがかかると推察されます．交渉には多大なコストがかかることが予想されます し，適切な留保価格を設定するためには，まず，入札者に関する情報を十分集めた上で，入札者のタイ プが従う分布を正確に推定する必要があります．その上，留保価格を設定するのであれば，それを説明 する書類を新たに作成したり，オークションについてあまり理解していない上司や関連部署の人を説得 したりする必要があるかもしれません．Bulow and Klemperer (1996)の定理は，そんなところにエネル ギーを使うよりも，留保価格なしの二位価格入札をすると早々に決めた上で，「参加者を一人でも多く集 める」ということに注力する方がよいということを示唆しています．

解⁾

(3-1)期待収入が高くなることを，例について実際に示せ

Y₁^′ :

=

max

{

MR1

⁽

1, ω1

⁾

, . . . , MRn+1

⁽

n

+

1, ωn+1

^{)} =}

max

i∈{1,...,n+1}

^{

^MRi

⁽

^{i, ωi}

^)}

とすると，問(2)と同様にして，

P

(

Y₁^′

≤

y

) =

(y

+

1 2

)n+1

f_Y^′

1

⁽

^y

^{) =}

(1 2

)n+1

(

n

+

1

)(

y

+

1

)

ⁿ となることがわかる．この場合の期待収入をR^′とすると，

R^′

=

E

[

Y₁^′

]

=

∫ ₁

−1^{y fY}

1′

⁽

^y

⁾

^dy

=

(1

2 )n+1

(

n

+

1

)

∫ ₁

−1^y

⁽

^y

⁺

¹

⁾

n_dy

₌

²

⁽

ⁿ

⁺

¹

⁾

n

+

2

⁻

¹

=

ⁿ n

+

2 となるので，⁶

R^′

−

R

=

ⁿ n

+

2

⁻

n

−

1

+

2⁻ⁿ n

+

1

=

²

⁻

²

−n

₍

_n

₊

₂

₎

(

n

+

1

)(

n

+

2

) ^>

⁰

⁽

ⁿ

^{∈ N \ {}

⁰

^})

5最後の等式は，例えば，

∫ ₁

0 ^y(y+1)

n−1_dy=^{∫ 1}

0 ^{(y+1−1)(y+1)}

n−1_dy=^∫1 0 ^(y+1)

n_dy−^∫1 0 ^(y+1)

n−1_dy とすれば求まります．

6_{途中の計算は(2)}の場合と同様なので省略します．

より，「留保価格をつけて期待収入を最大化した二位価格入札」より，「(留保価格などの工夫を特にせず， 単に)参加者を一人増やした上で行った二位価格入札」の方が期待収入が大きいことがわかる．

(3-2)期待収入が高くなる理由⁽定理^5-8の簡単なケースについての証明⁾⁷

実は，分布対称性とvirtual valuationの単調増加性に加えてもう一つ，定理が成立するための重要な前 提がある．⁸

[Serious Bidders]:

∀

i; E

[

MRi

⁽

i, ωi

^{)] ≥}

0

Serious Biddersは，「どのbidderも，virtual valuation(売り手にとっての買い手の事実上の価値)の期 待値が，売り手の財評価より高い」ことを保証する．この条件が満たされているとき，

E

[

Y₁^′

|

Y1

^<

0

] =

E

[

max

{

Y1, MRn+1

⁽

n

+

1, ωn+1

^{)} |}

Y1

^<

0

]

≥

E

[

MRn+1

(

n

+

1, ωn+1

) |

Y1

^<

0

]

=

E

[

MRn+1

(

n

+

1, ωn+1

)] (∵

独立性

)

≥

0

(∵

Serious Bidders

)

に注意すると，

E

[

max

{

Y1, 0

}] =

E

[

max

{

Y1, 0

} |

Y1

^≥

0

] ·

P

(

Y1

^≥

0

) +

E

[

max

{

Y1, 0

} |

Y1

^<

0

] ·

P

(

Y1

^<

0

)

=

E

[

Y1

|

Y1

≥

0

] ·

P

(

Y1

≥

0

) +

E

[

0

|

Y1

^<

0

] ·

P

(

Y1

^<

0

)

≤

E^[Y₁^′

|

Y1

^≥

0^]

·

P

(

Y1

^≥

0

) +

E^[Y₁^′

|

Y1

^<

0^]

·

P

(

Y1

^<

0

)

=

E

[

Y₁^′

]

となることがわかる．以上より，定理が示された．⁹

7_{ここでの証明は，}independent private values(IPV)の設定においての証明になっています．実は，IPVでない場合(affiliated signalsの場合)についてもこの結果は拡張できます．興味のある方は，Bulow and Klemperer (1996)を参照してください．

8問題のケースでは満たされている．各自確認されたし．

9直観的な説明を試みようと思ったのですが，思いの外難しく，諦めてしまいました．もし上手い直観的説明を思いついた 方は，是非教えてください．

おまけ: スライド 11, ページ 14 の別証

定理5-5の証明中の，

E [_∫ ω_i

0 ^vi2

⁽

^g

⁽

ω^′

i^{, ω−i}

⁾

^,

⁽

^ωi^{′, ω−i}

⁾⁾

^dωi^′

]

=

E^ω_−i [_{∫ 1}

0

^{

^vi2

⁽

^g

⁽

ω

₎

_{, ω}

₎₍

₁

₋

_Pi

₍

ω_i

_))}

_dωi ]

を示す箇所について，先生の説明ではよくわからなかった人向けに，愚直な積分計算によっても証明で きることを紹介しておきます．

E [_∫ ω_i

0 ^vi2

⁽

^g

⁽

ω^′

i^{, ω−}i

⁾

^,

⁽

^ω′i^{, ω−}i

⁾⁾

^dω′i

]

=

E^ω_−i [_{∫ 1}

0

{_∫ ω_i 0 ^vi2

⁽

^g

⁽

ω^′

i^{, ω−}i

⁾

^,

⁽

^ω′i^{, ω−}i

⁾⁾

^dω′i

}

p_i

(

^ω_i

)

dω_i ]

=

E^ω_−i [_{∫ 1}

0

{_{∫ 1}

ω^′

i

vi2

⁽

g

(

^ω′_i, ω−i

⁾

,

(

^ω′_i, ω−i

⁾⁾

pi

⁽

^ωi

⁾

dωi

} dω_i^′

]

=

E^ω_−i [_{∫ 1}

0

{v_i2

(

g

(

^ω_i^′, ω−i

⁾

^,

⁽

^ω′i^{, ω−}i

⁾⁾⁽

¹

⁻

^Pi

⁽

^ω′i

⁾⁾

}dω_i^′ ]

=

E^ω_−i [_{∫ 1}

0

^{

^vi2

⁽

^g

⁽

ω

₎

_{, ω}

₎₍

₁

₋

_Pi

₍

ω_i

_))}

_dωi ]

一つ目の等式では，いままで^ω1, . . . , ωnというn個の確率変数に関してとっていた積分のうち，特に^ω_i に関する部分に着目しています．二つ目の等式は積分順序の交換，三つ目の等式は部分積分をすればそ れぞれ導けます．最後の等式は，単に積分変数名を付け替えただけです．

References

Bulow, Jeremy and Paul Klemperer, “Auctions versus Negotiations,” American Economic Review, 1996, 86 (1), 180–94.

Krishna, Vijay, Auction theory, 2nd ed., Academic Press/Elsevier, 2009.