Fall 2022: Social and Economic Networks.
Fall 2022: Social and Economic Networks.
Show all your work giving a final solution is not sufficient. Clearly define notation and explain all steps.
All answers must be your own work. Do not discuss the exam with anyone else, in or outside the class.
Question 1 (25 points)
Explain how and why (i) the first price sealed-bid auction is equivalent to a descending- bid (Dutch) auction and (ii) the second price sealed-bid auction is equivalent to an ascending bid (English) auction. (10 points)
Show that the VCG mechanism is equivalent to a second-price auction when it is used to auction a single item. (15 points)
Question 2 (20 points)
A painting is sold using an English (ascending-bid) auction. Let vi denote the maximum price bidder i is willing to pay for the painting. Let r denote the reserve price, below which the seller will not sell the painting. Let p denote the final selling price of the painting. If bidder i wins the auction, her payo is si = vi p; otherwise, the payo is zero.
Suppose a group of n 2 buyers colludes in the bidding. Their objective is to maximize the sum of the payos obtained by the n bidders. What bid should each of the n bidders submit? Why? Explain your answer. (10 points)
Now suppose that there is another group of m 2 bidders who also decide to collude and bid for the painting. How does the presence of this second group change the bidding for the n original bidders in part (a)? Explain. (10 points)
Question 3 (20 points)
A search engine can sell two ad slots. Slot A has a clickthrough rate of 0.03 and slot B has a clickthrough rate of 0.04. There are three advertisers who are interested in buying these slots. The value obtained per click is 10 for advertiser X, 40 for advertiser Y and 30 for advertiser Z.
Suppose that the search engine runs the VCG procedure to allocate slots. What are the slot assignments and the prices paid by the advertisers? Explain. (10 points)
The search engine can create a third ad slot, C, with a clickthrough rate of 0.02. What will be the assignment of slots and what prices will the advertisers pay if the search engine creates slot C and again uses the VCG procedure to allocate slots? Do you think the search engine should create slot C? (10 points)
Question 4 (20 points)
Suppose that you have n 3 identical tickets to the World Cup and that you want to sell them using the VCG procedure. You only accept separate bids for individual tickets. Suppose you receive m > n bids. Let bi denote the ith bid. Let b1 > b2 > . . . > bm. Calculate the VCG payment for each of the n winners. Explicitly show the steps in your calculations. In light of your answer, is there a better way for the seller to auction the tickets?
Question 5 (15 points + 15 extra credit points for part (c))
2516384177550
In the above graph, vertices 1 and 2 represent passengers and vertices A, B, C, D represent Uber cars. Each edge represents a feasible matching of a passenger to a car. Suppose passenger 1 is matched to car D. Call it a 1-D matching.
What type of matching is the 1-D matching: a maximal matching, a maximum matching or a perfect matching? Explain. (5 points)
Starting with the 1-D matching, find an augmenting path and use it to obtain an improved matching (show your work). What type of matching is this improved matching: a maximal matching, a maximum matching or a perfect matching? (10 points)
Consider the following algorithm for matching cars to passengers. (i) Randomly order the four cars; (ii) When a passenger arrives, match him/her to the highest-ranked car that is both feasible and available. For example, suppose all four cars are available. If passenger 1 arrives first, then he/she will be assigned the highest-ranked of the four cars. But if passenger 2 arrives before passenger 1, then he/she will be assigned car D regardless of its rank, because it is the only feasible car for passenger 2. Suppose Uber does not know whether passenger 1 or 2 will arrive first. What is the expected number of passengers it will match by using this algorithm? What are the strengths and weaknesses of the algorithm? (Extra credit: 15 points)
