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

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

奥村 恭平

^∗†‡

November 4, 2017

コメント

• 答案はなるべくtexで書いてください．お願いします．tex環境の構築の仕方については，奥村晴 彦ら(2017)『[改訂第七版] L^A_TEX2ε美文書作成入門』などを参考にしてください．

• 「メカニズムデザイン・宿題解答」のところに，この文書の元になったtexファイルを置いておき ます．数式の入力の仕方等参考にしてください．

• 「宿題に関しての諸注意」をキチンと読んでください．両面に書いていた人が3人，提出時刻に遅 れた人が10人程いました．

• 横書きの文章をホチキスで留める場合は左上を留めましょう．

• 答えを書くときは，(可能な場合は，)まず最初に答え^/これから示すことを明示した上で，その下 にその証明・説明を書くようにしてください．たとえば，何も断らずにいきなり証明を始め，証明 の最後に証明すべき命題を書くようなことはやめてください．

• 場合分けの仕方がわかりにくい人が多くいました．ちゃんと，(i), (ii)のようにセクションをわけ， どう場合分けをしているのかが一目でわかるように答案を書いてください．

• interdependent valuesをindependent valuesと書いている人が山ほどいました．意味が真逆に なるので注意してください．

Notation

•

∃

x

∈

Xは，「集合Xのある元xが存在して∼」，

∀

x

∈

Xは，「集合Xの任意の元xについて∼」の 意味です．これらの記号の扱いに不安のある人は，適当な数学の本で勉強することをオススメし ます．(例えば，新井敏康(2016)『集合・論理と位相』 東京図書 の第1章・第2章)

• ある関数f : X

→

Yについて，「f

(

x

) ≡

c」は，「

∀

x

∈

X; f

(

x

)

:

=

c」の意味です．(「a :

=

b」は，

「aをbで定義する」，もしくは「aにbを代入する」の意味です．)

• X, Yが集合のとき，Y^Xで「XからYへの関数全ての集合」を表します．

つまり，Y^X:

= {

f

|

f : X

→

Y

}

です．

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

†E-mail: [email protected]

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

問 ¹

外部性がある二位価格入札の問題でした．

(1)

完備情報の場合の優位戦略

¹

を求めよ

コメント

おそらく，今回の宿題の中で一番難しい問題だったと思いますが，授業中に出されたヒントがあったた めか，多くの人が解けていました．均衡(この問題の場合は優位戦略(均衡))を求める際の一つの常套手 段は"guess and verify"，つまり，

1. まず，均衡となる戦略の組を(ときに「動物的直感」を用いて)予測する．

2. 予測した戦略の組が均衡であることを実際に確かめる．(上手くいかなかったら，1に戻る．) というものです．

Guess and verifyをする場合，まずguessを思いつくのが大変で，①パラメータにいろいろな値を

代入して簡単な例で実験②均衡が満たすべき条件を書き出す 等しながら，問題の形に合わせて，扱いや すい関数形(線形関数や対数関数など)を当てはめることが多いです．(扱いやすい形でないとguessす るのもverifyするのも大変．)この解説でも，guess and verifyで解いていきます．²

解⁾ Guess

授業で扱ったprivate valuesの二位価格入札では「自分のvaluationが高いときは勝ち，低いときは負け るのが良い」となっていたが，この問題のケースはちょっと異なっている．適当な値を^ω₁, ω2^に代入し

ながらいくつか例を作って考えてみると，「自分のvaluationが高いときでも，相手のvaluationも高い 場合は，(相手の戦略によっては)自分が勝たない方がむしろ得である場合がある」ということに気づく．

例えば，^ω₁:

=

1, ω2 :

=

0.9とし，player 2が正直に指値をしているような状況を考えてみる．この とき，player 1は，勝つと0.1

(=

1

−

0.9

)

の利得を得るが，負けると0.3

(=

0.9

×

1/3

)

の利得を得るの で，負ける方が得になる．

