1. Homepage
  2. Homework
  3. CSCI 1440/2440 Introduction to Game Theory - Homework 7: Vickrey-Clarke-Groves Mechanism
This question has been solved

CSCI 1440/2440 Introduction to Game Theory - Homework 7: Vickrey-Clarke-Groves Mechanism

Engage in a Conversation
Brown UniversityUSCSCI 1440CSCI 2440Introduction to Game Theory Equal-Revenue DistributionVickrey AuctionPayment BoundsVCG mechanismVickrey-Clarke-Groves Mechanism

Homework 7: The Vickrey-Clarke-Groves Mechanism CSCI 1440/2440
2022
-03-24 CourseNana.COM

Due Date: Tuesday, April 12, 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 to solve the first five problems. For 2000-level credit, you should solve all six problems. CourseNana.COM

1 The Vickrey Auction: An Oldie but Goodie CourseNana.COM

Consider a single-good auction, and assume bidders’ values are drawn i.i.d. from a regular distribution F. Prove that the expected revenue of the Vickrey auction (second-price without a reserve) with n bidders, Vn, is at least n1/n times that of Myerson’s optimal auc- tion (second-price with the monopoly price as the reserve) with the same number of bidders. Hint: Use the Bulow-Klemperer Theorem itself, or a similar proof technique. CourseNana.COM

2 Payment Bounds CourseNana.COM

The VCG mechanism collects (possibly misleading) reports from all bidders and then computes a welfare-maximizing allocation ωtogether with corresponding payments pi(ω), which ensure that a dominant strategy comprises truthful reports. CourseNana.COM

Prove that, for all bidders i ∈ I,
1. VCG payments p
i(ω) are lower-bounded by 0.
2. VCG payments p
i(ω) are upper-bounded by vi(ω). CourseNana.COM

3 Revenue CourseNana.COM

This problem asks you to construct examples of multiparameter auctions, by which we mean you should specify 1. a set of goods, and 2. each bidder’s valuation. Let Rev(I) be the revenue generated by the VCG mechanism, given a set of bidders I. CourseNana.COM

1. Show, by example, that the following is possible: Rev(I \ {i}) > Rev(I), for some i ∈ I. CourseNana.COM

2. Construct a non-trivial example of a multiparameter auction in which the VCG mechanism yields Rev(I) = 0. (By non-trivial, we mean that each bidder’s valuation should be non-negative for every outcome and strictly positive for at least one outcome, and the number of bidders should exceed 1.) CourseNana.COM

4 Collusion CourseNana.COM

This problem highlights two shortcomings of the VCG mechanism. CourseNana.COM

1. Show that, when the VCG mechanism is used, it is possible for two bidders not to be allocated anything when bidding truthfully, but for one or both of them to obtain strictly positive utility if they tacitly collude, by both submitting untruthful reports. CourseNana.COM

2. Suppose that a single bidder submits multiple false bids to a VCG mechanism. That is, the auctioneer thinks there are n distinct bidders, but in reality, at least two of the n bids are submitted by a single bidder i. Show that a bidder can obtain strictly higher utility by submitting multiple false bids rather than one truthful bid. CourseNana.COM

5 Ties CourseNana.COM

The outcome, namely the allocation and payments, of a VCG mech- anism depends on the solution to welfare-maximization problem, which may not be unique. Multiple optima would not impact the welfare, as if one of them yielded lower welfare it would not be welfare-maximizing! But a question arises as to whether the choice of welfare-maximizing solution (i.e., allocation) on which the outcome (i.e., payments) depend impacts revenue. CourseNana.COM

It turns out that the revenue earned in a VCG mechanism also does not depend on the choice of welfare-maximizing allocation. Prove this claim in the case of 2 goods and 2 bidders. CourseNana.COM

6 Unit Demand CourseNana.COM

A unit-demand valuation is one in which bidders value a bundle based on only the value of their favorite good in the bundle. More formally, let S denote the set of goods, and let vij represent bidder i’s value for good j S. If bidder i has unit demand, then CourseNana.COM

vi(S) = max vij, S G. (1) jS CourseNana.COM

Prove that the VCG mechanism can be run in time polynomial in the number of bidders and goods, assuming unit-demand valuations. CourseNana.COM

In other words, prove that the allocation problem can be solved in polynomial time in this special case. CourseNana.COM

  CourseNana.COM

Get in Touch with Our Experts

WeChat WeChat
Whatsapp WhatsApp
Brown University代写,US代写,CSCI 1440代写,CSCI 2440代写,Introduction to Game Theory代写, Equal-Revenue Distribution代写,Vickrey Auction代写,Payment Bounds代写,VCG mechanism代写,Vickrey-Clarke-Groves Mechanism代写,Brown University代编,US代编,CSCI 1440代编,CSCI 2440代编,Introduction to Game Theory代编, Equal-Revenue Distribution代编,Vickrey Auction代编,Payment Bounds代编,VCG mechanism代编,Vickrey-Clarke-Groves Mechanism代编,Brown University代考,US代考,CSCI 1440代考,CSCI 2440代考,Introduction to Game Theory代考, Equal-Revenue Distribution代考,Vickrey Auction代考,Payment Bounds代考,VCG mechanism代考,Vickrey-Clarke-Groves Mechanism代考,Brown Universityhelp,UShelp,CSCI 1440help,CSCI 2440help,Introduction to Game Theoryhelp, Equal-Revenue Distributionhelp,Vickrey Auctionhelp,Payment Boundshelp,VCG mechanismhelp,Vickrey-Clarke-Groves Mechanismhelp,Brown University作业代写,US作业代写,CSCI 1440作业代写,CSCI 2440作业代写,Introduction to Game Theory作业代写, Equal-Revenue Distribution作业代写,Vickrey Auction作业代写,Payment Bounds作业代写,VCG mechanism作业代写,Vickrey-Clarke-Groves Mechanism作业代写,Brown University编程代写,US编程代写,CSCI 1440编程代写,CSCI 2440编程代写,Introduction to Game Theory编程代写, Equal-Revenue Distribution编程代写,Vickrey Auction编程代写,Payment Bounds编程代写,VCG mechanism编程代写,Vickrey-Clarke-Groves Mechanism编程代写,Brown Universityprogramming help,USprogramming help,CSCI 1440programming help,CSCI 2440programming help,Introduction to Game Theoryprogramming help, Equal-Revenue Distributionprogramming help,Vickrey Auctionprogramming help,Payment Boundsprogramming help,VCG mechanismprogramming help,Vickrey-Clarke-Groves Mechanismprogramming help,Brown Universityassignment help,USassignment help,CSCI 1440assignment help,CSCI 2440assignment help,Introduction to Game Theoryassignment help, Equal-Revenue Distributionassignment help,Vickrey Auctionassignment help,Payment Boundsassignment help,VCG mechanismassignment help,Vickrey-Clarke-Groves Mechanismassignment help,Brown Universitysolution,USsolution,CSCI 1440solution,CSCI 2440solution,Introduction to Game Theorysolution, Equal-Revenue Distributionsolution,Vickrey Auctionsolution,Payment Boundssolution,VCG mechanismsolution,Vickrey-Clarke-Groves Mechanismsolution,