Auctions &
Combinatorial Auctions
Adapted from notes by Vincent Conitzer
Auctions Assumption is –
• If you buy the item for exactly what it is
worth, there is no utility.
• Yale slides bring this home – especially if
your evaluation isn’t correct.
• If you sell the item for exactly what is it
worth, there is no utility.
• We are trying to do better than purchase for
its actual value – a good deal for both.
2
Auction Parameters
• Goods can have
– private value (Aunt Bessie’s Broach)
– public/common value (oil field to oil companies)
– correlated value (partially private, partially values of others):
consider the resale value
– Reservation Price
• Winner pays
– first price (highest bidder wins, pays highest price)
– second price (to person who bids highest, but pay value of second
price)
• Bids may be
– open cry
– sealed bid
• Bidding may be
– one shot
– ascending
– descending
3
English Auctions
•
•
•
•
Most commonly known type of auction:
– first price
– open cry
– ascending
– Real time
Dominant strategy is for agent to successively bid a small amount more
than the current highest bid until it reaches their valuation, then withdraw
Efficient (pareto sense) as person who values item most gets it
If you win in an English auction, you know that no one else valued it as
much as you. Are you happy you have won?
4
English Auctions
• Susceptible to:
– winner’s curse – get excited and bid too much
or not know true valuation
– shills (no intention of buying. Bid up the price.
Work for auctioneer on commission. Illegal in
most cases.)
– The earliest use of the word 'shill' actually dates back to
Elizabethan England when theatre owners would pay a
'shilling' to a theatre goer who would applaud and cheer
loudly at the end of a performance. Since applause is
contagious, this would help ensure the success of a
production.
5
Auction protocols:
Dutch (open-cry descending)
The hand of the clock starts always on
the top.
The hand of the clock runs counter
clockwise, from left to right.
The price drops from high to low.
The first person, out of the 300 buyers,
who pushes the button is the buyer of
the goods
6
• Protocol: Auctioneer continuously lowers the price until a bidder
takes the item at the current price
• Strategically equivalent to first-price sealed-bid protocol in all
auction settings
• Time efficient (real-time) – auction happens fast
• Strategy: Bid as a function of agent’s private value and his prior
estimates of others’ valuations.
• Bayesian – reasoning with uncertain statements.
– Specify from prior probability and update in light of new relevant data.
• Best strategy: No dominant strategy in general (without more info)
– Lying (down-biasing bids) & counter-speculation
– Possible to determine Nash equilibrium strategies via common
knowledge assumptions regarding the probability distributions
of others’ values
– Requires multiple rounds of posting current price
• Dutch flower market, Ontario tobacco auction, Filene’s basement,
Waldenbooks
7
• Multiple identical item auction – can all pay lowest price or
• The Yankee auction– only actually pay what you bid:
Example of Yankee auction:
• Bidder D bids 2 items at $7 each.
• Bidder C bids 3 items at $6 each.
• Bidder B bids 5 items at $5 each.
• Bidder A bids 5 items at $3 each.
10 items total yields:
• Bidder D wins 2 items at $7 each.
• Bidder C wins 3 items at $6 each.
• Bidder B wins 5 items at $5 each.
• Bidder A wins no items.
8
First-price sealed-bid
•
Protocol: Each bidder submits one bid without knowing others’ bids. The highest bidder wins
the item at the price of his bid
– Single round of bidding
– (once you bid, there are no counter offers)
•
•
Strategy: Bid as a function of agent’s private value and his prior estimates of others’ valuations
Best strategy: No dominant strategy in general
– Strategic underbidding & counter speculation
– Can determine Nash equilibrium (not do anything different, knowing what others
would do) strategies via common knowledge assumptions about the probability
distributions from which valuations are drawn
– Goal is to try to maximize the expected profit.
•
•
No relevant information is revealed – not even price or winner (if you aren’t the
winner)
Bidder uncertainty of valuation is a factor
• No dominant strategy – as may not be pareto
optimal using the “best strategy”.
• Efficient in real time as each person takes
minimal time (as bidding happens in parallel) –
but not too satisfying (no feedback). Lot’s of
communication – all must bid.
9
Second-price sealed-bid Vickrey Auction
• Vickrey auctions are:
– one shot
– second-price
– sealed-bid
• Good is awarded to the agent that made the highest bid; at the
price of the second highest bid
• Bidding your true valuation is dominant strategy in Vickrey
auctions. Why?
• Not prone to strategic manipulation.
• Vickrey auctions susceptible to antisocial behavior (bid really
high to guarantee win, someone else bids somewhat high to stick
you with it)
• Effort not wasted in counter-speculation as just bid true value.
• Widely advocated for computational multiagent systems
• Old method [Vickrey 1961], but not widely used among humans
10
• direct revelation: only option is for agent to
announce his private information
• A direct mechanism is said to be truthful if
the agent announces his true value
1-item auction mechanisms
• English auction:
– Each bid must be higher than previous bid
– Last bidder wins, pays last bid
• Japanese auction:
– Price rises, bidders drop out when price is too high (signal
when leave)
– Last bidder wins at price of last dropout
• Dutch auction:
– Price drops until someone takes the item at that price
• Sealed-bid auctions (direct revelation mechanisms):
– Each bidder submits a bid in an envelope
– Auctioneer opens the envelopes, highest bid wins
• First-price sealed-bid auction: winner pays own bid
• Second-price sealed bid (or Vickrey) auction: winner pays secondhighest bid
Complementarity and substitutability
• How valuable one item is to a bidder may
depend on whether the bidder can get
another item
• Items a and b are complementary if v({a, b}) >
v({a}) + v({b}) superadditive
e.g., Camera and tripod
• E.g.
• Items a and b are substitutes if v({a, b}) <
v({a}) + v({b}) subadditive
e.g., Milk or OJ
• E.g.
• Strict substitutes – their combined value is
the value of either one of the goods
Sequential auctions
• Suppose your valuation function is v( ) = $200, v(
) = $100, v(
) = $500
• Now suppose that there are two (say, Vickrey)
auctions, the first one for
and the second one for
• What should you bid in the first auction?
• If you bid $200, you may lose to a bidder who bids
$250, only to find out that you could have won the
monitor for $200
• If you bid anything higher, you may pay more than
$200, only to find out that the computer sells for $1000
• Sequential (and parallel) auctions are inefficient
• What do we mean by inefficient in this
context? runtime? outcome desirability?
exposure problem
• exposure problem: a bidder might bid
aggressively for a set of good in the hopes
of winning a bundle, but succeed in
winning only a subset (and therefore pay
too much)
• So named as bidder is exposed to risk.
• In superadditive case, how does the
“extra” get allocated in terms of bidding
strategies?
Combinatorial auctions
Simultaneously for sale:
,
,
bid 1
v(
) = $500
bid 2
v(
) = $700
bid 3
v(
) = $300
used in truckload transportation, industrial procurement, radio spectrum allocation, …
Vickrey-Clarke-Groves
Mechanism
The system charges a bidder for the harm they cause other bidders
For example, suppose that we want to auction two apples, and we have three bidders.
Bidder A wants one apple and bids $5 for that apple. Bidder B wants one apple and is
willing to pay $2 for it. Bidder C wants two apples and is willing to pay $6 to have both of
them, but is uninterested in buying only one without the other.
A and B should have the apples – as they value them the most.
But both A and B are thinking, the seller thinks the apples are worth more BECAUSE OF
ME. The price shouldn’t be higher for me because of me.
Currently, B has a payment of $2.
If bidder A had not been present, C would have won, and had a utility of $6, so A pays
$6 (price without me)-$2 (value to others if I win) = $4. (The real cost to the seller of A’s
getting the apple.)
For the payment of bidder B: currently A has a utility of $5 and C has a utility of 0. If
bidder B had been absent, C would have won and had a utility of $6, so B pays $6-$5 =
$1. C does not need to pay anything because he doesn’t get anything.
W. Vickrey. Counterspeculation, Auctions, and Competitive Sealed Tenders.
Journal of Finance, 16(1):8–37, 1961. E.H. Clarke. Multipart Pricing of Public Goods.
Public Choice, 11(1):17–33,
19
1971. T. Groves. Incentives in Teams. Econometrica, 41(4):617–631, 1973.
Vickrey-Clarke-Groves
Mechanism
The system charges a bidder for the harm they cause
other bidders
Two apples for sale. Bid are:
A: (1,$5) - one apple for five dollars
B: (1, $2) - one apple for two dollars
C: (2, $6) - two apples for six dollars
A: without me, revenue is $6, I should only have
to pay $4 (as what I cost the system)
20
Vickrey-Clarke-Groves
Mechanism
The system charges a bidder for the harm they cause
other bidders
Two apples for sale
A: (1,$5) - one apple for five dollars
B: (1, $2)
C: (2, $6)
D: (1,$5)
Who wins and what do they pay?
21
VCG Mechanism for
Combinatorial Auctions
I pay: The value of the best allocation possible without
me minus the value to everyone else of the best
allocation with me
Consider the following example:
Agent 1: ({a}, 0), ({b}, 0), ({a, b}, 9)
Agent 2: ({a}, 4), ({b}, 0), ({a, b}, 0)
Agent 3: ({a}, 0), ({b}, 2), ({a, b}, 0)
Agent 4: ({a}, 0), ({b}, 2), ({a, b}, 2)
Clearly agent 1 should win BUT he feels he shouldn’t be bidding
against himself. He would like to pay only what it is worth to others:
without agent 1 – worth 6
with agent 1 – nobody else gets any value so worth = 0
Agent 1 is happy to pay 6
22
Another
Example
The value of the best allocation possible without me minus
the value to everyone else of the best allocation with me
Consider the following example:
Agent 1: ({a}, 0), ({b}, 0), ({a, b}, 19)
Agent 2: ({a}, 3), ({b}, 0), ({c}, 3)
Agent 3: ({a}, 0), ({b}, 2), ({c}, 2)
Agent 4: ({a}, 0), ({b}, 2), ({a,b,c},13)
Clearly agent 1 should win BUT he feels he shouldn’t be bidding
against himself. He would like to pay only what it is worth to others:
without agent 1 bidding – worth 13
with agent 1 – Agent 2 still gets 3
Agent 1 is happy to pay 10
What should agent 2 pay for c?
23
Argue for or against:
• Changing my bid does not change what I
pay (though it may change whether or not I
win and it may change what others pay)
Consider the following example:
Agent 1: ({a}, 0), ({b}, 0), ({a, b}, 15)
Agent 2: ({a}, 8), ({b}, 8), ({c}, 3)
Agent 3: ({a}, 0), ({b}, 12), ({c}, 2)
Consider the changed example:
Agent 1: ({a}, 0), ({b}, 0), ({a, b}, 15)
Agent 2: ({a}, 8), ({b}, 13), ({c}, 3)
Agent 3: ({a}, 0), ({b}, 12), ({c}, 2)
Agent 2 pays: 5 (for a and c)
Agent 3 pays: 8 for b (19-11)
24
Strategy-Proofness
• In the VCG mechanism, reporting their true
valuation is a dominant strategy for each
bidder – similar to the reasons that
truthfulness is dominant with Vickrey
25
So, does it work well?
• Consider the following example:
•
Agent 1: ({a}, 0), ({b}, 0), ({a, b}, 4)
•
Agent 2: ({a}, 1), ({b}, 0), ({a, b}, 0)
•
Agent 3: ({a}, 0), ({b}, 2), ({a, b}, 0)
•
Agent 4: ({a}, 0), ({b}, 2), ({a, b}, 2)
•
• Best allocation is agent 1 ({a, b}, 4)
• Agent 1 pays: 3 – 0 = 3 So it works just like we thought it
would
• Lots of the problems come from very few bidders – which
would always be a problem for Vickrey auctions.
26
Another Example
• Consider the following example:
•
•
•
•
Agent 1: ({a}, 0), ({b}, 0), ({a, b}, 4)
Agent 2: ({a}, 2), ({b}, 0), ({a, b}, 0)
Agent 3: ({a}, 0), ({b}, 2), ({a, b}, 0)
Agent 4: ({a}, 0), ({b}, 2), ({a, b}, 2)
• Best allocation is agent 1 ({a, b}, 4)
• Agent 1 pays: 4 – 0 = 4 So it works just like
we thought it would
• In this case, second price bid is really the
same as the first price bid
27
•
Collusion
•
•
•
•
•
•
•
The VCG mechanism is not collusion-proof: if bidders work
together they can manipulate the mechanism. Consider the
following example:
Agent 1: ({a}, 0), ({b}, 0), ({a, b}, 4)
Agent 2: ({a}, 1), ({b}, 0), ({a, b}, 0)
Agent 3: ({a}, 0), ({b}, 1), ({a, b}, 0)
Who wins? What do they pay?
• But if the two losing bidders collude and increase their two bids to
• ({a}, 4) and ({b}, 4), respectively, they can obtain the items for free.
• Agent 1: ({a}, 0), ({b}, 0), ({a, b}, 4)
•
Agent 2: ({a}, 4), ({b}, 0), ({a, b}, 0)
•
Agent 3: ({a}, 0), ({b}, 4), ({a, b}, 0)
• Who wins? What do they pay?
28
Problems with the VCG Mechanism
• Despite their nice game-theoretical properties, combinatorial auctions
using VCG to determine payments have several problems:
–
–
–
–
Low (and possibly even zero) revenue for the auctioneer
Non-monotonicity: “better” bids can lower revenue
Collusion amongst (losing) bidders
False-name bidding: bidders may benefit from submitting bids using
multiple identities. Can you give an example?
– Shill bid – seller will submit a fake bid just below the high bid
• L.M. Asubel and P. Milgrom. The Lovely but Lonely Vickrey Auction. In
• P. Cramton et al. (eds.), Combinatorial Auction, MIT Press,
2006.
29
Conclusions
Pros
VCG processes have great theoretical appeal. Truth telling is a dominant strategy mechanism.
This means that, in theory, a bidder’s decision to use a strategy does not depend on what
the bidder thinks her competitors’ strategies are, and she need spend no effort in trying to
find them out or to keep her competitors from learning her strategy.
In some circumstances, they produce, expected revenue equivalent to other common auction
forms.
Cons
• However, VCG processes are just not practical. They do not work the way the (simple)
theory says they should.
So Why do we study VCG processes ?
Because finding equilibrium strategies in combinatorial auctions is extraordinarily difficult except
in VCG processes, there may well be useful insights to be had from such knowledge. For
example, Mishra and Parkes (2007) analyze an iterative version of the VCG process.
In addition, computerized bidding agents may be able to avoid some of the problems.
Rothkopf: Thirteen Reasons Why the Vickrey-Clarke-Groves Process Is Not Practical
Operations Research 55(2), pp. 191–197, ©2007 INFORMS
30
The winner determination problem
(WDP)
• Choose a subset A (the accepted bids) of the
bids B,
vb is value of the bid to the person who
received the items
maximize Σ(b in A)vb (Value of accepted bids
maximized )
under the constraint that every item occurs at
most once in A
– This is assuming free disposal, i.e., not everything
needs to be allocated
•
•
•
•
•
•
•
•
•
•
•
WDP example
Items A, B, C, D, E
Bids:
({A, C, D}, 7)
({B, E}, 7)
({C}, 3)
({A, B, C, E}, 9)
({D}, 4)
({A}, 4)
({A, B}, 5)
({B, D}, 5)
({D,E},7)
• What’s an
optimal
solution?
• How can we
prove it is
optimal?
(Important for
NP-complete)
Price-based argument for optimality
Suppose we create “prices”
Items A, B, C, D, E
(each item has the
Bids:
smallest price so that the
({A, C, D}, 7)
sum of the prices is at
least the bid price) for the
({B, E}, 7)
items.
({C}, 3)
({A, B, C, E}, 9)
({D}, 4)
({A, B, C}, 5)
({B, D}, 5)
Pick a set of prices.
If our solution achieves the
value indicated by the
prices, we feel we have
achieved optimal.
Price-based argument for optimality
Suppose we create “prices”
Items A, B, C, D, E
(each item has the
Bids:
smallest price so that the
({A, C, D}, 7)
sum of the prices is at
least the bid price) for the
({B, E}, 7)
items:
({C}, 3)
p(A)
=
0,
p(B)
=
7,
p(C)
=
3,
({A, B, C, E}, 9)
p(D) = 4, p(E) = 0
({D}, 4)
Every bidder bids at most
({A, B, C}, 5)
the sum of the prices of its
({B, D}, 5)
items, so we can’t expect
to get more than 14.
Create Price Based for this model
•
•
•
•
•
•
•
•
•
•
•
Items A, B, C, D, E
Bids:
({A, C, D}, 7)
({B, E}, 7)
({C}, 3)
({A, B, C, E}, 9)
({D}, 4)
({A}, 4)
({A, B}, 5)
({B, D}, 5)
({D,E},7)
Create Price Based for this model
•
•
•
•
•
•
•
•
•
•
•
Items A, B, C, D, E
Bids:
({A, C, D}, 7)
({B, E}, 7)
({C}, 3)
({A, B, C, E}, 9)
({D}, 4)
({A}, 4)
({A, B}, 5)
({B, D}, 5)
({D,E},7)
Can you beat?
A4
B4
C3
D4
E 3
Price-based argument
•
•
•
•
•
Items A, B, C
Bids:
({A, B}, 2)
({B, C}, 2)
({A, C}, 2)
• What would prices be here?
• What is actual upper bound on revenue?\
• What if we allowed partial bid filling?
Price-based argument does not
always give matching upper bound
•
•
•
•
•
Items A, B, C
Bids:
({A, B}, 2)
({B, C}, 2)
({A, C}, 2)
• Clearly can get at most 2
• If we want to set prices that sum to 2,
there must exist two items whose prices
sum to < 2
• But then there is a bid on those two items
of value 2
– (Can set prices that sum to 3, so that’s
an upper bound)
An integer program formulation
• xb equals 1 if bid b is accepted, 0 if it is not
 maximize Σb vbxb
 subject to: for each item j, Σb: j in b xb ≤ 1