以上の考察を踏まえて，次のような戦略が優位戦略になることを推測できたとする．

si

(

^ω1, ω2

)

:

=

max {

ω_i

₋

¹ 3^{ωj, 0}

}

(

i

̸=

j

)

以下で，これが実際に優位戦略になっていることを示す．

(このguessができなくてこの設問が解けなかった人は，以下の解説を見る前に，「自力でこの戦略が

優位戦略になることを示せるか」を確認してから，解説を読むと良いと思います．)

Verify

プレイヤー1について，s1

⁽

^ω1, ω2

⁾

:

=

max

{

^ω₁

−

^ω₂/3, 0

}

が優位戦略になっていることを示す．(プレ イヤー2についてもほぼ同様に示せる．)優位戦略の定義より，示すべきは，

∀

^ω

∈

^Ω

∀

m1

∈

M1

\ {

s1

(

^ω

)} ∀

m2

∈

M2; u1

(

s1

(

^ω

)

, m2, ω

) ≥

u1

(

m1, m2, ω

)

(1) である．³以下，プレイヤー1が勝つ場合とプレイヤー1が負ける場合について場合分けして示す．

1dominant strategyに対しては，「支配戦略」という訳語が用いられることもあります．

2授業中に先生が出したヒントにしたがって(i.e.均衡が満たすべき必要十分条件を書き出して)解く方がスマートです．こ の解答では，①TAがこうやって解いたため②guess and verifyを紹介するため に，少し違った方法で示します．

3厳密には，授業中の優位戦略の定義では，これに加えて，

∀^ω∈^Ω∀m₁∈M₁\ {s₁(^ω)} ∃m2^∈M2; u₁(s₁(^ω), m2, ω) >u₁(m₁, m2, ω)

を示す必要がある(授業中の定理1.1の証明に"outline"とついているのは，この部分の証明をしていないため．)が，その部分 は省略する．各自確認されたし．

Case (i):_{プレイヤー}1_{が勝つ場合}i.e.m2

≤

s1

(

^ω

)

_の場合

u1

(

s1

(

^ω

)

, m2, ω

) =

^ω1

−

m2

となっている．1が勝つ限り，1の利得は変化しない．1が利得を変化させるためには，1が負けるよう にm1

^(<

m2

⁾

^をbidする必要がある．このときの1の利得は，

u1

(

m1, m2, ω

) =

¹ 3^ω2 Subcase (i-1): ω₁

−

^ω2/3

≥

0のとき

u1

⁽

s1

⁽

^ω

⁾

, m2, ω

) =

^ω₁

−

m2

≥

^ω₁

−

s1

⁽

^ω

^{) =}

^ω1

⁻

( ω₁

₋

¹

3^ω2 )

=

¹

3^ω2

⁼

^u1

⁽

^{m1, m2, ω}

⁾

Subcase (i-2): ω₁

−

^ω₂/3

^<

0のとき

このとき，s1

⁽

^ω

^{) =}

0である．m2

^>

0のときは1は負けているので，この場合には含まれない．m2

=

0 の場合はこの場合に含まれるが，この場合1は負けることができず，利得を変えることができない．

Case (ii): _{プレイヤー}1_{が負ける場合}i.e.m2

^>

s1

(

^ω

)

_の場合 u1

⁽

s1

⁽

^ω

⁾

, m2, ω

) =

¹

3^ω2

となっている．1が負ける限り，1の利得は変化しない．1が利得を変化させるためには，1が勝つよう にm1

^(≥

m2

⁾

をbidする必要がある．このときの1の利得は，

u1

⁽

m1, m2, ω

) =

^ω₁

−

m2

Subcase (ii-1): ω₁

−

^ω2/3

≥

0のとき

u1

(

m1, m2, ω

) =

^ω1

−

m2

^<

^ω1

−

s1

(

^ω

) =

¹

3^ω2

⁼

^u1

⁽

^s1

⁽

^ω

