Portal de Periódicos da CAPES

Efficiency of Dual Equilibria in Selfish Task Allocation to Selfish Machines

2012; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-642-31770-5_28

1611-3349

Xujin Chen, Xiao Hu, Weidong Ma, Changjun Wang,

Evolutionary Game Theory and Cooperation

In this paper we consider the task allocation problem from a 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.