Anzeige
Erschienen in:
06.03.2020
Tighter price of anarchy for selfish task allocation on selfish machines
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2022
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.