Transcript Iterative Combinatorial Auctions

Issue on the Border of Economics
and Computation
Iterative Combinatorial Auctions
1
Outline
• Why is VCG rarely used?
• The communication complexity of combinatorial
auctions.
– Exponential lower bound.
• Ascending-price auctions
– Walrasian equilibrium.
– Substitutes valuations.
– Unit-demand valuations.
Multiple items
• Goal: design auctions that allow for multiple
kinds of items
– Items are non identical.
– Also known as “Combinatorial Auctions”
• Examples:
– Spectrum licenses.
– Financial assets.
– Transportation of
packages.
– Advertising campaigns
– Industrial equipment.
–
–
–
–
Airport landing slots.
Bus routes.
Internet ads.
Privatization
Combinatorial preferences
• Why shouldn’t we auction each item separately?
• Auctioning each item alone ignores:
– complements:
v(TV) + v(VCR) < v(TV+VCR)
– Substitutes:
v(TV Toshiba) + v(TV Sony) > v(both TVs)
• Bidding for packages (or bundles) may increase the
efficiency of the auction.
Combinatorial Auctions
•
•
•
•
Set M of m indivisible items
Set N of n bidders
Preferences are on subsets S – bundles – of items
Valuation function vi: 2M  R
– vi(S) – bidder i’s value for bundle S
– monotone: vi(S) not decreasing in S
– normalized: vi() = 0
Allocation: mutually-disjoint subsets S1, S2, … Sn
Social welfare of allocation: i vi(Si)
VCG in practice
• VCG seems like the ultimate solution: implements
the efficient outcome in dominant strategies.
– And bidders simply need to tell the truth!
• It turns out that VCG is rarely used in practice
– Except maybe for 2nd-price auctions.
• Reasons:
1. Computation Complexity
2. Some economic and behavioral problems.
3. Communication Complexity
Computational complexity
• As you saw last week:
– Computing the efficient allocation is NP-hard.
– Even hard to approximate (better than m1/2 approximation)
– Even for very simple inputs (single-minded bidders)
– (We would like mechanisms to be polynomial in n,m.)
• This is a very important issue in large-scale real-life
auctions.
– Usually solved quite efficiently by linear-programming
solvers.
– The computational issue is not considered the biggest
obstacle in combinatorial auctions.
Economic and behavior problems
• VCG has some very severe drawbacks:
– Revenue non-monotonicity (adding bidders can decrease
revenue).
– Vulnerable to collusion.
– Vulnerable to false-name bids.
– Is not budget balanced (sometimes the mechanism should
be subsidized).
• Payment structure is non-intuitive
– Auction rules need to be simple
Communication Complexity
• What if the auctioneer had unlimited communication
power?
– Still needs to elicit the preferences of the bidders.
• In the general combinatorial auction problem: bidders
have private values of exponential size.
– Truthful auctions are not practical even with few dozens of
items.
• Possible solution: design some iterative auctions
where bidders transmit only the relevant data.
• Methodological tool: Communication Complexity.
Communication Complexity
• We will now discuss the communication complexity in
combinatorial auctions.
Communication Complexity Model
Private input:
x (k1 bits)
0011010
Private input:
y (k2 bits)
11000
01
Alice
01001100
Bob
• Goal: compute a function f(x,y)
• How many bits of communication are needed to
compute f(x,y) in the worst case?
– For a some mechanism (“protocol”) P that computes f,
Cf(P) is the its worst-case communication cost.
– Communication complexity: min P Cf(P)
Iterative Communication
• It is well known that iterative protocols can reduce
communication exponentially:
y
• Example:
x (log(n) bits)
(n bits)
1
0
10010
0
Alice
f = y[x]
Bob
…
• It is easy to see that:
• Computing f in a simultaneous protocol
requires O(n) bits.
• A 2-round protocol takes logn+1 bits.
1
0
Communication in CA
• So maybe we can carefully design auctions that will
ask bidders for the “relevant” information and
compute an efficient allocation with polynomial
communication?
• Answer: no!
Every protocol that computes the optimal allocation
requires exponential communication for some inputs.
– We will show this even for:
• binary valuations (v(S) is either 0 or 1 for every S)
• 2 bidders.
Communication in CA
• Theorem: every protocol that finds the efficient
allocation for every pair of binary valuations,
must use at least  m  bits of communication in the
 m / 2
worst case.
–
 m 


m
/
2