_______________________________
• If each xb can take any value in [0, 1], we say that bids
can be partially accepted
• In this case, this is a linear program that can be solved
in polynomial time
• This requires that
– each item can be divided into fractions
– if a bidder gets a fraction f of each of the items in his bundle,
then this is worth the same fraction f of his value vb for the
bundle
– We would expect this to be easier – like fractional knapsack
Idea: Use weighted independent set to
solve winner determination problem
2
2
3
3
4
2
4
• Build an intersection graph: nodes are bids, edges are
conflicts between bids.
• Choose subset of the vertices with maximum total
weight, such that no two vertices can have an edge
between them
• NP-hard (generalizes regular independent set)
The winner determination problem as a
weighted independent set problem
• Each bid is a vertex
• Draw an edge between two vertices if they share an item
bid 2
v(
) = $700
bid 3
v(
) = $300
bid 1
v(
) = $500
• Optimal allocation = maximum weighted independent set
• Can model any weighted independent set instance as a CA (combinatorial
auction) winner determination problem (1 item per edge (or clique))
• Weighted independent set is NP-hard, even to solve approximately [Håstad
96] - hence, so is WDP: winner determination problem
– [Sandholm 02] noted that this inapproximability applies to the WDP (can’t bound
the error to any constant factor)
• cannot be approximated uniformly –
means there does not exist a polynomial
time algorithm and a fixed constant k>0
such that the algorithm returns a solution
that is at least s*/k where s* is the value of
the optimal solution. (a higher s* is better)
Heuristic Approaches
• Complete heuristic – guaranteed to find an
optimal solution if one exists – but may not
be able to estimate amount of time it will
take.
• incomplete heuristic - 1/n of optimal (n
is number of items), but often perform well
in practice.
• Example of incomplete: greedy (allocates
one bid at a time and never reconsiders)
Dynamic programming approach
to WDP [Rothkopf et al. 98]
• Give a description of dynamic programming.
• For every subset S of I, compute w(S) = the
maximum total value that can be obtained when
allocating only items in S
• Then, w(S) = max {maxi vi(S), maxS’: S’ is a subset of
S, and there exists a bid on S’ w(S’) + w(S \ S’)}
• Requires exponential time – because the set of
all subsets is exponential
So…
• How do we approach the problem given
that the solutions we have tried are NPhard or NP-complete?
• Look for restricted set of problems for
which we can find efficient solutions.
Bids on connected sets of items in a tree
• Suppose items are organized in a tree
item B
item A
item C
item E
item F
item G
item D
item H
• Suppose each bid is on a connected set of items
– E.g. {A, B, C, G}, but not {A, B, G}
• Then the WDP can be solved in polynomial time (using
dynamic programming) [Sandholm & Suri 03]
• Tree does not need to be given: can be constructed from the
bids in polynomial time if it exists [Conitzer, Derryberry, Sandholm 04]
• More generally, WDP can also be solved in polynomial time for
graphs of bounded treewidth [Conitzer, Derryberry, Sandholm 04]
– Even further generalization given by [Gottlob, Greco 07]
Maximum weighted matching
(not necessarily bipartite graphs
– see next slide)
1
2
3
B
2
C
A
3
4
5
3
4
• If each bidder is only interested in winning one item.
• Choose subset of the edges with maximum total
weight,
• Constraint: no two edges can share a vertex
• Still solvable in polynomial time
Bids with few items [Rothkopf et al. 98]
• If each bid is on a bundle of at most two items,
• then the winner determination problem can be solved
in polynomial time as a maximum weighted matching
problem. What is purpose of dummy nodes?
– 3-item example:
Value of highest
bid on {A, B}
item A
Value of
highest bid
on {B, C}
Value of highest
bid on {A}
A’s dummy
item B
Value of
highest bid
on {A, C}
item C
Value of
highest bid
on {B}
Value of
highest bid
on {C}
B’s dummy
C’s dummy
• If each bid is on a bundle of three items, then the
winner determination problem is NP-hard again
Variants [Sandholm et al. 2002]:
combinatorial reverse auction
• In a combinatorial reverse auction (CRA),
the auctioneer seeks to buy a set of
items, and bidders have values for the
different bundles that they may sell to the
auctioneer
 minimize Σb vbxb xb is 1 if bid is accepted
 subject to
 for each item j, Σb: (j in b) xb ≥ 1 (get all items)
