Strong Equilibrium in Cost Sharing Connection Games∗  Amir Epstein  School of Computer Science  Tel-Aviv University  Tel-Aviv, 69978, Israel  amirep@tau.ac.il  Michal Feldman  School of Computer Science  The Hebrew University of  Jerusalem  Jerusalem, 91904, Israel  mfeldman@cs.huji.ac.il  Yishay Mansour  School of Computer Science  Tel-Aviv University  Tel-Aviv, 69978, Israel  mansour@tau.ac.il  ABSTRACT  In this work we study cost sharing connection games, where  each player has a source and sink he would like to connect,  and the cost of the edges is either shared equally (fair   connection games) or in an arbitrary way (general connection  games). We study the graph topologies that guarantee the  existence of a strong equilibrium (where no coalition can  improve the cost of each of its members) regardless of the  specific costs on the edges.  Our main existence results are the following: (1) For a  single source and sink we show that there is always a strong  equilibrium (both for fair and general connection games).  (2) For a single source multiple sinks we show that for a  series parallel graph a strong equilibrium always exists (both  for fair and general connection games). (3) For multi source  and sink we show that an extension parallel graph always  admits a strong equilibrium in fair connection games.  As for the quality of the strong equilibrium we show that  in any fair connection games the cost of a strong equilibrium  is Θ(log n) from the optimal solution, where n is the number  of players. (This should be contrasted with the Ω(n) price  of anarchy for the same setting.) For single source general  connection games and single source single sink fair   connection games, we show that a strong equilibrium is always an  optimal solution.  Categories and Subject Descriptors  C.2.4 [Computer-Communication Networks]:   Distributed Systems; F.2.0 [Analysis of Algorithms and   Problem Complexity]: General; J.4 [Social and Behavioral  Sciences]: Economics; K.4.4 [Electronic Commerce]:   Payment schemes    1. INTRODUCTION  Computational game theory has introduced the issue of  incentives to many of the classical combinatorial   optimization problems. The view that the demand side is many times  not under the control of a central authority that optimizes  the global performance, but rather under the control of   individuals with different incentives, has led already to many  important insights.  Consider classical routing and transportation problems  such as multicast or multi-commodity problems, which are  many times viewed as follows. We are given a graph with  edge costs and connectivity demands between nodes, and  our goal is to find a minimal cost solution. The classical   centralized approach assumes that all the individual demands  can both be completely coordinated and have no individual  incentives. The game theory point of view would assume  that each individual demand is controlled by a player that  optimizes its own utility, and the resulting outcome could  be far from the optimal solution.  When considering individual incentives one needs to   discuss the appropriate solution concept. Much of the research  in computational game theory has focused on the classical  Nash equilibrium as the primary solution concept. Indeed  Nash equilibrium has many benefits, and most importantly  it always exists (in mixed strategies). However, the solution  concept of Nash equilibrium is resilient only to unilateral   deviations, while in reality, players may be able to coordinate  their actions.  A strong equilibrium [4] is a state from which no coalition  (of any size) can deviate and improve the utility of every  member of the coalition (while possibly lowering the utility  84  of players outside the coalition). This resilience to   deviations by coalitions of the players is highly attractive, and  one can hope that once a strong equilibrium is reached it is  highly likely to sustain. From a computational game theory  point of view, an additional benefit of a strong equilibrium  is that it has a potential to reduce the distance between the  optimal solution and the solution obtained as an outcome  of selfish behavior. The strong price of anarchy (SPoA),   introduced in [1], is the ratio between the cost of the worst  strong equilibrium and the cost of an optimal solution.  Obviously, SPoA is meaningful only in those cases where  a strong equilibrium exists. A major downside of strong  equilibrium is that most games do not admit any strong  equilibrium. Even simple classical games like the prisoner"s  dilemma do not posses any strong equilibrium (which is also  an example of a congestion game that does not posses a  strong equilibrium1  ). This unfortunate fact has reduced the  concentration in strong equilibrium, despite its highly   attractive properties. Yet, [1] have identified two broad   families of games, namely job scheduling and network formation,  where a strong equilibrium always exists and the SPoA is  significantly lower than the price of anarchy (which is the  ratio between the worst Nash equilibrium and the optimal  solution [15, 18, 5, 6]).  In this work we concentrate on cost sharing connection  games, introduced by [3, 2]. In such a game, there is an  underlying directed graph with edge costs, and individual  users have connectivity demands (between a source and a  sink). We consider two models. The fair cost connection  model [2] allows each player to select a path from the source  to the sink2  . In this game the cost of an edge is shared  equally between all the players that selected the edge, and  the cost of the player is the sum of its costs on the edges it  selected. The general connection game [3] allows each player  to offer prices for edges. In this game an edge is bought if  the sum of the offers at least covers its cost, and the cost of  the player is the sum of its offers on the bought edges (in  both games we assume that the player has to guarantee the  connectivity between its source and sink).  In this work we focus on two important issues. The first  one is identifying under what conditions the existence of a  strong equilibrium is guaranteed, and the second one is the  quality of the strong equilibria. For the existence part, we  identify families of graph topologies that possess some strong  equilibrium for any assignment of edge costs. One can view  this separation between the graph topology and the edge  costs, as a separation between the underlying infrastructure  and the costs the players observe to purchase edges. While  one expects the infrastructure to be stable over long periods  of time, the costs the players observe can be easily modified  over short time periods. Such a topological characterization  of the underlying infrastructure provides a network designer  topological conditions that will ensure stability in his   network.  Our results are as follows. For the single commodity case  (all the players have the same source and sink), there is a  strong equilibrium in any graph (both for fair and general  connection games). Moreover, the strong equilibrium is also  1  while any congestion game is known to admit at least one  Nash equilibrium in pure strategies [16].  2  The fair cost sharing scheme is also attractive from a   mechanism design point of view, as it is a strategyproof   costsharing mechanism [14].  the optimal solution (namely, the players share a shortest  path from the common source to the common sink). For  the case of a single source and multiple sinks (for   example, in a multicast tree), we show that in a fair connection  game there is a strong equilibrium if the underlying graph  is a series parallel graph, and we show an example of a   nonseries parallel graph that does not have a strong equilibrium.  For the case of multi-commodity (multi sources and sinks),  we show that in a fair connection game if the graph is an  extension parallel graph then there is always a strong   equilibrium, and we show an example of a series parallel graph  that does not have a strong equilibrium. As far as we know,  we are the first to provide a topological characterization for  equilibrium existence in multi-commodity and single-source  network games.  For any fair connection game we show that if there exists  a strong equilibrium it is at most a factor of Θ(log n) from  the optimal solution, where n is the number of players. This  should be contrasted with the Θ(n) bound that exists for the  price of anarchy [2].  For single source general connection games, we show that  any series parallel graph possesses a strong equilibrium, and  we show an example of a graph that does not have a strong  equilibrium. In this case we also show that any strong   equilibrium is optimal.  Related work  Topological characterizations for single-commodity network  games have been recently provided for various equilibrium  properties, including equilibrium existence [12, 7, 8],   equilibrium uniqueness [10] and equilibrium efficiency [17, 11]. The  existence of pure Nash equilibrium in single-commodity   network congestion games with player-specific costs or weights  was studied in [12]. The existence of strong equilibrium  was studied in both utility-decreasing (e.g., routing) and  utility-increasing (e.g., fair cost-sharing) congestion games.  [7, 8] have provided a full topological characterization for  a SE existence in single-commodity utility-decreasing   congestion games, and showed that a SE always exists if and  only if the underlying graph is extension-parallel. [19] have  shown that in single-commodity utility-increasing   congestion games, the topological characterization is essentially  equivalent to parallel links. In addition, they have shown  that these results hold for correlated strong equilibria as  well (in contrast to the decreasing setting, where correlated  strong equilibria might not exist at all). While the fair cost  sharing games we study are utility increasing network   congestion games, we derive a different characterization than  [19] due to the different assumptions regarding the players"  actions.3  2. MODEL  2.1 Game Theory definitions  A game Λ =< N, (Σi), (ci) > has a finite set N = {1, . . . , n}  of players. Player i ∈ N has a set Σi of actions, the joint   action set is Σ = Σ1 × · · · × Σn and a joint action S ∈ Σ  is also called a profile. The cost function of player i is  3  In [19] they allow to restrict some players from using certain  links, even though the links exist in the graph, while we do  not allow this, and assume that the available strategies for  players are fully represented by the underlying graph.  85  ci : Σ → R+  , which maps the joint action S ∈ Σ to a  non-negative real number. Let S = (S1, . . . , Sn) denote  the profile of actions taken by the players, and let S−i =  (S1, . . . , Si−1, Si+1, . . . , Sn) denote the profile of actions taken  by all players other than player i. Note that S = (Si, S−i).  The social cost of a game Λ is the sum of the costs of  the players, and we denote by OPT(Λ) the minimal social  cost of a game Λ. i.e., OPT(Λ) = minS∈Σ costΛ(S), where  costΛ(S) = i∈N ci(S).  A joint action S ∈ Σ is a pure Nash equilibrium if no player  i ∈ N can benefit from unilaterally deviating from his action  to another action, i.e., ∀i ∈ N ∀Si ∈ Σi : ci(S−i, Si) ≥  ci(S). We denote by NE(Λ) the set of pure Nash equilibria  in the game Λ.  Resilience to coalitions: A pure deviation of a set of   players Γ ⊂ N (also called coalition) specifies an action for each  player in the coalition, i.e., γ ∈ ×i∈ΓΣi. A joint action S ∈  Σ is not resilient to a pure deviation of a coalition Γ if there  is a pure joint action γ of Γ such that ci(S−Γ, γ) < ci(S) for  every i ∈ Γ (i.e., the players in the coalition can deviate in  such a way that each player in the coalition reduces its cost).  A pure Nash equilibrium S ∈ Σ is a k-strong equilibrium, if  there is no coalition Γ of size at most k, such that S is not  resilient to a pure deviation by Γ. We denote by k-SE(Λ)  the set of k-strong equilibria in the game Λ. We denote by  SE(Λ) the set of n-strong equilibria, and call S ∈ SE(Λ) a  strong equilibrium (SE).  Next we define the Price of Anarchy [9], Price of   Stability [2], and their extension to Strong Price of Anarchy  and Strong Price of Stability. of anarchy (k-SPoA) for the  game Λ. The Price of Anarchy (PoA) is the ratio between  the maximal cost of a pure Nash equilibrium (assuming one  exists) and the social optimum, i.e., maxS∈NE(Λ) costΛ(S)  /OPT(Λ). Similarly, the Price of Stability (PoS) is the   ratio between the minimal cost of a pure Nash equilibrium and  the social optimum, i.e., minS∈NE(Λ) costΛ(S)/OPT(Λ). The  k-Strong Price of Anarchy (k-SPoA) is the ratio between  the maximal cost of a k-strong equilibrium (assuming one  exists) and the social optimum, i.e., maxS∈k-SE(Λ) costΛ(S)  /OPT(Λ). The SPoA is the n-SPoA. Similarly, the Strong  Price of Stability (SPoS) is the ratio between the minimal  cost of a pure strong equilibrium and the social optimum,  i.e., minS∈SE(Λ) costΛ(S)/OPT(Λ). Note that both k-SPoA  and SPoS are defined only if some strong equilibrium exists.  2.2 Cost Sharing Connection Games  A cost sharing connection game has an underlying   directed graph G = (V, E) where each edge e ∈ E has an  associated cost ce ≥ 04  . In a connection game each player  i ∈ N has an associated source si and sink ti.  In a fair connection game the actions Σi of player i   include all the paths from si to ti. The cost of each edge is  shared equally by the set of all players whose paths   contain it. Given a joint action, the cost of a player is the  sum of his costs on the edges it selected. More formally,  the cost function of each player on an edge e, in a joint  action S, is fe(ne(S)) = ce  ne(S)  , where ne(S) is the   number of players that selected a path containing edge e in  S. The cost of player i, when selecting path Qi ∈ Σi is  ci(S) = e∈Qi  fe(ne(S)).  4  In some of the existence proofs, we assume that ce > 0 for  simplicity. The full version contains the complete proofs for  the case ce ≥ 0.  In a general connection game the actions Σi of player i  is a payment vector pi, where pi(e) is how much player i  is offering to contribute to the cost of edge e.5  Given a  profile p, any edge e such that i pi(e) ≥ ce is considered  bought, and Ep denotes the set of bought edges. Let Gp =  (V, Ep) denote the graph bought by the players for profile  p = (p1, . . . , pn). Clearly, each player tries to minimize his  total payment which is ci(p) = e∈Ep  pi(e) if si is connected  to ti in Gp, and infinity otherwise.6  We denote by c(p) =  i ci(p) the total cost under the profile p. For a subgraph  H of G we denote the total cost of the edges in H by c(H).  A symmetric connection game implies that the source and  sink of all the players are identical. (We also call a   symmetric connection game a single source single sink connection  game, or a single commodity connection game.) A single  source connection game implies that the sources of all the  players are identical. Finally, A multi commodity connection  game implies that each player has its own source and sink.  2.3 Extension Parallel and Series Parallel  Directed Graphs  Our directed graphs would be acyclic, and would have  a source node (from which all nodes are reachable) and a  sink node (which every node can reach). We first define the  following actions for composition of directed graphs.  • Identification: The identification operation allows to  collapse two nodes to one. More formally, given graph  G = (V, E) we define the identification of a node v1 ∈  V and v2 ∈ V forming a new node v ∈ V as creating a  new graph G = (V , E ), where V = V −{v1, v2}∪{v}  and E includes the edges of E where the edges of v1  and v2 are now connected to v.  • Parallel composition: Given two directed graphs, G1 =  (V1, E1) and G2 = (V2, E2), with sources s1 ∈ V1 and  s2 ∈ V2 and sinks t1 ∈ V1 and t2 ∈ V2, respectively,  we define a new graph G = G1||G2 as follows. Let  G = (V1 ∪ V2, E1 ∪ E2) be the union graph. To create  G = G1||G2 we identify the sources s1 and s2, forming  a new source node s, and identify the sinks t1 and t2,  forming a new sink t.  • Series composition: Given two directed graphs, G1 =  (V1, E1) and G2 = (V2, E2), with sources s1 ∈ V1 and  s2 ∈ V2 and sinks t1 ∈ V1 and t2 ∈ V2, respectively, we  define a new graph G = G1 → G2 as follows. Let G =  (V1 ∪ V2, E1 ∪ E2) be the union graph. To create G =  G1 → G2 we identify the vertices t1 and s2, forming a  new vertex u. The graph G has a source s = s1 and a  sink t = t2.  • Extension composition : A series composition when  one of the graphs, G1 or G2, is composed of a   single directed edge is an extension composition, and we  denote it by G = G1 →e G2.  An extension parallel graph (EPG) is a graph G consisting  of either: (1) a single directed edge (s, t), (2) a graph G =  G1||G2 or (3) a graph G = G1 →e G2, where G1 and G2 are  5  We limit the players to select a path connecting si to ti  and payment only on those edges.  6  This implies that in equilibrium every player has its sink  and source connected by a path in Gp.  86  extension parallel graphs (and in the extension composition  either G1 or G2 is a single edge.). A series parallel graph  (SPG) is a graph G consisting of either: (1) a single directed  edge (s, t), (2) a graph G = G1||G2 or (3) a graph G = G1 →  G2, where G1 and G2 are series parallel graphs.  Given a path Q and two vertices u, v on Q, we denote the  subpath of Q from u to v by Qu,v. The following lemma,  whose proof appears in the full version, would be the main  topological tool in the case of single source graph.  Lemma 2.1. Let G be an SPG with source s and sink t.  Given a path Q, from s to t, and a vertex t , there exist a  vertex y ∈ Q, such that for any path Q from s to t , the path  Q contains y and the paths Qy,t and Q are edge disjoint.  (We call the vertex y the intersecting vertex of Q and t .)  3. FAIR CONNECTION GAMES  This section derives our results for fair connection games.  3.1 Existence of Strong Equilibrium  While it is known that every fair connection game   possesses a Nash equilibrium in pure strategies [2], this is not  necessarily the case for a strong equilibrium. In this section,  we study the existence of strong equilibrium in fair   connection games. We begin with a simple case, showing that every  symmetric fair connection game possesses a strong   equilibrium.  Theorem 3.1. In every symmetric fair connection game  there exists a strong equilibrium.  Proof. Let s be the source and t be the sink of all the  players. We show that a profile S in which all the players  choose the same shortest path Q (from the source s to the  sink t ) is a strong equilibrium. Suppose by contradiction  that S is not a SE. Then there is a coalition Γ that can  deviate to a new profile S such that the cost of every player  j ∈ Γ decreases. Let Qj be a new path used by player j ∈ Γ.  Since Q is a shortest path, it holds that c(Qj \ (Q ∩ Qj)) ≥  c(Q \ (Q ∩ Qj)), for any path Qj. Therefore for every player  j ∈ Γ we have that cj(S ) ≥ cj(S). However, this contradicts  the fact that all players in Γ reduce their cost. (In fact, no  player in Γ has reduced its cost.)  While every symmetric fair connection game admits a SE,  it does not hold for every fair connection game. In what   follows, we study the network topologies that admit a strong  equilibrium for any assignment of edge costs, and give   examples of topologies for which a strong equilibrium does not  exist. The following lemma, whose proof appears in the full  version, plays a major role in our proofs of the existence of  SE.  Lemma 3.2. Let Λ be a fair connection game on a series  parallel graph G with source s and sink t. Assume that player  i has si = s and ti = t and that Λ has some SE. Let S be  a SE that minimizes the cost of player i (out of all SE),  i.e., ci(S) = minT ∈SE(Λ) ci(T) and let S∗  be the profile that  minimizes the cost of player i (out of all possible profiles),  i.e., ci(S∗  ) = minT ∈Σ ci(T). Then, ci(S) = ci(S∗  ).  The next lemma considers parallel composition.  Lemma 3.3. Let Λ be a fair connection game on graph  G = G1||G2, where G1 and G2 are series parallel graphs. If  every fair connection game on the graphs G1 and G2   possesses a strong equilibrium, then the game Λ possesses a  strong equilibrium.  Proof. Let G1 = (V1, E1) and G2 = (V2, E2) have sources  s1 and s2 and sinks t1 and t2, respectively. Let Ti be the  set of players with an endpoint in Vi \ {s, t}, for i ∈ {1, 2}.  (An endpoint is either a source or a sink of a player). Let  T3 be the set of players j such that sj = s and tj = t. Let  Λ1 and Λ2 be the original game on the respective graphs G1  and G2 with players T1 ∪ T3 and T2 ∪ T3, respectively.  Let S and S be the SE in Λ1 and Λ2 that minimizes  the cost of players in T3, respectively. Assume w.l.o.g. that  ci(S ) ≤ ci(S ) where player i ∈ T3. In addition, let Λ2 be  the game on the graph G2 with players T2 and let ¯S be a  SE in Λ2.  We will show that the profile S = S ∪ ¯S is a SE in Λ.  Suppose by contradiction that S is not a SE. Then, there  is a coalition Γ that can deviate such that the cost of every  player j ∈ Γ decreases. By Lemma 3.2 and the assumption  that ci(S ) ≤ ci(S ), a player j ∈ T3 cannot improve his  cost. Therefore, Γ ⊆ T1 ∪ T2. But this is a contradiction to  S being a SE in Λ1 or ¯S being a SE in Λ2.  The following theorem considers the case of single source  fair connection games.  Theorem 3.4. Every single source fair connection game  on a series-parallel graph possesses a strong equilibrium.  Proof. We prove the theorem by induction on the   network size |V |. The claim obviously holds if |V | = 2. We  show the claim for a series composition, i.e., G = G1 → G2,  and for a parallel composition, i.e., G = G1||G2, where  G1 = (V1, E1) and G2 = (V2, E2) are SPG"s with sources  s1, s2, and sinks t1, t2, respectively.  series composition. Let G = G1 → G2. Let T1 be  the set of players j such that tj ∈ V1, and T2 be the set of  players j such that tj ∈ V2 \ {s2}.  Let Λ1 and Λ2 be the original game on the respective  graphs G1 and G2 with players T1 ∪ T2 and T2, respectively.  For every player i ∈ T2 with action Si in the game Λ let  Si ∩E1 be his induced action in the game Λ1, and let Si ∩E2  be his induced action in the game Λ2.  Let S be a SE in Λ1 that minimizes the cost of players in  T2 (such a SE exists by the induction hypothesis and Lemma  3.2). Let S be any SE in Λ2. We will show that the profile  S = S ∪ S is a SE in the game Λ, i.e., for player j ∈ T2 we  use the profile Sj = Sj ∪ Sj .  Suppose by contradiction that S is not a SE. Then, there  is a coalition Γ that can deviate such that the cost of every  player j ∈ Γ decreases. Now, there are two cases:  Case 1: Γ ⊆ T1. This is a contradiction to S being a SE.  Case 2: There exists a player j ∈ Γ ∩ T2. By Lemma 3.2,  player j cannot improve his cost in Λ1 so the improvement  is due to Λ2. Consider the coalition Γ ∩ T2, it would still  improve its cost. However, this contradicts the fact that S  is a SE in Λ2.  parallel composition. Follows from Lemma 3.3.  While multi-commodity fair connection games on series  parallel graphs do not necessarily possess a SE (see   Theorem 3.6), fair connection games on extension parallel graphs  always possess a strong equilibrium.  Theorem 3.5. Every fair connection game on an   extension parallel graph possesses a strong equilibrium.  87  t2  t1  s1  s2 2  2  1  3  3  1  (b)(a)  a  b  e  f  c  d  Figure 1: Graph topologies.  Proof. We prove the theorem by induction on the   network size |V |. Let Λ be a fair connection game on an EPG  G = (V, E). The claim obviously holds if |V | = 2. If the  graph G is a parallel composition of two EPG graphs G1  and G2, then the claim follows from Lemma 3.3. It remains  to prove the claim for extension composition. Suppose the  graph G is an extension composition of the graph G1   consisting of a single edge e = (s1, t1) and an EPG G2 = (V2, E2)  with terminals s2, t2, such that s = s1 and t = t2. (The case  that G2 is a single edge is similar.)  Let T1 be the set of players with source s1 and sink t1  (i.e., their path is in G1). Let T2 be the set of players with  source and sink in G2. Let T3 be the set of players with  source s1 and sink in V2 \ t1.  Let Λ1 and Λ2 be the original game on the respective  graphs G1 and G2 with players T1 ∪ T3 and T2 ∪ T3,   respectively. Let S , S be SE in Λ1 and Λ2 respectively. We will  show that the profile S = S ∪ S is a SE in the game Λ.  Suppose by contradiction that S is not a SE. Then, there is  a coalition Γ of minimal size that can deviate such that the  cost of any player j ∈ Γ decreases. Clearly, T1 ∩Γ = φ, since  players in T1 have a single strategy. Hence, Γ ⊆ T2 ∪T3. Any  player j ∈ T2 ∪T3 cannot improve his cost in Λ1. Therefore,  any player j ∈ T2 ∪ T3 improves his cost in Λ2. However,  this contradicts the fact that S is a SE in Λ2.  In the following theorem we provide a few examples of  topologies in which a strong equilibrium does not exist,  showing that our characterization is almost tight.  Theorem 3.6. The following connection games exist: (1)  There exists a multi-commodity fair connection game on a  series parallel graph that does not possess a strong   equilibrium. (2) There exists a single source fair connection game  that does not possess a strong equilibrium.  Proof. For claim (1) consider the graph depicted in   Figure 1(a). This game has a unique NE where S1 = {e, c},  S2 = {b, f}, and each player has a cost of 5.7  However,   consider the following coordinated deviation S . S1 = {a, b, c},  7  In any NE of the game, player 1 will buy the edge e and  player 2 will buy the edge f. This is since the alternate  path, in the respective part, will cost the player 2.5. Thus,  player 1 (player 2) will buy the edge c (edge b) alone, and  each player will have a cost of 5.  s  2 + 2  2  1 − 2  1 + 3  1  2 − 3  1 1  1  2 − 3  t1 t2  a  c  d e  f  h  g  b  Figure 2: Example of a single source connection game  that does not admit SE.  and S2 = {b, c, d}. In this profile, each player pays a cost of  4, and thus improves its cost.  For claim (2) consider a single source fair connection game  on the graph G depicted in Figure 2. There are two players.  Player i = 1, 2 wishes to connect the source s to its sink ti  and the unique NE is S1 = {a, b}, S2 = {a, c}, and each  player has a cost of 2. 8  Then, both players can deviate to  S1 = {h, f, d} and S2 = {h, f, e}, and decrease their costs  to 2 − /2.  Unfortunately, our characterization is not completely tight.  The graph in Figure 1(b) is an example of a non-extension  parallel graph which always admits a strong equilibrium.  3.2 Strong Price of Anarchy  While the price of anarchy in fair connection games can  be as bad as n, the following theorem shows that the strong  price of anarchy is bounded by H(n) = n  i=1  1  i  = Θ(log n).  Theorem 3.7. The strong price of anarchy of a fair   connection game with n players is at most H(n).  Proof. Let Λ be a fair connection game on the graph G.  We denote by Λ(Γ) the game played on the graph G by a set  of players Γ, where the action of player i ∈ Γ remains Σi (the  same as in Λ). Let S = (S1, . . . , Sn) be a profile in the game  Λ. We denote by S(Γ) = SΓ the induced profile of players in  Γ in the game Λ(Γ). Let ne(S(Γ)) denote the load of edge  e under the profile S(Γ) in the game Λ(Γ), i.e., ne(S(Γ)) =  |{j|j ∈ Γ, e ∈ Sj}|. Similar to congestion games [16, 13] we  denote by Φ(S(Γ)) the potential function of the profile S(Γ)  in the game Λ(Γ), where Φ(S(Γ)) = e∈E  ne(S(Γ))  j=1 fe(j),  and define Φ(S(φ)) = 0. In our case, it holds that  Φ(S) =  e∈E  ce · H(ne(S)). (1)  Let S be a SE, and let S∗  be the profile of the optimal  solution. We define an order on the players as follows. Let  Γn = {1, ..., n} be the set of all the players. For each k =  8  We can show that this is the unique NE by a simple case  analysis: (i) If S1 = {h, f, d} and S2 = {h, f, e}, then player  1 can deviate to S1 = {h, g} and decrease his cost. (ii) If  S1 = {h, g} and S2 = {h, f, e}, then player 2 can deviate to  S2 = {a, c} and decrease his cost. (iii) If S1 = {h, g} and  S2 = {a, c}, then player 1 can deviate to S1 = {a, b} and  decrease his cost.  88  n, . . . , 1, since S is a SE, there exists a player in Γk, w.l.o.g.  call it player k, such that,  ck(S) ≤ ck(S−Γk , S∗  Γk  ). (2)  In this way, Γk is defined recursively, such that for every  k = n, . . . , 2 it holds that Γk−1 = Γk \ {k}. (I.e., after the  renaming, Γk = {1, . . . , k}.)  Let ck(S(Γk)) denote the cost of player k in the game  Λ(Γk) under the induced profile S(Γk). It is easy to see that  ck(S(Γk)) = Φ(S(Γk)) − Φ(S(Γk−1)).9  Therefore,  ck(S) ≤ ck(S−Γk , S∗  Γk  ) (3)  ≤ ck(S∗  (Γk)) = Φ(S∗  (Γk)) − Φ(S∗  (Γk−1)).  Summing over all players, we obtain:  i∈N  ci(S) ≤ Φ(S∗  (Γn)) − Φ(S∗  (φ))  = Φ(S∗  (Γn)) =  e∈S∗  ce · H(ne(S∗  ))  ≤  e∈S∗  ce · H(n) = H(n) · OPT(Λ),  where the first inequality follows since the sum of the right  hand side of equation (3) telescopes, and the second equality  follows from equation (1).  Next we bound the SPoA when coalitions of size at most  k are allowed.  Theorem 3.8. The k-SPoA of a fair connection game  with n players is at most n  k  · H(k).  Proof. Let S be a SE of Λ, and S∗  be the profile of the  optimal solution of Λ. To simplify the proof, we assume that  n/k is an integer. We partition the players to n/k groups  T1, . . . , Tn/k each of size k. Let Λj be the game on the  graph G played by the set of players Tj. Let S(Tj) denote  the profile of the k players in Tj in the game Λj induced by  the profile S of the game Λ. By Theorem 3.7, it holds that  for each game Λj, j = 1, . . . , n/k,  costΛj (S(Tj)) =  i∈Tj  ci(S(Tj))  ≤ H(k) · OPT(Λj) ≤ H(k) · OPT(Λ).  Summing over all games Λj, j = 1, . . . , n/k,  costΛ(S) ≤  n/k  j=1  costΛj (S(Tj)) ≤  n  k  · H(k) · OPT(Λ),  where the first inequality follows since for each group Tj and  player i ∈ Tj, it holds that ci(S) ≤ ci(S(Tj)).  Next we show an almost matching lower bound. (The  lower bound is at most H(n) = O(log n) from the upper  bound and both for k = O(1) and k = Ω(n) the difference  is only a constant.)  Theorem 3.9. For fair connection games with n players,  k-SPoA ≥ max{n  k  , H(n)}.  9  This follows since for any strategy profile S, if a single  player k deviates to strategy Sk, then the change in the  potential value Φ(S) − Φ(Sk, S−k) is exactly the change in  the cost to player k.  t2  s  t1 tn−2 tn  1  2  t3 tn−1  1  1  3  1  n−2  2  n  1 +  00  0 0 0 00  0  Figure 3: Example of a network topology in which  SPoS > PoS.  Proof. For the lower bound of H(n) we observe that in  the example presented in [2], the unique Nash equilibrium  is also a strong equilibrium, and therefore k-SPoA = H(n)  for any 1 ≤ k ≤ n. For the lower bound of n/k, consider  a graph composed of two parallel links of costs 1 and n/k.  Consider the profile S in which all n players use the link  of cost n/k. The cost of each player is 1/k, while if any  coalition of size at most k deviates to the link of cost 1, the  cost of each player is at least 1/k. Therefore, the profile S  is a k-SE, and k-SPoA = n/k.  The results of Theorems 3.7 and 3.8 can be extended to  concave cost functions. Consider the extended fair   connection game, where each edge has a cost which depends on the  number of players using that edge, ce(ne). We assume that  the cost function ce(ne) is a nondecreasing, concave   function. Note that the cost of an edge ce(ne) might increase  with the number of players using it, but the cost per player  fe(ne) = ce(ne)/ne decreases when ce(ne) is concave.  Theorem 3.10. The strong price of anarchy of a fair   connection game with nondecreasing concave edge cost functions  and n players is at most H(n).  Proof. The proof is analogues to the proof of   Theorem 3.7. For the proof we show that cost(S) ≤ Φ(S∗  ) ≤  H(n)·cost(S∗  ). We first show the first inequality. Since the  function ce(x) is concave, the cost per player ce(x)/x is a  nonincreasing function. Therefore inequality (3) in the proof  of Theorem 3.7 holds. Summing inequality (3) over all   players we obtain cost(S) = i ci(S) ≤ Φ(S∗  (Γn))−Φ(S∗  (φ)) =  Φ(S∗  ). The second inequality follows since ce(x) is   nondecreasing and therefore ne  x=1(ce(x)/x) ≤ H(ne) · ce(ne).  Using the arguments in the proof of Theorem 3.10 and  the proof of Theorem 3.8 we derive,  Theorem 3.11. The k-SPoA of a fair connection game  with nondecreasing concave edge cost functions and n players  is at most n  k  · H(k).  Since the set of strong equilibria is contained in the set of  Nash equilibria, it must hold that SPoA ≤ PoA, meaning  that the SPoA can only be improved compared to the PoA.  However, with respect to the price of stability the opposite  direction holds, that is, SPoS ≥ PoS. We next show that  there exists a fair connection game in which the inequality  is strict.  89  2 − 2 − 2 − 3  s  t1 t2 t3  Figure 4: Example of a single source general connection  game that does not admit a strong equilibrium. The  edges that are not labeled with costs have a cost of zero.  Theorem 3.12. There exists a fair connection game in  which SPoS > PoS.  Proof. Consider a single source fair connection game on  the graph G depicted in Figure 3.10  Player i = 1, . . . , n  wishes to connect the source s to his sink ti. Assume that  each player i = 1, . . . , n − 2 has his own path of cost 1/i  from s to ti and players i = n − 1, n have a joint path of  cost 2/n from s to ti. Additionally, all players can share a  common path of cost 1+ for some small > 0. The optimal  solution connects all players through the common path of  cost 1 + , and this is also a Nash equilibrium with total  cost 1 + . It is easy to verify that the solution where each  player i = 1, . . . , n−2 uses his own path and users i = n−1, n  use their joint path is the unique strong equilibrium of this  game with total cost n−2  i=1  1  i  + 2  n  = Θ(log n)  While the example above shows that the SPoS may be  greater than the PoS, the upper bound of H(n) = Θ(log n),  proven for the PoS [2], serves as an upper bound for the  SPoS as well. This is a direct corollary from theorem 3.7, as  SPoS ≤ SPoA by definition.  Corollary 3.13. The strong price of stability of a fair  connection game with n players is at most H(n) = O(log n).  4. GENERAL CONNECTION GAMES  In this section, we derive our results for general connection  games.  4.1 Existence of Strong Equilibrium  We begin with a characterization of the existence of a  strong equilibrium in symmetric general connection games.  Similar to Theorem 3.1 (using a similar proof) we establish,  Theorem 4.1. In every symmetric fair connection game  there exists a strong equilibrium.  While every single source general connection game   possesses a pure Nash equilibrium [3], it does not necessarily  admit some strong equilibrium.11  10  This is a variation on the example given in [2].  11  We thank Elliot Anshelevich, whose similar topology for  the fair-connection game inspired this example.  Theorem 4.2. There exists a single source general   connection game that does not admit any strong equilibrium.  Proof. Consider single source general connection game  with 3 players on the graph depicted in Figure 4. Player i  wishes to connect the source s with its sink ti.We need to  consider only the NE profiles: (i) if all three players use the  link of cost 3, then there must be two agents whose total  sum exceeds 2, thus they can both reduce cost by deviating  to an edge of cost 2− . (ii) if two of the players use an edge  of cost 2− jointly, and the third player uses a different edge  of cost 2 − , then, the players with non-zero payments can  deviate to the path with the edge of cost 3 and reduce their  costs (since before the deviation the total payments of the  players is 4 − 2 ). We showed that none of the NE are SE,  and thus the game does not possess any SE.  Next we show that for the class of series parallel graphs,  there is always a strong equilibrium in the case of a single  source.  Theorem 4.3. In every single source general connection  game on a series-parallel graph, there exists a strong   equilibrium.  Proof. Let Λ be a single source general connection game  on a SPG G = (V, E) with source s and sink t. We present an  algorithm that constructs a specific SE. We first consider the  following partial order between the players. For players i and  j, we have that i → j if there is a directed path from ti to tj.  We complete the partial order to a full order (in an arbitrary  way), and w.l.o.g. we assume that 1 → 2 → · · · → n.  The algorithm COMPUTE-SE, considers the players in  an increasing order, starting with player 1. Each player i  will fully buy a subset of the edges, and any player j > i  will consider the cost of those (bought) edges as zero. When  COMPUTE-SE considers player j, the cost of the edges  that players 1 to j−1 have bought is set to zero, and player j  fully buys a shortest path Qj  from s to tj. Namely, for every  edges e ∈ Qj  \ ∪i<jQi  we have pj(e) = ce and otherwise  pj(e) = 0. We next show that the algorithm   COMPUTESE computes a SE.  Assume by way of contradiction that the profile p is not a  SE. Then, there exists a coalition that can improve the costs  of all its players by a deviation. Let Γ be such a coalition  of minimal size and let player i = max{j ∈ Γ}. For a player  j ∈ Γ let ¯Qj  and ¯pj  be the path and payment of player  j after the deviation, respectively. Let Q be a path from  the sink of player i, i.e. ti, to the sink of G, i.e. t. Then  Q = ¯Qi  ∪ Q is a path from the source s to the sink t. For  any player j < i, let yj be the intersecting vertex of Q and  tj (by Lemma 2.1 one is guarantee to exist). Let y be the  furthest vertex on the path Q such that y = yj for some  j < i. The path from the source s to node y was fully paid  for by players j < i in p (before the deviation). There are  two cases we consider.  case a: After the deviation player i does not pay for edges  in j∈Γ\{i}  ¯Qj  . This is a contradiction to the minimality of  the coalition Γ size, since the players in Γ \ {i} can form a  smaller coalition with payments ¯p.  case b: Otherwise, we show that player i cost after the   deviation, i.e. ci(¯p), is at least his cost before the deviation, i.e.  ci(p), contradicting the fact that player i improved his cost.  Recall that given two vertices u, v on path ¯Q we denote by  ¯Qu,v the subpath of ¯Q from u to v.  90  Before the deviation of the coalition Γ, a path from s to  y was fully paid for by the players j < i. Next we show that  no player k > i pays for any edge on any path from s to ti.  Consider a player k > i and let Qk = Qk  ∪ Qk , where Qk is  a path connecting tk to t. Let yk be the intersecting vertex  of Qk and ti. Since there exists a path from s to yk that was  fully paid for by players j < k before the deviation, in   particularly the path Qi  s,yk  , player k will not pay for any edge  on any path connecting s and yk. Therefore player i fully  pays for all edges on the path ¯Qi  y,ti  , i.e., ¯pi(e) = ce for all  edges e ∈ ¯Qi  y,ti  . Now consider the algorithm   COMPUTESE at the step when player i selects a shortest path from  the source s to its sink ti and determines his payment pi. At  this point, player i could buy the path ¯Qi  y,ti  , since a path  from s to y was already paid for by players j < i. Hence,  ci(¯p) ≥ ci(p). This contradicts the fact that player i   improved its cost and therefore not all the players in Γ reduce  their cost. This implies that p is a strong equilibrium.  4.2 Strong Price of Anarchy  While for every single source general connection game, it  holds that PoS = 1 [3], the price of anarchy can be as large  as n, even for two parallel edges. Here, we show that any  strong equilibrium in single source general connection games  yields the optimal cost.  Theorem 4.4. In single source general connection game,  if there exists a strong equilibrium, then the strong price of  anarchy is 1.  Proof. Let p = (p1, . . . , pn) be a strong equilibrium, and  let T∗  be the minimum cost Steiner tree on all players,  rooted at the (single) source s. Let T∗  e be the subtree of  T∗  disconnected from s when edge e is removed. Let Γ(Te)  be the set of players which have sinks in Te. For a set of  edges E, let c(E) = e∈E ce. Let P(Te) = i∈Γ(Te) ci(p).  Assume by way of contradiction that c(p) > c(T∗  ). We  will show that there exists a sub-tree T of T∗  , that connects  a subset of players Γ ⊆ N, and a new set of payments ¯p, such  that for each i ∈ Γ, ci(¯p) < ci(p). This will contradict the  assumption that p is a strong equilibrium.  First we show how to find a sub-tree T of T∗  , such that  for any edge e, the payments of players with sinks in T∗  e is  more than the cost of T∗  e ∪ {e}. To build T , define an edge  e to be bad if the cost of T∗  e ∪ {e} is at least the payments  of the players with sinks in T∗  e , i.e., c(T∗  e ∪ {e}) ≥ P(T∗  e ).  Let B be the set of bad edges. We define T to be T∗  −  ∪e∈B(T∗  e ∪ {e}). Note that we can find a subset B of B  such that ∪e∈B(T∗  e ∪ {e}) is equal to ∪e∈B (T∗  e ∪ {e}) and  for any e1, e2 ∈ B we have T∗  e1  ∩ T∗  e2  = ∅. (The set B will  include any edge e ∈ B for which there is no other edge  e ∈ B on the path from e to the source s.) Considering  the edges in e ∈ B we can see that any subtree T∗  e we  delete from T can not decrease the difference between the  payments and the cost of the remaining tree. Therefore, in  T for every edge e, we have that c(Te ∪ {e}) < P(Te).  Now we have a tree T and our coalition will be Γ(T ).  What remain is to find payments ¯p for the players in Γ(T )  such that they will buy the tree T and every player in Γ(T )  will lower its cost, i.e. ci(p) > ci(¯p) for i ∈ Γ(T ). (Recall  that the payments have the restriction that player i can only  pay for edges on the path from s to ti.)  We will now define the coalition payments ¯p. Let ci(¯p,  Te) = e∈Te  ¯pi(e) be the payments of player i for the   subtree Te. We will show that for every subtree Te, ci(¯p, Te ∪  {e}) < ci(p), and hence ci(¯p) < ci(p). Consider the   following bottom up process that defines ¯p. We assign the  payments of edge e in T , after we assign payments to all  the edges in Te. This implies that when we assign payments  for e, we have that the sum of the payments in Te is equal to  c(Te) = i∈Γ(Te) ci(¯p, Te). Since e was not a bad edge, we  know that c(Te ∪ {e}) = c(Te) + ce < P(Te). Therefore, we  can update the payments ¯p of players i ∈ Γ(Te), by setting  ¯pi(e) = ce∆i/( j∈Γ(Te) ∆j), where ∆j = cj(p) − cj(¯p, Te).  After the update we have for player i ∈ Γ(Te),  ci(¯p, Te ∪ {e}) = ci(¯p, Te) + ¯pi(e)  = ci(¯p, Te) + ∆i  ce  j∈Γ(Te) ∆j  = ci(p) − ∆i(1 −  ce  P(Γ(Te)) − c(Te)  ),  where we used the fact that j∈Γ(Te) ∆j = P(Γ(Te))−c(Te).  Since ce < P(Γ(Te)) − c(Te) it follows that ci(¯p, Te ∪ {e}) <  ci(p).  5. REFERENCES  [1] N. Andelman, M. Feldman, and Y. Mansour. Strong  Price of Anarchy. In SODA"07, 2007.  [2] E. Anshelevich, A. Dasgupta, J. M. Kleinberg,  ´E. Tardos, T. Wexler, and T. Roughgarden. The price  of stability for network design with fair cost  allocation. In FOCS, pages 295-304, 2004.  [3] E. Anshelevich, A. Dasgupta, E. Tardos, and  T. Wexler. Near-Optimal Network Design with Selfish  Agents. In STOC"03, 2003.  [4] R. Aumann. Acceptable Points in General  Cooperative n-Person Games. In Contributions to the  Theory of Games, volume 4, 1959.  [5] A. Czumaj and B. V¨ocking. Tight bounds for  worst-case equilibria. In SODA, pages 413-420, 2002.  [6] A. Fabrikant, A. Luthra, E. Maneva,  C. Papadimitriou, and S. Shenker. On a network  creation game. In ACM Symposium on Principles of  Distriubted Computing (PODC), 2003.  [7] R. Holzman and N. Law-Yone. Strong equilibrium in  congestion games. Games and Economic Behavior,  21:85-101, 1997.  [8] R. Holzman and N. L.-Y. (Lev-tov). Network structure  and strong equilibrium in route selection games.  Mathematical Social Sciences, 46:193-205, 2003.  [9] E. Koutsoupias and C. H. Papadimitriou. Worst-case  equilibria. In STACS, pages 404-413, 1999.  [10] I. Milchtaich. Topological conditions for uniqueness of  equilibrium in networks. Mathematics of Operations  Research, 30:225244, 2005.  [11] I. Milchtaich. Network topology and the efficiency of  equilibrium. Games and Economic Behavior,  57:321346, 2006.  [12] I. Milchtaich. The equilibrium existence problem in  finite network congestion games. Forthcoming in  Lecture Notes in Computer Science, 2007.  [13] D. Monderer and L. S. Shapley. Potential Games.  Games and Economic Behavior, 14:124-143, 1996.  [14] H. Moulin and S. Shenker. Strategyproof sharing of  91  submodular costs: Budget balance versus efficiency.  Economic Theory, 18(3):511-533, 2001.  [15] C. Papadimitriou. Algorithms, Games, and the  Internet. In Proceedings of 33rd STOC, pages 749-753,  2001.  [16] R. W. Rosenthal. A class of games possessing  pure-strategy Nash equilibria. International Journal of  Game Theory, 2:65-67, 1973.  [17] T. Roughgarden. The Price of Anarchy is Independent  of the Network Topology. In STOC"02, pages 428-437,  2002.  [18] T. Roughgarden and E. Tardos. How bad is selfish  routing? Journal of the ACM, 49(2):236 - 259, 2002.  [19] O. Rozenfeld and M. Tennenholtz. Strong and  correlated strong equilibria in monotone congestion  games. In Workshop on Internet and Network  Economics, 2006.  92