New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Resource Allocation Games of Utilitarian Social Objectives

SpeakerBo Chen

Co-authorSinan Gurel

In this paper, we study two models of resource allocation games: the classical load balancing game and its new variant involving resource activation costs. The resources we consider are identical and the social costs of the games are utilitarian, which are the average of all individual players' costs. Using the social costs we assess the quality of pure Nash equilibria in terms of the price of anarchy (PoA) and the price of stability (PoS). For each game problem, we identify a problem parameter and provide a parametric bound on the PoA and the PoS. In the case of the load balancing game, the parametric bounds we provide are sharp and asymptotically tight, filling a gap in the literature on the well-studied load balancing game.