Ph.D Thesis | |

Ph.D Student | Lewin-Eytan Liane |
---|---|

Subject | Algorithmic Game Theoretic Perspectives of Network Routing and Cost Sharing |

Department | Department of Electrical and Computers Engineering |

Supervisors | PROF. Ariel Orda |

PROF. Joseph Naor | |

Full Thesis text |

In many networking scenarios, including the Internet, network users act according to their individual interests without taking into account overall network performance.

Users thus may make selfish decisions based on the state of the network, which depends on the behavior of other users, resulting in a non-cooperative game.

The emerging field of Algorithmic Game Theory focuses on computational and algorithmic issues arising in large and complex games motivated by large decentralized computer networks such as the Internet.

We investigate non-cooperative
games in communication networks shared by a finite number of selfish users, and
analyze the penalty incurred by lack of cooperation between the players. This
penalty is mostly quantified by the well known notion of *price of anarchy*,
which is the ratio between the overall system performance of the worst
possible Nash equilibrium, and the system performance of the optimal
solution. We study the Nash equilibria reached by a natural game course
induced by *best* *response dynamics*, where each player in its turn
makes a strategy decision that minimizes its payment (or maximizes its profit).
We investigate means for restricting the reachable Nash equilibria, so that all
the reachable equilibria have a bounded price of anarchy. In case there is no central
trusted authority to rely on, this is achieved by analyzing games that start
from an empty initial configuration. Specifically, we focus on multicast
settings, where there is a special source node and each player is interested in
connecting to the source by making a routing decision that minimizes its
payment (or maximizes its profit). We investigate multicast games in “classic”
(wired) networks, as well as in wireless networks.

Finally, we consider
non-cooperative games, where the natural game course starting from an empty
configuration, and induced by best response dynamics, can converge to bad
equilibria. For these games, we propose a framework where a central authority
can improve the social welfare by offering subsidies. Specifically, we
consider cost sharing systems where each user is interested in purchasing a
service at the lowest possible cost. We develop subsidy mechanisms that
encourage the purchase of services by offering subsidies that reduce their
price, in order to improve the social welfare. The subsidies are financed by
taxes collected from the users. The performance of such a subsidy mechanism is
measured both by the price of anarchy of the resulting solution, and by the *taxation
ratio*, defined as the percentage of the payments collected as taxes from
the users.