两台平行机排序博弈问题的协调机制

• 作者: 农庆琴 方奇志 赵婷
• 来源期刊: 中国海洋大学学报（自然科学版）
• 学科: 数学
• 关键词: SPT-LPT机制 排序博弈 纳什均衡解 无秩序代价
• 年，卷（期）: 2013,（7）
• 所属期刊栏目: 研究论文
• 页码范围: 110-114
• 页数: 5页
• 分类号: O224|C935
• 字数: 4118字
• 语种: 中文

摘要

排序理论是组合最优化理论的重要组成部分,如果在排序过程中有一个系统管理员来安排相应任务,那么往往会得到比较理想的解.但是,随着互联网的发展,在许多排序过程中由系统管理员来强加控制是不可行的,因为互联网的用户具有独立性和自利性,他们“自私”地追求自身的利益最优,而不在乎是否造成社会资源的浪费.若没有合理的资源使用机制,这种自利性往往会使结果与理论最优值偏差巨大.因此设计合理的机制以影响、引导独立和“自私”的用户的选择从而减少社会资源的浪费将具有重大的理论意义.本文针对如下排序博弈模型:具有2台平行机,工件是局中人,工件的策略是对机器的选择,工件的目标是最小化它的完工时间,全局目标是最小化最大完工时间,探讨SPT-LPT机制(SPT-LPT机制是指一台机器按工件加工时间的不减顺序排序,另一台机器按工件加工时间的不增顺序排序),首先研究了SPT-LPT机制下相应排序博弈问题的纳什均衡解的情况,其次证明了当工件数不小于4时,SPT-LPT机制下的无秩序代价为4/3.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵婷	中国海洋大学数学科学学院	6	68	3.0	6.0
2	方奇志	中国海洋大学数学科学学院	11	8	2.0	2.0
3	农庆琴	中国海洋大学数学科学学院	5	5	1.0	2.0