Network Formation Games

Scenario

• Consider users constructing a shared network

  • Each user has its own interest and is driven by:

  • Minimising the price he pays for creating/using the network

• Receiving a high quality of service

• We wish to model the networks generated by such selfish behaviour(自私的行为) of the users and compare them to the optimal networks

Objectives

• How to evaluate the overall quality of a network?

  • social cost = sum of players’ costs

• What are stable networks?

  • we use Nash equilibrium as solution concept

  • we refer to networks corresponding to Nash equilibrium as being stable

Global Connection Game

• Global connection game:

  • users want to connect two nodes si , ti in the network // 用户想在网络中链接 si, ti

  • users share the cost of used edges // 用户分享已使用边的花销

  • users minimise their cost // 用户最小化他们的（通信）花销

  • Resembles (似) use of a large scale shared network

• Model

• Directed G=(V,E) with non-negative edge cost ce.

• k players , each player i ∈ [k] has a source si and sink node ti

• A strategy for a player i is a path Pi from si to ti in G.

• Given a strategy profile S = (P1,…,Pk), we define the constructed network to be ∪i Pi .

• Players who use edge e divide the cost ce according to some cost sharing mechanism.

• We will consider the equal-division(等分) mechanism:

  // Sum(每条边的花销 / 人数) = Cost ce

  

• Example

Existence of Stable Networks

• Does every global connection game have a pure Nash equilibrium? Y

  This is because it is a special congestion game! ce(x) = ce/x

• Rosenthal’s potential function

  

Price of Anarchy

• Example

  

• Theorem 4.1

  For any global connection game with k players, PoA ≤ k.

• Some definitions

  • PoA(Price of Anarchy): worst NE

  • PoS(Price of Stabity): best NE

• Definition: Price of Stability

  

Potential Games and Price of Stability

• Potential Games: All games that admit a potential function Φ, s.t. for all outcomes s, all player i, and all alternative strategies si′,

  Ci (si′, s−i ) − Ci (s) = Φ(si′, s−i ) − Φ(s).

• Existence of Equilibrium: Φ(s) minimal ⇒ s is a Nash equilibrium.

• Theorem 4.2

  • Suppose that we have a potential game with potential function Φ, and assume that for any outcome s, we have

    (SC(s) / A) ≤ Φ(s) ≤ B · SC(s)

  for some constants A, B ≥ 0. Then the price of stability is at most A · B.

• Lemma 4.3

  • For any strategy profile S = (P1,…,Pk) we have SC(S) ≤ Φ(S) ≤ Hk · SC(S)

  

• Theorem 4.4

  • The price of stability in the global connection game with k players is at mostHk =Θ(logk).

• Theorem 4.5

  • The price of stability in the global connection game with k players is at least Hk.

• Finding PoS Lower bound α

Similarly to the PoA, we need to construct an instance with PoS ≥ α. But here all equilibria should be at least α away from optimal solution.