Koster A., Munoz X. Graphs and Algorithms in Communication Networks

Подождите немного. Документ загружается.

8 Optimization of OSPF Routing in IP Networks 239

41. Feldmann, A., Greenberg, A., Lund, C., Reingold, N., Rexford, J.: NetScope: Trafﬁc engi-

neering for IP networks. IEEE Transactions on Networking 14, 11–19 (2000)

42. Fortz, B., Thorup, M.: Internet trafﬁc engineering by optimizing OSPF weights. In: Proceed-

ings of IEEE INFOCOM’00, pp. 519–528 (2000)

43. Fortz, B., Thorup, M.: Optimizing OSPF/IS-IS weights in a changing world. IEEE Journal on

Selected Areas in Communications 20(4), 756–767 (2002)

44. Fortz, B., Thorup, M.: Robust optimization of OSPF/IS-IS weights. In: W. Ben-Ameur,

A. Petrowski (eds.) Proc. INOC 2003, pp. 225–230 (2003)

45. Fortz, B., Thorup, M.: Increasing Internet capacity using local search. Computational Opti-

mization and Applications 29(1), 13–48 (2004)

46. Gajowniczek, P., Pi

oro, M., Szentesi, A., Harmatos, J., J

uttner, A.: Solving an OSPF routing

problem with simulated allocation. In: Proceedings of 1st Polish-German Teletrafﬁc Sympo-

sium, pp. 177–184. Dresden, Germany (2000)

47. Gerla, M., Kleinrock, L.: Communication nets: stochastic message ﬂow and delay 25(1), 48–

60 (1977)

48. de Giovanni, L., Fortz, B., Labb

e, M.: A lower bound for the Internet protocol network design

problem. In: Proceedings of the 2nd International Network Optimization Conference (INOC

2005), Lisbon, Portugal, vol. 1, pp. 402–408 (2005)

49. Gourdin, E.: Optimizing internet networks. ORMS Today 28(2), 46–49 (2001)

50. Gourdin, E., Klopfenstein, O.: Comparison of different QoS-oriented objectives for multi-

commodity ﬂow routing optimization. In: Proceedings of the International Conference on

Telecommunications (ICT 2006) (2006)

51. Holmberg, K., Yuan, D.: A Lagrangian heuristic based branch-and-bound approach for the

capacitated network design problem. Operations Research 48, 461–481 (2000)

52. Holmberg, K., Yuan, D.: Optimization of Internet protocol network design and routing. Net-

works 43(1), 39–53 (2004)

53. ILOG CPLEX Division, 889 Alder Avenue, Suite 200, Incline Village, NV 89451, USA:

CPLEX 11.0 Reference Manual (2007). URL http://www.cplex.com

54. J

uttner A. Szentesi, A., Harmatos, J., Pi

oro, M.: On solvability of an OSPF routing problem.

In: Proc. 15th Nordic Teletrafﬁc Seminar (2000)

55. Karas, P., Pi

oro, M.: Optimization problems related to the assignment of administrative

weights in the IP networks routing protocols. In: Proceedings of the 1st Polish-German Tele-

trafﬁc Symposium PGTS’2000, pp. 185–192 (2000)

56. Klopfenstein, O., Mamy, S.: Choosing weights for IP network dimensioning optimization. In:

Proc. of the International Symposium on Computers and Communications (ISCC 2006), pp.

994–999 (2006)

57. Leduc, G., Abrahamsson, H., Balon, S., Bessler, S., D’Arienzo, M., Delcourt, O., Domingo-

Pascual, J., Cerav-Erbas, S., Gojmerac, I., Masip, X., Pescaph, A., Quoitin, B., Romano, S.,

Salvatori, E., Skiv

ee, F., Tran, H., Uhlig, S.,

Umit, H.: An open source trafﬁc engineering

toolbox. Computer Communications, 29(5), 593–610 (2006)

58. Lin, F., Wang, J.: Minimax open shortest path ﬁrst routing algorithms in networks suporting

the SMDS service. In: Proceedings of the IEEE International Conference on Communications

1993 (ICC’93), Geneva, Suisse, vol. 2, pp. 666–670 (1993)

59. Menth, M., Hartmann, M., Martin, R.: Robust IP link costs for multilayer resilience. In:

Networking. Atlanta, GA, USA (2007)

60. Milbrandt, J.: Possibilities of routing optimization in IP networks. Master’s thesis, Department

of Computer Science, University of W

urzburg (2001)

61. Moy, J.: OSPF: Anatomy of an Internet Routing Protocol. Addison-Wesley (1998)

62. Mulyana, E., Killat, U.: An alternative genetic algorithm to optimize OSPF weights. In: Inter-

net Trafﬁc Engineering and Trafﬁc Management, 15th ITC Specialist Seminar, pp. 186–192

(July 2002). W

urzburg, Germany

63. Nemhauser, G., Wolsey, L.: Integer and Combinatorial Optimization. John Wiley & Sons

(1988)

240 A. Bley et al.

64. Nucci, A., Schroeder, B., Bhattacharyya, S., Taft, N., Diot, C.: IGP link weight assignment for

transient link failures. In: Proceedings of 18th International Teletrafﬁc Congress, pp. 321–330

(2003)

65. Oran, D.: OSI IS-IS intra-domain routing protocol. Internet RFC 1142 (1990).

Http://www.ietf.org/rfc/rfc1142.txt

66. Orlowski, S., Pi

oro, M., Tomaszewski, A., Wess

aly, R.: SNDlib 1.0–Survivable Network De-

sign Library. In: Proceedings of the 3rd International Network Optimization Conference

(INOC 2007), Spa, Belgium (2007). http://sndlib.zib.de

67. Parmar, A., Ahmed, S., Sokol, J.: An integer programming approach to the OSPF weight

setting problem. Optimization Online (2005)

68. Pi

oro, M., Medhi, D.: Routing, Flow, and Capacity Design in Communication and Computer

Networks. Morgan Kaufman (2004)

69. Pi

oro, M., Szentesi, A., Harmatos, J., J

uttner, A.: On OSPF related network optimization prob-

lems. In: 8th IFIP Workshop on Performance Modelling and Evaluation of ATM & IP Net-

works, pp. 70/1–70/14. Ilkley, UK (2000)

70. Pi

oro, M., Szentesi, A., Harmatos, J., J

uttner, A., Gajowniczek, P., Kozdrowski, S.: On OSPF

related network optimization problems. Performance Evaluation 48, 201–223 (2002). (A

preliminary version of this paper appeared in the proc. IFIP ATM IP 2000, Ilkley, England,

July 2000)

71. Pi

oro, M., Tomaszewski, A.: Feasibility issues in shortest-path routing with trafﬁc ﬂow split.

In: Proceedings of the 3rd International Network Optimization Conference (INOC 2007), Spa,

Belgium (2007)

72. Pi

oro, M., Tomaszewski, A., Dzida, M., Mycek, M., Zago

zon, M.: Literature survey, mod-

els, polyhedral results, and exact and heuristic methods for shortest-path routing problems.

Technical report, Institute of Telecommunications, Warsaw University of Technology (2007)

73. Prytz, M.: On optimization in design of telecommunications networks with multicast and uni-

cast trafﬁc. Ph.D. thesis, Royal Institute of Technology, Stockholm, Sweden (2002)

74. Ramalingam, G., Reps, T.: An incremental algorithm for a generalization of the shortest-path

problem. Jounal of Algorithms 21(2), 267–305 (1996)

75. Rexford, J.: Handbook of Optimization in Telecommunications, chap. Route optimization in

IP networks (2006)

76. Srivastava, S., Agrawal, G., Pi

oro, M., Medhi, D.: Determining link weight system under

various objectives for OSPF networks using a lagrangean relaxation-based approach. IEEE

e-Transactions on Network and Service Management 2(1), 9–18 (2005)

77. Staehle, D., K

ohler, S., Kohlhaas, U.: Towards an optimization of the routing parameters

for IP networks. Technical Report TR 258, Department of Computer Science, University

of W

urzburg (2000)

78. Tomaszewski, A., Pi

oro, M., Dzida, M., Mycek, M., Zago

zon, M.: Valid inequalities for a

shortest-path routing optimization problem. In: Proceedings of the 3rd International Network

Optimization Conference (INOC 2007), Spa, Belgium (2007)

79. Tomaszewski, A., Pi

oro, M., Dzida, M., Zago

zon, M.: Optimization of administrative

