Vipin Ravindran Vijayalakshmi: Selfishness in Strategic Resource Allocation Problems

 

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).