中文

Operations Research Transactions >

2022 , Vol. 26 >Issue 3: 109 - 119

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.03.008

Tight Price of Anarchy for selfish task scheduling on two selfish machines

Expand
  • 1. Hunan First Normal University, Changsha 410205, Hunan, China
    2. Key Laboratory of High Performance Computing and Stochastic Information Processing, Department of Mathematics, Hunan Normal University, Changsha 410081, Hunan, China
LI Rongheng, E-mail: lirongheng@hunnu.edu.cn

Received date: 2022-01-28

  Online published: 2022-09-07

Supported by

National Natural Science Foundation of China(11471110);Scientific Research Foundation Grant of Education Department of Hunan(16A126)

Fold

Abstract

In this paper, we study selfish task scheduling on two selfish machines with respect to Dual Equilibrium, called Dual Equilibrium Schedule. For any job list $L$, we show that the Price of Anarchy of Dual Equilibrium Schedule is $\frac{8}{7}$. If the job sizes are constrained in $[1, r](r\ge1)$, this research states that the tight PoA(Price of Anarchy) of Dual Equilibrium Schedule is a piecewise linear function of $r$.

Key words： selfish machines; scheduling; tight bound; Nash equilibrium

Cite this article

Xiayan CHENG, Yin HE, Congcong ZHAO, Rongheng LI . Tight Price of Anarchy for selfish task scheduling on two selfish machines[J]. Operations Research Transactions, 2022 , 26(3) : 109 -119 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.008

References

1 Nisan N , Ronen A . Algorithmic mechanism design[J]. Games and Economic Behavior, 2001, 35, 166- 196.
2 Koutsoupias E, Papadimitriou C. Wrost-case equlibria[C]//Proceeding of the 16th International Symposium on Theoretical Aspects of Computer Science. Berlin Heidelberg: Springer-Verlag, 1999: 404-413.
3 Caragiannis I , Flammini M , Kaklamanis C , et al. Tight Bounds for Selfish and Greedy Load Balancing[J]. Algorithmica, 2011, 61 (3): 606- 637.
4 Czumaj A , Krysta P , V?cking B . Selfish traffic allocation for server farms[J]. SIAM Journal on Computing, 2010, 39 (5): 1957- 1987.
5 Chen B , Gürel S . Efficiency analysis of load balancing games with and without activation costs[J]. Journal of Scheduling, 2012, 15 (2): 157- 164.
6 Xie F , Xu Z , Zhang Y , et al. Scheduling games on uniform machines with activation cost[J]. Theoretical Computer Science, 2015, 580, 28- 35.
7 Hoeksma R , Uetz M . The price of anarchy for utilitarian scheduling games on related machines[J]. Discrete Optimization, 2019, 31, 29- 39.
8 Xie F , Zhang Y , Bai Q , et al. Inefficiency analysis of the scheduling game on limited identical machines with activation costs[J]. Information Processing Letters, 2016, 116 (4): 316- 320.
9 Berenbrink P , Friedetzky T , Goldberg L A , et al. Distributed selfish load balancing[J]. SIAM Journal on Computing, 2007, 37 (4): 1163- 1181.
10 Angel E , Bampis E , Pascual F , et al. On truthfulness and approximation for scheduling selfish tasks[J]. Journal of Scheduling, 2009, 12 (5): 437- 445.
11 Chen X , Hu X , Ma W , et al. Reducing price of anarchy of selfish task allocation with more selfishness[J]. Theoretical Computer Science, 2013, 507 (7): 17- 33.
12 Cheng X , Li R , Zhou Y . Tighter price of anarchy for selfish task allocation on selfish machines[J]. Journal of Combinatorial Optimization, 2020,
Options
Outlines

/

〈 〉