Ph.D Thesis

Ph.D StudentLewin-Eytan Liane
SubjectAlgorithmic Game Theoretic Perspectives of Network Routing
and Cost Sharing
DepartmentDepartment of Electrical and Computers Engineering
Supervisors PROF. Ariel Orda
PROF. Joseph Naor
Full Thesis textFull thesis text - English Version


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.