01 May 1. (25 points) Prove that for any single-item auction, the VCG payment coincides
1. (25 points) Prove that for any single-item auction, the VCG payment coincides with the payment given by Myerson’s Lemma when the allocation rule always selects a welfaremaximizing outcome. (Further prove it for arbitrary single-parameter problems if you want a more challenging version.) 2. (25 points) Consider an auction with two bidders, where bidder 1’s value is uniformly distributed over [0,1], and bidder 2’s value is uniformly distributed over [0,2]. (a) (10 points) What is the revenue optimal auction? How much revenue does it get inexpectation? (b) (10 points) What is the best anonymous reserve price if we would like to run 2nd priceauction with an anonymous reserve? How much revenue does it get in expectation? (c) (5 points) What is the best reserve prices if we would like to run 2nd price auctionwith potentially different reserve prices for the two bidders? How much revenue does it get in expectation? 3. (25 points) Recall the problem of pricing one item in the sample complexity model, where we have m i.i.d. samples from the underlying value distribution and would like to price the item according to the samples to maximize the expected revenue from selling to a new buyer whose value is a fresh sample. Suppose we believe that the underlying distribution is “natural” in the sense that the optimal price sells to at least 50% of the time. (a) (15 points) How would you price the item (as an algorithm) based on samples? (b) (10 points) Suppose we want to guarantee a 1 approximation with probability at least 1 – , how many samples (asymptotically, e.g., )) do we need? Hint: Try to mimic the analysis in the slides. Note the difference in the assumptions on value distributions and make changes accordingly. 4. (25 + 10 points) Recall the 99% approximation allocation algorithm for knapsack auction, where b1,b2,…,bn are the values/bids and w1,w2,…,wn are the weights/sizes: 1. Let B = maxi bi be the largest value/bid. 2. Round all values down to the closest multiple of . 3. Find the optimal allocation w.r.t. the rounded values. Answer the following questions: (a) (25 points) Show the above algorithm is NOT monotone by constructing an examplein which a bidder is not picked by the algorithm if it bids truthfully, but would be picked if it underbids appropriately. (b) (bonus, 10 points) Propose a way to fix this non-monotonicity.
Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Fill in all the assignment paper details that are required in the order form with the standard information being the page count, deadline, academic level and type of paper. It is advisable to have this information at hand so that you can quickly fill in the necessary information needed in the form for the essay writer to be immediately assigned to your writing project. Make payment for the custom essay order to enable us to assign a suitable writer to your order. Payments are made through Paypal on a secured billing page. Finally, sit back and relax.
About Writedemy
We are a professional paper writing website. If you have searched a question and bumped into our website just know you are in the right place to get help in your coursework. We offer HIGH QUALITY & PLAGIARISM FREE Papers.
How It Works
To make an Order you only need to click on “Order Now” and we will direct you to our Order Page. Fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Are there Discounts?
All new clients are eligible for 20% off in their first Order. Our payment method is safe and secure.