COMP558
Network Games
Martin Gairing
University of Liverpool, Computer Science Dept
2nd Semester 2013/14
COMP558 – Network Games · 0.1
Topic 4: Network Formation Games Ch.19
Local Connection Game
Model
Characterizing Solutions and Price of Stability
Price of Anarchy
Global Connection Game
Model
Price of Anarchy
Price of Stability
Facility Location
Model
Existence of pure NE and PoS
Utility games and PoA
COMP558 – Network Games Network Formation · 4.1
4 Network Formation Games
Scenario
I Consider users constructing a shared network
I Each user has its own interest and is driven by:
I Minimising the price he pays for creating/using the network
I Receiving a high quality of service
I We wish to model the networks generated by such selfish
behaviour of the users and compare them to the optimal networks
COMP558 – Network Games Network Formation · 4.2
Objectives
I How to evaluate the overall quality of a network?
I social cost = sum of players’ costs
I What are stable networks?
I we use Nash equilibrium as solution concept
I we refer to networks corresponding to Nash equilibrium as being
stable
I Our main goal: bounding the efficiency loss resulting from
selfishness
I Price of Anarchy
I Price of Stability
COMP558 – Network Games Network Formation · 4.3
Local vs. Global Connection Game
I Local connection game:
I users buy edges
I bought edge can be used by all users
I users wish to minimise distance to all other nodes
I while minimizing the number of edges they buy
I Resembles formation of P2P networks
I Global connection game:
I users want to connect two nodes si , ti in the network
I users share the cost of used edges
I users minimise their cost
I Resembles use of a large scale shared network
COMP558 – Network Games Network Formation · 4.4
Local Connection Game
Topic 4: Network Formation Games
Local Connection Game
Model
Characterizing Solutions and Price of Stability
Price of Anarchy
Global Connection Game
Model
Price of Anarchy
Price of Stability
Facility Location
Model
Existence of pure NE and PoS
Utility games and PoA
COMP558 – Network Games Network Formation · 4.5
Local Connection Game Model
Local Connection Game
Model
I n players: nodes in a graph G on which the network will be build
I Strategy Su of player u ∈ V is a set of undirected edges that u will
build (all are incident to u)
I For a strategy vector S, the union of all edges in players’
strategies form a network G(S)
I α ... cost for building an edge
I distS(u, v) ... distance (number of edges on shortest path)
between u and v in G(S)
I Cost of player u ∈ V :
Cu(S) =
∑
v∈V
distS(u, v) + α · nu,
where nu is number of edges bought by player u
COMP558 – Network Games Network Formation · 4.6
Local Connection Game Model
Local Connection Game
I A network G = (V ,E) is stable for a value α, if there is a NE S
that forms G.
Social Cost of a Network G = (V ,E) (= sum of players’ costs)
SC(G) =
∑
u 6=v
dist(u, v) + α · |E |
Observations
I Since the graph is undirected an edge (u, v) is available to both u
and v
I At Nash equilibrium at most one of the nodes u, v pays for the
edge (u, v)
I At Nash equilibrium we must have a connected graph, since
dist(u, v) =∞, if u and v are not connected
COMP558 – Network Games Network Formation · 4.7
Local Connection Game Characterizing Solutions and Price of Stability
Characterizing Solutions and Price of Stability
Lemma 4.1 (Lem. 19.1)
If α ≥ 2 then any star is an optimal solution, and if α ≤ 2 then the
complete graph is an optimal solution.
Lemma 4.2 (Lem. 19.2)
If α ≥ 1 then any star is a Nash equilibrium, and if α ≤ 1 then the
complete graph is a Nash equilibrium.
Remark: There are also other Nash equilibria.
Theorem 4.3 (Thm. 19.3)
If α ≥ 2 or α ≤ 1, the price of stability is 1. For 1 < α < 2, the price of
stability is at most 4/3.
COMP558 – Network Games Network Formation · 4.8
Local Connection Game Price of Anarchy
Price of Anarchy
To prove upper bound on the Price of Anarchy we
1 bound the diameter of a stable (NE) graph
2 use diameter to bound cost
Lemma 4.4 (Lem. 19.4)
If a graph G at Nash equilibrium has diameter d , then PoA(G) = O(d).
492 network formation games
proof The cost of the optimal solution is at least!(αn+ n2), as we need to buy
a connected graph, which costs at least (n− 1)α, and there are !(n2) distances,
each of which is at least 1. To bound the quality of the solution, consider the
distance costs and edge costs separately. The distance cost is at most n2d, and
thus is at most d times the minimum possible.
We now examine edge costs. First we consider cut edges, those edges whose
removal disconnects G. There are at most n− 1 cut edges, so the total cost of
all cut edges is at most α(n− 1), which in turn is at most the optimal solution
cost. Now consider the set of all noncut edges paid for by a vertex v. We will
argue that there are O(nd/α) such edges, with cost O(dn) for node v, and thus
the total cost of all noncut edges is O(dn2). This will establish that the cost of G
is O(αn+ dn2), completing the proof.
Pick a node u, and for each edge e = (u, v) paid for by node u, let Ve be the
set of nodes w, where the shortest path from u to w goes through edge e. We
will argue that the distance between nodes u and v with edge e deleted is at most
2d. Thus deleting e increases the total distance from u to all other nodes by at
most 2d|Ve|. Since deleting the edge would save α in edge costs and G is stable,
we must have that α ≤ 2d|Ve|, and hence |Ve| ≥ α/2d. If there are at least α/2d
nodes in each Ve, then the number of such edges adjacent to a node v must be at
most 2dn/α, as claimed.
We now bound the distance between nodes u and v with edge e deleted.
Consider Figure 19.1, depicting a shortest path avoiding edge e. Let e′ = (u′, v′)
be the edge on this path entering the set Ve. The segment Pu of this path from u
to node u′ is the shortest path from u to u′ as u′ !∈ Ve, and hence deleting e does
not affect the shortest path. So Pu is at most d long. The segment Pv from v′ to v
is at most d − 1 long, as Pv ∪ e forms the shortest path between u and v′. Thus
the total length is at most 2d.
Using this lemma, we can bound the price of anarchy by O(√α).
Theorem 19.5 The diameter of Nash equilibrium is at most 2√α, and hence
the pric of narchy is at most O(√α).
proof From Lemma 19.4, we need only prove that for any nodes u and v,
dist(u, v) < 2√α. Suppose for nodes u and v, dist(u, v) ≥ 2k, for some k. The
u v
e’
e
v’
u’
Ve
Pv
Pu
Figure 19.1. Path Pu, (u′, v ′)Pv is the u–v shortest path after edge e = (u, v ) is deleted.
COMP558 – Network Games Network Formation · 4.9
Local Connection Game Price of Anarchy
Price of Anarchy
Theorem 4.5 (Thm. 19.5)
The diameter of a stable graph G is at most 2
√
α, and hence
PoA(G) = O(
√
α).
Theorem 4.6 (Thm. 19.6)
The price of anarchy is O(1) whenever α = O(
√
n). More generally,
PoA = O(1 + α√n ). the local connection game 493
u
w
t
v
Aw
d ′
Bu
Figure 19.2. Nodes u and v that are at maximum distance d apart. B is the set of nodes at
most d′ = (d− 1)/4 away from node u, and Aw is the set of nodes whose shortest path leaves
B at w.
main observation is that by adding the edge (u, v), the node u would pay α and
improve her distance to the nodes on the second half of the u− v shortest path
by (2k − 1) + (2k − 3) + · · · + 1 = k2. So if dist(u, v) > 2√α, node u would
benefit from adding the edge (u, v), a contradiction.
We now show an O(1) bound on the price of anarchy that was given by Lin (2003)
(and independently also by Albers et al., 2006) for α = O(√n).
Theorem 19.6 The price of anarchy is O(1) whenever α is O(√n). More gen-
erally, price of anarchy is O(1+ α/√n).
proof We again use Lemma 19.4, so all we have to do is improve our bound
on the diameter d. Consider nodes u and v with dist(u, v) = d. Let d ′ = "(d −
1)/4$ and let B be the set of nodes at most d ′ away from u, as shown on
Figure 19.2. Consider how the distance d(v,w) changes for nodes w ∈ B by
adding edge (v, u). Before adding the edge dist(v,w) ≥ d − d ′. After adding
(v, u), the distance decreases to at most d ′ + 1. Thus v saves at least (d − 2d ′ − 1)
in distance to all nodes in B, and hence would save at least (d − 2d ′ − 1)|B| ≥
(d − 1)|B|/2 in total distance costs by buying edge (v, u). If G is stable, we must
have (d − 1)|B|/2 ≤ α.
For a node w ∈ B let Aw contain all nodes t for which the u–t shortest path
leaves the set B after the node w. Note that if Aw is nonempty, then w must
be exactly at distance d ′ from u. Therefore, node u would save |Aw|(d ′ − 1)
in distance cost by buying edge (u,w). If the network is at equilibrium, then
we must have that |Aw|(d ′ − 1) ≤ α. There must be a node w ∈ B that has
|Aw| ≥ (n− |B|)/|B|. Combining these, we get that
(d ′ − 1)(n− |B|)/|B| ≤ α.
This implies that |B|(1 + α/(d ′ − 1)) ≥ n, and since α > d > d ′,
|B| ≥ n(d ′ − 1)/2α.
Combining this with the previous bound of α ≥ (d − 1)|B|/2 yields
α ≥ (d − 1)|B|/2 ≥ (d − 1)n(d ′ − 1)/4α ≥ n(d ′ − 1)2/α.
COMP558 – Network Games Network Formation · 4.10
Global Connection Game Model
Topic 4: Network Formation Games
Local Connection Game
Model
Characterizing Solutions and Price of Stability
Price of Anarchy
Global Connection Game
Model
Price of Anarchy
Price of Stability
Facility Location
Model
Existence of pure NE and PoS
Utility games and PoA
COMP558 – Network Games Network Formation · 4.11
Global Connection Game Model
Global Connection Game
Model
I directed G = (V ,E) with non-negative edge cost ce
I k players , each player i ∈ [k ] has a source si and sink node ti
I A strategy for a player i is a path Pi from si to ti in G
I Given each players strategy we define the constructed network to
be ∪iPi
I Players who use edge e divide the cost ce according to some cost
sharing mechanism.
I We will consider the equal-division mechanism:
costi(S) =
∑
e∈Pi
ce
ke
I S = (P1, . . . ,Pk )
I ke ... number of players whose path contains e
COMP558 – Network Games Network Formation · 4.12
Global Connection Game Model
Existence of Stable Networks
I Does every global connection game have a pure Nash
equilibrium?
I Yes.
I Why?
I It is a special congestion game!
I Rosenthal’s potential function
Φ(S) =
∑
e∈E ,ke>0
ke∑
j=1
ce
j
=
∑
e∈E
ce · Hke
(Hk is k-th harmonic number)
COMP558 – Network Games Network Formation · 4.13
Global Connection Game Price of Anarchy
Price of Anarchy
Social Cost (total cost of used edges)
SC(S) =
∑
i∈[k ] costi(S)
Example
potential games and a global connection game 495
a vast number of possible cost-sharing mechanisms, each of which induces a distinct
network formation game. We will briefly touch on this large space of games at the
end of the section, but for now, our primary focus will be on a single cost-sharing
mechanism with a number of nice properties, that is both simple and easy to motivate.
In particular, we consider the mechanism that splits the cost of an edge evenly among
all players whose path contains it. More concretely, if ke denotes the number of players
whose path contains edge e, then e assigns a cost share of ce/ke to each player using
e. Thus the total cost incurred by player i under a strategy vector S is given by
costi(S) =
∑
e∈Pi
ce/ke.
Note that the total cost assigned to all players is exactly the cost of the constructed
network. This equal-division mechanism was suggested by Herzog et al. (1997), and
has a number of basic economic motivations. Moulin and Shenker prove that this
mechanism can be derived from the Shapley (2001) value, and it can be shown to
be the unique cost-sharing scheme satisfying a number of natural sets of axioms (see
Feigenbaum et al., 2001; Moulin and Shenker, 2001). We refer to it as the fair or
Shapley cost-sharing mechanism. The social objective for this game is simply the cost
of the constructed network.
One may view this game as a competitive version of the generalized Steiner tree
problem; given a graph and pairs of terminals, find the cheapest possible network
connecting all terminal pairs. Indeed, an optimal generalized Steiner tree is precisely
the outcome against which we will compare stable solutions in evaluating the efficiency
of equilibria. This connection highlights an important difference between this game
and routing games; in routing games such as those discussed in Chapter 18, players
are sensitive to congestion effects, and thus seek sparsely used paths. But in the global
connection game, as with the Steiner forest problem, the objective is simply to minimize
costs, and thus sharing edges is in fact encouraged.
The two examples in Chapter 17 provide a few useful observations about this game.
Example 17.2 (see Figure 19.3(a)) shows that even on very simple networks, this game
has multiple equilibria, and that these equilibria may differ dramatically in quality.
There are two equilibria with costs k and 1 respectively. Since the latter is also optimal
t
s1 s2 s3 sk-1 sk
1
1
2
1
3
1
k-1
1
k
1 + ε
(a)
1 k
v
t1, t2, ..., tk
s1, s2, ..., sk
(b)
Figure 19.3. An instance of the global connection game with price of anarchy k (a) and an
instance with price of stability Hk (b).
I optimal network has cost 1
I best NE: all players use the left edge
⇒ PoS = 1
I worst NE: all players use the right edge
⇒ PoA = k
Theorem 4.7
For any global connection game with k players, PoA ≤ k .
COMP558 – Network Games Network Formation · 4.14
Global Connection Game Price of Stability
Price of Stability: a lower bound ( ε > 0 arbitrary small)
potential games and a global connection game 495
a vast number of possible cost-sharing mechanisms, each of which induces a distinct
network formation game. We will briefly touch on this large space of games at the
end of the section, but for now, our primary focus will be on a single cost-sharing
mechanism with a number of nice properties, that is both simple and easy to motivate.
In particular, we consider the mechanism that splits the cost of an edge evenly among
all players whose path contains it. More concretely, if ke denotes the number of players
whose path contains edge e, then e assigns a cost share of ce/ke to each player using
e. Thus the total cost incurred by player i under a strategy vector S is given by
costi(S) =
∑
e∈Pi
ce/ke.
Note that the total cost assigned to all players is exactly the cost of the constructed
network. This equal-division mechanism was suggested by Herzog et al. (1997), and
has a number of basic economic motivations. Moulin and Shenker prove that this
mechanism can be derived from the Shapley (2001) value, and it can be shown to
be the unique cost-sharing scheme satisfying a number of natural sets of axioms (see
Feigenbaum et al., 2001; Moulin and Shenker, 2001). We refer to it as the fair or
Shapley cost-sharing mechanism. The social objective for this game is simply the cost
of the constructed network.
One may view this game as a competitive version of the generalized Steiner tree
problem; given a graph and pairs of terminals, find the cheapest possible network
connecting all terminal pairs. Indeed, an optimal generalized Steiner tree is precisely
the outcome against which we will compare stable solutions in evaluating the efficiency
of equilibria. This connection highlights an important difference between this game
and routing games; in routing games such as those discussed in Chapter 18, players
are sensitive to congestion effects, and thus seek sparsely used paths. But in the global
connection game, as with the Steiner forest problem, the objective is simply to minimize
costs, and thus sharing edges is in fact encouraged.
The two examples in Chapter 17 provide a few useful observations about this game.
Example 17.2 (see Figure 19.3(a)) shows that even on very simple networks, this game
has multiple equilibria, and that these equilibria may differ dramatically in quality.
There are two equilibria with costs k and 1 respectively. Since the latter is also optimal
t
s1 s2 s3 sk-1 sk
1
1
2
1
3
1
k-1
1
k
1 + ε
(a)
1 k
v
t1, t2, ..., tk
s1, s2, ..., sk
(b)
Figure 19.3. An instance of the global connection game with price of anarchy k (a) and an
instance with price of stability Hk (b).
I optimal network has a cost of 1 + ε Is it stable?
I cost of unique stable network:
∑k
j=1
1
j = Hk
COMP558 – Network Games Network Formation · 4.15
Global Connection Game Price of Stability
Price of Stability: an upper bound
Lemma 4.8 (Lem. 19.8)
For any strategy profile S = (P1, . . . ,Pk ) we have
SC(S) ≤ Φ(S) ≤ Hk · SC(S)
Lemma 4.8 and Lemma 3.18 directly imply:
Theorem 4.9 (Thm. 19.10)
The price of stability in the global connection game with k players is at
most Hk .
Remark: Hk = Θ(log k)
COMP558 – Network Games Network Formation · 4.16
Facility Location
Topic 4: Network Formation Games
Local Connection Game
Model
Characterizing Solutions and Price of Stability
Price of Anarchy
Global Connection Game
Model
Price of Anarchy
Price of Stability
Facility Location
Model
Existence of pure NE and PoS
Utility games and PoA
COMP558 – Network Games Network Formation · 4.17
Facility Location Model
Facility Location Game
Model
I k service providers and a set of clients [m]
I each provider i ∈ [k ] has a set of possible locations Ai where he
can locate his facility; denote A = ∪i∈[k ]Ai
I cjsi .. cost of serving customer j ∈ [m] from location si ∈ Ai
I pij .. value of client j ∈ [m] for being served
502 network formation games
the worst case. See the notes on this chapter (Section 19.5.2) for a brief discussion of
research concerning other cost-sharing approaches.
19.4 Facility Location
In the models we have considered so far, players construct networks so as to achieve
certain connectivity-based goals. Intuitively, these goals are meant to capture players’
desires to provide service for some implicit population of network users. Given this per-
spective, we might then ask what happens when we instead view players as financially
motivated agents; after all, service providers are primarily concerned with maximizing
profits, and only maintain networks for this purpose. This suggests a model in which
players not only build networks but also charge for usage, while network users spur
competition by seeking the cheapest service available.
We will consider here a pricing game introduced by Vetta (2002) that is based on the
facility location problem. In the facility location problem, we want to locate k facilities,
such as Web servers or warehouses, so as to serve a set of clients profitably. Our focus
here will be to understand the effect of selfish pricing on the overall efficiency of the
networks that players form.
We first present Vetta’s competitive facility location problem, in which players place
facilities so as to maximize their own profit. We then show that this facility location
game is a potential game, and prove that the price of anarchy for an even broader class
of games is small.
19.4.1 The Model
Suppose that we have a set of users that need a service, and k service providers. We
assume that each service provider i has a set of possible locations Ai where he can
locate his facility.
Define A = ∪iAi to be the set of all possible facility locations. For each location
si ∈ Ai there is an associated cost cjsi for serving customer j from location si . We
can think of these costs as associated with edges of a bipartite graph that has all users
on one side and all of A on the other, as shown on Figure 19.4. A strategy vector
Possible
facilities
A1
Clients
s
jcjs
A2
Figure 19.4. The bipartite graph of possible locations and clients. Selected facilities are marked
in black.
COMP558 – Network Games Network Formation · 4.18
Facility Location Model
Facility Location Game
Model cont.
I If provider i serves client j from
location si at a price p
I pij − p .. benefit for client j
I p − cjsi .. profit for provider i
I ⇒ social value: pij − cjsi
(independent of price)
502 network formation games
the worst case. See the notes on this chapter (Section 19.5.2) for a brief discussion of
research concerning other cost-sharing approaches.
19.4 Facility Location
In the models we have considered so far, players construct networks so as to achieve
certain connectivity-based goals. Intuitively, these goals are meant to capture players’
desires to provide service for some implicit population of network users. Given this per-
spective, we might then ask what happens when we instead view players as financially
motivated agents; after all, service providers are primarily concerned with maximizing
profits, and only maintain networks for this purpose. This suggests a model in which
players not only build networks but also charge for usage, while network users spur
competition by seeking the cheapest service available.
We will consider here a pricing game introduced by Vetta (2002) that is based on the
facility location problem. In the facility location problem, we want to locate k facilities,
such as Web servers or warehouses, so as to serve a set of clients profitably. Our focus
here will be to understand the effect of selfish pricing on the overall efficiency of the
networks that players form.
We first present Vetta’s competitive facility location problem, in which players place
facilities so as to maximize their own profit. We then show that this facility location
game is a potential game, and prove that the price of anarchy for an even broader class
of games is small.
19.4.1 The Model
Suppose that we have a set of users that need a service, and k service providers. We
assume that each service provider i has a set of possible locations Ai where he can
locate his facility.
Define A = ∪iAi to be the set of all possible facility locations. For each location
si ∈ Ai there is an associated cost cjsi for serving customer j from location si . We
can think of these costs as associated with edges of a bipartite graph that has all users
on one side and all of A on the other, as shown on Figure 19.4. A strategy vector
Possible
facilities
A1
Clients
s
jcjs
A2
Figure 19.4. The bipartite graph of possible locations and clients. Selected facilities are marked
in black.
I To simplify notation assume pij ≥ cjsi for all j , i and si ∈ Ai .
I This does not change social value.
I Given s = (s1, . . . , sk ), each client j
I is assigned to provider i with lowest cost cjsi ,
I pays price pij = mini′ 6=i cjsi′
I total social value of s = (s1, . . . , sk ):
V (s) =
∑
j∈[m]
(pij −min
i∈[k ]
cjsi )
COMP558 – Network Games Network Formation · 4.19
Facility Location Existence of pure NE and PoS
Facility Location Game is Potential Game
Theorem 4.10 (Thm. 19.16)
V (s) is a potential function for the facility location game.
Corollary 4.11
1 Each facility location game admits a pure NE.
2 Every optimum is also a NE and thus PoS = 1.
Up next:
I bound price of anarchy
I we do this for the more general class of utility games
COMP558 – Network Games Network Formation · 4.20
Facility Location Utility games and PoA
Utility Games
I each player i ∈ [k ] has a set of available strategies Ai (e.g.
locations)
I A = ∪i∈[k ]Ai
I Social welfare function V (B) defined for all B ⊆ A
I αi(s) .. welfare of player i in s = (s1, . . . , sk )
Utility games satisfy the following properties:
(i) V (B) is submodular: for any sets B ⊂ B′ ⊂ A and any element
e ∈ A, we have V (B ∪ {e})− V (B) ≥ V (B′ ∪ {e})− V (B′).
(ii) The total value for players is less than or equal to the total social
value:
∑
i∈[k ] αi(s) ≤ V (s).
(iii) The value for player i is at least his added value for the society:
αi(s) ≥ V (s)− V (s − si).
Utility game is basic, if (iii) is satisfied with equality, and monotone if for
all B ⊆ B′ ⊆ A, V (B) ≤ V (B′)
COMP558 – Network Games Network Formation · 4.21
Facility Location Utility games and PoA
PoA in Utility Games
To view facility location game as a utility game define for each
B ⊆ A = ∪i∈[k ]Ai :
V (B) =
∑
j∈[m]
(pij −min
e∈B
cje)
Theorem 4.12
The facility location game is a monotone basic utility game.
Theorem 4.13
For all monotone utility games G, we have PoA(G) ≤ 2.
COMP558 – Network Games Network Formation · 4.22

欢迎咨询51作业君