Advertisement
Published in:
06-03-2020
Tighter price of anarchy for selfish task allocation on selfish machines
Published in: Journal of Combinatorial Optimization | Issue 3/2022
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Given a set \(L = \{J_1,J_2,\ldots ,J_n\}\) of n tasks and a set \(M = \{M_1,M_2, \ldots ,M_m\}\) of m identical machines, in which tasks and machines are possessed by different selfish clients. Each selfish client of machine \(M_i \in M\) gets a profit equal to its load and each selfish client of task allocated to \(M_i\) suffers from a cost equal to the load of \(M_i\). Our aim is to allocate the tasks on the m machines so as to minimize the maximum completion times of the tasks on each machine. A stable allocation is referred to as a dual equilibrium (DE). We firstly show that 4/3 is tight upper bound of the Price of Anarchy(PoA) with respect to dual equilibrium for \(m\in \{3,\ldots ,9\}\). And secondly \((7m-6)/(5m-3)\) is an upper bound for \(m\ge 10\). The result is better than the existing bound of 7/5.