Stat155 Game Theory - Homework 1: Incentive Problems, Nash equilibrium and Auctions
Problem 1.1 Identify a real-world system in which the goals of some of the participants and the designer are fundamentally misaligned, leading to manipulative behavior by the participants. A “system” could be, for example, a Web site, a competition, or a political process. Propose how to improve the system to mitigate the incentive problems. Your answer should include:
1. (a) A description of the system, detailed enough that you can express clearly the incentive problems and your solutions for them.
2. (b) Anecdotal or demonstrated evidence that participants are gaming the system in undesirable ways.
3. (c) A convincing argument why your proposed changes would reduce or eliminate the strategic behavior that you identified.
Exercise 2.3 Suppose there are k identical copies of an item and n > k bidders. Suppose also that each bidder can receive at most one item. What is the analog of the second-price auction? Prove that your auction is DSIC.
Exercise 2.5 Suppose you want to hire a contractor to perform some task, like remodeling a house. Each contractor has a cost for performing the task, which a priori is known only to the contractor. Give an analog of a second-price auction in which contractors report their costs and the auction chooses a contractor and a payment. Truthful reporting should be a dominant strategy in your auction and, assuming truthful bids, your auction should select the contractor with the smallest cost. The payment to the winner should be at least her reported cost, and losers should be paid nothing.
[Auctions of this type are called procurement or reverse auctions.]
Exercise 2.8 Recall the sponsored search setting of Section 2.6, in which bidder i has a valuation vi per click. There are k slots with click-through rates (CTRs) α1 ≥ α2 ≥ ··· ≥ αk. The social welfare of an assignment of bidders to slots is , where xi equals the CTR of the slot to which i is assigned (or 0 if bidder i is not assigned to any slot).
Prove that the social welfare is maximized by assigning the bidder with the ith highest valuation to the ith best slot for i = 1,2,...,k.
Problem 2.1 This problem considers online single-item auctions, where bidders arrive one-by-one. Assume that the number n of bidders is known, and that bidder i has a private valuation vi. We consider auctions of the following form.
Online Single-Item Auction
For each bidder arrival i = 1,2,...,n:
if the item has not been sold in a previous
iteration, formulate a price pi and then accept a
bid bi from bidder i
if pi ≤ bi, then the item is sold to bidder i at the
price pi; otherwise, bidder i departs and the item
remains unsold
(a) Prove that an auction of this form is DSIC.
(b) Assume that bidders bid truthfully. Prove that if the valuations of the bidders and the order in which they arrive are arbitrary, then for every constant c > 0 independent of n, there is no deterministic online auction that always achieves social welfare at least c times the highest valuation.
(c) (H) Assume that bidders bid truthfully. Prove that there is a constant c > 0, independent of n, and a deterministic online auction with the following guarantee: for every unordered set of n bidder valuations, if the bidders arrive in a uniformly random order, then the expected welfare of the auction’s outcome is at least c times the highest valuation.
