2015/07/15 by Akaki Mamageishvili, Mamageishvili, Akaki, Matúš Mihaľák +1
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1507.04222
openalex publication_date 2015/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we 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 4/3 and prove a matching upper bound for the price of stability, which is the ratio of the social costs of a best Nash equilibrium and of a general optimum. Therefore, we answer an open question posed by Fanelli et al. in [12]. 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 4/3, and provide an upper bound of 26/19. To the end, we conjecture and argue that the right answer is 4/3.