COMP326 Assignment 1 (15% of the final grade)
Due: 12:00 on Thursday 18 March 2021
Please submit your solutions electronically (in PDF format) at the electronic submission system
of the Computer Science Department which you can find at the following url.
https://sam.csc.liv.ac.uk/COMP/Submissions.pl.
Please be aware of the University guidelines on plagiarism and collusion. The marks for late
submissions will be affected in accordance with the University’s Code of Practice on Assessment
published in Section 2.2 of the Postgraduate Student Handbook.
Total: 100 marks
1. Load Balancing Games: (20 marks)
a. (10 marks) Let G be any instance of the load balancing game with n = 3 tasks that
should be placed on m = 2 identical machines. Show that any pure Nash equilibrium
A for G is optimal, i.e., cost(A) = opt(G).
b. (10 marks) (Lower bound Theorem 2.7(a)). Show that, for every m, there exists an
instance G of the load balancing game with m identical machines and n = 2m tasks
that has a Nash equilibrium assignment A : [n] 7→ [m] with
cost(A) =
(
2− 2
m + 1
)
· opt(G)
Hint: Generalize the example with two machines given on slide 2.10.
2. Congestion Games: (50 marks)
a. Wardrop Model: (15 marks) Suppose that we modify Pigou’s example, so that the
costs of the two parallel edges to be 1 and xd (instead of 1 and x) for some d ≥ 1, as
given in the following graph.
What is the price of anarchy of the resulting selfish routing network as a function of d?
b. Atomic Weighted Congestions games: (15 marks) Consider the weighted net-
work congestion game G with 4 players and linear latency functions, which is given by
the following graph:
1
models and examples 467
s1
u
w
0
x
x
xx
0
s2
t1
t2 t3 s4
s3v t4
Figure 18.3. The AAE example (Example 18.6). In atomic instances with affine cost functions,
different equilibrium flows can have different costs, and the price of anarchy can be as large
as 5/2.
Example 18.7 (Nonexistence in weighted atomic instances) Consider the net-
work shown in Figure 18.4. Extend this network to an atomic selfish routing game
by adding two players, both with source s and sink t , with traffic amounts r1 = 1
and r2 = 2.
We claim that there is no equilibrium flow in this atomic instance. To prove
this, let P1, P2, P3, and P4 denote the paths s → t , s → v→ t , s → w→ t ,
and s → v→ w→ t , respectively. The following four statements then imply the
claim.
(1) If player 2 takes path P1 or P2, then the unique response by player 1 that minimizes
its cost is the path P4.
(2) If player 2 takes path P3 or P4, then the unique best response by player 1 is the
path P1.
(3) If player 1 takes the path P4, then the unique best response by player 2 is the
path P3.
(4) If player 1 takes the path P1, then the unique best response by player 2 is the
path P2.
We leave verification of (1)–(4) to the reader.
On the other hand, Section 18.3.2 proves that every atomic instance in which all
players route the same amount of traffic admits at least one equilibrium flow. We call
s t
w
v
47x
x2 + 443x2
6x2x + 33 13x
Figure 18.4. An atomic instance with no equilibrium flow (Example 18.7).
Each player i ∈ {1, 2, 3, 4} controls the pair si, ti and has weight wi. Find the weights
of the players so that the price of anarchy of the resulting weighted network congestion
game is exactly 3+
√
5
2 ≈ 2.618.
Hint: In Exercise 2 of the second tutorial, we computed the PoA of the same unweighted
network congestion game. The players had 2 strategies: a single arc and a 2-length
directed path (for instance, player 1 can either choose arc (u, v) or the directed path
(u,w, v). In the tutorial, we showed that it is a Nash equilibrium when all players use
their 2-length directed path. We denote this strategy profile by P . In the weighted
version of the game, P is a Nash equilibrium if and only if w1 = w2 and w3 = w4.
c. Atomic Unweighted Congestions games: (20 marks) Show that the Price of
Stability of unweighted congestion game with latencies of the form ce(x) = x is at most
2.
Hint: Use the Potential Function Method, which is Theorem 19.13 of [1]. By appro-
priately defining the parameters of this theorem, you will need to show that cost of the
potential minimizer is at most twice the optimal cost.
3. Global Connection Game: (30 marks) The lower bound construction illustrated in
figure 19.3 (b), page 495 of [1] shows that the price of stability is at least Hk for directed
networks, in the Global Connection Game of section 19.3.1.
• Explain why this example does not give a Hk lower bound for the price of stability
of undirected (where each edge can be used in both directions) networks.
• Provide a l wer bound of 4/3, for the pric of stabilit of undirected networks with
only two play r .
Hint: To show a lower bound for the Price of Stability it is a good idea to construct
a game which has a unique Nash equilibrium with as high cost as possible.
References
[1] N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani. Algorithmic Game Theory. Cam-
bridge University Press, 2007.
2

欢迎咨询51作业君