Sample Solution for AGTA Tutorial 8
1. Suppose you are running a VCG-based simultaneous multi-item auction, where three related items A, B, and C, are being auctioned simultaneously, and each bidder can bid on any possible subset of the items. Suppose there are two bidders, X and Y , and they provide you with their “claimed valuation” as their bids for every subset of the items, as part of the bidding process. Suppose that the valuation functions vX and vY that you receive from the two bidders, X and Y, respectively, are as follows (the numbers denote millions of pounds):
vi(∅) vi(A) vi(B) vi(C)
vi({A, B}) 29
Copyright By PowCoder代写 加微信 powcoder
vi({A, C}) 38
vi({B, C}) 20
vi({A, B, C}) 50
i:=X 0 24 4 9 i:=Y 0 15 18 11
• What is the outcome of this VCG auction? In other words, which of the two bidders will get which of the item(s), and what price will they each pay?
Solution: Assume the bidders bid their true valuations (which we can, since in the VCG mechanism bidding the true valuations is a dominant strategy for all bidders). Then given these valuations, the VCG mechanism firstly picks an outcome that maxi- mizes the sum total valuation of all the bidders, i.e., maximizes the total social welfare of the outcome. In this case, interestly, there are two completely different outcomes that maximize the social welfare. Namely, if player (bidder) X gets allocated items {A,C} and player Y gets allocated {B}, then the sum total valuation of this outcome is:
vX ({A, C}) + vY ({B}) = 38 + 18 = 56.
Likewise, if X gets {A} and Y gets {B, C} then the total valuation of this other outcome
vX ({A}) + vY ({B, C}) = 24 + 32 = 56.
Furthermore, one can check (exhaustively) that these two outcomes provide the maxi- mum total valuation of any outcome.
Therefore, the VCG mechanism picks one of these possible outcomes, and then asks the bidders to pay the VCG payments associated with that outcome. Note that the VCG mechanism, as given, does not specify which of these outcomes is to be preferred. Either will do (and this does not change the incentive structure of the mechanism).
We note that these two outcomes are very different, and also yield very different pay- ments. Specifically, assume the outcome that gives X the set {A,C} and gives Y the
We now calculate the payments of X and Y for this outcome: Note that, since Y is the only player other than X, the VCG payment for X in this outcome is (maxO∈outcomes vY (O))− vY ({B}). Now, clearly, the maximum valuation of any outcome O for Y is vY ({A, B, C}) = 47. Thus, the payment for X is 47 − 18 = 29. Similarly, the payment for Y is (maxO∈outcomes VX (O)) − VX ({A, C}) = 50 − 38 = 12.
On the other hand, if the VCG mechanism chooses the other social-welfare-maximizing outcome, namely X gets {A} and Y gets {B,C}, then the payments are as follows: the payment of X is (maxO∈outcomes vY (O)) − vY ({B, C}) = 47 − 32 = 15. the payment of Y is(maxO∈outcomesVX(O))−VX({A})=50−24=26.
• Do you expect the bidders to tell you the truth about their valuations?
Solutions: Yes. Despite the fact that there are two entirely different VCG outcomes in this multi-item auction, and despite the facts that the payments of the two bidders are completely different in the two outcomes, nevertheless, for both bidders it is a (weakly) dominant strategy to bid their true valuation functions, regardless of which total-value- optimal outcome is chosen by the VCG mechanism.
(This can be checked by following the proof given in class that the VCG mechanism is incentive compatible. That proof never uses an assumption that the optimal outcome is unique.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com