weights in IP networks using the branch-and-cut approach. In: Proceedings of the 2nd Interna-

tional Network Optimization Conference (INOC 2005), Lisbon, Portugal, vol. 2, pp. 393–400

(2005)

80. Tong, C., Lam, K.: An embedded connectionist approach for the inverse shortest paths prob-

lem. Technical report, Department of Systems Engineering and Engineering Management,

The Chinese University of Hong Kong (1996)

81.

Umit, H., Fortz, B.: Fast heuristic techniques for intra-domain routing metric optimization. In:

Proc. INOC 2007 (2007)

82. Wang, Y., Wang, Z., Zhang, L.: Interenet trafﬁc engineering without full mesh overlaying. In:

Proc. INFOCOM’2001 (2001). New York, USA

83. Wolsey, L.: Integer Programming. John Wiley & Sons (1998)

84. Xiao, X., Hannan, A., Bailey, B., Ni, L.: Trafﬁc engineering with MPLS in the Internet. IEEE

Network 14, 28–33 (2000)

Chapter 9

Game-Theoretic Approaches to Optimization

Problems in Communication Networks

Vittorio Bil

o, Ioannis Caragiannis, Angelo Fanelli, Michele Flammini, Christos

Kaklamanis, Gianpiero Monaco, and Luca Moscardelli

Abstract In this chapter we consider fundamental optimization problems arising in

communication networks. We consider scenarios where there is no central authority

that coordinates the network users in order to achieve efﬁcient solutions. Instead,

the users act in an uncoordinated and selﬁsh manner and reach solutions to the

above problems that are consistent only with their selﬁshness. In this sense, the

users act aiming to optimize their own objectives with no regard to the globally

optimum system performance. Such a behavior poses several intriguing questions

ranging from the deﬁnition of reasonable and practical models for studying it to the

quantiﬁcation of the efﬁciency loss due to the lack of users’ cooperation. We present

several results we achieved recently in this research area and propose interesting

future research directions.

Key words: non-cooperative networks, strategic games, Nash equilibria, price of

anarchy, price of stability

Vittorio Bil

Department of Mathematics, University of Salento, Provinciale Lecce-Arnesano, P.O. Box 193,

73100 Lecce, Italy, e-mail: vittorio.bilo@unile.it

Ioannis Caragiannis · Christos Kaklamanis

Computer Technology Institute & Department of Computer Engineering and Informatics, Univer-

sity of Patras, 26500 Rio, Greece, e-mail: caragian,kakl@ceid.upatras.gr

Angelo Fanelli · Michele Flammini · Gianpiero Monaco · Luca Moscardelli

Dipartimento di Informatica, Universit

a degli Studi dell’Aquila,

Via Vetoio, Loc. Coppito, 67100 L’Aquila, Italy, e-mail:

angelo.fanelli,flammini,gianpiero.monaco,moscardelli@di.univaq.it

A.M.C.A. Koster, X. Mu

noz (eds.), Graphs and Algorithms in Communication 241

Networks, Texts in Theoretical Computer Science. An EATCS Series,

DOI 10.1007/978-3-642-02250-0

 Springer-Verlag Berlin Heidelberg 2010

242 V. B i l

oetal.

9.1 Introduction

In the last few years, a mutual interest between the community of computer sci-

entists and of economists is emerging, especially concerning the relationships be-

tween Distributed Systems and Game Theory. The trigger for this synergy is the

evolution of uncoordinated and non-cooperative communication networks such as

the Internet, peer-to-peer networks, and wireless ad hoc networks, and the conse-

quent diversity of the owners of the relative physical components (routers, comput-

ing devices, communication channels, etc.). This has determined a radical change

in the deﬁnition of what distributed computing means. Indeed, in the classical com-

putational model adopted in Theoretical Computer Science, processors are faithful

executors of an algorithm. Conversely, in the incentive-based model, which is the

one traditionally studied by economists, processors (usually called agents) pursue

a selﬁsh strategy and the system evolves as a consequence of the complex interac-

tions among them. Therefore, Game Theory comes to pursue the synthesis between

two requirements: the system designer’s or operator’s (whose goal is to compute a

socially efﬁcient solution), and the agents’ (which, in a non-cooperative scenario,

aim to maximize their own proﬁt and, therefore, could induce the system to reach

suboptimal solutions).

