Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Problem Set 2

COMP3352 Algorithmic Game Theory (2022 Spring)

1.  (25 points)  Consider an auction with two bidders. Bidder 1’s value is uniformly distributed over [0, 2], and bidder 2’s value is uniformly distributed over [0 , 3].  (It is okay to submit answers in the forms of (1) mathematical calculations, (2) calculations done via websites such as WolframAlpha, or (3) solution given by a program that you write.)

(a)  (10 points) What is the expected revenue given by the 2nd-price auction?

(b)  (10 points) What is the revenue optimal auction?  How much revenue does it get in expectation?

(c)  (5 points) What is the best anonymous reserve price if we would like to run 2nd price auction with an anonymous reserve? How much revenue does it get in expectation?

2.  (25 points)  This problem considers variations on the Bulow-Klemperer theorem. Consider selling k  > 1 identical items (with at most one given to each bidder) to n bidders with valuations drawn i.i.d. from the uniform distribution over [2 , 4].

(a)  (10 points) What is the optimal auction and the corresponding optimal revenue?

(b)  (15 points)  Suppose that you are only allowed to run the 2nd-price auction, but with k additional bidders. Would the expected revenue be better or worse than running the optimal auction with n bidders? Why?

3.  (25 points)  Consider the following variant of k-item auctions with n bidders. Rather than having a fixed supply of k copies of the item, consider a soft supply constraint characterized by production costs.  Concretely, for any 1 < i < n, producing the i-th copy of the item costs ci  > 0; cl  < c2  < . . . < cn.  The social welfare is defined to be the sum of values of the bidders who get a copy of the item, minus the total production cost.  The revenue is defined to be the sum of payments collected from the bidders, minus the total production cost. The original k-item auction is the special case when ci  = 0 for 1 < i < k , and o for k < i < n.

(a)  (10 points)  Design a DSIC, welfare-maximizing auction.   Does your auction run in polynomial time?

(b)  (15 points) Further assume Bayesian priors Fi’s such that bidder i’s value is drawn from Fi.   Design  a DSIC, revenue-maximizing  auction.   Does your  auction run in polynomial time? (You may assume Fi’s are continuous distributions with well-defined densities on support [0, 1].)

4.  (25 points)  Consider three advertisers Alice, Bob, and Charlie and three impressions (e.g., user search queries). Further suppose that the platform can show two ads to each impression, and can show each advertiser’s ad at most twice. The advertisers’ values for each impression is given by the following table (note that an advertiser is not interested in having its ad shown twice to the same impression):

An advertiser’s value for two impressions is simply the sum of the corresponding values for individual impressions.

(a)  (10 points) Explain how the VCG mechanism would allocate two advertisers’ ads to each impression.

(b)  (15 points) What are the VCG payments?

(c)  (optional, 0 points)  Consider the general problem with n advertisers, m impressions. Each advertiser’s ad can be shown at most ka  times and each impression has ki  ad slots. Can VCG be implemented in polynomial time? Why or why not?

5.  (optional, 0 points)  This question explores an alternative approach for designing a 1 + ∈- approximate and DSIC knapsack auction. Consider n items; each item i has a value vi  > 0 and weight wi  > 0.  The capacity of the knapsack is W > 0.  We assume that wi  is public information while vi  is private.

(a)  Prove that if wi  < W for any item i, the greedy algorithm by efficiency is a 1 + ∈ approximation.

(b) What is the maximum number of items with weights larger than W that could have been chosen in the optimal solution?

(c)  Consider an algorithm that tries all possible decisions on the “large items” in part (b), and conditioned on the decisions on those items, runs greedy by efficiency to handle the “small items” in part (a). What is the approximation guarantee of this algorithm? What is its running time (asymptotically, as a function of n and )?

(d) Is the algorithm in part (c) monotone?  If so, give an argument; otherwise, could you propose a way to fix it?