STAT155 Game Theory - Homework 4: Simple Near-Optimal Auctions, Multi-Parameter Mechanism, Spectrum Auctions and Stable Matching
Exercise adapted from Problem 4.3:
Consider a set M of distinct items. There are n bidders, and each bidder i has a publicly known subset T_i \subseteq M of items that it wants, and a private valuation v_i for getting them. If bidder i awarded a set S_i of items at a total price of p, then her utility is v_ix_i - p, where x_i is 1 if S_i \supseteq T_i and 0 otherwise. Since each item can only be awarded to one bidder, a subset W of bidders can all receive their subsets simultaneously if and only if T_i \cap T_j = \empty for each distinct i, j \in W.
(a) Is this a single-parameter environment? Explain fully.
(b) The allocation rule that maximizes social welfare is well known to be NP hard(as the knapsack auction was) and so we make a greedy allocation rule. Give a reported truthful bid b_i from each player i, here is a greedy allocation rule:
(i) Initialize the set of winners W = \empty , and the set of remaining items X = M.
(ii) Sort and re-index the bidders so that b_1 \ge b_2 \ge ... \ge b_n.
(iii) For i = 1, 2, 3, ..., n:
If T_i \subseteq X, then:
- Delete T_i from X.
- Add i to W.
(iv) Return W (and give the bidders in W their desired items)
Is this allocation rule monotone (bidder smaller leads to a smaller cost)? If so, find a DSIC auction based on this allocation rule. Otherwise, provide an explicit counterexample.
(c) Does the greedy allocation rule maximize social welfare? Prove the claim or construct an explicit counterexample.
Exercise 6.4 (H) Consider an n-bidder single-item auction, with bidders’ valuations drawn i.i.d. from a regular distribution F . Prove that the expected revenue of a second-price auction (with no reserve price) is at least \frac {n−1} n times that of an optimal auction.
Exercise 7.4 Consider a combinatorial auction in which bidders can submit multiple bids under different names, unbeknownst to the mechanism. The allocation and payment of a bidder is the union and sum of the allocations and payments, respectively, assigned to all of her pseudonyms.
(a) Exhibit a combinatorial auction and bidder valuations such that, in the VCG mechanism, there is a bidder who can earn higher utility by submitting multiple bids than by bidding truth- fully as a single agent (assuming others bid truthfully).
(b) Can this ever happen in a second-price single-item auction?
Exercise 9.5 Another mechanism for the house allocation problem, familiar from the assignment of dorm rooms to college students, is the random serial dictatorship.
Random Serial Dictatorship
initialize H to the set of all houses randomly order the agents for i = 1,2,3,...,n do assign the ith agent her favorite house h from among those in H delete h from H
(a) Does an analog of Theorem 9.7 hold for the random serial dictatorship, no matter which random ordering is chosen by the mechanism?
(b) Does an analog of Theorem 9.8 hold for the random serial dictatorship, no matter which random ordering is chosen by the mechanism?
Exercise 10.5 Suppose each applicant and hospital has a total ordering over the vertices of the opposite side and also an “outside option.” In other words, vertices can prefer to go unmatched over some of their potential matches.
(a) Extend the definition of a stable matching to accommodate outside options.
(b) Extend the deferred acceptance algorithm and Theorem 10.5 to compute a stable matching in the presence of outside options.
Exercise 10.6 (H)