⁾

^{, m2, ω}

⁾

Subcase (ii-2): ω1

−

^ω2/3

^<

0のとき

u1

⁽

m1, m2, ω

) =

^ω₁

−

m2

^≤

^ω1

^<

¹

3^ω2

⁼

^u1

⁽

^s1

⁽

^ω

⁾

^{, m2, ω}

⁾

以上より，(1)が満たされていることがわかる．

(2)

不完備情報の場合，優位戦略が存在しないことを示せ

コメント

(1)でも少し見たように，自分のタイプがなんであれ，相手のタイプと戦略によって勝つのが良い場合も あれば負けるのが良い場合もあるため，「相手のタイプに依存させないと優位戦略が作れない」ことがポ イントです．以下の証明は，この直観を丁寧にくどくど述べているだけです．

解⁾⁴

プレイヤー1について，優位戦略が存在しないことを示す．(プレイヤー2についてもほぼ同様に示せ る．)優位戦略の定義より，次の命題が成立することを示せばよい．

∀

s1

^∈

M^Ω₁¹

∃

^ω

∈

^Ω

∃

m1

^∈

M1

^{\ {}

s1

⁽

^ω1

^{)} ∃}

m2

∈

M2; u1

⁽⁽

s1

⁽

^ω1

⁾

, m2

)

, ω

) <

u1

⁽⁽

m1, m2

)

, ω

)

4₍₁₎の結果と，「標準形ゲームでは優位戦略は存在するならば一意」「不完備情報ゲームでの優位戦略は，対応する完備情報 ゲームでの優位戦略でもある」という事実を用いればすぐに示せるが，ここでは，(1)の結果を経由せずに愚直に証明する．

Case (i):s1

(

^ω1

) ≡

0の場合

このとき，例えば^ω1 :

=

1, ω2:

=

0.03, m1 :

=

1, m2 :

=

0.1とすれば，

u1

⁽⁽

s1

⁽

^ω1

⁾

, m2

⁾

, ω

) =

0.01

^<

1

=

u1

⁽⁽

m1, m2

⁾

, ω

)

が成り立っていることがわかる．よって，s1

⁽

^ω1

^{) ≡}

0は優位戦略ではない．

Case (ii):

∃

^ω₁

∈

^Ω₁; s1

⁽

^ω1

^{) >}

0_の場合

s1

⁽

^ω1

^{) >}

0となる^ω₁

∈ (

0, 1

]

をひとつとり，固定する．(ω1 :

=

0の場合については，s1

⁽

^ω1

^{) >}

0とな るs1は不適であることがすぐに示せる．^ω2:

=

1, m2:

=

^ε, m1:

=

0を考えよ．)⁵

Subcase (ii-1): 0

^<

^ω1

^≤

1/3_のとき

ω_2:

₌

_{1, ω :}

_{= (}

ω_{1, ω2}

₎

_{とする．m2:}

₌

_s1

₍

ω₁

_{) −}

ε

_(>

₀

₎

_{, m1:}

₌

_{0とすれば，} u1

((

s1

(

^ω1

)

, m2

)

, ω

) =

^ω1

− (

s1

(

^ω1

) −

^ε

) <

¹

3

⁼

^u1

⁽⁽

^{m1, m2}

⁾

^{, ω}

⁾

が成立する．よって，このようなs1は優位戦略ではない．

Subcase (ii-2): 1/3

^<

^ω1

≤

1_のとき

s1

⁽

^ω1

^{) <}

^ω1としてよい．(s1

⁽

^ω1

^{) >}

^ω1が不適なのは明らか．s1

⁽

^ω1

^{) =}

^ω1のときは，^ω2が十分大 きく，m2がs1

⁽

^ω1

⁾

よりわずかに小さいときに，1は負けた方が得であることを考えればよい．)以下， ω_2:

₌

_{0, ω :}

_{= (}

ω_{1, ω2}

₎

_とする．

m2:

=

s1

⁽

^ω1

^{) +}

