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

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

奥村 恭平^∗†‡ November 4, 2017

(1)

例えば，ω₁ := 1, ω₂ := 0．

このとき，ω₁+ ω₂= 1 > cなので，橋を建設するのが効率的だが，村民2について， [橋が建設された時の利得] = 0 − c/2 = −c/2 < 0 = [橋が建設されないときの利得] となるので，村民2は建設に反対する．

(2)

次のようなx1が答え．(x2 = −x1) ¹

x₁(ω₁, ω₂) :=







0 if ω₁+ ω₂< c or (ω₁≥ c/2 and ω₂≥ c/2) ω₁− c/2 if ω₁ ≥ c/2, ω₂< c/2

−(ω2− c/2) if ω1 < c/2, ω2≥ c/2

∵₎

利得が0以上のとき(利得が0のときは「建設される」「「建設されない」について無差別であるが，そのとき も)村民は建設に賛成するものと仮定する．x₁(ω₁, ω₂) + x₂(ω₁, ω₂) = 0より，x₁(ω₁, ω₂) = −x₂(ω₁, ω₂) であるので，以下，x₁についてのみ記す．

(i): ω₁+ ω₂ < c_のとき

この場合は建設しなくてよいので，特に何もしなくてよい．(何もしないと，どちらかの村民iについて

ωi < c/2が成立し，その村民iが建設に反対して橋は建設されない．つまり，ほっておいても効率的供

給が達成される．) (ii): ω₁+ ω₂ ≥ c_のとき

(ii-1): ω₁≥ c/2, ω₂≥ c/2_のとき

このときはなにもせずとも二人は賛成して効率的供給が達成されるので，特になにもしなくてよい．

(ii-2): ω₁≥ c/2, ω₂< c/2_のとき

この場合，村民1から多めに徴収し，それを村民2に与えることで，効率的供給が達成される．つまり， x₁(ω₁, ω₂) := ω₁−¹

2^c

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

†E-mail: utgame2017@gmail.com

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

1_{他にも，いろいろなx}

1が考えられます．あくまで一例です．

1

とすれば，

u₁(ω₁, ω₂) = ω₁− ¹

2^{c − x1(ω1, ω2) = 0} u2(ω1, ω2) = ω2−¹

2^{c + x1(ω1, ω2) = ω1+ ω2− c ≥ 0} となるので，村民は二人とも建設に賛成し，効率的供給が達成される．

(ii-3): ω₁ < c/2, ω₂ ≥ c/2_のとき

x₁(ω₁, ω₂) := − (

ω₂−¹ 2^c

) とすればよい．((ii-2)と同様の議論が成立．)

(ii-3): ω₁ < c/2, ω₂ < c/2_のとき

この場合は，そもそもω₁+ ω₂≥ cに反するので考えなくてよい． 以上より，x1は以下のように定めればよいことがわかる．

x₁(ω₁, ω₂) :=







0 if ω1+ ω2< c or (ω1≥ c/2 and ω2≥ c/2) ω₁− c/2 if ω₁ ≥ c/2, ω₂< c/2

−(ω₂− c/2) if ω₁ < c/2, ω₂≥ c/2

(3)

次のような，(g, (xi)i)が答え．

g(ω) =

{建設する if ω₁+ ω₂− c ≥ 0

建設しない o.w. ^{, xi(ω) =}







−c/2 if ω_j ≥ c

−(ωj− c/2) if ωi+ ωj ≥ c and ωj < c

0 o.w.

∵₎

この場合配分集合A := {建設する,建設しない}となっている．Pivot mechanismを作るためには， allocation rule gとpayment rule (x_i)_iを求める必要がある．

(i): g_について

gがefficientになるように定める必要がある．つまり，gは次の式を満たす．

∀ω ∈ Ω ∀a ∈ A; ^∑

j∈N

ν_j(g(ω), ω_j) ≥^∑

j∈N

ν_j(a, ω_j) ただし，

∑

j∈N

νj(a, ωj) =

{0 if a =建設しない

ω₁+ ω₂− c if a =建設する

である．以上より，次のようにgを定めると，gはefficientになることがわかる． g(ω) =

{建設する if ω₁+ ω₂− c ≥ 0 建設しない o.w.

また，このとき，

∑

j∈N

ν_j(g(ω), ω_j) = max{ω₁+ ω₂− c, 0} (1)

2

(ii): (x_i)_{iについて}

まず，一般にVCGメカニズムにおいて，payment ruleは次のように作るのであった． x_i(ω) := − ^∑

j∈N \{i}

ν_j(g(ω), ω_j) + h_i(ω_−i)

(i)でgは求まっているが，hiの決め方についてはVCGメカニズムは定めていない．Pivot mechanism はVCGメカニズムの中でも特にCentral Plannerの収入を最大化するメカニズムであり，それはh_iを 次のように定めることで得られるのであった．

hi(ω−i) := min

ωi∈Ωi





∑

j∈N

νj(g(ω), ωj)



 この問題の場合は，

∑

j∈N \{i}

νj(g(ω), ωj) = νj(g(ω), ωj) =

{ω_j − c/2 if ω₁+ ω₂ ≥ c

0 o.w.

∴ _{xi(ω) = −}

∑

j∈N \{i}

ν_j(g(ω), ω_j) + h_i(ω_−i)

=

{−(ω_j − c/2) + min_ωi∈Ωi

[∑

j∈N^{νj(g(ωi, ωj), ωj)}

] if ω₁+ ω₂ ≥ c

0 o.w.

(1)=

{−(ωj− c/2) + minωi∈Ωimax [ωi+ ωj− c, 0] if ω1+ ω2≥ c

0 o.w.

=







−c/2 if ω_j ≥ c

−(ωj− c/2) if ωi+ ωj ≥ c and ωj < c

0 o.w.

(4)

「任意のタイプの組について収支均衡を満たせるようなVCGメカニズム」が存在しないことを示したい． Pivot mechanismはVCGメカニズムの中でも収入を最大化するメカニズムであるので，Pivot mechanism において不可能なことを示せば十分．

(3)の結果を利用する． Case (i): ω1, ω2 ≥ c_のとき²

x1(ω) + x2(ω) = −c < 0 Case (ii): ω1 ≥ c, ω2< c_のとき

x₁(ω) + x₂(ω) = −^c

2^{− (ω1−} c

2^{) = −ω2 ≤ 0} 等号成立(i.e. 収支均衡)はω2:= 0のときのみ．

Case (iii): ω1 < c, ω2 ≥ c_のとき

x₁(ω) + x₂(ω) = −^c

2^{− (ω2−} c

2^{) = −ω1 ≤ 0} 等号成立(i.e. 収支均衡)はω1:= 0のときのみ．

2問に答えるためには，このときについてのみ示せば十分だが，参考のため，全ての^ωの組合せについて収支を示しておく．

3

Case (iv): ω₁< c, ω₂ < c_のとき Subcase (iv-1): ω₁+ ω₂ ≥ c_のとき

x₁(ω) + x₂(ω) = −(ω₁+ ω₂− c) ≤ 0 等号成立(i.e. 収支均衡)はω₁+ ω₂ = cのときのみ．

Subcase (iv-2): ω₁+ ω₂ < c_のとき

x₁(ω) + x₂(ω) = 0

以上より，ごく一部の場合を除いて，pivot mechanismでは収支が均衡しないことがわかる．

4