Item

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.