CSCI 1440/2440 Introduction to Game Theory - Homework 5: Posted-Price Mechanisms
Homework 5: Posted-Price Mechanisms CSCI 1440/2440
2021-03-10
Due Date: Tuesday, March 15, 2021. 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 only solve the first four problems. For 2000-level credit, you should solve all five problems.
1 An Equal-Revenue Distribution
Suppose all bidders draw their values for a single good from the
following distribution:
0 for x ≤ 1
F(v) =
1−1/v forx≥1
- Assuming just one bidder, what revenue curve corresponds to this distribution, when the posted price is π > 1? Hint: Distributions of this form are called equal-revenue distributions.
- What virtual value function corresponds to this distribution?
- How would Myerson’s optimal auction allocate this good? What would each bidder pay to satisfy IC and IR?
- Why isn’t Myerson’s auction optimal in this setting?
- Describe an IC and IR auction that achieves greater expected rev- enue than Myerson’s “optimal” auction given this distribution.
2 Revenue Curves and the Median
Assuming a single buyer with regular distribution F, the revenue curve as a function of a quantile q ∈ [0, 1] is given by: Rev(q) = q F−1 (1 − q) .
1. What is the value of the revenue curve at quantile q = 1/2? State your answer in terms of the median,
2. Prove that the median upper bounds the revenue curve: i.e., Rev(q) ≤ κ, for all q ∈ [0, 1]. Hint: Use the fact that the revenue curve is concave.
3 Optimizing Posted Prices
Consider a symmetric setting comprising n bidders whose values are all drawn i.i.d. from the distribution F.
Recall the formula for revenue as a function of a posted price π: Rev(π) = π (1 − F(π)n)
- Solve for the optimal posted price when values are all drawn i.i.d. from the uniform distribution on [0, 1].
- Solve for the optimal posted price for an arbitrary F. Your solution should be in terms of F(π) and f (π).
- The CDF and PDF of the first-order statistic is given by F (π)n and nF (π)n−1 f (π), respectively. Using this information, relate the optimal posted price to the hazard rate of the first-order statistic distribution. Reminder: The hazard rate of a continuous random variable T with CDF F and PDF f is defined as f (t)/1−F(t).
4 Posted-Price vs. Second-Price Revenue
Consider a symmetric setting comprising n bidders whose values are all drawn i.i.d. from the uniform distribution on [0, 1].
Prove that the ratio of the expected revenue of the posted-price mechanism for a single good, with posted price π = F−1 (1 − 1/n), to that of the second-price auction is:
2nd e Hint: (1−1/n)n ≤ 1/e, for all n ≥ 1.
5 Approximately-Optimal Second-Price Auctions
This problem concerns the single-sample second-price auction, a second-price auction with a reserve price, which works as follows:
Bids are collected. A reserve price is chosen by removing an arbitrary bidder j from the auction, and setting the reserve price to be j’s bid. The auctioneer then allocates the good to the bidder with the highest bid iff their bid is at least this reserve, and charges the winner, if any, the greater of the second-highest bid and the reserve price.
The goal of this problem is to show that this auction achievesof the optimal revenue, where n is the number of bidders, assuming symmetic values drawn i.i.d. from a regular distribution F.
1. Let t and v be two values in the support of F. Let r∗ be the monopoly ∗ −1 reserve price: i.e., r = φ (0). Show thatE [R(max{t,v})]≥1/2R(max{t,r∗}).
Hint: Prove this result in quantile space, namely:
E [R (min{q(t), q(v)})] ≥ 1 R (min{q(t), q(r∗)}) . q(v)∼U(0,1) 2
2. Let APX denote the expected revenue generated by the single- sample second-price auction. Let OPT denote the expected rev- enue generated by the optimal (i.e., revenue-maximizing) auction. Using part 1, show that the single-sample second-price auction generates, in expectation, approximately half the total expected revenue generated by the optimal auction: i.e.,
