联系我们： 手动添加方式: 微信>添加朋友>企业微信联系人>13262280223 或者 QQ: 1483266981

Please submit your solutions electronically (in PDF format) on Canvas.
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) Lemma 2.6 states, for indentical machines, ”Suppose task i makes a best
response: For all tasks j with wj ≥ wi, if j was satisfied before, it remains satisfied
after i’s best response.”
Show that this does not hold for the case of related machines. That is, construct a
counter-example showing that a best response of some task i with weight wi can make
a task j with weight wj > wi unsatisfied.
b. (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 running the LPT algorithm
gives a solution A for G that is optimal, i.e., cost(A) = opt(G).
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 x
d
(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_x005f work congestion game G with 4 players and linear latency functions, which is given by
the following graph:
1
models and examples 467

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 + 44 3×2
6×2 x + 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 tutorial 2, 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
(from 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 lower bound of 4/3, for the price of stability of undirected networks with
only two players.
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.
2
References
[1] N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani. Algorithmic Game Theory. Cam bridge University Press, 2007.