Skip to main content

On the price of stability of undirected multicast games

Publication ,  Conference
Freeman, R; Haney, S; Panigrahi, D
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 2016

In multicast network design games, a set of agents choose paths from their source locations to a common sink with the goal of minimizing their individual costs, where the cost of an edge is divided equally among the agents using it. Since the work of Anshelevich et al. (FOCS 2004) that introduced network design games, the main open problem in this field has been the price of stability (PoS) of multicast games. For the special case of broadcast games (every vertex is a terminal, i.e., has an agent), a series of works has culminated in a constant upper bound on the PoS (Bil`o et al., FOCS 2013). However, no significantly sub-logarithmic bound is known for multicast games. In this paper, we make progress toward resolving this question by showing a constant upper bound on the PoS of multicast games for quasi-bipartite graphs. These are graphs where all edges are between two terminals (as in broadcast games) or between a terminal and a nonterminal, but there is no edge between nonterminals. This represents a natural class of intermediate generality between broadcast and multicast games. In addition to the result itself, our techniques overcome some of the fundamental difficulties of analyzing the PoS of general multicast games, and are a promising step toward resolving this major open problem.

Duke Scholars

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

January 1, 2016

Volume

10123 LNCS

Start / End Page

354 / 368

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Freeman, R., Haney, S., & Panigrahi, D. (2016). On the price of stability of undirected multicast games. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 10123 LNCS, pp. 354–368). https://doi.org/10.1007/978-3-662-54110-4_25
Freeman, R., S. Haney, and D. Panigrahi. “On the price of stability of undirected multicast games.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10123 LNCS:354–68, 2016. https://doi.org/10.1007/978-3-662-54110-4_25.
Freeman R, Haney S, Panigrahi D. On the price of stability of undirected multicast games. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2016. p. 354–68.
Freeman, R., et al. “On the price of stability of undirected multicast games.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10123 LNCS, 2016, pp. 354–68. Scopus, doi:10.1007/978-3-662-54110-4_25.
Freeman R, Haney S, Panigrahi D. On the price of stability of undirected multicast games. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2016. p. 354–368.

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

January 1, 2016

Volume

10123 LNCS

Start / End Page

354 / 368

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences