Author
Çaşkurlu, B., Açikalin, U. U., Kizilkaya, F. E., Ekici, Özgün
Publication Date
2022
Publication Place
-
TÜBİTAK
Subject
Algorithmic game theory, Approximate Nash equilibrium, Connection game, Network formation games
Type
Periodical
Language
English
Digital
Yes
Manuscript
No
Library
Özyeğin University
Library Asset ID
1300-0632
Record ID
461b9d50-07e5-4ea6-9247-ebdc20aa23ab
Library Location
Economics
Date
2022
Sample Text
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 3/2 -approximate Nash equilibrium that is socially optimal. Moreover, we show that it is computable in polynomial time.
DOI
10.55730/1300-0632.3934
Cilt
30