WDP example (as Combinatorial Reverse
Auction )
• Items A, B, C, D, E
• Bids:
Buyer needs all items
Can get two of same item
• ({A, C, D}, 7)
• ({B, E}, 7)
• ({C}, 3)
• ({A, B, C, E}, 9)
• ({B,D}, 4)
• ({A, B, C}, 5)
• ({B, D}, 5)
Variants: multi-unit CAs/CRAs
• Multi-unit variants of CAs and CRAs: multiple
units of the same item are for sale/to be
bought, bidders can bid for multiple units
• Let qbj be number of units of item j in bid b, qj
total number of units of j available/demanded
 maximize Σb vbxb (CA)
 subject to
 for each item j, Σb qbjxb ≤ qj
 minimize Σb vbxb (CRA)
 subject to
 for each item j, Σb qbjxb ≥ qj
Variants: (multi-unit)
combinatorial exchanges
• Combinatorial exchange (CE): bidders can
simultaneously be buyers and sellers
– Example bid: “If I receive 3 units of A and -5 units of
B (i.e., I have to give up 5 units of B), that is worth
$100 to me.”
 maximize Σb vbxb
 subject to
 for each item j, Σb qb,jxb ≤ 0 cumulatively give up
more than get
Exponentially many bundles
• In general, in a combinatorial auction with set of
items I (|I| = m) for sale, a bidder could have a
different valuation for every subset S of I
– Implicit assumption: no externalities (bidder does
not care what the other bidders win)
• Must a bidder communicate 2m values?
– Impractical
– Also difficult for the bidder to evaluate every bundle
• Could require vi(Ø) = 0
– Does not help much
• We could require: if S is a superset of S’, v(S)
≥ v(S’) (free disposal)
– Does not help in terms of number of values
Variants: no free disposal
• Change all inequalities to equalities
• A bidder is single-minded if she only wants
one subset of the goods.
– Usually not the case
• Even restricting valuations to be single
minded does NOT make the winner
determination problem any easier.
Two sided auctions
aka double auctions
• many buyers and sellers. Bid is price and
quantity - positive (buyer) negative (seller).
When do trades occur?
• continuous double – as soon as bid is
received attempt to match
• periodic double (aka call market) – trades
happen at predetermined times (called
clearing the market) - rank sellers in order
and buyers in order – find the point at
which supply equals demand
Example of a double auction
Sell
5@$1
3@$2
6@$4
2@$6
4@$9
Buy
6@$9
4@$5
6@$4
3@$3
5@$2
2@$1
Who should get the items and what should they pay?
(Other views of same data)
Sell 1 1 1 1 1 2 2 2 4 4 4 4 4 4 6 6 9 9 9 9
Buy 9 9 9 9 9 9 5 5 5 5 4 4 4 4 4 4 3 3 3 2 2 2 2 2 1 1
Sell 9 9 9 9 6 6 4 4 4 4 4 4 2 2 2 1 1 1 1 1
Buy 9 9 9 9 9 9 5 5 5 5 4 4 4 4 4 4 3 3 3 2 2 2 2 2 1 1
Result
Before
Sell
5@$1
3@$2
6@$4
2@$6
4@$9
Buy
6@$9
4@$5
6@$4
3@$3
5@$2
Sell
2@$6
4@$9
Buy
2@$4
3@$3
5@$2
2@$1
2@$1
After
The amount paid to the seller could be less than the amount charged to the
buyer, allowing a commission
Bidding Languages
• How do you expect to be able to express
your bids in a combinatorial auction?
Bidding languages
• Bidding language = a language for expressing valuation
functions
• A good bidding language allows bidders to concisely express
natural valuation functions
• Example: the OR bidding language [Rothkopf et al. 98, DeMartini et al. 99]
• Bundle-value pairs are ORed together, auctioneer may accept
any number of these pairs (assuming no overlap in items)
• E.g. ({a}, 3) OR ({b, c}, 4) OR ({c, d}, 4)
implies what values for the following:
– {a}
– {b, c, d}
– {a, b, c}
Bidding languages
• Bidding language = a language for expressing
valuation
• Can we express the valuation function v({a, b})
= v({a}) = v({b}) = 1 using the OR bidding
language? subadditive issue
• ({a, b},1) OR ({a},1) OR ({b},1)?
XORs
• If we use XOR instead of OR, that means that only one of the
bundle-value pairs can be accepted
• Can express any valuation function (simply XOR together all
bundles)
• E.g. ({a}, 3) XOR ({b, c}, 4) XOR ({c, d}, 4) implies
– A value of 3 for {a}
– A value of 4 for {b, c, d}
– A value of 4 for {a, b, c} Can’t easily get additive values
• Sometimes not very concise
• E.g. suppose that for any S, v(S) = Σs in Sv({s})
– How can this be expressed in the OR language?
– What about the XOR language?
• Can also combine ORs and XORs to get benefits of both [Nisan
00, Sandholm 02]
WDP and bidding languages
• Single-minded bidders bid on only one bundle
– Valuation is v for any superset including that bundle, 0
otherwise
• If we can solve the WDP for single-minded bidders,
how can we solve WDP for general OR problems?
• Bidder 1: ({a}, 3) OR ({a, b}, 4) OR ({c},2)
• Bidder 2: ({a,b}, 6) OR ({c}, 1)
WDP and bidding languages
• Single-minded bidders bid on only one bundle
– Valuation is v for any superset including that bundle, 0
otherwise
• Suppose we have an OR language but wanted XOR.
Can we make that work?
• For example, express the following with an OR
language:
• ({a}, 3) XOR ({b, c}, 4)
Iterative Mechanisms
• Probe valuations only as necessary
• Benefit to bidders who want to reveal as little as possible about
their valuations
• Helpful if difficult to determine valuation
• Agents may gain by waiting for others to reveal information –
especially if determining own valuation is costly
• What would auctioneer queries look like?
Iterative Mechanisms
• Auctioneer can query the bidders with:
– value query: suggest a bundle and ask how much is worth
– demand query: ask how many would buy good for a specific
price
– order query: which of two bundles is preferred.
– bounding query: is a give bundle worth more or less than amt
As a bidder, what is your expected profit in a first price
auction?
(assume only two bidders)
• It seems natural to try to maximize your expected
profit.
• If you are trying to maximize profit, what
should you bid? A little (so reward is
great)? A lot (so chance of winning is
good)?
• What is profit a function of?
67
What is your expected profit in a first price auction?
(assume only two bidders)
• Expected profit (as a function of a specific bid) is the
probability that you will win the bid times the amount
of your profit at that price.
• Let p be the price you bid for an item. v be your
valuation. [a,b] be the uniform range of others bid.
• The probability that you win the bid at this price is
the fraction of the time that the other person bids
lower than p. (p-a)/(b-a)
• The profit you make at p is v-p
• Expected profit as a function of p is the function
• = (v-p)*(p-a)/(b-a) + 0*(1- (p-a)/(b-a))
68
Finding maximum profit is a simple
calculus problem
• Expected profit as a function of p is the function
•
(v-p) * (p-a)/(b-a) amount of profit * prob of winning
• So what is next?
69
Finding maximum profit is a simple
calculus problem
• Take the derivative with respect to p and set that
value to zero. Where the slope is zero, is the
maximum value. (as second derivative is negative)
• f(p) = 1/(b-a) * (vp -va -p2+pa)
• f’(p) = 1/(b-a) (v-2p+a) = 0
• p=(a+v)/2 (half the distance between your valuation
and the min range value)
• Notice that the upper value (b) doesn’t matter – as
you don’t care about anything higher than v.
70
Are you surprized?
The results make sense. You never bid higher than your
valuation. You can’t win these cases, so we’ll ignore them.
Of the remaining cases, if you bid halfway between the low
evaluation and your valuation, you expect to win half the
time and lose half the time [in the cases where you have a
chance].
When you do win, you pay considerably less than your
valuation, and hence make a handsome profit.
You have to bid more often as you won’t get everything you
bid on – but this is a good plan.
BUT As there are more bidders, how would that affect your
bid?
71
In general, n agents with uniform distribution
on range [0,Max] what should each agent bid?
• For simplicity, lets assume a=0. In order to win the bid at price p,
every other person would need to bid below p. What is the chance of
that? Since we want bidder 1 to bid below p and bidder 2 (and so
forth), we multiply the probabilities for each of the other n-1 bidders:
• Expected valued =
(p/b)n-1 * (p-v) = (1/bn-1)*(p(n) – vpn-1)
• derivative wrt p = (1/bn-1*((n)p(n-1) – (n-1)vp(n-2)) = 0
• (n)p(n-1) – nvp(n-2) +vp(n-2) = p(n-2)(pn –nv + v)
• so either p = 0 (obviously a minimum) or
p=((n-1)/n) * v
• When n=2, we get the results on the previous slide. Idea is that with
more bidders (randomly bidding within the range), you have to bid
closer to your valuation to win; the idea of competition.
72
Revenue for the Auctioneer
Which protocol is best for the auctioneer?
• Revenue-equivalence Theorem (Vickrey, 1961):
All four protocols give the same expected revenue for private value auctions
amongst risk-neutral bidders with valuations independently drawn from a
uniform distribution.
• Intuition: revenue second highest valuation:
– Vickrey: clear
– English: bidding stops just after second highest valuation
– Dutch/FPSB: because of the uniform value distribution and
counter speculation, top bid second highest valuation
• But: this applies only to an artificial and rather idealized
situation; in reality there are many exceptions.
73
Revelation Principle
• You can transform any auction into an “equivalent”
one which is direct and incentive compatible (i.e.,
bidder will bid the true valuation)
• Do you believe that? That is quite a statement.
• Rather than lie (bid less than your true valuation), the
mechanism will “lie” for you
• Example: assume two bidders (with valuations drawn
from a uniform distribution on a fixed interval [0,max]).
The optimal strategy is to bid ½ your true value.
• How could you change the rules so the bidder was
motivated to bid true valuation?
74
Revelation Principle
• Example: assume two bidders (with valuations drawn
from a uniform distribution on a fixed interval [0,max]).
The optimal strategy is to bid ½ your true value.
• But if the rule is changed so that the winner only pays
half his bid, it is optimal to bid your true value.
75
Descargar

CPS 296.1: auctions and combinatorial auctions