English

运筹学学报 >

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

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

两台自私型机器上自私工件排序的PoA紧界

展开
  • 1. 湖南第一师范学院, 湖南长沙 410205
    2. 计算与随机数学教育部重点实验室, 湖南师范大学数学与统计学院, 湖南长沙 410081

收稿日期: 2022-01-28

  网络出版日期: 2022-09-07

收起

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

摘要

本文研究了两台自私型机器上有自私型工件的关于二元均衡的排序问题。对任意工件序列$L$, 证明了二元均衡排序的PoA的紧界为$\frac{8}{7}$。如果工件尺寸在区间$[1, r](r\ge1)$内, 得到了二元均衡排序的PoA的紧界为关于$r$的分段线性函数。

关键词： 自私型机器; 排序; 紧界; 纳什均衡

本文引用格式

成夏炎, 何滢, 赵聪聪, 李荣珩 . 两台自私型机器上自私工件排序的PoA紧界[J]. 运筹学学报, 2022 , 26(3) : 109 -119 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.008

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

参考文献

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
文章导航

/

〈 〉