1. Homepage
  2. Homework
  3. CSCI 1440/2440 Introduction to Game Theory - Homework 4: Myerson’s Theorem - Revenue Maximization
This question has been solved

CSCI 1440/2440 Introduction to Game Theory - Homework 4: Myerson’s Theorem - Revenue Maximization

Engage in a Conversation
Brown UniversityUSCSCI 1440CSCI 2440Introduction to Game TheorySocial WelfareSponsored Search AucktionMyersons Theorem

Homework 5: Myerson’s Theorem CSCI 1440/2440
2022
-03-03 CourseNana.COM

Due Date: Tuesday, March 10, 2022. 11:59 PM. CourseNana.COM

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. CourseNana.COM

For 1000-level credit, you need only solve the first three problems. For 2000-level credit, you should solve all four problems. CourseNana.COM

1 Bayesian Constraints, continued CourseNana.COM

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 CourseNana.COM

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.) CourseNana.COM

2 Sponsored Search: Revenue CourseNana.COM

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. CourseNana.COM

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 v
i that corresponds to how CourseNana.COM

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. CourseNana.COM

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 CourseNana.COM

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. CourseNana.COM

3 Another Auction with Reserve Prices CourseNana.COM

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. CourseNana.COM

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! CourseNana.COM

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: CourseNana.COM

• Assume vi Fi for all bidders i N, where Fi is regular with bounded support. CourseNana.COM

• 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. CourseNana.COM

Amy also wants her auction to be IC and IR. Thus, she proposes using Myerson’s payment characterization lemma to set payments. CourseNana.COM

  1. Explain Amy’s payment rule in words. What does the winning bidder pay?
  2. 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. CourseNana.COM

  1. 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. CourseNana.COM

(b) Provide an example in which Myerson’s auction produces greater revenue. CourseNana.COM

Your examples should define the number of bidders, each bidder’s value distribution, and each bidder’s value. CourseNana.COM

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. CourseNana.COM

4 A Simple(r) Approximately-Optimal Auction CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

Assume bidder i wins the optimal auction, and bidder j, the sim- ple auction, so that OPT = EviFi [φi(vi)] and APX = EvjFj [pj]. As the winners of the auctions, i and j, are random variables, CourseNana.COM

OPT = EviFi[φi(vi) | i = j]Pr[i = j]+EviFi[φi(vi) | i ̸= j]Pr[i ̸= j] CourseNana.COM

the same winner different winners CourseNana.COM

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., CourseNana.COM

APX EviFi[φi(vi) | i = j]Pr[i = j] (1) CourseNana.COM

APX EviFi[φi(vi) | i ̸= j]Pr[i ̸= j], (2) CourseNana.COM

from which it follows that 2APX OPT. CourseNana.COM

Get in Touch with Our Experts

WeChat WeChat
Whatsapp WhatsApp
Brown University代写,US代写,CSCI 1440代写,CSCI 2440代写,Introduction to Game Theory代写,Social Welfare代写,Sponsored Search Aucktion代写,Myersons Theorem代写,Brown University代编,US代编,CSCI 1440代编,CSCI 2440代编,Introduction to Game Theory代编,Social Welfare代编,Sponsored Search Aucktion代编,Myersons Theorem代编,Brown University代考,US代考,CSCI 1440代考,CSCI 2440代考,Introduction to Game Theory代考,Social Welfare代考,Sponsored Search Aucktion代考,Myersons Theorem代考,Brown Universityhelp,UShelp,CSCI 1440help,CSCI 2440help,Introduction to Game Theoryhelp,Social Welfarehelp,Sponsored Search Aucktionhelp,Myersons Theoremhelp,Brown University作业代写,US作业代写,CSCI 1440作业代写,CSCI 2440作业代写,Introduction to Game Theory作业代写,Social Welfare作业代写,Sponsored Search Aucktion作业代写,Myersons Theorem作业代写,Brown University编程代写,US编程代写,CSCI 1440编程代写,CSCI 2440编程代写,Introduction to Game Theory编程代写,Social Welfare编程代写,Sponsored Search Aucktion编程代写,Myersons Theorem编程代写,Brown Universityprogramming help,USprogramming help,CSCI 1440programming help,CSCI 2440programming help,Introduction to Game Theoryprogramming help,Social Welfareprogramming help,Sponsored Search Aucktionprogramming help,Myersons Theoremprogramming help,Brown Universityassignment help,USassignment help,CSCI 1440assignment help,CSCI 2440assignment help,Introduction to Game Theoryassignment help,Social Welfareassignment help,Sponsored Search Aucktionassignment help,Myersons Theoremassignment help,Brown Universitysolution,USsolution,CSCI 1440solution,CSCI 2440solution,Introduction to Game Theorysolution,Social Welfaresolution,Sponsored Search Aucktionsolution,Myersons Theoremsolution,