关于算法:MATH4321游戏理论

MATH4321 Game Theory (2023 Spring)
Assignment 1
Submission deadline of Assignment 1: 11:59p.m. of 10th Mar, 2022 (Fri)
Instruction: Please complete all required problems. Full details (including (i)
description of methods used and explanation, (ii) key formula and theorem used
and (iii) calculation and final answer) must be shown clearly to receive full credits.
Please make sure that your work is clearly presented. Marks can be deducted for
incomplete solution or unclear solution. You may earn extra score by completing
some bonus problems. Also, additional score will be given for well-written
assignment.
Please submit your completed work via the submission system in canvas before the
deadline. Late assignment will not be accepted.
Your submission must
be 100% hand-written (typed assignment will not be accepted, you may write
on ipad if you wish)
in a single pdf. file (other file formats will not be accepted) and
contain your full name and student ID on the first page of the assignment.

Problem 1 (Required, 25 marks)
In a two-person games, each player can choose to submit one of the following requests
simultaneously without any communication:
Request 1: Give me $1,000
Request 2: Give other player $4,000.
We assume that the payoff function of a player is the total amount received by the
player after the games. Also, we assume that both players adopt pure strategy.
(a) Express the games in the normal form.
(b) Determine if there is any dominated strategy in this games. Determine the final
outcomes of the games.
(c) Verify that the final outcome obtained in (b) is the Nash equilibrium.

Problem 2 (Required, 25 marks)
The payoff matrix of a two-person games is given as follows:
Player 2
W X Y Z
Player 1 A (8,7) (6,6) (4,8) (2,8)
B (5,4) (10,9) (5,5) (3,6)
C (6,9) (5,4) (9,10) (7,3)
D (5,8) (4,7) (5,6) (6,4)
Assume that both players adopt pure strategy.
(a) Reduce the games using IESDS.
(b) Hence, find all possible Nash equilibrium of the games.
(c) Hence, find the Pareto-optimal equilibrium and the risk-dominant equilibrium.

Problem 3 (Required, 25 marks)
An employee (player 1) who works for a boss (player 2) can either work (W) or shirk (S),
while his boss can either monitor the employee (M) or ignore him (I). As in many
employee-boss relationships, if the employee is working then the boss prefers not to
monitor, but if the boss is not monitoring then the employee prefers to shirk. The game
can be represented by the following payoff matrix:

Player 2
Monitor (M) Ignore (I)
Player 1 Work (W) (1,1) (1,3)
Shirk (S) (0,2) (3,1)
Find all possible Nash equilibria (Pure strategy and Mixed strategy) of this games. Please
provide full justification to your answer.

Problem 4 (Required, 25 marks)
(a) We consider a -person games. Suppose that for any combination of opponents’
strategies , the pure strategy
∈ is the unique best response for
player . Show that any strategy other than
is the dominated strategy for
player .
(b) Recall that ∈ is dominated by some mixed strategy ∈ Δ if and only if.
Then we say is dominated strategy for player .
(i) As discussed in the lecture, it is sufficient to check the above inequality
holds for any rival’s pure strategy . Show that if is dominated
strategy, then we must have
for any rival’s mixed strategy ?.
(ii) Suppose that a pure strategy is dominated by a mixed strategy with
() > 0, show that is also dominated by another mixed strategy
′
with
′() = 0.
(iii) If ∈ is dominated by some mixed strategy , show that player
never choose under any mixed strategy Nash equilibrium
Bonus Problem 1 (Optional, 25 marks)
We consider a contribution games as follows: people in a company are working in a
business project. You are given that
Each person can choose either contribute (denoted by) or not contribute
(denoted by) in the project. The cost of contributing the project is > 0.
The project will be successful if at least people (where ≤) contributed to
the project.
If the project is successful, each member will get a payoff of + > 0, where
, are positive constant and denotes the number of people contributing the
project. If the project is not successful, each member will get nothing.

Assuming that the players adopted pure strategy,
(a) If + < , show that nobody will contribute under the Nash equilibrium.
(b) If + > , we let 0 be the smallest integer which + 0 > . Determine
all possible Nash equilibrium for this game.
(Hint: Since all players are symmetric (i.e. having same payoff and same payoff
function), so you can describe the Nash equilibrium by specifying the number of
people who will contribute to the project. On the other hand, you will need to
divide the analysis into several cases depending on the value of . Try to recall
my comments about the contributed games presented in the lecture.)

Bonus Problem 2 (Optional, 20 marks)
We consider the Cournot Duopoly games as discussed in Example 8. In this problem, we
shall explore the mathematical justification of the result obtained in the lecture note.
For = 1,2,3, …, we let = [,] denotes the strategic set of firm after
round
of IESDS. Recall that 0 = [0, ∞) and 1 = [22.5, 45] after the 1
st round of IESDS (i.e.
adjusting both upper bound and lower bound of the strategic set).
(a) Show that.
(b) Using mathematical induction, show that
22.5 ≤ ≤ ≤ 45.
(c) Show that
≤ +1 +1 ≤ .
(d) Hence, show that the sequences {} and {} converge and find their limits.
Based on this result, deduce the survivor(s) under IESDS.