Lec2 14 最近の更新履歴 yyasuda's website

Lecture 14: Mechanism Design

Advanced Microeconomics II

Yosuke YASUDA

Osaka University, Department of Economics yasuda@econ.osaka-u.ac.jp

January 20, 2015

Mechanism Design

This lecture is mostly based on Chapter 14 “Mechanism Design” of Tadelis (2013).

There are many economic and political situations in which some central authority wishes to implement a decision that depends on the private information of a set of players. The theory of mechanism design is the study of what kinds of mechanisms such a central authority (or mechanism designer) can devise in order to reveal some or all of the private information from the group of players who interact each other.

In essence, the mechanism designer will design a game to be played by the players, and in equilibrium the designer wishes to both reveal the relevant information and act upon it.

2 / 16

Formulate Private Information

Environment

N = {1, 2, . . . , n} : A set of players. X : A set of public alternatives. θ_i ∈ Θ_i : Player i’s type.

Θi : Player i’s set of types, or i’s type space. θ= (θ₁, θ₂, . . . , θ_n) ∈ Θ : The state of the world. Θ = Θ1× Θ2× · · · × Θn : The state space.

✞

✝

☎

Rm The braw of θ is according to some prior distribution φ(·)✆ over Θ. We assume that θ_i is player i’s private information and that the prior φ(·) is common knowledge.

Quasilinear Preferences

Suppose that player i is given an amount of money equal to m_i ∈ R and that public alternative x ∈ X is chosen.

Then, player i’s payoff is given by vi(x, mi, θi) = ui(x, θi) + mi,

where ui(x, θi) is the money-equivalent value of alternative x ∈ X. This assumes the case of private values in which player i’s payoff does not depend directly on other players’ types. If it does, then it is called common values case. The outcome (of the mechanism) is described by

y= (x, m1^{, m}2, . . . , m_n) ∈ Y.

4 / 16

Social Objectives

The mechanism designer’s objective is given by a choice rule, a mapping from a state of the world to an outcome:

f(θ) = (x(θ), m₁(θ), m₂(θ), . . . , m_n(θ)),

where x(θ) ∈ X and^Pn_i=1mi(θ) ≤ 0; the latter requires that the monetary payments have to be self-financed.

x(θ) : The decision rule

(m1(θ), m2(θ), . . . , mn(θ)) : The transfer rule

✞

✝

☎

Ex Allocation of Private Good✆ X =

(

(x1^{, x}2, . . . , x_n) | xi ∈ {0, 1} and

n

X

i=1

x_i = 1. )

Mechanisms as Bayesian Games

Definition 1 (Mechanism)

A mechanism, Γ =< A1^{, A}2, . . . , A_n, g(·) > is a collection of n action sets and an outcome function g : A₁× A₂× · · · × An→ Y .

A (pure) strategy for player i in the mechanism Γ is a function that maps types into actions, si : Θi→ Ai

The payoff of the players are given by vi(g(s), θi). Definition 2 (BNE)

The strategy profile s^∗(·) is a Bayesian Nash equilibrium of the mechanism Γ if for every i ∈ N and for every θi ∈ Θi,

E_θ−i[vi(g(s^∗_i(θi), s^∗_−i(θ_−i)), θi|θi)] ≥ Eθ_−i[vi(a^′_i, s^∗_−i(θ_−i)), θi|θi)] for all a^′_i ∈ Ai.

6 / 16

Implementation

Definition 3

A mechanism Γ implements the choice rule f (·) if there exists a Bayesian Nash equilibrium of the mechanism of Γ, s^∗ such that

g(s^∗₁(θ₁), s^∗₂(θ₂), . . . , s^∗_n(θ_n)) = f (θ) for all θ ∈ Θ.

✞

✝

☎

Fg Figure 14.1 in Tadelis.✆

The concept is sometimes called partial implementation because it requires that the desired outcome be an equilibrium, but allows other undesirable equilibrium outcome as well. The implementation without so-called bad equilibria in which f(θ) is not implemented is called full implementation.

Revelation Principle (1)

The revelation principle, due to a seminal work by Myerson (1979) and others, is a fundamental tool for designing mechanisms. Definition 4

A direct (revelation) mechanism is a mechanism in which each player’s only action is to submit a message about her type. That is, action sets satisfy Ai = Θi for every player i.

In direct mechanisms, g(a) = g(θ) = f (θ). Definition 5

The choice rule f (·) is truthfully implementable in BNE if truth-telling is a BNE strategy in the direct mechanism, i.e., if for all θ the direct mechanism has a BNE s^∗_i(θ_i) = θ_i for all i:

E_θ−i[vi(f (θi, θ_−i), θi|θi)] ≥ E_θ−i[vi(f (ˆθi, θ_−i), θi|θi)] for all ˆθ_i ∈ Θ_i.

8 / 16

Revelation Principle (2)

Theorem 6 (Revelation Principle: BNE)

A choice rule f(·) is implementable in BNE if and only if it is truthfully implementable in BNE.

That is, any BNE (of any Bayesian game) can be attained by a truth-telling BNE of some direct mechanism.

When no direct mechanism can achieve some outcome in a truth-telling BNE, no mechanism (no matter how it were general or complicated) can achieve the same outcome. In light of the revelation principle, we can restrict our attention to direct mechanisms when searching for some desirable mechanism.

Revelation Principle: Proof

Proof.

Let s^∗: Θ → A be the BNE of the original mechanism with the outcome function g(·). Consider the direct mechanism which selects the corresponding outcome given reported types.

The choice rule of the direct mechanism f (˜θ) is set equal to g(s^∗(˜θ)) for any combination of revealed types ˜θ∈ Θ. Then, it is easy to show that truth-telling, ˜θ_i = θ_i for all i, must be a BNE of this direct mechanism.

Suppose not, then for some i, there exists an action (in the original mechanism) a^′_i = s^∗_i( ˜θ_i) 6= s^∗_i(θi) such that

E_θ−i[v_i(g(a^′_i, s^∗_−i(θ_−i)), θ_i|θ_i)]

> E_θ−i[v_i(g(s^∗_i(θ_i), s^∗_−i(θ_−i)), θ_i|θ_i)],

which contradicts to that s^∗ is a BNE of the original game.

10 / 16

Dominant Strategies

Definition 7 (DSE)

The strategy profile s^∗(·) is a dominant strategy equilibrium of the mechanism Γ if for every i ∈ N and for every θi ∈ Θi,

v_i(g(s^∗_i(θi), a−i), θi) ≥ vi(a^′_i, a_−i), θi) for all a^′_i ∈ A_i and for all a_−i∈ A_−i. Theorem 8 (Revelation Principle: DSE)

A choice rule f(·) is implementable in DSE if and only if it is truthfully implementable in DSE.

To check if f (·) is implementable in DSE we need only check that f(·) is truthfully implementable in DSE:

v_i(f (θi^{, θ}−i), θi) ≥ vi(f (˜θ_i, θ_−i), θi) for all ˜θ_i ∈ Θ_i and for all θ_−i ∈ Θ_−i.

Pareto Efficiency

In what follows, we focus on quasilinear environment in which each player has quasilinear preferences:

v_i(x, mi^{, θ}i) = ui(x, θi) + mi^.

Theorem 9

Given a state of the world θ∈ Θ, an alternative x^∗∈ X is Pareto efficient if and only if it is a solution to

maxx∈X n

X

i=1

ui(x, θi).

Definition 10

A decision rule x^∗(·) is the first-best decision rule if

x^∗(θ) ∈ arg max

x∈X n

X

i=1

u_i(x, θ_i) ∀θ ∈ Θ.

12 / 16

VCG Mechanism

Definition 11 (VCG)

The choice rule f (ˆθ) = (x^∗(ˆθ), m₁(ˆθ), . . . , m_n(ˆθ)) is a Vickrey-Clarke-Groves (VCG) mechanism if x^∗(·) is the first-best decision rule and if for all i ∈ N

m_i(ˆθ) =^X

j6=i

u_j(x^∗(ˆθ_i, ˆθ_−i), ˆθ_j) + hi(ˆθ_−i),

where h_i(ˆθ_−i) is an arbitrary function of ˆθ_−i.

The general family of choice rules was first described by Groves (1973).

Vickrey (1961) and Clarke (1971) had studied particular instances of such mechanisms.

Theorem 12

Any VCG mechanism is truthfully implementable in DSE.

Strategy Proofness of VCG: Proof

Proof.

In the VCG mechanism, each player i maximizes the sum of ui and m_i, u_i(x^∗(˜θ_i, ˆθ_−i), θ_i) + m_i(˜θ_i, ˆθ_−i):

˜max

θi∈Θi

u_i(x^∗(˜θ_i, ˆθ_−i), θi) +^X

j6=i

u_j(x^∗(˜θ_i, ˆθ_−i), ˆθ_j) + hi(ˆθ_−i).

Since hi(ˆθ_−i) does not affect i’s choice, for any reported types ˆθ_−i, it is optimal for i to report ˜θ_i that maximizes total surplus,

˜max

θi∈Θi

u_i(x^∗(˜θ_i, ˆθ_−i), θi) +^X

j6=i

u_j(x^∗(˜θ_i, ˆθ_−i), ˆθ_j)

Given that x^∗ is the first-best decision rule, ˜θ_i = θi, i.e., truth-telling, becomes i’s dominant strategy.

14 / 16

Clarke’s Pivotal Mechanism

Definition 13 (Pivotal Mechanism)

The pivotal mechanism a class of VCG mechanisms such that h_i(ˆθ_−i) = −^X

j6=i

u_j(x^∗_−i(ˆθ_−i), ˆθ_j)

where

x^∗_−i(ˆθ_−i) ∈ arg max

x∈X

X

j6=i

uj(x, ˆθj)

is the first-best choice of x if player i were absent. The transfer mi is always non-positive (i.e., payment):

m_i(ˆθ) =^X

j6=i

u_j(x^∗(˜θ_i, ˆθ_−i), ˆθ_j) −^X

j6=i

u_j(x^∗_−i(ˆθ_−i), ˆθ_j).

Vickrey’s Second Price Auction

Definition 14

The Vickrey (second price) auction is a pivotal mechanism in a situation where an indivisible private object is allocated to a player. The first-best decision rule (allocation rule) x^∗ solves

(x₁,...,xmaxn_)∈{0,1}ⁿ

X

i∈N

θ_ix_i subject to ^X

i∈N

x_i = 1,

which results in allocating the good to the player with the highest valuation, i^∗ = arg max_i∈Nθ_i. The winner i^∗’s payment is

−m_i^∗(ˆθ) = ^X

j6=i^∗

u_j(x^∗_−i∗(ˆθ_−i^∗), ˆθ_j) −^X

j6=i^∗

u_j(x^∗(˜θ_i^∗, ˆθ_−i^∗), ˆθ_j)

= max

j6=i^∗

θˆj − 0 = max

j6=i^∗

θˆj,

the highest valuation among the losing players.

16 / 16