ETH Zu ̈rich Algorithmic Game Theory - Exercise Set 3: Nash equilibria and Congestion Game
Algorithmic Game Theory
Autumn 2021 Exercise Set 3
Exercise 1: (2+3+1 Points)
In this exercise, we adapt the definition of Price of Anarchy for cost-minimization games, to games with positive utilities in the natural way. Specifically, for ui(s) being the utility of player i in state s, the corresponding social welfare is the sum of all players utilities,
SW(s) = 
and the Price of Anarchy for pure Nash equilibria iswhere PNE is set of all pure Nash equilibria in the game, and S the set of all possible states as usual.
We also adapt the definition of (λ, μ)-smooth games as follows:
A game as above is called (λ, μ)-smooth if, for λ > 0 and μ ≥ 0, the inequality
≥ λSW (s∗) − μSW (s)
holds for any two states s∗, s ∈ S.
Note: The utilities are always strictly positive, ui(s) > 0 for all possible s ∈ S, where S = S1 × · · · × Sn are the possible states, with Si being the strategies available to player i.
Your task:
1. Prove the following result:
Theorem: If a game is (λ,μ)-smooth, then the Price of Anarchy for pure Nash equilibria satisfies
1+μ PoAPNE ≤ λ .
2. Use the previous theorem to show that the following game has P oAPNE ≤ n:
Technology game: There are n players and m different technologies available, where technology j has a quality parameter αj > 0. Each player must adopt one technology, and the more players adopt the same technology, the better it is for them: If nj players adopt technology j, then each of these players has utility αj · nj.
Theorem: If a game is (λ,μ)-smooth, then the Price of Anarchy for pure Nash equilibria satisfies
1+μ PoAPNE ≤ λ .
3. Show that the previous bound is tight, that is, PoAPNE ≥ n in some instances of technology games above.
Exercise 2: (6 Points) Nash’s Theorem states that every finite strategic game has a mixed Nash equilibrium. Prove this theorem for the special case in which we have only two players and each of them has only two strategies.
Note: Your proof should be elementary and self-contained (in particular, it should not rely on the general proof for arbitrary games, nor it should use the sophisticated arguments in the known proofs for the general case like e.g., Brouwer’s fixed point, etc.)
Exercise 3: (3 Points) Consider the class of congestion games with delay functions of the resources of the form dr(x) = arx + br with constant ar ≥ 0 and br any constant (possibly negative) such that dr(x) ≥ 0 for all integers x ≥ 1. Also set dr(0) = 0 as usual.
Show that the price of anarchy for pure Nash equilibria (PoAPNE) can be bigger than 5/2. (Hint: one possibility is to encode delays of the form dr(1) = dr(0) = 0 and dr(2) = M.)
Exercise 4: (6 Points) Prove that computing pure Nash equilibria in congestion games remains PLS-complete also when we restrict to affine delay functions. That is, for dr (x) = ar x + br with ar , br ≥ 0. (Note that the condition ar ≥ 0 and br ≥ 0 is important.)