Let us introduce informally the concepts studied in this chapter with an example.

Assume that we have a simple communication network in which two nodes s and t

are connected through two directed links e

and e

(see Figure 9.1). There are two

users, each having a unit amount of trafﬁc. Each user wishes to route her trafﬁc from

s to t unsplit, using one of the two links. Link e

has a latency function d

(x)=x,

which means that the latency experienced by each user that uses this link is x when

x users in total use this link. The latency function of link e

is d

(x)=2+

, where

is a negligible but strictly positive constant. A natural objective is to minimize

the average (or total) latency among the two users. So, from the network designer

point of view, a solution which forces one user to use link e

and the other to use

link e

would be the desired one with a total latency of 3 +

. However, if each

user is selﬁsh in the sense that she prefers to use the link which minimizes her

latency given the decision of the other user, we could never end up with this desired

solution. The user that is assigned to link e

(where she experiences a latency of

2 +

) has an incentive to change her strategy and use link e

instead; then, the

latency experienced would be only 2. From this latter assignment, no user has an

incentive to unilaterally deviate; such a solution is consistent with the selﬁsh nature

of the behavior of the users. Unfortunately, selﬁshness may result in deterioration

of system performance; the total latency in this latter solution is 4 since both users

experience a latency of 2 on link e

In the above example, we have implicitly assumed that users (called players in

the following) play a strategic game which reﬂects their selﬁsh behavior. Solutions

that are consistent with this behavior are called equilibria; these notions are for-

mally deﬁned in the next section. Issues related to the existence, the structure, the

computation, and the efﬁciency of equilibria in strategic games arising from opti-

mization problems are studied (among other issues) in the recently emerging ﬁeld

9 Game-Theoretic Approaches to Optimization Problems in Communication Networks 243

Fig. 9.1 A simple communication network

of Algorithmic Game Theory. In this chapter we present some basic contributions in

this fascinating emerging area related to some fundamental optimization problems

that arise in communication networks with non-cooperative users. We focus on re-

sults which we have obtained recently; the interested reader may see [39] for a more

systematic study of the recent trends in Algorithmic Game Theory.

9.2 Preliminary Notions

We begin with some necessary deﬁnitions. Given a set U,ak-tuple a =(u

,...,u

)

of elements of U, an index i ∈{1,...,k}, and an element u ∈U, we write (a

−i

,u)=

,...,u

i−1

,u,u

i+1

,...,u

) to denote the k-tuple obtained from a by replacing u

with u.

Strategic games. A strategic game G is a triple G =(P,S

i∈P

) where P is a set

of n players, S

is the set of strategies available to player i and

: S

×...×S

→IR

is her payoff function. The payoff function

can model either a beneﬁt or a cost

for player i; thus each player may seek the maximization or the minimization of her

payoff. In the sequel we will always assume that the payoff functions model costs

for the players.

States and improving steps. The set S = S

×...×S

is called the set of states or

strategy proﬁles of G . Consider a state

,...,

) ∈ S. A player i cannot be

happy with her payoff in

if there exists another state



−i

,s),forsomes ∈S

such that

(



) <

(

). The action of changing their strategy from

to s (with

the consequent transition of G from state

to state



) is called an improving step

or a selﬁsh move performed by player i.

Pure Nash equilibria. A very important and challenging issue in game theory is

to characterize solutions of games which are consistent with the selﬁsh and ratio-

nal behavior of the players. Among all the approaches proposed so far, the notion

of Nash equilibrium is the most accepted and used one. A state

is a pure Nash

equilibrium if no player has an improving step, that is, ∀i ∈ P and ∀s ∈ S

it holds

(

−i

,s) ≥

(

). A pure Nash equilibrium is a stable outcome of a game in the

sense that it is a state in which all players are satisﬁed with their payoff and none

244 V. B i l

oetal.

of them can improve it by unilaterally changing her strategy. The drawback of this

notion is, however, due to the fact that pure Nash equilibria are not guaranteed to

exist for any game.

Mixed strategies. A mixed strategy for player i is a probability distribution Y

de-

ﬁned over the set S

of her pure strategies. Given a mixed strategy Y

for player i,

the support of Y

, denoted as support(Y

),isthesetofstrategiess ∈ S

