Auction Design without Commitment

A Appendix

Proof of Lemma 4

First assume that φ = g ◦ h is deterministic, i.e., φ(θ) = g(h(θ)) is singleton
for all θ. We show that g(h(θ)) = φ^E [p](θ), for all θ ∈ Θ. Denote, for notational
simplicity, Yi = {θ ∈ Θ : w(θ) = i} for all i.

Since g ◦ h is not ex post dominated by φ^E [p(s, h)] for any s ∈ h(supp(p)),
g(h(θ)) has to allocate the good to the same buyer as φ^E [p] (θ) does, for all θ.
Thus the partition {Y_i} specifies the winner under g ◦ h. Since, by EXP-IR, a non-
winner cannot be imposed a strictly positive monetary transfer, the allocation of
g(h(θ)) may differ from φ^E [p] (θ) only in the winner’s monetary transfer. Denote
the winner’s monetary transfer under g(h(θ)) by mi(θ). Our task reduces to
showing that mi(θ) = m^E(i, θ-i,p), for all θ ∈ Yi, for all i.

Fix i. Since Θ_i is discrete and bounded below, we can order its elements by
θ_i⁰ <...<θ_i^k < .... We prove by induction that m_i (θ_i^k,θ_-i)=m^E(i, θ_-i, p), for
all θ_-i such that (θ_i^k , θ_-i) ∈ Y_i , for allk =0, 1,  Assume that the induction
hypothesis holds until step k - 1, i.e.,

mi(θ^l_i, θ-i) = m^E(i, θ-i, p), for all (θ^l_i, θ-i) ∈ Yi ∩ supp(p), for all l =0, ..., k - 1.

(9)

We show that (9) holds also for step k.

Take any s ∈ h(supp(p)). Since φ does not leave surplus to the winner that
could be extracted by φ^E (p((x, s), φ)),

mi(θ_i^k, θ-i) ≥ m^E(i, θ-i,p(s, h)), for all (θ_i^k, θ-i) ∈ supp(p(s, h)).

Since supp(p(s, h)) ⊆supp(p),

m^E (i, θ_-i, p(s, h)) ≥ m^E (p, θ_-i), for all (θ_i^k, θ_-i) ∈ supp(p(s, h)).     (10)

Noting that (10) holds for all s ∈ h(supp(p)), it follows from the above two con-
ditions that

mi(θ_i^k, θ-i) ≥ m^E(i, θ-i, p), for all (θ_i^k, θ-i) ∈ supp(p).            (11)

It remains to be shown that the weak inequality in (11) holds as equality.

By (6),

m^E(i, θ-i, p) = θ_i^k for all (θ_i^k, θ-i) ∈ Yi ∩ supp(p) such that (θ_i^k-1 , θ-i) 6∈ Yi. (12)

This has two implications. First,

^P   [θ^k-m^E(i,θ-i,p)]p(θi^k,θ-i)=     ^P    [θ^k-m^E(i,θ-i,p)]p(θi^k,θ-i).

(θi^k,θ-i,)∈Yi                                                       (θ_i^k-1,θ-i)∈Yi

(13)

18

<<   19   20   21   22   23   24   25   >>

More intriguing information