^ε

^(<

^ω1

⁾

, m1 :

=

0とすれば，

u1

⁽⁽

s1

⁽

^ω1

⁾

, m2

)

, ω

) =

0

^<

^ω1

^{− (}

s1

⁽

^ω1

^{) +}

^ε

^{) =}

u1

⁽⁽

m1, m2

)

, ω

)

が成立する．よって，このようなs1^{は優位戦略ではない．}

以上より，どんな関数s1 : Ω1

^→

M1も優位戦略になり得ないことが示せた．

(3) Private Values or Interdependent Values?

Interdependent values．自身のタイプのみならず，相手のタイプも自分の効用関数に影響している．

(4)

_{事後均衡を求めよ}

コメント

(1)の場合と異なり，相手のタイプに依存した戦略はとれません．(2)で見たように，この場合優位戦略 均衡は存在しませんが，事後均衡は存在します．(優位戦略均衡ではないが，事後均衡となっている戦略 の組の一例になっています．)事後均衡は，直観的には，オークションが終わったあとに相手の出した指 値を見て，「ああ，やっぱりああしておけばよかった」といったことがないような戦略の組だと考えられ ます．例によって，guess and verifyでいきます．

解⁾ Guess

各プレイヤーの状況が対称的なので，対称(かつ単調増加)な戦略の組が均衡になるだろうということが 推測される．次のような戦略の組が均衡になるのではないかと予測する．

s1

⁽

^ω1

⁾

:

=

²

3^{ω1, s2}

⁽

^ω2

⁾

^:

⁼

2 3^ω2 以下で，これが実際に均衡になっていることを示す．

5_εは「十分小さい正の実数」を表す．

Verify

ω₁

_≥

ω₂の場合についてのみ示す．(ω1

^<

^ω2の場合もほぼ同様に示せる．) プレイヤー¹について

u1

⁽

s1

⁽

^ω1

⁾

, s2

⁽

^ω2

⁾

, ω

) =

^ω₁

−

² 3^ω2

となっている．プレイヤー1が利得を変化させるためには，プレイヤー1が負ける必要があるが，仮に， プレイヤー1がs2

(

^ω2

)

より小さくbidした場合，(m1:

=

s2

(

^ω2

) −

^εとして，⁶)

u1

(

m1, s2

(

^ω2

)

, ω

) =

¹

3^ω2

⁼

^ω2

⁻

2

3^ω2

^≤

^ω1

⁻

2

3^ω2

⁼

^u1

⁽

^s1

⁽

^ω1

⁾

^{, s2}

⁽

^ω2

⁾

^{, ω}

⁾

となり，プレイヤー1は得をしないことがわかる．

プレイヤー²について

u2

⁽

s1

⁽

^ω1

⁾

, s2

⁽

^ω2

⁾

, ω

) =

¹ 3^ω1

となっている．プレイヤー2が利得を変化させるためには，プレイヤー2が勝つ必要があるが，仮に，プ レイヤー2がs1

⁽

^ω1

⁾

より大きくbidした場合，(m2 :

=

s1

⁽

^ω1

^{) +}

^εとして，)

u2

⁽

s1

⁽

^ω2

⁾

, m2, ω

) =

^ω₂

−

² 3^ω1

^≤

1

3^ω1

⁼

^u2

⁽

^s1

⁽

^ω1

⁾

^{, s2}

⁽

^ω2

⁾

^{, ω}

⁾

となり，プレイヤー2は得をしないことがわかる．

6_{細かいが，そのようなm}

1^をbidすることが不可能な場合(ω₂:=0のときは，s₂(^ω) =0となり，プレイヤー1はプレイ ヤー2より小さい額をbidできない．)は，そもそもプレイヤー1は利得を変化させることができないので，以下，s2^{(ω) >}0 というケースについてのみ考える．次の(ii)の場合においても同様の注意が言える．以下，そのような説明を省略する．