Vipin Ravindran Vijayalakshmi: Selfishness in Strategic Resource Allocation Problems



Vipin Ravindran Vijayalakshmi

Ehem. Promotionsstudent


Vipin Ravindran Vijayalakshmi investigated congestion games, an important class of games to model decentralised resource allocation problems. An allocation is a pure Nash equilibrium if and only if none of the users/jobs have an improving deviation from it. Computing exact or approximate pure Nash equilibria is, in general, PLS6 -complete. Vijayalakshmi presents an algorithm to efficiently compute improved approximate pure Nash equilibria in games with arbitrary non-decreasing resource cost functions. His analysis exhibits an interesting method to compute universal load dependent taxes. Scheduling games on parallel related machines form a special class of congestion games. He considers the setting where each agents control a job and select a machine to process the job. Each agents aims to minimise his/her individual completion time. The completion time, however, depends on the strategies of all agents, since each machine is endowed with a publicly known priority list determining the processing order of jobs by a machine. Vijayalakshmi presents results on the computational hardness, existence of equilibria, and inapproximability of equilibria for various special cases. He also studies the problem to maintain a connected network in the presence of an adversary who may remove or add nodes so as to disconnect the network into multiple components. He investigates the maintenance of a structured overlay network (e.g., P2P networks) under massive churn, where an adversary may churn a constant fraction of nodes over the course of O(log n) rounds, where n is the minimal number of nodes in the network each round. Vijayalakshmi presents an algorithm to construct a new overlay every 2 rounds with congestion at most O(polylog n).