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

## 全文

(1)

### Lecture 11: Auction Theory

Yosuke YASUDA

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

January 13, 2015

(2)

### Auctions

Imagine that there is a (potential) seller who has a painting that is worth nothing to her personally. She hopes to make some money by selling the art through an auction.

Suppose there are two potential buyers, called bidders 1 and 2. Let x1 and x2 denote the valuations of the two bidders. If bidder i wins the painting and has to pay b for it, then her payoff is xi− b.

where x1 and x2are chosen independently by nature, and each of which is uniformly distributed between 0 and 1. The bidders observe their own valuations before engaging in the auction. The seller and the rival do not observe a bidder’s valuation; they only know the distribution.

In what follows, we study two prominent sealed-bid auctions: a first-price auction and a second-price auction.

The former is commonly used while the latter has great

theoretical importance and started to be applied in reality. 2 / 15

(3)

### First-Price Auction (1)

Bidders simultaneously and independently submit bids b1 and b2. The painting is awarded to the highest bidder i with max bi , who must pay her own bid, bi.

To derive a Bayesian Nash equilibrium, we assume the bidding strategy in equilibrium is i) symmetric, and ii) linear function of xi. That is, in equilibrium, player i chooses

β(xi) = c + θxi. (1)

Now suppose that player 2 follows the above equilibrium strategy, and we shall check whether player 1 has an incentive to choose the same linear strategy (1). Player 1’s optimization problem, given she received a valuation x1, is

maxb1 (x1− b1) Pr{b1 > β(x2)}. (2)

(4)

### First-Price Auction (2)

Since x2 is uniformly distributed on [0, 1] by assumption, we obtain Pr{b1 > β(x2)} = Pr{b1 > c+ θx2}

= Pr b1− c θ > x2



= b1− c θ .

The first equality comes from the linear bidding strategy (1), the third equality is from the uniform distribution. Substituting it into (2), the expected payoff becomes a quadratic function of b1.

maxb1 (x1− b1)

b1− c θ

Taking the first order condition, we obtain du1

db1

= 1

θ[−2b1+ x1+ c] = 0 ⇒ b1= c 2 +

x1

2 . (3)

Comparing (3) with (1), we can conclude that c = 0 and θ = 12 constitute a Bayesian Nash equilibrium.

4 / 15

(5)

### Second-Price Auction

Bidders simultaneously and independently submit bids b1 and b2. The painting is awarded to the highest bidder i with max bi , at a price equal to the second-highest bid, maxj6=ibj.

Unlike the first-price auction, there is a weakly dominant strategy for each player in this game.

Theorem 1

In a second-price auction, it is weakly dominant strategy to bid according to β(xi) = xi for all i.

Since the combination of weakly dominant strategies always becomes a Nash equilibrium, bi = xi for all i is a BNE.

Rm Note that there are other asymmetric equilibria.

For example, β1(x1) = 1 and β2(x2) = 0 for any x1 and x2

constitute a Bayesian Nash equilibrium.

(6)

### Expectation (1)

Definition 2

Given a random variable X taking on values in [0, ω], its

cumulative distribution function (CDF) F : [0, ω] → [0, 1] is: F(x) = Pr[X ≤ x]

the probability that X takes on a value not exceeding x.

F is non-decreasing F(0) = 0 and F (ω) = 1.

We assume that F is increasing and continuously differentiable.

6 / 15

(7)

### Expectation (2)

Definition 3

If X is distributed according to F , then its expectation is E[X] =

Z ω 0

xf(x)dx



= Z ω

0

xdF(x)



and if γ : [0, ω] → R is some arbitrary function, then the expectation of γ(X) is analogously defined as

E[γ(X)] = Z ω

0

γ(x)f (x)dx



= Z ω

0

γ(x)dF (x)

 .

(8)

### Expectation (3)

Definition 4

The conditional expectation of X given that X < x is E[X | X < x] = 1

F(x) Z x

0

tf(t)dt,

which can be rewritten as follows (by integrating by parts): F(x)E[X | X < x] =

Z x 0

tf(t)dt

= xF (x) − Z x

0

F(t)dt. The conditional expectation of γ(X) is defined as

E[γ(X) | X < x] = 1 F(x)

Z x 0

γ(t)f (t)dt.

8 / 15

(9)

### Order Statistics

Let X1, X2, . . . , Xnbe n independent draws from a distribution F with associated probability density function (PDF) f (= F).

