CSCI 1440/2440 Introduction to Game Theory - Homework 4: Myerson’s Theorem - Revenue Maximization
Homework 5: Myerson’s Theorem CSCI 1440/2440
2022-03-03
Due Date: Tuesday, March 10, 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 only solve the first three problems. For 2000-level credit, you should solve all four problems.
1 Bayesian Constraints, continued
Recall the Bayesian (i.e., interim) formulation of the auction design problem from Homework 4. Since the interim constraints are weaker than the ex-post constraints presented in lecture, you might imagine that the welfare achieved by the welfare-maximizing auction in the interim case exceeds that of the ex-post case. Argue that this is not
in fact the case: i.e., that the value that maximizes expected welfare in this model is the same regardless of whether the IC and IR con- straints are interim or ex-post. (The same holds for revenue, but you need only make the argument once.)
2 Sponsored Search: Revenue
As in Homework 4, assume n bidders (online advertisers) are com- peting for one of k slots on a page that results from a keyword search (e.g., “TV”). Each slot can be allocated to at most one bidder, and each bidder can be allocated at most one slot.
Associated with each slot j is a probability that a user conducting an organic search will click on an ad in that slot. This probability is called the click-through-rate (CTR). For slot j, we denote the CTR byαj,andweassumeα1 ≥α2 ≥···≥αk.
Each bidder i also has a private value vi that corresponds to how
much they value a user clicking on their ad (e.g., an estimate of how much profit they expect per click). Thus, if a bidder is allocated slot j (i.e., xi = αj) and pays pi, their utility is given by ui = αjvi − pi.
Design a sponsored search auction (i.e., an allocation scheme and a payment rule) for slots on a web page that collects one bid from each bidder, and then allocates each slot to at most one bidder, and at
most one slot to each bidder. Your auction should maximize revenue and satisfy the usual constraints of individual rationality, incentive compatibility, and ex-post feasibility. Use Myerson’s lemma and theorem to argue that your auction satisfies these requirements.
3 Another Auction with Reserve Prices
Reserve prices are necessary to maximize expected revenue, since they give auctioneers the flexibility to charge more money to bid- ders whom they expect to have high values, while still preserving incentive compatibility and individual rationality.
Amy understands this, but she does not understand why the revenue-maximizing auction for a single good would allocate to a bidder with the highest virtual value, rather than a bidder with the highest value. To her, it seems like the revenue-maximizing auction should allocate to a bidder with the highest value, since such a bid- der is willing to pay the most!
So Amy proposes the following revision to Myerson’s optimal auction: use the same reserve prices as Myerson, but allocate to a bidder with the highest value among the bidders who bid above their reserve prices. More precisely, Amy’s allocation rule works as follows:
• Assume vi ∼ Fi for all bidders i ∈ N, where Fi is regular with bounded support.
• Determine the set C of bidders i who bid at least their reserve, −1 namely φi (0), where φi is bidder i’s virtual value function. • Allocate the good to the highest bidder in C.
Amy also wants her auction to be IC and IR. Thus, she proposes using Myerson’s payment characterization lemma to set payments.
- Explain Amy’s payment rule in words. What does the winning bidder pay?
- When at most one bidder bids above their reserve prices, Amy’s and Myerson’s auctions yield the exact same outcome.
Consider the case in which there are at least two bidders who bid above their reserve prices, and among them, the bidder with the highest value is not the same as the bidder with the highest virtual value. Prove that Amy’s auction yields weakly greater expected revenue than Myerson’s auction in this case.
- Consider the other case, in which the bidder with the highest value also has the highest virtual value. In this case:
(a) Provide an example in which Amy’s auction produces greater revenue.
(b) Provide an example in which Myerson’s auction produces greater revenue.
Your examples should define the number of bidders, each bidder’s value distribution, and each bidder’s value.
4. Extra Credit: Suppose there are just two bidders: Bidder A whose value is drawn from U(0, 1) and Bidder B whose value is drawn from U(0, 2). Compute the expected revenue of both Amy’s and Myerson’s auctions.
4 A Simple(r) Approximately-Optimal Auction
Assuming regularity (i.e., weakly increasing virtual values), prove that, the expected revenue of the second-price auction with Myer- son’s reserve prices is always at least half of the expected revenue of the optimal auction. In this simple(r) auction, the highest bidder wins as long as their bid exceeds their reserve, and they pay the maximum of the second-highest bid and their reserve.
N.B. This second-price auction with Myerson reserves is simpler than Myerson’s optimal auction, as it requires inverting the virtual value function only at 0, to compute reserve prices.
Hint: Here is an outline of how to proceed. Define OPT as the expected revenue of the optimal auction, and APX as the expected revenue of the simpler auction. The goal is to show APX ≥ 1/2 OPT.
Assume bidder i wins the optimal auction, and bidder j, the sim- ple auction, so that OPT = Evi∼Fi [φi(vi)] and APX = Evj∼Fj [pj]. As the winners of the auctions, i and j, are random variables,
OPT = Evi∼Fi[φi(vi) | i = j]Pr[i = j]+Evi∼Fi[φi(vi) | i ̸= j]Pr[i ̸= j]
the same winner different winners
Thus, it suffices to show (1) APX is at least the expected revenue of the optimal auction when i = j (i.e., when the same bidder wins both auctions); and (2) APX is at least the expected revenue of the optimal auction when i ̸= j (i.e., when the winners of the two auctions differ): i.e.,
APX ≥ Evi∼Fi[φi(vi) | i = j]Pr[i = j] (1)
APX ≥ Evi∼Fi[φi(vi) | i ̸= j]Pr[i ̸= j], (2)
from which it follows that 2APX ≥ OPT.
