On approximate Nash equilibria of the two-source connection game

Name: On approximate Nash equilibria of the two-source connection game
Author: Çaşkurlu, B., Açikalin, U. U., Kizilkaya, F. E., Ekici, Özgün

İsim	On approximate Nash equilibria of the two-source connection game
Yazar	Çaşkurlu, B., Açikalin, U. U., Kizilkaya, F. E., Ekici, Özgün
Basım Tarihi:	2022
Basım Yeri	- TÜBİTAK
Konu	Algorithmic game theory, Approximate Nash equilibrium, Connection game, Network formation games
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	1300-0632
Kayıt Numarası	461b9d50-07e5-4ea6-9247-ebdc20aa23ab
Lokasyon	Economics
Tarih	2022
Örnek Metin	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

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

On approximate Nash equilibria of the two-source connection game

Yazar Çaşkurlu, B., Açikalin, U. U., Kizilkaya, F. E., Ekici, Özgün

Basım Tarihi 2022

Basım Yeri - TÜBİTAK

Konu Algorithmic game theory, Approximate Nash equilibrium, Connection game, Network formation games

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 1300-0632

Kayıt Numarası 461b9d50-07e5-4ea6-9247-ebdc20aa23ab

Lokasyon Economics

Tarih 2022

Örnek Metin 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