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

Problem Set 1

COMP3352 Algorithmic Game Theory (2022 Spring)

1.  (25 points) In the MCU, Loki agreed to help the Time Variance Authority to catch Sylvie, a variant of Loki who was attacking the sacred timeline. Being able to travel through time and space, Sylvie can hide herself in one of two apocalyptic events, Pompeii during the eruption of Mount Vesuvius in AD 79, or Lamentis-1 in 2077 which is doomed to crash with a planet. If both Loki and Sylvie chose the same apocalyptic event, Loki would catch Sylvie. Otherwise, Sylvie would escape.

(a)  (10 points)  Model the above story as a two-player normal form game by giving the utility matrix.

(b)  (5 points) Is there a strictly dominant strategy for Loki or Sylvie? Why or why not?

(c)  (10 points) Find a (mixed) Nash equilibrium of this game.

2.  (25 points)  Consider two firms A, B that make the same product at unit cost c > 0.  If qA , qB   < 0 are the quantities of product made by firms A and B respectively, then the market unit price for the product would be p = a - b(qA + qB ) for some coefficient a, b > 0. The firms’ profits would be (p - c)qA  and (p - c)qB . Find a Nash equilibrium of this game.

3.  (25 points)  Consider an auction of one item with two bidders, Alice and Bob. Suppose the seller decides to give Alice an competitive advantage in the sense that Alice gets the item as long as her bid is at least (1) Bob’s bid minus $20 and (2) $5, whichever is larger; otherwise, Bob gets the item provided that his bid is at least $5.

(a)  (10 points)  Prove that the allocation rule is implementable.

(b)  (15 points)  Provide a payment rule that makes the auction DSIC.

4.  (25 points)  Suppose that the government needs to purchase n doses of vaccines from m firms.  Each firm i has a private unit cost ci  > 0, and can supply at most si  doses (public information). You may assume that > si  < n. The government will make the purchase through a (reverse) auction so that it will purchase from the firms with lowest costs (but the payments may not equal the costs in general).  First, the firms will submit their bids b1 , . . . , bm.  Then, with some allocation rule x and payment rule p, the government will purchase 0  ≤ xi(b1 , . . . , bm)  ≤ si  doses from each firm i, and will pay it pi(b1 , . . . , bm). Firm i’s utility/profit is then pi - xici. The auction is DSIC if a firm can always ensure a non-negative utility, and can always maximize its utility by bidding its cost, regardless of what other firms bid.

(a)  (7 points)  Prove that an allocation rule x is implementable (i.e., there exists a payment rule that makes it DSIC) if and only if xi  is non-increasing in bi  for any firm i.

(b)  (8 points) Explain what the corresponding payment rule should be.

(c)  (10 points)  Design an auction that (1) is DSIC, (2) minimizes the total cost of the n doses (a.k.a., the social cost), and (3) runs in polynomial time.