Improved bounds on equilibria solutions in the network design game

Akaki Mamageishvili (), Matúš Mihalák and Simone Montemezzani
Additional contact information
Akaki Mamageishvili: ETH Zurich
Matúš Mihalák: Maastricht University
Simone Montemezzani: ETH Zurich

International Journal of Game Theory, 2018, vol. 47, issue 4, No 4, 1113-1135

Abstract: Abstract In the network design game with n players, every player chooses a path in an edge-weighted graph to connect her pair of terminals, sharing costs of the edges on her path with all other players fairly. It has been shown that the price of stability of any network design game is at most $$H_n$$ H n , the n-th harmonic number. This bound is tight for directed graphs. For undirected graphs, it has only recently been shown that the price of stability is at most $$H_n \left( 1-\frac{1}{\Theta (n^4)} \right) $$ H n 1 - 1 Θ ( n 4 ) , while the worst-case known example has price of stability around 2.25. We improve the upper bound considerably by showing that the price of stability is at most $$H_{n/2} + \varepsilon $$ H n / 2 + ε for any $$\varepsilon $$ ε starting from some suitable $$n \ge n(\varepsilon )$$ n ≥ n ( ε ) . We also study quality measures of different solution concepts for the multicast network design game on a ring topology. We recall from the literature a lower bound of $$\frac{4}{3}$$ 4 3 and prove a matching upper bound for the price of stability. Therefore, we answer an open question posed by Fanelli et al. (Theor Comput Sci 562:90–100, 2015). We prove an upper bound of 2 for the ratio of the costs of a potential optimizer and of an optimum, provide a construction of a lower bound, and give a computer-assisted argument that it reaches 2 for any precision. We then turn our attention to players arriving one by one and playing myopically their best response. We provide matching lower and upper bounds of 2 for the myopic sequential price of anarchy (achieved for a worst-case order of the arrival of the players). We then initiate the study of myopic sequential price of stability and for the multicast game on the ring we construct a lower bound of $$\frac{4}{3}$$ 4 3 , and provide an upper bound of $$\frac{26}{19}$$ 26 19 . To the end, we conjecture and argue that the right answer is $$\frac{4}{3}$$ 4 3 .

Keywords: Network design game; Nash equilibrium; Price of stability; Ring topology; Potential-optimum price of stability/anarchy (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-017-0600-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:47:y:2018:i:4:d:10.1007_s00182-017-0600-z

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-017-0600-z

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().