Let Y1, Y2, . . . , Yn be a rearrangement of these so that Y1≥ Y2 ≥ · · · ≥ Yn.

Yk is called kth(-highest) order statistic.

Let Fk denote the distribution of Yk (with its pdf fk). The distribution of the highest order statistic is

F1(y) = F (y)n

f1(y) = nF (y)n−1f(y).

The distribution of the second-highest order statistic is F2(y) = F (y)n+ nF (y)n−1(1 − F (y))

= nF (y)n−1− (n − 1)F (y)n. f2(y) = n(n − 1)(1 − F (y))F (y)n−2f(y).

(10)

### Expected Revenue: First-Price

In a first-price auction, the payment is max{12X1,12X2} . Recall that β(xi) = 12xi is a BNE.

max{12X1,12X2} = 12max{X1, X2} = 12Y1. The expectation of Y1 becomes

E[Y1] = Z 1

0

yf1(y)dy

= Z 1

0

2y2dy= 2 3y

3

1

0

= 2 3.

The expected revenue of the first-price auction is 1 3 (=

1 2×

2 3).

10 / 15

(11)

### Expected Revenue: Second-Price

In a second-price auction, the payment is min{X1, X2} .

Recall that β(xi) = xi, i.e., trugh-telling is a BNE. min{X1, X2} = Y2.

The expectation of Y2 becomes E[Y2] =

Z 1 0

yf2(y)dy

= Z 1

0

y× 2(1 − y)dy = Z 1

0

2(y − y2)dy

= 2  1 2y

2

1

0

 1 3y

3

1

0

!

= 1 3.

The expected revenue of the second-price auction is 1

3, which is identical to the expected revenue of the first-price auction!.

(12)

### Revenue Equivalence Theorem

The two sealed-bid auctions, first-price and second-price auctions, have different equilibrium bidding strategies but yield the same expected revenue.

Interestingly, this is not by chance; the revenue equivalence result, often called as “revenue equivalence theorem (RET)”, is known to hold in much more general situations.

Theorem 5

RET holds whenever the following conditions are satisfied: Private Value Each bidder knows her value of the object. Independent Bidders receives their values independently. Symmetric The distribution is identical among bidders. Risk Neutral Each bidder is risk neutral.

12 / 15

(13)

### First-Price: General Model (1)

Consider a first-price auction with n bidders in which all the conditions in the previous theorem are satisfied.

Assume that bidders play a symmetric equilibrium, β(x). Given some bidding strategy b, a bidder’s expected payoff becomes

(x − b) Pr{b > Y1n−1} = (x − b) × G(β−1(b))

where Y1n−1 is the highest order statistic among n − 1 random draws of the values and G is the associated distribution. Maximizing w.r.t. b yields the first order condition:

g(β−1(b))

β−1(b))(x − b) − G(β−1(b)) = 0 (4) where g = G is the density of Y1n−1.

(14)

### First-Price: General Model (2)

Since (4) holds in equilibrium, i.e., b = β(x), g(x)

β(x)(x − b) − G(x) = 0 ⇐⇒ G(x)β(x) + g(x)β(x) = xg(x), which yields the differential equation

d

dx(G(x)β(x)) = xg(x).

Taking integral between 0 and x, we obtain

Z x 0

d

dy(G(y)β(y))dy =



G(x)β(x) − G(0)β(0) = Z x

0

yg(y)dy

⇒ β(x) = 1 G(x)

Z x 0

yg(y)dy = E[Y1n−1| Y1n−1 < x].

Rm The equilibrium strategy is to bid the amount equal to the conditional expectation of second-highest value given that my value x is the highest.

14 / 15

(15)

### First-Price: General Model (3)

The expected payment (to the seller) of each bidder given x is G(x) × E[Y1n−1| Y1n−1 < x],

which is identical to that of the second-price auction.

Rm The expected revenue is just the aggregation of the expected payment of all bidders, it can be derived by

n× Z ω

0

G(x) × E[Y1n−1| Y1n−1 < x]f (x)dx

= n Z ω

0



G(x) × 1 G(x)

Z x 0

yg(y)dy



f(x)dx

= n Z ω

0

Z x 0

yg(y)dy



f(x)dx = n Z ω

0

Z ω y

f(x)dx



yg(y)dy

= n Z ω

0

y(1 − F (y))g(y)dy = Z ω

0

yf2(y)dy

⇒ E[Y2n] since f2(y) = n(1 − F (y))f1n−1(y).

Updating...