for which

(s) > 0. A mixed strategy Y =(Y

...,Y

) is an n-tuple of mixed strategies Y

for

each player i ∈ P. The support of a mixed strategy Y is deﬁned as the set of states

support(Y )=support(Y

) ×...×support(Y

). The payoff of player i yielded by

a mixed strategy Y is deﬁned as

(Y )=

∑

∈support(Y)

(

) ·Prob

(

)), where

Prob

(

∏

i=1

(

Mixed Nash equilibria. A mixed strategy Y is a (mixed) Nash equilibrium if

∀i ∈ P and for any probability distribution Z deﬁned over S

it holds

−i

,Z) ≥

(Y ). A fully mixed Nash equilibrium Y is a mixed Nash equilibrium such that

support(Y

)=S

for each i ∈ P. Mixed Nash equilibria are, hence, a generalization

of pure ones, obtained by allowing players to randomize on their chosen strategies

and computing the resulting payoffs in expectation. In this case the solution con-

cept becomes less reasonable (since, in practice, we are always asked to choose

pure strategies); but, on the other hand, Nash’s famous theorem [38] guarantees the

existence of at least one mixed Nash equilibrium for any game.

Price of anarchy and stability. One of the main concerns when dealing with non-

cooperative systems is to bound their inefﬁciencies due to the lack of coordination

among the players. More formally, given a function

: S → IR, called the social

function, let

∗

be a state optimizing

. On the other hand, given a mixed strat-

egy Y , the social value of Y is deﬁned as

(Y )=

∑

∈support(Y)

(

) ·Prob

(

)).

The price of anarchy [35] of game G for the social function

is deﬁned as

PoA(G ,

)=sup

Y∈NE(G )

(Y)

(

∗

)

, while the price of stability [3] of G for the social

function

is deﬁned as PoS(G ,

)=inf

Y∈NE(G )

(Y)

(

∗

)

, where NE(G ) denotes the set

of Nash equilibria of G . By restricting NE(G ) to the set of pure Nash equilibria,

similar deﬁnitions for the price of anarchy and stability are obtained for pure strate-

gies. The price of anarchy is a classical worst-case analysis and it measures the loss

of performance due to the selﬁsh behavior of players in this case. On the other hand,

the price of stability gives us information on the minimum loss of performance a

non-cooperative system has to suffer. This issue is best understood when dealing

with games, such as network design games, in which it is possible to assume the

presence of a central authority proposing or imposing a pure Nash equilibrium to

the players. In this setting, the best Nash equilibrium represents the optimal solu-

tion among all the proposed ones from which no player would have an incentive to

defect. By extending the above deﬁnition, the price of anarchy after a best response

walk can be deﬁned as the worst-case ratio of the social value of the last state of the

walk to the value of the social optimum.

9 Game-Theoretic Approaches to Optimization Problems in Communication Networks 245

Nash dynamics graph. For any game G it is possible to deﬁne a graph D(G )=

(S,A) capturing the dynamic behavior of the players in the game. The set of nodes

of D(G ) is represented by the set of states of G , and there is a directed edge between

any two nodes

and



with label i if and only if player i has an improving step

from



in G . By deﬁnition, we have that G possesses pure Nash equilibria

if and only if D(G ) has sink nodes, that is, nodes without any outgoing edge. An

important issue related to the notion of pure Nash equilibria is the ﬁnite improve-

ment path (FIP) property. A game has this property if, starting from any initial state

and letting a player perform arbitrary improving steps, a pure Nash equilibrium is

always reached, i.e., there does not exist an inﬁnite sequence of improving steps.

Again, by deﬁnition, we have that G has the FIP property if and only if D(G ) is

acyclic, that is, a DAG (directed acyclic graph). In a given state a player i may have

more than one improving step, i.e., for a given node there may exist more than one

outgoing edge labeled i in D(G ). An improving step for player i in state

is a best

response for i in

if it yields the maximum improvement in i’s payoff among all

improving steps i has in

. We deﬁne the best response dynamics graph of G as the

graph obtained from D(G ) by removing all edges not modeling best responses.

Best response walks. Any path in the best response dynamics graph is called a

best response walk. As there are games that do not have the FIP property as well as

games for which the number of best responses (or, more generally, improving steps)

