Four bidders 1 2 3 and 4 bid for three items i1 i2 and i3

Question

Q1. There are two firms 1 and 2, both producing the same kind of product. Firm i has two possible unit cost c_i^H and c_i^L, where c_i^H ≥ c_i^L > 0. Assuming that firm i produces q_i units of the product and firm i's unit cost is c_i ∈ {c_i^H, c_i^L}, i =1, 2, then the payoff of firm i is

u_i(q₁,c₁,q₂,c₂) = (120 - q₁ - q₂ - c_i) x q_i.

Assume that c₁^H = 40, c₁^L = 40, c₂^H = 60, c₂^L = 20. Answer the following questions.

• Assume that firm 1 knows that firm 2 will choose c₂ = c₂^H. If both firms will simultaneously decide on the number of units to produce where firm i produces q_i units of the product, what are the values of q₁ and q₂ that will form a Nash equilibrium? You need to show the derivations and the result.
• Assume that firm 1 knows that firm 2 will choose c₂ = c₂^H with probability 1/3, and choose c₂ = c₂^L with probability 2/3. If both firms will simultaneously decide on the number of units to produce where firm 1 produces q₁ units, and firm 2 produces q₂^H (q₂^L, respectively) units when its unit cost c₂ is c₂^H (c₂^L, respectively), what are the values of q₁, q₂^H and q₂^L that will form a Nash equilibrium? You need to show the derivations and the result.

Q2. Four bidders 1, 2, 3, and 4 bid for three items I₁, I₂, and I₃ using VCG auction. We use w_jk to denote bidder j's value for item k. Assume that w₁₁ = 300, w₁₂ = 200, w₁₃ = 100; w₂₁ = 310, w₂₂ = 210, w₂₃ = 110; w₃₁ = 320, w₃₂ = 220, w₃₃ = 120; w₄₁ = 330, w₄₂ = 230, w₄₃ = 130. Answer the following questions.

• Which bidders are the winners in this auction? For each winning bidder, which item does it win?
• What is the payment for each winning bidder?

Q3. This question is concerned with the paper, "Routing in Max-min Fair Networks: A Game Theoretic Approach", discussed in class (ICNP'2010).

• Did the paper prove the existence of a Nash equilibrium?
• Does the game have a unique Nash equilibrium?
• In your view, what is the major contribution of this paper?
• In your view, what is the major weakness of this paper?

Q4. This question is concerned with the paper, "Crowdsourcing to Smartphones: Incentive Mechanism Design for Mobile Phone Sensing", discussed in class (MobiCom'2012).

• Did the paper prove the existence of a Stackelberg equilibrium?
• Does the game have a unique Stackelberg equilibrium?
• Is the auction designed in this paper a single auction or a double auction?
• Does the auction guarantee that the number of winners is greater than zero?