Transcript No Slide Title - School of Computer Science

Multi-unit auctions &
exchanges
(multiple indistinguishable units
of one item for sale)
Tuomas Sandholm
Computer Science Department
Carnegie Mellon University
Auctions with multiple
indistinguishable units for sale
• Examples
–
–
–
–
–
IBM stocks
Barrels of oil
Pork bellies
Trans-Atlantic backbone bandwidth from NYC to Paris
…
Multi-unit auctions: pricing rules
•
•
•
Auctioning multiple indistinguishable units of an item
Naive generalization of the Vickrey auction: uniform price auction
– If there are k units for sale, the highest k bids win, and each bid pays the
k+1st highest price
– Demand reduction lie [Crampton&Ausubel 96]:
• k=5
• Agent 1 values getting her first unit at $9, and getting a second unit
is worth $7 to her
• Others have placed bids $2, $6, $8, $10, and $14
• If agent 1 submits one bid at $9 and one at $7, she gets both items,
and pays 2 x $6 = $12. Her utility is $9 + $7 - $12 = $4
• If agent 1 only submits one bid for $9, she will get one item, and pay
$2. Her utility is $9-$2=$7
Incentive compatible mechanism that is Pareto efficient and ex post
individually rational
– Clarke tax. Agent i pays a-b
• b is the others’ sum of winning bids
• a is the others’ sum of winning bids had i not participated
– What about revenue (if market is competitive)?
Multi-unit auctions: Clearing
complexity
[Sandholm & Suri IJCAI-01]
In all of the curves together
Multi-unit reverse auctions with
supply curves
• Same complexity results apply as in auctions
– O(#pieces log #pieces) in nondiscriminatory case
with piecewise linear supply curves
– NP-complete in discriminatory case with
piecewise linear supply curves
– O(#agents log #agents) in discriminatory case with
linear supply curves
Multi-unit exchanges
• Multiple buyers, multiple sellers, multiple
units for sale
• By Myerson-Satterthwaite thrm, even in 1unit case cannot obtain all of
• Pareto efficiency
• Budget balance
• Individual rationality (participation)
Screenshot from
eMediator
[Sandholm AGENTS-00]
Supply/demand curve bids
Quantity
Aggregate supply
Aggregate demand
profit
psell
pbuy
Unit price
profit = amounts paid by bidders – amounts paid to sellers
Can be divided between buyers, sellers & market maker
One price for everyone (“classic partial equilibrium”):
profit = 0
One price for sellers, one for buyers ( nondiscriminatory pricing ):
profit > 0
Nondiscriminatory vs.
discriminatory pricing
Aggregate demand
Quantity
Supply of agent 1
Supply of agent 2
psell pbuy
Unit price
p2sell
pbuy
p1sell
One price for sellers, one for buyers
( nondiscriminatory pricing ):
profit > 0
One price for each agent
( discriminatory pricing ):
greater profit
Shape of supply/demand curves
• Piecewise linear curve can approximate any curve
• Assume
– Each buyer’s demand curve is downward sloping
– Each seller’s supply curve is upward sloping
– Otherwise absurd result can occur
• Aggregate curves might not be monotonic
• Even individuals’ curves might not be continuous
Pricing scheme has implications
on time complexity of clearing
• Piecewise linear curves (not necessarily continuous) can approximate any curve
• Clearing objective: maximize profit
• Thrm. Nondiscriminatory clearing with piecewise linear supply/demand: O(p log p)
– p = total number of pieces in the curves
• Thrm. Discriminatory clearing with piecewise linear supply/demand: NP-complete
• Thrm. Discriminatory clearing with linear supply/demand: O(a log a)
– a = number of agents
• These results apply to auctions, reverse auctions, and exchanges
• So, there is an inherent tradeoff between profit and computational complexity