1. Art and Diseño

NETS 412: Algorithmic Game Theory
January 22+27, 2015
Lecture 3 and 4
Lecturer: Aaron Roth
Scribe: Aaron Roth
Congestion Games
In general, to represent an n player game in which each player has k actions, we need k n numbers just
to encode the utility functions. Clearly, for even moderately large k and n, nobody could be expected
to understand, let alone play rationally, in such a game. Hence, we will generally think about games
that have substantially more structure – despite being large, they have a concise description that makes
them easy to reason about.
In this lecture, we will think about congestion games. It will be convenient to think of players as
having cost functions rather than utility functions. Players want to minimize their cost, rather than
maximize their utility – but if you like, you can define their utility functions to be the negation of their
cost functions.
Definition 1 A congestion game is defined by:
1. A set of n players P
2. A set of m facilities F
3. For each player i, a set of actions Ai . Each action ai ∈ Ai represents a subset of the facilities:
ai ⊆ F .
4. For each facility j ∈ F , a cost function `j : {0, . . . , n} → R≥0 . `j (k) represents “the cost of facility
j when k players are using it”.
Player costs are then defined as follows. For action profile a = (a1 , . . . , an ) define nj (a) = |{i : j ∈ ai }|
to be the number of players using facility j. Then the cost of agent i is:
X
ci (a) =
`j (nj (a))
j∈ai
i.e. the total cost of the facilities she is using.
Example 1 In class we gave examples of a network routing game and a network creation game. Both
are defined over a graph G = (V, E), with facilities F = E, and each Ai corresponding to some set of
si ti paths in the graph. In general, in a network routing game we think of the cost of each edge as
increasing with k (i.e. usage causes congestion). In contrast, in a network creation game, we think of
the cost of an edge as being split between the users of that edge (who share the cost to construct the edge)
– for example, we could have `j (k) = wj /k, where wj is the construction cost of edge j.
Ok – so congestion games define an interesting class of n player, many action games that nevertheless
have a simple structure and concise representation. What can we say about them? Do they have pure
strategy Nash equilibria? Can we find those equilibria efficiently? Would agents, interacting together in
a decentralized way naturally find said equilibria?
Note that the more of these questions we can answer “yes”, the more we can be comfortable with
treating “pure strategy Nash equilibria” as reasonable predictions for what rational players should end
up doing in a congestion game.
To answer many of these questions, we will consider “Best response dynamics”. We present it as an
algorithm, but you could equally well think about it as a natural model for how people would actually
behave in a game. The basic idea is this: we start with players playing an arbitrary set of actions.
Then, in arbitrary order, they take turns changing their actions so that they are best responding to their
opponents. We continue until (if?) this process converges.
We first make a simple observation:
3 and 4-1
Algorithm 1 Best Response Dynamics
Initialize a = (a1 , . . . , an ) to be an arbitrary action profile.
while There exists i such that ai 6∈ arg mina∈Ai ci (a, a−i ) do
Set ai = arg mina∈Ai ci (a, a−i )
end while
Halt and return a.
Claim 2 If best response dynamics halts, it returns a pure strategy Nash equilibrium.
Proof Immediate from halting condition – by definition, every player must be playing a best response.
Of course, it won’t always halt – consider matching pennies – but what the above claim means is that
to prove the existence of pure strategy Nash equilibria in congestion games, it suffices to analyze the
above algorithm and prove that it always halts.
Theorem 3 Best response dynamics always halt in congestion games.
Corollary 4 All congestion games have at least one pure strategy Nash equilibrium.
Proof
We will study the following potential function φ : A → R defined as follows:
φ(a) =
j (a)
m nX
X
`j (k)
j=1 k=1
(Note that the potential function is not social welfare). Now consider how the potential function changes
in a single round of best response dynamics, when player i switches from playing some action ai ∈ Ai
to playing bi ∈ Ai instead.
First, because this was a step of best response dynamics, we know that the switch decreased player
i’s cost:
∆ci
≡ ci (bi , a−i ) − ci (ai , a−i )
X
X
=
`j (nj (a) + 1) −
`j (nj (s))
j∈bi \ai
j∈ai \bi
< 0
The change in potential is:
∆φ
≡ φ(bi , a−i ) − φ(ai , a−i )
X
X
=
`j (nj (a) + 1) −
`j (nj (s))
j∈bi \ai
=
j∈ai \bi
∆ci
Hence, we know that ∆φ < 0. But since φ can take on only finitely many different values (why?)
and decreases between each round of best response dynamics, best response dynamics must eventually
halt (and hence output a pure strategy Nash equilibrium).
Of course, we have only proven convergence, not fast convergence. It might take a long time, and if
it takes an unreasonably long time (say exponentially many rounds in the number of players), then it
might not be a reasonable prediction to assert that rational players will play a Nash equilibrium.
Bad news: it might take a really long time for best response dynamics to converge! But we will be
able to say that they converge quickly to an approximate Nash equilibrium.
3 and 4-2
Definition 5 An action profile a ∈ A is an -approximate pure strategy Nash equilibrium if for every
player i, and for every action a0i ∈ Ai :
ci (ai , a−i ) ≤ ci (ai , a−i ) + i.e. nobody can gain more than by deviating.
.
Lets consider a modification of best response dynamics that only has people move if they can decrease
their cost by at least :
Algorithm 2 FindApproxNash()
Initialize a = (a1 , . . . , an ) to be an arbitrary action profile.
while There exists i, a0i such that ci (a0i , a−i ) ≤ ci (ai , a−i ) − do
Set ai = arg mina∈Ai ci (a, a−i )
end while
Halt and return a.
Claim 6 If FindApproxNash() halts, it returns an -approximate pure strategy Nash equilibrium
Proof
Immediately, by definition.
Theorem 7 In any congestion game, FindApproxNash() halts after at most:
n · m · cmax
steps, where cmax = maxj,k `j (k) is the maximum facility cost.
Proof We revisit the potential function φ. Recall that ∆ci = ∆φ on any round when player I moves.
Observe also that at every round, φ ≥ 0, and
φ(a) =
j (a)
m nX
X
cj (k) ≤ n · m · cmax
j=1 k=1
By definition of the algorithm, we have ∆ci = ∆φ ≤ − at every round, and so the theorem follows.
What if we want to efficiently find exact Nash equilibria in congestion games? As we will see, we are
out of luck in general, but we can do it in a symmetric network routing game.
Definition 8 A symmetric network routing game is a congestion game defined by a graph G = (V, E)
and a fixed source/sink pair s and t. F = E, and Ai = {s → t paths in G} for each player i.
Theorem 9 There is a polynomial time algorithm to find pure strategy Nash equilibria in symmetric
network congestion games.
Proof We reduce the problem of computing Nash equilibria in such games to the min-cost flow
problem in graphs, and rely on the fact that there are polynomial time algorithms for solving min-cost
flow problems.
For each edge e ∈ E with costs `e (1), . . . , `e (n), we replace e with n parallel edges, each with capacity
1 and edge costs `e (1), . . . , `e (n) respectively.
We can find the integral min-cost flow in polynomial time. Note that this flow corresponds to an
action vector a, whose cost is φ(a). Hence, the min-cost flow corresponds to an action vector which
minimizes the potential function, and so must be a pure strategy Nash equilibrium.
3 and 4-3
0.1
Hardness of Computing Nash equilibria in General Congestion Games
We have seen that in any congestion game we can efficiently compute an approximate Nash equilibrium,
and that we can compute exact Nash equilibria in symmetric congestion games. Unfortunately, here
we show that in general congestion games, computing exact Nash equilibria is hard. First we need to
introduce a couple of concepts related to local optimization. (Note we want to show that finding a pure
strategy Nash equilibrium is hard, but the natural corresponding decision problem “Does there exist a
pure strategy Nash equilibrium” is easy – the answer is always yes. So we should not hope to show that
this problem is NP hard.)
Definition 10 An optimization (minimization) problem is defined by:
1. A set of instances I (e.g. all graphs)
2. A set of feasible solutions F (x) for each x ∈ I (i.e. TSP tours), and a cost function cx (s) : F (x) →
R≥0 . The set of feasible solutions and cost functions should be polynomial time computable.
The problem, given an instance x ∈ I is to find: s ∈ arg mins∈F (x) cx (s).
In contrast, a local optimization problem defines a neighborhood around each solution, and only asks
to find a local optimum with respect
Definition 11 A local optimization problem is an optimization problem, together with a neighborhood
Nx (s) ⊆ F (x) for each s ∈ F (x) (e.g. TSP tours differing in 2 edges). The problem is to find a locally
optimal solution:
s : cx (s) ≤ min cx (s)
x∈Nx (s)
Definition 12 A local optimization problem is in P LS if there exists a polynomial time algorithm such
that for every x ∈ I and s ∈ F (x) can determine whether s is locally optimal, and if not, returns an
s0 ∈ Nx (s) with cx (s0 ) < cx (s).
Definition 13 A problem is P LS-complete if it is in P LS all other problems in P LS reduce to it in
polynomial time.
Example 2 (Weighted SAT) Given: A CNF formula defined over k boolean variables x1 , . . . , xk ∈
{T, F }: C1 ∧ . . . ∧ Cn (e.g. (x1 ∨ x
¯2 ∨ x3 ) ∧ (x1 ∨ x
¯5 ) ∧ . . .) together with a weight wi for each clause Ci .
Feasible solutions are truth assignments, and the cost of a solution s is:
X
Cx (s) =
wi
i∈x:Ci is unsatisfied by s
The neighborhood of s is the set of all truth assignments that result from flipping a single variable.
Theorem 14 Weighted SAT is PLS complete. (read: strongly conjectured not to have a polynomial
time algorithm)
Theorem 15 The problem of finding a pure strategy Nash equilibrium in a congestion game is PLS
complete.
Proof Recall that the equilibria of congestion games correspond exactly to the local minima of the
potential function φ. Hence, the problem is in PLS (with the local neighborhood of an action profile
corresponding to the set of profiles resulting from unilateral agent deviations). To show completeness,
we reduce from Weighted-SAT:
Given a SAT instance with variables x1 , . . . , xk and clauses C1 , . . . , Cn , we define a congestion game
as follows:
3 and 4-4
• Players P = {x1 , . . . , xk }
• F = {C1 , . . . , Cn }
• For each i ∈ P , Ai = {Si , S¯i } where Si = {Ci : xi ∈ Ci }, S¯i = {Ci : x
¯ i ∈ Ci }
The intended semantics are that picking action Si corresponds to setting xi = F and picking action
S¯i corresponds to setting xi = T .
For each clause Cj with kj literals, set `j (k) = 0 for k < kj , `j (kj ) = wj .
It remains to show that under this reduction, local minima of φ correspond to local minima in the
weighted SAT instance. The key observation is that any unsatisfied clause Cj has kj players using it.
φ(S)
=
=
j (S)
n nX
X
`j (k)
j=1 k=1
n
X
`j (nj (S))
j=1
=
X
j:Cj is unsatisfied in S
which completes the proof.
3 and 4-5
wj