is exponential in m (by Stirling’s formula).
• The proof is via a standard approach in
communication complexity:
construction of a “fooling set”
– A collection of pairs of valuations where the protocol must
behave differently for each one.
Comm. Complexity Lower Bound: proof
Proof:
• given a binary valuation v, we define the dual
valuation v* to be
v*(S) = 1 - v(SC)
– SC=M\S
• Properties of v*
– Monotone.
– For every S,
v(S) + v*(SC)=1
• The set {v,v*}v is our fooling set, we will show that the
protocol behaves differently for every such pair.
Comm. Complexity Lower Bound: proof
Proof (cont.): We will prove the following lemma
Lemma: In an efficient mechanism, for all binary valuations v≠u
The bits transmitted
on inputs (v,v*)
The bits transmitted
on inputs (u,u*)
• Concluding the theorem from the lemma:
– In efficient mechanisms: # of distinct communication
sequences is at least the number of pairs (v,v*)
 m 


 m/2
– There are at least 2
binary valuations:
• For example, only count the valuations for which:
v(S)=0
v(S)=1
|S|<m/2,
|S|>m/2
 m 


 m / 2
• There are
sets of size m/2.
Each valuation assigns a bit for each such set.
Comm. Complexity Lower Bound: proof
Proof of lemma: (“cut-and-paste argument”)
Assume (v,v*) and (u,u*) have the same comm. sequence in the
efficient mechanism.
– Consider the pair (v,u*):
– Alice behaves exactly as in (v,v*), Bob as in (u,u*).
– The same holds for (v*,u).
 The same allocation for (v,v*),(u,u*) , (v,u*), (v*,u).
u≠v  there is T such that v(T) ≠u(T).
W.l.o.g. v(T)=1 and u(T)=0.  v(T)+u*(TC)=2.
Let S,SC be the efficient allocation for v, u*:
v(S)+u*(SC)≥2.
But we know that v(S)+v*(SC)+ u(S)+u*(SC) = 1 + 1 = 2
 u(S)+v*(SC)≤0  (S,SC) is not optimal for (u,v*)
Contradiction.
No hope?
• This lower bound can be strengthened:
exponential communication is needed even for
achieving better than m1/2 approximation to the
social welfare. 
• So how should we design large scale combinatorial
auctions?
• Key insights:
– Auctions will usually be iterative.
– Auctions will be tailored to specific classes of valuations.
Outline
• Why is VCG rarely used?
• The communication complexity of combinatorial
auctions.
– Exponential lower bound.
• Ascending-price auctions
– Walrasian equilibrium.
– Substitutes valuations.
– Unit-demand valuations.
Demand
• Bidders observe prices and determine their demand
• Per-item prices are announced
• Bidder decide what is the bundle that maximizes their
surplus under these prices
• (we all compute our demand. For example, when going to
the supermarket.)
• Formally:
For a bidder i, and prices p1,…,pn we say that the
bundle T is a demand of i if for every other bundle S:
vi (T )   p j  vi ( S )   p j
jT
jS
Walrasian Equilibrium
• We would like to reach an outcome where the market clears.
– Bidder receives their demand
– No excess demand or excess supply for goods.
• A Walrasian equilibrium is an allocation S1,…,Sn and
item prices p1,…,pn such that:
– Si is the demand of bidder i under the prices p1,…,pm
– For any item j that is not allocated (not in S1,…,Sn) we have
pj=0
Walrasian Equilibrium and welfare
• Intuitively: In a steady state, there is no excess
demand or excess supply and prices are thus stable.
 Market are in competitive/Walrasian equilibrium.
– How efficient are these equilibria?
• The two fundamental welfare theorems say:
(1) these equilibria are efficient,
(2) (roughly) they are always feasible.
– Adam Smith’s invisible hand, etc…
• Our model is for divisible goods, different than the
classic models.
– Welfare theorems holds nevertheless.
Efficiency of market-clearing prices
• The first welfare theorem:
The allocation in a Walrasian equilibrium is efficient.
•
proof: consider another allocation, T1,…,Tn
vi ( Si )   p j  vi (Ti )   p j
• For every bidder:
jS i
jTi
• Summing over all bidders:
n
n
n
n
 v (S )    p   v (T )    p
i 1
i
i
n
j
i 1 jS i
m
i
i 1
n
i
i 1 jTi
n
 v (S )   p   v (T )    p
i 1
i
i
n
i 1
i
i 1
i
i 1 jTi
j
The price of
unallocated items
is 0
n
 v (S )   v (T )
