Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games

M. Feldotto, Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games, Paderborn, 2019.

Download
Restricted Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games.pdf 3.12 MB
Dissertation | English
Abstract
This thesis investigates approximate pure Nash equilibria in different game-theoretic models. In such an outcome, no player can improve her objective by more than a given factor through a deviation to another strategy. In the first part, we investigate two variants of Congestion Games in which the existence of pure Nash equilibria is guaranteed through a potential function argument. However, the computation of such equilibria might be hard. We construct and analyze approximation algorithms that enable the computation of states with low approximation factors in polynomial time. To show their guarantees we use sub games among players, bound the potential function values of arbitrary states and exploit a connection between Shapley and proportional cost shares. Furthermore, we apply and analyze sampling techniques for the computation of approximate Shapley values in different settings. In the second part, we concentrate on the existence of approximate pure Nash equilibria in games in which no pure Nash equilibria exist in general. In the model of Coevolving Opinion Formation Games, we bound the approximation guarantees for natural states nearly independent of the specific definition of the players' neighborhoods by applying a concept of virtual costs. For the special case of only one influential neighbor, we even show lower approximation factors for a natural strategy. Then, we investigate a two-sided Facility Location Game among facilities and clients on a line with an objective function consisting of distance and load. We show tight bounds on the approximation factor for settings with three facilities and infinitely many clients. For the general scenario with an arbitrary number of facilities, we bound the approximation factor for two promising candidates, namely facilities that are uniformly distributed and which are paired.
Publishing Year
LibreCat-ID

Cite this

Feldotto M. Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games. Paderborn; 2019. doi:10.17619/UNIPB/1-588
Feldotto, M. (2019). Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games. Paderborn. https://doi.org/10.17619/UNIPB/1-588
@book{Feldotto_2019, place={Paderborn}, title={Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games}, DOI={10.17619/UNIPB/1-588}, author={Feldotto, Matthias}, year={2019} }
Feldotto, Matthias. Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games. Paderborn, 2019. https://doi.org/10.17619/UNIPB/1-588.
M. Feldotto, Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games. Paderborn, 2019.
Feldotto, Matthias. Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games. 2019, doi:10.17619/UNIPB/1-588.
Main File(s)
File Name
Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games.pdf 3.12 MB
Access Level
Restricted Closed Access
Last Uploaded
2019-03-28T13:40:51Z


Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar