Reducing price of anarchy of selfish task allocation with more selfishness
In this paper we consider the task allocation problem from a new game theoretic perspective. We assume that tasks and machines are both controlled by selfish agents with two distinct objectives, which stands in contrast to the passive role of machines in the traditional model of selfish task allocation. To characterize the outcome of this new game where two classes of players interact, we introduce the concept of dual equilibrium. We prove that the price of anarchy with respect to dual equilibria is 1.4, which is considerably smaller than the counterpart 2 in the traditional model. Our study shows that activating more freedom and selfishness in a game may bring about a better global outcome. Crown Copyright (C) 2013 Published by Elsevier B.V. All rights reserved.
price of anarchy selfish task allocation selfish scheduling