Transcript PowerPoint 演示文稿

Market Design and Analysis
Lecture 5
Lecturer: Ning Chen (陈宁)
Email: [email protected]
Worst Case Optimal Auction Design

Consider an auction setting where there are



one item (unlimited supplies)
n buyers who desire one copy each at value vi
Goal: Design a truthful auction that maximizes the
profit.

What if VCG?
2
Characterization of Truthfulness

An auction is called bid-independent if for each
buyer i, the auction computes ti  f(b-i)




if ti < bi, i wins at price pi = ti
if ti > bi, i does not win
if ti = bi, i either wins or not (doesnot matter)
Theorem. An auction is truthful if and only if it is
equivalent to a bid-independent auction.
3
Characterization of Truthfulness

Proof. Any bid-independent auction is truthful (trivial).
On the other direction, consider any truthful auction A.


Let bi(x) = (b1,…,bi-1,x,bi+1,…,bn)
If there is a value x* s.t. in A(bi(x*)), buyer i wins and
pays p (≤ x*), then define f(b-i) = p
4
Characterization of Truthfulness

Consider any value x and bi(x)

if buyer i wins, payment must be p.
(otherwise, there is y s.t. the payment is q ≠ p in A(bi(y)).
Assume wlog q>p. then the auction is not truthful when
vi = y.)
 buyer i wins for any bid x > p.
(otherwise, there is y > p s.t. i does not win when bidding
y. Again the auction is not truthful when vi = y.)

Hence, the auction is equivalent to bid-independent
auction f(∙) where f(b-i) = p.
5
A Bad News..

Consider a special case where there is only one
buyer.




By the above theorem, any truthful auction is bidindependent
The value ti offered to the buyer must be a constant
The real value of the buyer, however, can be arbitrarily
large…
In general, truthful auctions can work arbitrarily bad
in the worst case.
6
Analysis Approach


How we can arrive at a rigorous theoretical
framework to determine the optimality of some
auctions?
Answer: moving from absolute optimality to relative
optimality.
(E.g. in data compression, whenever there is an
information theoretic obstacle preventing us from
obtaining an absolute optimal solution, we try to
approximate.)
7
Analysis Approach


In our setting, the obstacle is the game theoretic
constraint that an auction does not know the true
values in advance and must solicit them in a truthinducing manner.
The approach to study relative optimality of auctions
is to find a suitable benchmark, and show that the
auction is always within a small factor of the
benchmark.
8
Benchmark

Benchmarks. Assume the values are
v1 ≥ v2 ≥ ∙∙∙ ≥ vn. The following are the natural
candidates:



T(v) = ∑i vi, i.e. the sum of values of all buyers
F(v) = maxi i∙vi, i.e. the optimal profit given by a single
price.
The example above, however, shows that both T(v)
and F(v) are not good benchmark, as they can be
arbitrarily larger than the profit of any truthful auction.
9
Benchmark

Definition (F(2)). The optimal single priced profit with
at least two winners is
F(2)(v) = maxi≥2 i∙vi

Definition (competitive ratio). The competitive ratio
of auction A is defined to be maxv F(2)(v) / A(v),
where A(v) is the (expected) profit of A on input v.

Goal: design a truthful auction A to minimize the
competitive ratio (worst-case analysis), i.e.
min maxv F(2)(v) / A(v)
10
Benchmark

Examples:


There are 50 bids $10 and 50 bids $1. Then
F(2) = 50 ∙ 10 = $500
There are 5 bids $10 and 95 bids $1. Then
F(2) = 1 ∙ 100 = $100
11
An Impossibility Result

Theorem. Roughly speaking, no deterministic
truthful auction is c-competitive for any given
constant c > 0.

Therefore, we have to look for randomized auctions.
12
Profit Extraction



Assume the goal of the seller is to raise a total profit R.
The auction profit extractor with target profit R,
ProfitExtract(R), sells to the largest set of k buyers
that can equally share R and change each R/k.
Example. Consider b = (5,4,3,2,1) and R = 9.



offer R/5 to all buyers, b5 = 1 drops out
offer R/4 to first four buyers, b4 = 2 drops out
offer R/3 to first three buyers, all accept at price R/3 = 3.
13
Profit Extraction




