Algorithmic Game Theory and Applications
Lecture 16: Selfish Network Routing, Congestion Games, and the Price of Anarchy
Kousha Etessami
Copyright By PowCoder代写 加微信 powcoder
games and the internet
Basic idea: “The internet is a huge experiment in interaction between agents (both human and automated)”.
Such interactions can profitably be viewed from a game theoretic viewpoint: agents trying to maximize their own payoffs, etc.
What are the implications of selfish behavior?
How do we set up the rules of these games to harness “socially optimal” results?
(Selfish) Network Routing as a Game
Figure: “The Internet”
Selfish agent i = 1, 2, 3, wants to route packets from Si to
Ti. So agent i must choose a directed path from Si to Ti. The delay on each edge of the path is governed by the congestion of that edge, i.e., the total number of agents using that edge in their path.
Agents can change their choice to decrease their delay.
What is a in this game? What are the welfare properties of such an NE? (Is it socially optimal? If not, how bad can it be?)
Congestion Games ([Rosenthal,1973])
A Congestion Game, G = (N,R,(Zi)i∈N,(dr)r∈R) has:
A finite set N = {1,…,n} of players.
A finite set of R = {1,…,m} of resources.
For each player, i , a set Zi ⊆ 2R , of admissible strategies for player i. So a pure strategy, si ∈ Zi is a set of resources. Eachresourcer∈Rhasacostfunction:dr :N→Z. Intuitively, dr(j) is the cost of using resource r if there are j agents simultaneously using r.
For a pure strategy profile s = (s1, . . . , sn) ∈ Z1 × . . . Zn, the congestion on resource r is: nr (s) =. |{i | r ∈ si }|.
Under strategy profile s = (s1, . . . , sn), the total cost to player i is:
Ci(s)=. dr(nr(s)) r ∈si
Every player, i, wants to minimize its own (expected) cost.
Best response dynamics, and pure
In a congestion game G, for any pure strategy profile
s = (s1, . . . , sn), suppose that some player i has a better alternative strategy, si′ ∈ Zi, such that Ci(s−i;si′) < Ci(s).
Player i can switch (unilaterally) from si to si′. This takes us from profile s to profile (s−i , si′).
We call this a single (strict) improvement step.
Starting at an arbitrary pure strategy profile s, what happens if the players perform a sequence of such improvement steps?
Theorem: ([Rosenthal’73]) In any congestion game, every sequence of strict improvement steps is necessarily finite, and terminates in a pure .
Thus, in particular, every congestion game has a pure strategy .
Proof: Potential functions
Proof: Consider the following potential function: nr(s)
φ(s)=. dr(i) (1) r∈R i=1
What happens to the value of φ(s) if player i switches unilaterally from si to si′, taking profile s to s′ := (s−i ; si′)?
Claim: φ(s) − φ(s′) = Ci (s) − Ci (s′).
Proof: Re-order the players in any arbitrary way, and index them as players 1, 2, . . . , n. (In particular, any player formerly indexed i could be re-indexed as n.) For i′ ∈ {1, . . . , n}, define
n(i′)(s)=|{i |r ∈s ∧i ∈{1,...,i′}}| ri
By exchanging the order of summation in equation (1) for φ(s), it can be seen that (check this yourself):
φ(s) = d (n(i)(s)) rr
proof of claim, continued
Now note that n(n)(s) = n (s). Thus rr
d (n(n)(s)) = d (n (s)) = C (s) rrrrn
r ∈sn r ∈sn
So, if player n switches from strategy sn to sn′ , leading us from profile s to s′ = (s−n; sn′ ), then:
φ(s) − φ(s′) = Cn(s) − Cn(s′).
But note that when re-ordering we could have chosen player n to be any player we want! So this holds for every player i.
Proof of Theorem, continued
To complete the proof of Rosenthal’s Theorem: Observe that every strict improvement step must decreases the value of the potential function φ(s) by at least 1 (the costs dr(s) are all integers). Furthermore, there are only finitely many pure strategies s, so there are finite integers:
a = mins φ(s) and b = maxs φ(s). Thus, every improvement sequence is finite.
Finally, note that the last profile s in any improvement sequence which can not be further improved is, by definition, a pure Nash equilibrium.2
Complexity of pure NE in network conges. games
Consider a network congestion game where we are given a network with source-sink node pairs (Si,Ti), for each player i, and each player must to choose a route (path) from Si to Ti . Suppose the cost (delay) of an edge, e, under profile s, is defined to be some linear function: de(ne(s)) = αene(s) + βe.
One obvious way to compute a pure NE is to perform an arbitrary improvement sequence. However, this may conceivably require many improvement steps.
Is there a better algorithm?
It turns out that it is as hard as any polynomial local search problem to compute a pure NE for network congestion games: Theorem: [Fabrikant et.al.’04, Ackermann et.al.’06]. Computing a pure NE for a network congestion game is PLS-complete, even when all edge delay functions, de, are linear.
So, unfortunately, a P-time algorithm is unlikely.
A flow network game 1 st
(from [Roughgarden-Tardos’00])
n customers in network: each wants to go from s to t.
Each can either take the edge with “latency” 1 (delay of crossing the edge), or edge with latency x. Here x represents the “congestion”: the ratio of the number of customers that are using that edge divided by the total n.
Assume n is very large, (basically, n → ∞). What is the delay in ? (NEs in such a setting yield essentially a unique average delay [Beckmann, et. al. ’56].) What is a “globally optimal” customer routing strategy profile that minimizes average delay?
What is the globally optimal average delay?
a modified game
What is the NE, and what is the average delay it induces? What is the globally optimal average delay?
a different network
What is the NE, and what is its average delay?
What is a globally optimal strategy profile and optimal
average delay?
What if an ambitious “network service provider” wanted to build an additional “high capacity superfast broadband” line?
Braess’s paradox
What is the NE and its average delay?
What is the globally optimal average delay?
social welfare and the price of anarchy
Recall that in a strategic game Γ, “utilitarian social welfare”, welfare(x), under a particular profile of mixed strategies
x ∈ X, is defined as welfare(x) := ni=1 Ui(x). For a game Γ, let NE(Γ) be the set of NE’s of Γ.
For our next definition suppose welfare(x) > 0 for all x ∈ X. (In many games, we can enforce this by, e.g., adding a fixed value to all payoffs.)
A version of “the price of anarchy” can be defined as: ([Koutsoupias-Papadimitriou’98])
PA(Γ) := maxx∈X welfare(x) minx∈NE(Γ) welfare(x)
Thus, the “price of anarchy” is the ratio of best “global” outcome to the the worst NE outcome. Note: this ratio is ≥ 1 and larger means “worse”.
It would be comforting to establish that in various situations the “price of anarchy” isn’t too high.
Pure price of anarchy
In some settings, such as congestion games, where we know that a pure equilibrium exists, it is sometimes more sensible to compare the best overall outcome to the worst pure-NE outcome.
Let pure-NE(Γ) denote the set of pure NEs in the game Γ. For settings (such as congestion games) where we know pure-NE(Γ) is non-empty, we define
“the pure price of anarchy” as:
pure-PA(Γ) := maxs∈S welfare(s) mins∈pure-NE(Γ) welfare(s)
Thus, the “pure price of anarchy” is the ratio of best (pure) “global” outcome to the the worst pure NE outcome.
price of anarchy in the flow network game
For flow f let welfare(f ) := 1/(average s-t-delay).
In Braess’s paradox, the price of anarchy is 4/3: by playing the NE the average delay is 2, but playing half-and-half on the upper and lower route, the average delay is 3/2 (and that’s optimal).
We have seen that the price of anarchy in network games can be arbitrarily high, when xd is an edge label.
Remarkably, [Roughgarden-Tardos’00] showed that in a more general flow network setting (where there can be multiple source-destination pairs (sj , tj )), as long as “congestions” labeling edges are linear functions of x, the worst-case price of anarchy is 4/3.
In other words, for linear latencies, the Braess’s paradox example yields the worst-case scenario.
Back to atomic network congestion games
By an “atomic” network congestion game, we simply mean a standard network congestion game with a finite number of players, where each aims to minimize its own cost. (Whereas in non-atomic network flow games the average cost in equilibrium is uniquely determined, this is not the case with atomic network congestion games.)
What is the (pure) price of anarchy in atomic network congestion games?
Theorem: [Christodoulou-Koutsoupias’2005]. The pure price of anarchy for a pure NE in atomic network congestion games with linear utilities is
(And this is tight, just like 4/3 for non-atomic network congestion games.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com