needed to reach an equilibrium starting from an arbitrary state may be exponentially

large, it becomes important to evaluate the social value of states reached after a

ﬁnite number of selﬁsh moves. To this aim, Mirrokni and Vetta [36] introduced the

following models capturing the intuitive notion of a fair sequence of moves.

Covering walk. A walk in the best response dynamics graph is a covering walk if

for each player i, it has at least one edge with label i.

k-Covering walk. A walk in the best response dynamics graph is a k-covering

walk if it can be split into k disjoint covering walks.

One-round walk. A covering walk of length n in the best response dynamics

graph is a one-round walk, that is, each player performs exactly one best re-

sponse.

Potential games. If G has the FIP property then, by exploiting the topological or-

dering of the nodes in D(G ), it is possible to deﬁne a potential function for G , that

is, a function

: S → IR always decreasing or always increasing each time an im-

proving step is performed. By generalizing this observation, it is possible to deﬁne

the class of potential games as the class of all games having a potential function and,

hence, the FIP property. Depending on the properties satisﬁed by

, three different

kinds of potential games can be deﬁned.

1. Exact potential games, where ∀

∈ S and ∀s ∈ S

, it holds

(

) −

(

−i

,s)=

(

) −

(

−i

,s).

246 V. B i l

oetal.

2. Weighted potential games, where ∃

,...,

) such that ∀

∈S and ∀s ∈S

it holds

(

) −

(

−i

,s)=

(

) −

(

−i

,s)).

3. Ordinal potential games, where ∀

∈ S and ∀s ∈ S

, it holds that

(

) −

(

−i

,s) and

(

) −

(

−i

,s) have the same sign.

Congestion games. Perhaps the most famous class of games is that of conges-

tion games. Results concerning congestion games are presented in Sections 9.3 and

9.7. Here, we present the basic related deﬁnitions. A congestion game is a 4-tuple

(P,E,S

i∈P

e∈E

), where P is a set of n players, E is a set of m resources, S

⊆2

|E|

for

each i ∈P, and d

:IN →IR for each e ∈E. Strictly speaking, each player in a conges-

tion game can choose among different subsets of resources; each resource e has an

associated delay (latency) function d

returning the delay experienced by any player

using e in terms of the number of players using it. Once n

(

)=|{i ∈ P : e ∈

is deﬁned as the number of players using resource e in state

, the payoff function

of player i is deﬁned as

(

∑

e∈

(

)). Congestion games were intro-

duced by Rosenthal [41], who proved that they have the FIP property by deﬁning

the potential function

(

∑

e∈E

∑

(

)

i=1

(i). As shown by Monderer and Shap-

ley [37], the class of congestion games is equivalent to that of exact potential games.

The class of weighted congestion games is a generalization obtained by allowing

players to have different demands. In this case the congestion of each resource e

is deﬁned as n

(

∑

i∈P:e∈

, where r

is the demand of player i. Some special

cases of congestion games are particularly interesting to computer scientists. In net-

work congestion games, resources correspond to the links of a network. Each player

i has a source s

and the destination t

and her set of strategies corresponds to the set

of paths connecting s

to t

. Load balancing games are congestion games in which

all possible strategies for each player are singletons.

Cost sharing games. Similarly to congestion games, a cost sharing game is a 4-

tuple (P,E,S

i∈P

e∈E

), where P is a set of n players, E is a set of m resources,

⊆ 2

|E|

for each i ∈ P, and c : E → IR

. In these games, each resource e has a

certain ﬁxed cost c

, which has to be shared among the players. In particular, each

strategy proﬁle

requires the use of a set of resources

(



i=1

{e ∈E : e ∈

}

of total cost cost(

(

)) =

∑

e∈

(

)

, and the payoffs yielded by

are computed

by applying a certain cost sharing method M distributing cost(

(

)) among the

players. Depending on the deﬁnition of M , different games can be obtained. The

most important family of cost sharing games arises in network design where the

cost of a certain self-emerging network needs to be shared among its users. In this

case, there is an edge-weighted graph G =(V,E, c), with c : E → IR

, modeling the

set of links which can be potentially implemented, as well as their building costs.

Each player i has a source s

and a destination t

that she wants to connect, and

her set of strategies corresponds to the set of paths connecting s

to t

in G.This

general network cost sharing game is referred to as the multi-commodity case. An

interesting and much studied restriction is the single-commodity case, also called

the multicast case, in which there is a common source s for all players and a set

9 Game-Theoretic Approaches to Optimization Problems in Communication Networks 247

R ⊂ V \{s} of n receivers which need to be connected to s. The most-used cost

sharing method is the one based on the well-known Shapley value formula [45]

which equally distributes the cost of each resource among the players using it, thus

yielding

(

∑

e∈

(

)

. A cost sharing game in which the underlying cost

sharing method is the Shapley value is called a Shapley cost sharing game. As ﬁrst

noted in [2] these games are also congestion games. Results related to cost sharing

games are covered in Sections 9.4 and 9.7.

9.3 Congestion Games

In this section we consider congestion games. Besides general congestion games,

we also focus on network congestion games and load balancing games.

We study issues related to the efﬁciency of equilibria in congestion games ac-

cording to the social cost function of the weighted total latency, i.e., the sum of

the latency experienced by each player multiplied by her demand. Formally, the

social cost of a state

(

∑

(

). An equivalent deﬁnition is

(

∑

(

)), since the sum of the demands of the players using resource e is

(

) and each of them experiences a latency of d

(

)) on e.

Price of anarchy. A large part of the literature related to congestion games is de-

voted to providing upper and lower bounds on the price of anarchy. What we essen-

tially want to do in this case is to relate the maximum social cost over all equilibria

to the optimal social cost. The following simple argument is the heart of most re-

lated proofs in the literature. Consider an equilibrium

for a congestion game and

let

∗

be the assignment of optimal social cost. Assume that the latency functions

are linear with the simple form d

(x)=

x and that the demands of the players are

the same (and equal to 1). Since no player has an incentive to change her strategy in

, this also means that

(

) ≤

(

−i

∗

), i.e., that the player i has no incentive

to change her strategy to the one it uses in

∗

. Substituting the payoff, this yields

that

∑

e∈

(

)) ≤

∑

e∈

∗

(

−i

∗

)) ≤

∑

e∈

∗

(

)+1).

The second inequality follows since (

−i

∗

) and

differ only in the strategy of

player i and since the latency functions are non-decreasing. Then, the social cost of

248 V. B i l

oetal.

(

∑

(

)

∑

e∈

(

))

≤

∑

e∈

∗

(

)+1)

∑

i:e∈

∗

(

)+1)

∑

(

∗

(

)+1)

∑

(

∗

(

)+n

(

∗

)) (9.1)

The next step is to apply a simple inequality such as xy + y ≤

for any

integer x,y ≥ 0 on the right part of (9.1) to obtain (by setting x = n

(

) and y =

(

∗

))

(

) ≤

∑

(

∗

)

(

∗

)

and, hence,

(

) ≤

(

∗

), which means that the price of anarchy is at most 5/2.

The above bound was independently obtained by Christodoulou and Koutsoupias

[21] and Awerbuch et al. [4]. The proof can be generalized to prove that the price

of anarchy of weighted linear congestion games over mixed Nash equilibria is at

most

≈2.62, where

√

is the golden ratio. These results are tight. Several

papers in the literature (e.g., [1, 4, 21, 46]) have applied the same technique for more

general (e.g., polynomial) latency functions.

Prior to these works, Suri et al. [46] had obtained the same bound for load balanc-

ing games. A natural question in load balancing games is whether their simplicity

(compared to congestion games) leads to better bounds on the price of anarchy.

In [15], it has been shown that this is not the case in general by proving tight lower

bounds of 2.62 and 5/2 on the price of anarchy of load balancing games with linear

latency functions and players with different or equal demands, respectively. How-

ever, there are cases where load balancing games have some special structure that

decreases the price of anarchy. For example, [15] exploits information about the

structural properties of load balancing games on machines with identical linear la-

tency functions to show an upper bound of 2.012 for the price of anarchy over pure

Nash equilibria. This result is tight; a matching lower bound had been previously

obtained in [46].

Price of stability. The argument that is used to prove upper bounds on the price of

stability is similar. Besides the use of the Nash inequality, information provided by

the potential function is also used. Essentially, we aim to relate the social cost of the

best pure Nash equilibrium



to the social cost of the optimal assignment

∗

.We