Non-cooperative multicast and facility location games

Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Joseph Naor, Ariel Orda

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider a multicast game with selfish non-cooperative 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 O(√n log2 n) 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 7th ACM Conference on Electronic Commerce 2006
PublisherAssociation for Computing Machinery
Pages72-81
Number of pages10
ISBN (Print)1595932364, 9781595932365
DOIs
StatePublished - 2006
Externally publishedYes
Event7th ACM Conference on Electronic Commerce - Ann Arbor, MI, United States
Duration: Jun 11 2006Jun 15 2006

Publication series

NameProceedings of the ACM Conference on Electronic Commerce
Volume2006

Other

Other7th ACM Conference on Electronic Commerce
CountryUnited States
CityAnn Arbor, MI
Period6/11/066/15/06

Keywords

  • Multicast game
  • Nash equilibrium
  • Price of anarchy
  • Price of stability

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Non-cooperative multicast and facility location games'. Together they form a unique fingerprint.

Cite this