CSCI 1440/2440 Introduction to Game Theory - Homework 7: Vickrey-Clarke-Groves Mechanism
Homework 7: The Vickrey-Clarke-Groves Mechanism CSCI 1440/2440
2022-03-24
Due Date: Tuesday, April 12, 2022. 11:59 PM.
We encourage you to work in groups of size two. Each group need only submit one solution. Your submission must be typeset using LATEX. Please submit via Gradescope with you and your partner’s Banner ID’s and which course you are taking.
For 1000-level credit, you need to solve the first five problems. For 2000-level credit, you should solve all six problems.
1 The Vickrey Auction: An Oldie but Goodie
Consider a single-good auction, and assume bidders’ values are drawn i.i.d. from a regular distribution F. Prove that the expected revenue of the Vickrey auction (second-price without a reserve) with n bidders, Vn, is at least n−1/n times that of Myerson’s optimal auc- tion (second-price with the monopoly price as the reserve) with the same number of bidders. Hint: Use the Bulow-Klemperer Theorem itself, or a similar proof technique.
2 Payment Bounds
The VCG mechanism collects (possibly misleading) reports from all bidders and then computes a welfare-maximizing allocation ω∗ together with corresponding payments pi(ω∗), which ensure that a dominant strategy comprises truthful reports.
Prove that, for all bidders i ∈ I,
1. VCG payments pi(ω∗) are lower-bounded by 0.
2. VCG payments pi(ω∗) are upper-bounded by vi(ω∗).
3 Revenue
This problem asks you to construct examples of multiparameter auctions, by which we mean you should specify 1. a set of goods, and 2. each bidder’s valuation. Let Rev(I) be the revenue generated by the VCG mechanism, given a set of bidders I.
1. Show, by example, that the following is possible: Rev(I \ {i}) > Rev(I), for some i ∈ I.
2. Construct a non-trivial example of a multiparameter auction in which the VCG mechanism yields Rev(I) = 0. (By non-trivial, we mean that each bidder’s valuation should be non-negative for every outcome and strictly positive for at least one outcome, and the number of bidders should exceed 1.)
4 Collusion
This problem highlights two shortcomings of the VCG mechanism.
1. Show that, when the VCG mechanism is used, it is possible for two bidders not to be allocated anything when bidding truthfully, but for one or both of them to obtain strictly positive utility if they tacitly collude, by both submitting untruthful reports.
2. Suppose that a single bidder submits multiple false bids to a VCG mechanism. That is, the auctioneer thinks there are n distinct bidders, but in reality, at least two of the n bids are submitted by a single bidder i. Show that a bidder can obtain strictly higher utility by submitting multiple false bids rather than one truthful bid.
5 Ties
The outcome, namely the allocation and payments, of a VCG mech- anism depends on the solution to welfare-maximization problem, which may not be unique. Multiple optima would not impact the welfare, as if one of them yielded lower welfare it would not be welfare-maximizing! But a question arises as to whether the choice of welfare-maximizing solution (i.e., allocation) on which the outcome (i.e., payments) depend impacts revenue.
It turns out that the revenue earned in a VCG mechanism also does not depend on the choice of welfare-maximizing allocation. Prove this claim in the case of 2 goods and 2 bidders.
6 Unit Demand
A unit-demand valuation is one in which bidders value a bundle based on only the value of their favorite good in the bundle. More formally, let S denote the set of goods, and let vij represent bidder i’s value for good j ∈ S. If bidder i has unit demand, then
vi(S) = max vij, ∀S ⊆ G. (1) j∈S
Prove that the VCG mechanism can be run in time polynomial in the number of bidders and goods, assuming unit-demand valuations.
In other words, prove that the allocation problem can be solved in polynomial time in this special case.
