Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Algorithmic Game Theory and Networks


Pyrga,  Evangelia
Algorithms and Complexity, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Pyrga, E. (2010). Algorithmic Game Theory and Networks. PhD Thesis, Universität des Saarlandes, Saarbrücken.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-1477-1
In this thesis we are studying three different problems that belong to the intersection of Game Theory and Computer Science. The first concerns the design of efficient protocols for a Contention Resolution problem regarding selfish users who all need to transmit information over a common single–access channel. We will provide efficient solutions for different variants of the problem, depending on the feedback that the users can receive from the channel. The second problem concerns the Price of Stability of a fair cost sharing Network Design problem for undirected graphs. We consider the general case for which the best known upper bound is the Harmonic number Hn, where n is the number of players, and the best known lower bound is 12=7 ~ 1:778. We improve the value of the previously best lower bound to 42=23 ~ 1:8261. Furthermore, we study two and three players instances. Our upper bounds indicate a separation between the Price of Stability on undirected graphs and that on directed graphs, where Hn is tight. Previously, such a gap was only known for the cases where all players shared a terminal, and for weighted players. Finally, the last problem applies Game Theory as an evaluation tool for a computer system: we will employ the concept of Stochastic Stability from Evolutionary Game Theory as a measure for the efficiency of different queue policies that can be employed at an Internet router.