How T relates to F
• Theorem: T/(2log h) F
• First, see that F uses the price opt(B):
opt( B) arg maxbi B bi (n i 1)
How T relates to F (2)
• Proof:
16
X
4 2
• 1. Divide the bids into log h bins. • 2. the sum of the bids = T => there exists a bin, say X, that sums to at least T/(log h). • 3. the lowest bid in X is at least 1/2 the highest. • 4. choose price(B) to be the lowest bid in that bin. • 5. Each bid in that bin will contribute at least half its value. 1 1 1 T • 6. b b
p j V j V j 1
• Rearrange the sum over V j and define p0 0 :
E[ R ] ( p j p j 1 )V j
i 1 n
An upper bound - proof(7)
E[ R ] ( p j p j 1 )V j
– downloadable software – pay-per-view movies
Motivation
• Mechanism Design purpose:
– to maximize seller‟s revenues!
• Using:
– – – – – Fixed price auctions Multiple price auctions Deterministic auctions Randomized auctions All single round, sealed bids
Ri pi bi
i 1
p j (b j 1 b j )
j 1
An upper bound - proof(5)
E[ R]
n
i 1
Ri
j 1
n 1 i 1 n 1
pi bi p j (b j 1 b j )
i 1 i 1 j 1
An upper bound - proof
• Let‟s define: – pi the probability a bid I is satisfy – ci expected cost to winning bidder I – gi expected profit (gain) for bidder I • (1) gi pi (ui ci )
i 1
p j (b j 1 b j )
j 1
• define the total expected revenue from bidder I as:
Ri pi ci • rewrite (1) gi pi (ui ci ) as: Ri pibi gi
• using equation (3) we get:
( F / log h )
An upper bound
• We can see that no truthful auction, even a multi price one, can do better then F in the average case: • Theorem: for any truthful auction: E[ R] F
E[ R] pn F F
Deterministic Optimal Threshold Auction
• A bid-independent auction, meaning bidder i„s bid value should only determine whether bidder i wins or losses. The bid value should not determine bidder i‟s price. • Uses optimal threshold function opt (Bi) ,to be used as a threshold for bidder i, which on set of bids B\bi returns the fixed price at which items should be sold to achieve revenue F. • This action has a worst case input that causes it not to be competitive.
n
n i 1
pi bi
i 1
p j (b j 1 b j )(n j )
n 1 j 1
pnbn pnbn
j 1 n 1 j 1
p j b j p j (b j 1 b j )(n j ) p j b j (b j 1 b j )(n j )
bi f ( B' )
Performance analysis
• Theorem: assume ah F , then R F / 6 with a probability 1 e a / 36 40e a / 72 • Proof is basing in the Chernoff bound. • By this Theorem: R 1 F
• • • • • • • Set of Bids, B= b1...bn, sorted: bi bi 1, so b1 bl & bn bh ui = utility of bidder I n T = i 1ui F = Optimal fixed price revenues R = current game revenues assumption: h is small compare to F
bi b j pi p j
bi b j
pi p j
An upper bound - proof(3)
• Theorem: for any truthful auction:
E ( R) F
• Proof:
• if bidder I-1 had the utility value of bi his gain will not exceed: (2) gi pi 1(bi ci 1) • so: gi pi 1(bi bi 1 bi 1 ci 1)
The economic view
Price
60 50 40 30 20 10 0 Demand
Quantity
The economic view
Price
60 50 40 30 20 10 0 Demand
Revenues = Price X Quantity Quantity
Notations
For example:
• The k-item vickery auction:
– truthful, single price
• Worst case scenario:
– k bidders bid at h, n-k bidders bid at 1.
• Vickery revd price revenues (F) k h • R 1 F h
Notations 2
• Truthful auction: encourage bidders to bid their utility value • Competitive auction: yields revenues within a constant factor of optimal fixed price. • We use computer science analysis similar to online algorithms analysis where we check if R 1 F
• define V j b j (n j 1), this is also the revenues from a fixed price auction using b j as the price. • Note that V j F .
E[ R ] pnVn
n 1 i 1
Competitive Auctions and Digital Goods
Andrew Goldberg, Jason Hartline, and Andrew Wright presenting: Keren Horowitz, Ziv Yirmeyahu
Introduction
• • • • Selling a large number of items every customer wants a single item unlimited supply examples:
i 1 n
• but V j F and by the lemma in the beginning we showed that p j p j 1 0 so:
E[ R ] F ( p j p j 1 )
i 1 n
• this sum telescopes to pn p0 but p0 0 so:
An upper bound - proof(2)
• Lemma: in a truthful auction: