Tutorial questions: allocating scarce resources
1. Auctions on eBay are ascending price open cry auctions but with a proxy bidding system, which proceeds as follows.
• The auctioneer sets a reserve price (so at the start of the auction the current highest bid is equal to the reserve price), an increment value, and an ending time.
• Potential buyers use a proxy bidding system. They submit a maximum value to the proxy bidding system (this must be higher than the current highest bid price).
• Whenever:
– the current highest bid plus increment is less than or equal to the submitted
maximum value, and
– the buyer is not the current highest bidder,
the proxy system will bid one increment more than the current highest bid on behalf of the buyer.
• The potential buyers are able to increase their maximum value at any point during the auction, as long as it is higher than the current highest bid.
• At the end of the auction, the proxy bidding system ensures that the bidder who submits the highest maximum value wins the auction and the price they pay is the the second highest maximum value submitted plus the increment. If more than one bidder submits the highest maximum value, the bidder who submitted first will win, and the amount they will pay is their maximum value.
Consider the following three possible bidder strategies.
Maxing: At the start of the auction, submit to the proxy bidding system a maximum value that is equal to your true valuation of the item and then wait for the auction to close.
Increments: If you are not the highest bidder and the current highest bid plus increment value is less than your true valuation of the item, submit to the proxy bidding system a maximum value that is the current auction price plus the increment value.
Sniping: Wait until the last moment before the end of the auction at which it is possible to submit a new maximum value to the proxy bidding system and then submit to the proxy bidding system a maximum value that is equal to your true valuation of the item.
Assume there are only two potential buyers for an eBay auction, BuyerA and BuyerB. BuyerA’s true valuation of the item is £50 and BuyerB’s true valuation of the item is £60. The reserve price is £40 and the increment value is £1. What would be the outcome of the auction in the following situations? Say who would win the auction and what price they would end up paying.
a) BuyerA uses maxing and BuyerB uses maxing.
Answer. Both bidders submit their true value at the start of the auction, so BuyerB
wins and pays £51
b) BuyerA uses increments and BuyerB uses sniping.
Answer. At the start of the auction, BuyerA submits the lowest possible maximum value which is £41. At the last moment, BuyerB submits a maximum value of £60. BuyerB wins and pays £42.
1
c) BuyerA uses increments and BuyerB uses maxing. (Assume that BuyerA is always first to submit their maximum value.)
Answer. At the start of the auction, BuyerA submits the lowest possible bid as their maxiumum value, which is £41, and BuyerB submits their true value as their maximum value, which is £60. The proxy system will bid £41 on behalf of BuyerA, followed by £42 on behalf of BuyerB. At this point, BuyerA will increase their maximum value to £43, the proxy system will bid £43 on behalf of BuyerA, followed by £44 on behalf of BuyerB. This continues until we reach a bid of £49 on behalf of BuyerA, followed by £50 on behalf of BuyerB. BuyerA is not prepared to go higher than 50 so BuyerB wins and pays £50.
d) BuyerA uses increments and BuyerB uses increments. (Assume that BuyerA is always the first to submit their maximum value.)
Answer. At the start of the auction, BuyerA and BuyerB both submit the lowest possible bid as their maximum value, which is £41. As BuyerA was first, the proxy system will bid £41 on behalf of BuyerA, at which point BuyerB will increase their maximum value to £42. The proxy system will bid £42 on behalf of BuyerB, at which point BuyerA will increase their maximum value to £43 and the proxy system will bid £43 on behalf of BuyerA. This continues until we reach a bid of £50 on behalf of BuyerB. BuyerA is not prepared to go higher than 50 so BuyerB wins and pays £50.
e) BuyerA uses sniping and BuyerB uses maxing.
Answer. At the start of the auction, BuyerB submits their true value as their maximum value, which is £60, and the proxy system bids £41 on behalf of BuyerB. At the last possible minute, BuyerA submits their true value of £50 as their maximum value. BuyerB wins and pays £51 (since the proxy system ensures that the bidder who submits the maximum value wins the auction and the price they pay is the maximum value of the second highest bidder plus the increment).
f) BuyerA uses sniping and BuyerB uses sniping.
Answer. At the last possible moment, BuyerA submits their true value as their max- imum, which is £50, and BuyerB submits their true value as their maximum, which is £60. BuyerB wins and pays £51 (since the proxy system ensures that the bidder who submits the maximum value wins the auction and the price they pay is the maximum value of the second highest bidder plus the increment).
2
2. Suppose we have two goods a and b and two agents ag1 and ag2. The agents declare the following true valuation functions:
vˆ1({a}) = v1({a}) = 8
vˆ1({b}) = v1({b}) = 7
vˆ1({a, b}) = v1({a, b}) = 14
vˆ2({a}) = v2({a}) = 6
vˆ2({b}) = v2{b}) = 4
vˆ2({a, b}) = v2{a, b}) = 12 a) Which allocation is made using the VCG mechanism?
Answer. The allocation that is made is the one that maximises social welfare according to the valuations that were declared: ({a, b}, ∅).
b) How much does each agent pay to the mechanism?
Answer.
ag1: If ag1 had declared a valuation of 0 for every possible allocation, then ag2 would have been allocated {a,b} for total social welfare (excluding ag1) of 12. The total value received by all agents except ag1 from the actual allocation is 0 (ag2 receives nothing in the actual allocation). Thus the amount ag1 must pay is p1 = 12 − 0 = 12.
ag2: If ag2 had declared a valuation of 0 for every possible allocation, then ag1 would have been allocated {a,b} for total social welfare (excluding ag2) of 14. The total value received by all agents except ag2 from the actual allocation is 14. Thus the amount ag2 mustpayisp2 =14−14=0.
c) What utility does each agent get?
Answer.
ag1: ag1 receives {a, b}, which it values at 14 and it has to pay 12. Thus the utility gained byag1 is14−12=2.
ag2: ag2 receives ∅, which it values at 0 and it has to pay 0. Thus the utility gained by ag2 is0−0=0.
d) Can ag2 improve its utility by lying and declaring valuation vˆ2′ ̸= v2 (assuming ag1 remains truthful)?
Hint. Think about the possible cases that can occur. In the allocation made when the agents submitted their true valuations we had that ag2 ends up with nothing, what other possible allocations might have been made and how would these have affected the utility gained by ag2?
3
Answer. There are three cases to consider. (Note, we don’t need to consider the cases where one or more of the items are not allocated, since these cases will never maximise social welfare.)
Case 1, allocation ({a}, {b}) is made. In this case ag2 would have to pay p2 = 14 − 8 = 6. The utility for ag2 in this case is thus 4 − 6 = −2 (since they would receive b which they value at 4 but would have to pay 6 for it). Therefore in this case ag2 would be worse off.
Case 2, allocation ({b}, {a}) is made. In this case ag2 would have to pay p2 = 14 − 7 = 7. The utility for ag2 in this case is thus 6 − 7 = −1 (since they would receive a which they value at 6 but would have to pay 7 for it). Therefore in this case ag2 would be worse off.
Case 3, allocation ({a, b}, ∅) is made. In this case ag2 would have to pay p2 = 14 − 14 = 0. The utility for ag2 in this case is thus 0 − 0 = 0 (since they would receive ∅ which they value at 0 and would have to pay 0 for it). Therefore in this case ag2 would be no better or worse off.
Case 4, allocation (∅, {a, b}) is made. In this case ag2 would have to pay p2 = 14 − 0 = 14. The utility for ag2 in this case is thus 12 − 14 = −2 (since they would receive {a, b} which they value at 12 but would have to pay 14 for it). Therefore in this case ag2 would be worse off.
Thus, for all possible allocations that might be made if ag2 falsely reports its valuation of the items, ag2 would be either no better than or worse off than if it reported its true valuation, and so ag2 cannot benefit from lying about its valuation.
4