Lemma 1. For any given value R, ProfitExtract(R) is
truthful.
Proof. assignment.
Lemma.
 If R ≤ F(v), then ProfitExtract(R) always obtains a
profit of R.
 If R > F(v), then ProfitExtract(R) obtains nothing.
Proof. assignment.
F(v) = maxi i∙vi
14
Random Sampling Profit Extraction

The random sampling profit extraction auction
(RSPE) works as follows:




randomly partition the bids b = (b1,…,bn) into two
groups g1 and g2.
compute R1 = F(g1) and R2 = F(g2), the optimal profit
given by a single price for each group.
run ProfitExtrac(R1) on g2
run ProfitExtrac(R2) on g1
F(v) = maxi i∙vi
15
Random Sampling Profit Extraction

Theorem. Random sampling profit extraction is
truthful.

Proof. Consider any buyer i.



Assume wlog that i is in group g1.
Then we will run ProfitExtrac(R2) on g1, where R2, the
optimal profit given by a single price for group g2, is
independent to the bid of i.
By Lemma 1, we know that ProfitExtrac(R2) is truthful
for buyer i.
16
Random Sampling Profit Extraction

Theorem. Random sampling profit extraction is 4competitive.
17
Random Sampling Profit Extraction


Lemma 2. If we flip a coin uniformly k ≥ 2 times, then
E[min {# heads, # tails}] ≥ k/4
Proof. Let Mi = min{# heads, # tails} be a random
variable after i coin flips. Observe that

E[M1] = 0
 E[M2] = 1/2
 E[M3] = 3/4
Let Xi = Mi – Mi-1. Thus,

E[X1] = 0
 E[X2] = 1/2
 E[X3] = 1/4
18
Random Sampling Profit Extraction


By linearity of expectation,
E[Mk] = ∑ki=1 E[Xi]
Thus, to compute E[Mk], it suffices to compute E[Xi].
Case 1. i is even. Hence i – 1 is odd. Thus, prior to
the i-th coin, # heads ≠ # tails. Assume wlog that
# heads < # tails. Now we flip the i-th coin:


with probability 1/2, it is head and we increase the
minimum by one;
with probability 1/2, it is tail and we do not increase the
minimum.
Thus, E[Xi] = 1/2.
19
Random Sampling Profit Extraction

Case 2. i is odd. We use the trivial lower bound
E[Xi] ≥ 0.

Therefore,
where recall that X1 = 0, X2 = 1/2, X3 = 1/4.
20
Random Sampling Profit Extraction

Theorem. Random sampling profit extraction is 4competitive.

Proof. Assume that F(2)(b) = kp, where k ≥ 2 is the
number of winners and p is the price. Of these k
winners,

let k1 be the number of them that are in g1
 R1 = F(g1) ≥ k1p

let k2 be the number of them that are in g2
 R2 = F(g2) ≥ k2p
F(v) = maxi i∙vi
F(2)(v) = maxi≥2 i∙vi
21
Random Sampling Profit Extraction

Hence,

That is, for any possible input vector, we always
have F(2)(v) / RSPE(v) ≤ 4, i.e.
maxv F(2)(v) / RSPE(v) ≤ 4
22
Random Sampling Profit Extraction

Theorem. Random sampling profit extraction is
truthful and 4-competitive.

Theorem. No randomized truthful auction can be
better than 2.42-competitive.

Theorem. There is a truthful auction for n buyers
with ratio 3.12.
23
Reading Assignment






R. Myerson, Optimal Auction Design, Mathematics of
Operations Research, V.6(1), 1981.
N. Nisan, A. Ronen, Algorithmic Mechanism Design, STOC
1999, 129-140.
A. Archer, E. Tardos, Truthful Mechanisms for One-Parameter
Agents, FOCS 2001, 482-491.
A. Karlin, D. Kempe, T. Tamir, Beyond VCG: Frugality of
Truthful Mechanisms, FOCS 2005, 615-626.
A. Goldberg, J. Hartline, A. Karlin, M. Saks, xxxx, Competitive
auctions, Games and Economic Behavior, 2009.
X. Bei, N. Chen, N. Gravin, P. Lu, Budget Feasible Mechanism
Design: From Prior-Free to Bayesian, STOC 2012.
24