hide
Free keywords:
-
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.
