[SOLVED] Cs3333 game theory with computer science applications homework 2

Problem 1. [Cournot Competition] Consider two companies, say company 1 and company 2,
which produce identical products. In the Cournot model of competition, companies decide
the amount they produce and the market determines a price depending on the total amounts
of the products available in the market. The price is higher if the amount of the product is
smaller. Let ai(i = 1,2) ∈ [0,∞) denote the amount of the product produced by company i.
Assume that producing one unit of the product costs each company $1, and the sales price
per unit of the product is determined as [2−(a1 + a2)]+. Thus, the payoffs of company 1 and
company 2 are given by
u1(a1,a2) = a1[2−(a1 + a2)]+ − a1
u2(a1,a2) = a2[2−(a1 + a2)]+ − a2,
respectively. Fine a pure Nash Equilibrium for this game.Problem 2. [Bertrand Competition] The Bertrand model is an alternative to the Cournot
model of competition. In the Bertrand model, again we consider two companies only, but
now each company sets a price and the demand for the product is a function of the lower of
the two companies’ prices. More precisely, each company i sets a price pi
for the product.The demand for the product is a function of the prices as follows: if company i sets its price
lower than that of the other company, i.e., pi < p−i
, the demand for the product of company
i is given by f (pi) units, and the demand for the product of the other company is zero. If
pi = p−i
, then the demand is f (pi)/2 for both companies. Let ci be the cost for company i toproduct one unit of the product. Then, the payoff for company i is given by
ui(pi
,p−i) =



f (pi)(pi −ci) if pi < p−i
,
f (pi)(pi −ci)/2 if pi = p−i
0 otherwise,
show that when c1 = c2 = c, p1 = p2 = c is the unique NE.Problem 3. Consider the following Pigou network: show that the price of anarchy (POA)
when CB (x) is of the form ax2 +bx +c,a,b,c > 0 is upper bounded by 3
p
3
3
p
3−2
.Problem 4. Consider a graph with a set of nodes V and a set of edges E. Let ce denote the cost
of using edge e ∈ E. This graph is accessed by a set of players, where each player chooses to
occupy a set of edges. If there are fe players occupying an edge e, the cost to each such player
is ce
fe
. Let Ri be the set of edges occupied by player i. Then its cost is given by Ci (Ri
,R−i) =
P
e∈Ri
ce
fe (Ri
,R−i)
. A Nash equilibrium for this problem is a set ¡
Rˆ
1,…,Rˆ
n
¢
if there are n players
such that Ci
¡
Ri
,Rˆ−i
¢
≥ Ci
¡
Rˆ
i
,Rˆ−i
¢
,∀Ri
.Moreover, global optimal solution to this game is a
set ¡
R
∗
1
,…,R
∗
n
¢
such that P
i Ci
¡
R
∗
i
,R
∗
−i
¢
≤
P
i Ci (Ri
,R−i),∀(Ri
,R−i).
1. Show that P
i Ci (Ri
,R−i) =
P
e:fe (Ri
,R−i)≥1 ce .2. Show that there exists a Nash equilibrium ¡
Rˆ
1,…,Rˆ
n
¢
such that
X
i
Ci
¡
Rˆ
i
,Rˆ−i
¢
≤
µ
1+
1
2
+…+
1
n
¶X
i
Ci
¡
R
∗
i
,R
∗
−i
¢
Hint: Use the potential function used in the congestion game described in the class to classify
the Nash equilibrium of this game.Problem 5. (1) Use Rosen’s theorem to prove the following result: consider a zero-sum game,
where U2(a1,a2) = −U1(a1,a2). Assume U1 is strictly concave in a1, and strictly convex in a2.
Then there exists a unique SP and the SP is in pure strategies (Note: SP= saddle point); (2)
During the prove of Rosen’s theorem, Why did we have to define the functions L(v,a)?