i 1
i
j
i
i
i 1
i
i
S1,…,Sn is efficient…
Outline
• Why is VCG rarely used?
• The communication complexity of combinatorial
auctions.
– Exponential lower bound.
• Ascending-price auctions
–
–
–
–
Walrasian equilibrium.
Simultaneous ascending auctions.
Substitutes valuations.
Unit-demand valuations.
Leading Application: Spectrum Auctions
• Adopted by the FCC in 1994.
– Revolutionized the sale of spectrum.
– Licenses are sold for specific frequencies
in specific geographic areas.
• Has been used since all over the
world.
– Also in UK, Germany, Netherlands,
Canada, The Pacific, India, etc…
• The basis of auctions for complex
resource allocation problems.
– Trigger for research
25
Objective
• Seller’s goal: maximize efficiency
– By law for FCC spectrum auctions.
Ascending-price auctions
• Initial prices are announces.
• Prices can only go up.
Revenue considerations:
• It is widely believed that ascending auctions gain more
revenue than other methods
• Rule of thumb, but supported by empirical data and
some theory.
Why ascending-price auctions?
• Simple and intuitive for bidders
– Terminates (relatively) quickly
• “Price discovery” – directs the attention of the bidders to
the relevant items.
– No need to determine the value of the other items/bundles.
– For example:
if they see an aggressive competition on one item, which
become expensive, they may let it go.
– Easier to assemble “packages” of items.
• Decreases communication volume.
– Again, bidders bid only on items that turn out to be relevant.
Simultaneous Ascending Auction
• The prevalent auction for spectrum auctions.
– And other multi-item auctions (Google’s TV,
transportation, etc.)
• Suggested to the FCC for the spectrum auctions in
1994
– By Milgrom, McAfee, and Wilson
• Main ideas:
–
–
–
–
–
Simultaneous
Ascending
Item prices
Stopping rule
Activity rule
29
Simultaneous Ascending Auction
Intuitively, the simultaneous ascending
auction works as follows: (“tâtonnement ”)
1. Start with zero prices.
2. Each bidder reports her favorite bundle (“demand”)
 Provisional winners are announced.
3. Price of over-demanded items is raised by ε.
4. Stop when there are no over-demanded items.
– i.e., Walrasian equilibrium is reached.
30
Simultaneous Ascending Auction
For formally proving the properties of the
auction, we will need to define it more
formally.
31
Simultaneous Ascending Auction
Before starting:
- pj=0 for every item j.
- Temporary bundle Si is empty.
Repeat the following process:
1. Let Di be a demand of bidder i under these prices:
•
•
pj for items in Si
pj+ε for all other items
2. If for all bidders Si=Di, stop the auction.
3. Otherwise, find a bidder i with Si ≠ Di and update:
•
•
•
For items j in Di but not in Si, set pj=pj+ ε
Si=Di
for every bidder k ≠i, Sk=Sk\Di (that is, remove the items in Di)
Collect
demand
Update
provisional
winners
and raise
prices
The final outcome: Allocation S1,….,Sn and prices p1,…., pn
32
Simultaneous Ascending Auction
• Theorem: when all bidders have substitutes
valuations, the simultaneous ascending auction
terminates at a Walrasian equilibrium.
– Therefore, at an efficient outcome.
– Up to an ε
Based on literature by Kelso and Crawford (1982), Demange, Gale and
Sotomayor (1986), Gul and Stacchetti (1999), Milgrom (2000)
33
Substitutes (or “gross substitutes”)
• The economic intuition: if a,b are substitutes and the
price of a increases, then the bidder still demands b.
• Formal definition:
Substitutes valuations satisfy the following condition:
Consider prices p1,…,pm and prices q1,…,qm where some
of the prices are increased.
For every demand Ai of bidder i under prices p1,…,pm,
bidder i demands a bundle Di under the prices q1,…,qn
that contains all the items in Ai that their prices were not
changed.
– (Think about the case where the demand is a unique bundle.
Quantifiers in the definition handle the case of multiple demand)
34
Substitutes: examples
$3 $8
$7
$1
$10
The following valuations satisfy the substitutes condition:
• Additive: there is a value attached to each item, and the
value of a bundle is the sum of the values of the item in it.
V(
) = 3 + 1 + 10 = 14
• Unit demand: bidder have value per each item, but want at
most one item
– The value of a bundle = maximal value of an item in it.
– V(
) = max{ 3, 1, 10 } = 10
• Identical goods with downward sloping values.
35
Substitutes: examples
$3 $8
$7
$1
$10
Substitute valuations rule out any form of
complementarities:
For example, if I am willing to pay 10 for the bundle
{a,b},
then I will demand both items at prices {3,3},
I will demand nothing if the price of a is raised to 8.
36
Simultaneous Ascending Auction
• Theorem: when all bidders have substitutes
valuations, the simultaneous ascending auction
terminates at a Walrasian equilibrium.
– Therefore, at an efficient outcome.
– Up to an ε
Based on literature by Kelso and Crawford (1982), Demange, Gale and
Sotomayor (1986), Gul and Stacchetti (1999), Milgrom (2000)
37
Proof
The theorem follows from the following lemma:
• Lemma: At every stage of the auction, and for every bidder i,
Si  Di
(*)
• Proof: By induction. (Clearly holds at the beginning.)
– Assume (*) holds, and we will show it still holds after the update.
– Consider bidder i that is selected at stage 2:
• After the updating, we have Si=Di.
• Consider bidder k ≠ i:
– Two changes can occur:
• If items were taken from Sk by i, Sk became smaller and (*)
still holds. (needs the substitutes property)
• If prices of items not in Sk were increased, due to the
substitutes property the only items that can be removed now
are items whose prices were increased. (But those were
38
taken to i.)
Simultaneous Ascending Auction
• Theorem: when all bidders have substitutes
valuations, the simultaneous ascending auction
terminates at a Walrasian equilibrium.
– Therefore, at an efficient outcome.
– Up to an ε
We will conclude the theorem from the lemma:
• Every item with non-zero price was allocated to one of the bidders.
• From this point on, it was demanded by at least one of the bidders.
• At the end, all demanded items are allocated – Walrasian equilibrium.
39
Walrasian equilibrium
• We actually proved: with substitutes valuations,
Walrasian equilibrium always exists.
– Constructive proof: it is reached by the ascending-price
auctions.
– The ascending auction can be viewed as a primal-dual
algorithm.
– The auction terminates in at most
m
vmax

steps.
• However, Walrasian equilibria do not always exist.
40
Walrasian eq. does not always exist
• Consider the following valuations:
a
b
{a,b}
Alice
2
2
2
Bob
0
0
3
Claim: there is no Walrasian equilibrium for these
preferences.
Why?
• What is the efficient allocation?
– Bob gets both items.
 Alice should demand nothing in any Walrasian equilibrium.
 Price of both items should be at least 2
 But then Bob will not demand {a,b}.
41
Outline
• Why is VCG rarely used?
• The communication complexity of combinatorial
auctions.
– Exponential lower bound.
• Ascending-price auctions
– Walrasian equilibrium.
– Substitutes valuations.
– Unit-demand valuations.
Incentives
• In the analysis we assumed that bidders bid
“straightforward” bidding:
bid their actual demand at each stage.
• Will they? Is the SSA truthful?
– For substitutes preferences.
• Answer: no.
Reason: Bidders can benefit from “demand reduction”.
• Nevertheless: variants of this auction are used
successfully in many environments.
43
Profitable Demand reduction
• Consider the following substitutes preferences:
a
b
{a,b}
Alice
4
4
4
Bob
5
5
10
• SSA auction terminates with a Walrasian
equilibrium: pa=4, pb=4 and Bob wins {a,b}.
– Bob’s payoff: 2
• If Bob strategically reduces his demand to a only:
auction stops at pa=pb=0. Bob wins a, Alice wins b.
– Bob’s payoff: 5 !
44
Unit-demand preferences
• However, the simultaneous ascending auction is
incentive compatible for a sub-family of substitutes
preferences: unit-demand valuations.
– Each bidder wants at most one item (but items are still nonidentical)
• Non identical items: a, b, c, d, e,
• Each bidder has a value for each item
vi(a),vi(b),bi(c),..
vi ( S )  max jS vi ( j )
45
VCG and Walrasian equilibrium
• Theorem: for unit-demand valuations
1. The VCG outcome is a Walrasian equilibrium
2. The SSA terminates at VCG prices
• Actually it is known that the VCG price vector is the
lowest Walrasian equilibrium for such preferences.
– That is, least preferable to the seller.
• Conclusion:
Truthful behavior is an equilibrium in the auction.
(Any deviation leads to a non-optimal outcome)
Summary
• Variants of the simultaneous ascending auction
have been widely in use in the past 20 years.
– Mainly in spectrum auctions, also in advertising allocation
• When the bidders have substitute preferences:
ends up with market clearing prices ( efficient
allocation)
– In the more restricted case of unit demand: also end up
with VCG payments.
• More complex solutions are needed in the presence
of complementarities.
47