Tighter price of anarchy for selfish task allocation on selfish machines

Xiayan Cheng, Rongheng Li () and Yunxia Zhou
Additional contact information
Xiayan Cheng: Hunan Normal University
Rongheng Li: Hunan Normal University
Yunxia Zhou: Hunan Normal University

Journal of Combinatorial Optimization, No 0, 32 pages

Abstract: Abstract Given a set $$L = \{J_1,J_2,\ldots ,J_n\}$$L={J1,J2,…,Jn} of n tasks and a set $$M = \{M_1,M_2, \ldots ,M_m\}$$M={M1,M2,…,Mm} of m identical machines, in which tasks and machines are possessed by different selfish clients. Each selfish client of machine $$M_i \in M$$Mi∈M gets a profit equal to its load and each selfish client of task allocated to $$M_i$$Mi suffers from a cost equal to the load of $$M_i$$Mi. 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\}$$m∈{3,…,9}. And secondly $$(7m-6)/(5m-3)$$(7m-6)/(5m-3) is an upper bound for $$m\ge 10$$m≥10. The result is better than the existing bound of 7/5.

Keywords: Price of anarchy; Dual equilibrium; Schedule; Game theory (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00556-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-020-00556-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00556-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().