NAME STUDENT ID NUMBER SIGNATURE
DATE: Monday, 14 December 2020
MODULE: COMP323
ASSIGNMENT: Class Test 2
EXAMINER: Prof. Paul G. Spirakis
The class test is held online and will account for 15% of your final mark.
EXERCISE 1.(30%) We consider the case of selfish load balancing where the available machines have speeds.
The LPT rule for placing the tasks is as follows:
“Insert the tasks in a nonincreasing order of weights; each task is assigned to a machine that minimizes the
cost of the task at its insertion time.”
It is known that this rule produces a pure Nash equilibrium assignment of tasks.
As an application, we are given two machines, M1,M2, with speeds s1 = 2 and s2 = 3. We are also given
tasks 1, 2, 3, 4, 5 with weights w1 = 6, w2 = 12, w3 = 18, w4 = 24, w5 = 30, respectively.
(a) (25%) For each task, find the machine in which the task goes (by applying the LPT) and justify why below.
Task . . . . . . goes to machine . . . . . ..
Explanation:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Task . . . . . . goes to machine . . . . . ..
Explanation:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Task . . . . . . goes to machine . . . . . ..
Explanation:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Task . . . . . . goes to machine . . . . . ..
Explanation:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Task . . . . . . goes to machine . . . . . ..
Explanation:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(b) (5%) Find the makespan (cost) of the pure Nash equilibrium produced by the LPT rule and fill in the
answer below.
The makespan (cost) of the pure Nash equilibrium produced by the LPT rule is . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
EXERCISE 2.(30%) Consider the following network congestion game. There are 7 cars that wish to go from
A to B as shown in the figure below. There are two possible roads for each car, road 1 (the upper), and road
2 (the bottom), as shown in the Figure. Each road has a delay function (determines the delay per car) which
is a function of the number of cars taking that road. For example, if 5 cars use road 2, then the delay per car
in that road is 52 = 25. An allocation pi of cars is a split of the 7 cars to two disjoint populations σ1(pi), σ2(pi)
so that population σi(pi) uses the i
th road.
A B
d2(x) = x
2
d1(x) = x
For this congestion game instance, the Rosenthal Potential under an allocation pi is:
Φ(pi) =
2∑
i=1
σi(pi)∑
k=1
di(k), where di(k) is the delay of the i
th road when k players use it, and σi(pi) is the total
number of players that use road i under allocation pi.
Given that
∑n
x=1 x =
n(n+1)
2 and
∑n
x=1 x
2 = n(n+1)(2n+1)6 :
(a) (10%) If all cars use road 1, find the Rosenthal Potential value of the game in that situation.
(b) (10%) Find a pure Nash equilibrium of the game (hint: you can use the Rosenthal Potential).
(c) (10%) Justify your answer to (b).
EXERCISE 3.(20%) Consider the following extensive form game of two players with perfect information.
When the game starts, player 1 has two available actions, namely A and B. If she chooses B then the game
ends, while if she chooses A then player 2 plays. If player 2 chooses D then the game ends, while if she chooses
C then player 1 chooses either E or F . After this move the game ends. In the following tree the payoffs for the
two players are shown for each terminal history; the leftmost is player 1’s payoff, and the rightmost is player
2’s payoff.
(a) (10%) Find all subgame perfect equilibria of the game.
(b) (10%) Justify your answer to (a).
1
2
1
(1, 1)
E
(2, 2)
F
C
(6, 4)
D
A
(5, 6)
B
EXERCISE 4.(20%) Suppose that we have a second-price sealed bid auction of 3 players 1, 2, 3 and a single
item. Let vi be the valuation of player i for the item, and suppose that v1 = 30, v2 = 20, and v3 = 5. Let
(b1, b2, b3) be an action profile where player i bids bi. In case more than one bids are maximum, the item goes
to the player with the smallest index.
(a) (10%) Give a profile that is a Nash equilibrium, where player 3 wins the item.