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

doi:10.15960/j.cnki.issn.1007-6093.2022.03.008

运筹学学报 ›› 2022, Vol. 26 ›› Issue (3): 109-119.doi: 10.15960/j.cnki.issn.1007-6093.2022.03.008

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

成夏炎¹, 何滢², 赵聪聪², 李荣珩²^,*()

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

收稿日期:2022-01-28 出版日期:2022-09-15 发布日期:2022-09-07
通讯作者: 李荣珩 E-mail:lirongheng@hunnu.edu.cn

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

Xiayan CHENG¹, Yin HE², Congcong ZHAO², Rongheng LI²^,*()

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

Received:2022-01-28 Online:2022-09-15 Published:2022-09-07
Contact: Rongheng LI E-mail:lirongheng@hunnu.edu.cn
About author:LI Rongheng, E-mail: lirongheng@hunnu.edu.cn
Supported by:
National Natural Science Foundation of China(11471110);Scientific Research Foundation Grant of Education Department of Hunan(16A126)

摘要/Abstract

摘要：

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

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

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

中图分类号:

O223

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

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.

图/表 1

参考文献 12

1	Nisan N , Ronen A . Algorithmic mechanism design[J]. Games and Economic Behavior, 2001, 35, 166- 196. doi: 10.1006/game.1999.0790
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. doi: 10.1007/s00453-010-9427-8
4	Czumaj A , Krysta P , Vöcking B . Selfish traffic allocation for server farms[J]. SIAM Journal on Computing, 2010, 39 (5): 1957- 1987. doi: 10.1137/070693862
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. doi: 10.1007/s10951-011-0247-8
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. doi: 10.1016/j.tcs.2015.02.023
7	Hoeksma R , Uetz M . The price of anarchy for utilitarian scheduling games on related machines[J]. Discrete Optimization, 2019, 31, 29- 39. doi: 10.1016/j.disopt.2018.08.001
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. doi: 10.1016/j.ipl.2015.10.006
9	Berenbrink P , Friedetzky T , Goldberg L A , et al. Distributed selfish load balancing[J]. SIAM Journal on Computing, 2007, 37 (4): 1163- 1181. doi: 10.1137/060660345
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. doi: 10.1007/s10951-009-0118-8
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, doi: 10.1007/s10878-020-00556-6

[1]	王冬, 李刚刚, 罗文昌. 工件具有任意尺寸的混合分批平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(3): 133-142.
[2]	周萍, 季敏, 蒋义伟. 极大化提前完工总量平行机排序问题的LPT算法[J]. 运筹学学报, 2022, 26(3): 151-156.
[3]	龚铭炀, 谈之奕, 严羽洁. 两台同类机排序问题SPT算法的最坏情况比[J]. 运筹学学报, 2022, 26(3): 92-108.
[4]	李文杰, 李钰晶, 刘海玲. 工件的释放时间和加工时间具有一致性的单机在线排序问题研究[J]. 运筹学学报, 2022, 26(2): 55-63.
[5]	毕春燕, 万龙, 罗文昌. 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(2): 73-82.
[6]	王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.
[7]	余山杉, 金苗苗, 罗文昌. 工件延误和可拒绝下的单机重新排序问题的近似方案[J]. 运筹学学报, 2021, 25(2): 104-114.
[8]	姜晓燕, 帅天平. 两台恒速机上的MapReduce排序算法研究[J]. 运筹学学报, 2020, 24(3): 57-66.
[9]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[10]	陈如冰, 原晋江. 工件具有加工位置上限最小化加权总误工量的单机排序问题[J]. 运筹学学报, 2020, 24(2): 131-144.
[11]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[12]	林杨, 王应明. 不确定偏好序下的双边匹配博弈[J]. 运筹学学报, 2020, 24(1): 155-162.
[13]	苟燕, 戴秦, 张新功. 具有时间与位置相关的两类平行机排序问题[J]. 运筹学学报, 2019, 23(4): 86-94.
[14]	李刚刚, 鲁习文. 目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报, 2019, 23(4): 95-104.
[15]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 12

相关文章 15

编辑推荐

Metrics

本文评价