Please use this identifier to cite or link to this item:
Title: On approximate Nash equilibria of the two-source connection game
Authors: Caskurlu, Bugra
Acikalin, Utku Umur
Kizilkaya, Fatih Erdem
Ekici, Ozgun
Keywords: Algorithmic game theory
network formation games
connection game
approximate Nash equilibrium
Network Design
Issue Date: 2022
Publisher: Scientific And Technological Research Council Turkey
Abstract: The arbitrary-sharing connection game is prominent in the network formation game literature [1]. An undirected graph with positive edge weights is given, where the weight of an edge is the cost of building it. An edge is built if agents contribute a sufficient amount for its construction. For agent i, the goal is to contribute the least possible amount while assuring that the source node si is connected to the terminal node ti . In this paper, we study the special case of this game in which there are only two source nodes. In this setting, we prove that there exists a 2-approximate Nash equilibrium that is socially optimal. We also consider the further special case in which there are no auxiliary nodes (i.e., every node is a terminal or source node). In this further special case, we show that there exists a 32-approximate Nash equilibrium that is socially optimal. Moreover, we show that it is computable in polynomial time.
ISSN: 1300-0632
Appears in Collections:Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
TR Dizin İndeksli Yayınlar / TR Dizin Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection

Show full item record

CORE Recommender

Page view(s)

checked on Sep 25, 2023

Google ScholarTM



Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.