1. Homepage
  2. Homework
  3. Stat155 Game Theory - Homework 1: Incentive Problems, Nash equilibrium and Auctions
This question has been solved

Stat155 Game Theory - Homework 1: Incentive Problems, Nash equilibrium and Auctions

Engage in a Conversation
Algorithmic Game TheoryMechanism Design BasicsSingle-Item AuctionsFirst-Price AuctionsSecond-Price AuctionsSponsored Search AuctionsStat155UC BerkeyleyIncentive ProblemsNash equilibrium

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

1.     (a)  A description of the system, detailed enough that you can express clearly the incentive problems and your solutions for them. CourseNana.COM

2.     (b)  Anecdotal or demonstrated evidence that participants are gaming the system in undesirable ways. CourseNana.COM

3.     (c)  A convincing argument why your proposed changes would reduce or eliminate the strategic behavior that you identified. CourseNana.COM

  CourseNana.COM

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

  CourseNana.COM

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

[Auctions of this type are called procurement or reverse auctions.] CourseNana.COM

  CourseNana.COM

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

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

  CourseNana.COM

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


CourseNana.COM

                Online Single-Item Auction CourseNana.COM

  CourseNana.COM

For each bidder arrival i = 1,2,...,n: CourseNana.COM

    if the item has not been sold in a previous CourseNana.COM

      iteration, formulate a price pi and then accept a CourseNana.COM

      bid bi from bidder i CourseNana.COM

    if pi bi, then the item is sold to bidder i at the CourseNana.COM

      price pi; otherwise, bidder i departs and the item CourseNana.COM

      remains unsold CourseNana.COM

(a)  Prove that an auction of this form is DSIC. CourseNana.COM

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

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

  CourseNana.COM

Get in Touch with Our Experts

WeChat WeChat
Whatsapp WhatsApp
Algorithmic Game Theory代写,Mechanism Design Basics代写,Single-Item Auctions代写,First-Price Auctions代写,Second-Price Auctions代写,Sponsored Search Auctions代写,Stat155代写,UC Berkeyley代写,Incentive Problems代写,Nash equilibrium代写,Algorithmic Game Theory代编,Mechanism Design Basics代编,Single-Item Auctions代编,First-Price Auctions代编,Second-Price Auctions代编,Sponsored Search Auctions代编,Stat155代编,UC Berkeyley代编,Incentive Problems代编,Nash equilibrium代编,Algorithmic Game Theory代考,Mechanism Design Basics代考,Single-Item Auctions代考,First-Price Auctions代考,Second-Price Auctions代考,Sponsored Search Auctions代考,Stat155代考,UC Berkeyley代考,Incentive Problems代考,Nash equilibrium代考,Algorithmic Game Theoryhelp,Mechanism Design Basicshelp,Single-Item Auctionshelp,First-Price Auctionshelp,Second-Price Auctionshelp,Sponsored Search Auctionshelp,Stat155help,UC Berkeyleyhelp,Incentive Problemshelp,Nash equilibriumhelp,Algorithmic Game Theory作业代写,Mechanism Design Basics作业代写,Single-Item Auctions作业代写,First-Price Auctions作业代写,Second-Price Auctions作业代写,Sponsored Search Auctions作业代写,Stat155作业代写,UC Berkeyley作业代写,Incentive Problems作业代写,Nash equilibrium作业代写,Algorithmic Game Theory编程代写,Mechanism Design Basics编程代写,Single-Item Auctions编程代写,First-Price Auctions编程代写,Second-Price Auctions编程代写,Sponsored Search Auctions编程代写,Stat155编程代写,UC Berkeyley编程代写,Incentive Problems编程代写,Nash equilibrium编程代写,Algorithmic Game Theoryprogramming help,Mechanism Design Basicsprogramming help,Single-Item Auctionsprogramming help,First-Price Auctionsprogramming help,Second-Price Auctionsprogramming help,Sponsored Search Auctionsprogramming help,Stat155programming help,UC Berkeyleyprogramming help,Incentive Problemsprogramming help,Nash equilibriumprogramming help,Algorithmic Game Theoryassignment help,Mechanism Design Basicsassignment help,Single-Item Auctionsassignment help,First-Price Auctionsassignment help,Second-Price Auctionsassignment help,Sponsored Search Auctionsassignment help,Stat155assignment help,UC Berkeyleyassignment help,Incentive Problemsassignment help,Nash equilibriumassignment help,Algorithmic Game Theorysolution,Mechanism Design Basicssolution,Single-Item Auctionssolution,First-Price Auctionssolution,Second-Price Auctionssolution,Sponsored Search Auctionssolution,Stat155solution,UC Berkeyleysolution,Incentive Problemssolution,Nash equilibriumsolution,