English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Thesis

Algorithmic Game Theory and Networks

MPS-Authors
/persons/resource/persons45230

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

/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

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


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1477-1
Abstract
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.