TY - JOUR

T1 - Non-cooperative multicast and facility location games

AU - Chekuri, Chandra

AU - Chuzhoy, Julia

AU - Lewin-Eytan, Liane

AU - Naor, Joseph

AU - Orda, Ariel

N1 - Funding Information:
Manuscript received July 1, 2006; revised February 15, 2006. Chandra Chekuri is with the Dept. of Computer Science, Univ. of Illinois, Urbana, IL 61801. This work was done while the author was at Lucent Bell Labs. (e-mail: chekuri@cs.uiuc.edu). Julia Chuzhoy is with the School of Mathematics, Institute for Advanced Study, Princeton NJ 08540 (e-mail: cjulia@math.ias.edu). Liane Lewin-Eytan is with the Department of Electrical Engineering, Technion, Haifa 32000, Israe (e-mail: liane@tx.technion.ac.il). Joseph (Seffi) Naor is with the Computer Science Department, Technion, Haifa 32000, Israel. Part of this research was done while visiting Microsoft Research, Redmond, WA 98052. This research is supported in part by US-Israel BSF Grant 2002276 (e-mail: naor@cs.technion.ac.il). Ariel Orda is with the Department of Electrical Engineering, Technion, Haifa 32000, Israel (e-mail: ariel@ee.technion.ac.il). Digital Object Identifier 10.1109/JSAC.2007.070813.

PY - 2007/8

Y1 - 2007/8

N2 - We consider a multicast game with selfish noncooperative players. There is a special source node and each player is interested in connecting to the source by making a routing decision that minimizes its payment. The mutual influence of the players is determined by a cost sharing mechanism, which in our case evenly splits the cost of an edge among the players using it. We consider two different models: an integral model, where each player connects to the source by choosing a single path, and a fractional model, where a player is allowed to split the flow it receives from the source between several paths. In both models we explore the overhead incurred in network cost due to the selfish behavior of the users, as well as the computational complexity of finding a Nash equilibrium. The existence of a Nash equilibrium for the integral model was previously established by the means of a potential function. We prove that finding a Nash equilibrium that minimizes the potential function is NP-hard. We focus on the price of anarchy of a Nash equilibrium resulting from the best-response dynamics of a game course, where the players join the game sequentially. For a game with n players, we establish an upper bound of 0( 7rafic;n log 2n) on the price of anarchy, and a lower bound of Ω(log n/ log log n). For the fractional model, we prove the existence of a Nash equilibrium via a potential function and give a polynomial time algorithm for computing an equilibrium that minimizes the potential function. Finally, we consider a weighted extension of the multicast game, and prove that in the fractional model, the game always has a Nash equilibrium.

AB - We consider a multicast game with selfish noncooperative players. There is a special source node and each player is interested in connecting to the source by making a routing decision that minimizes its payment. The mutual influence of the players is determined by a cost sharing mechanism, which in our case evenly splits the cost of an edge among the players using it. We consider two different models: an integral model, where each player connects to the source by choosing a single path, and a fractional model, where a player is allowed to split the flow it receives from the source between several paths. In both models we explore the overhead incurred in network cost due to the selfish behavior of the users, as well as the computational complexity of finding a Nash equilibrium. The existence of a Nash equilibrium for the integral model was previously established by the means of a potential function. We prove that finding a Nash equilibrium that minimizes the potential function is NP-hard. We focus on the price of anarchy of a Nash equilibrium resulting from the best-response dynamics of a game course, where the players join the game sequentially. For a game with n players, we establish an upper bound of 0( 7rafic;n log 2n) on the price of anarchy, and a lower bound of Ω(log n/ log log n). For the fractional model, we prove the existence of a Nash equilibrium via a potential function and give a polynomial time algorithm for computing an equilibrium that minimizes the potential function. Finally, we consider a weighted extension of the multicast game, and prove that in the fractional model, the game always has a Nash equilibrium.

KW - Multicast game

KW - Nash equilibrium

KW - Price of anarchy

KW - Price of stability

UR - http://www.scopus.com/inward/record.url?scp=34547538270&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34547538270&partnerID=8YFLogxK

U2 - 10.1109/JSAC.2007.070813

DO - 10.1109/JSAC.2007.070813

M3 - Article

AN - SCOPUS:34547538270

SN - 0733-8716

VL - 25

SP - 1193

EP - 1206

JO - IEEE Journal on Selected Areas in Communications

JF - IEEE Journal on Selected Areas in Communications

IS - 6

ER -