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

作     者：赵婷 农庆琴 方奇志 ZHAO Ting;NONG Qing-Qin;FANG Qi-Zhi

作者机构：中国海洋大学数学科学学院山东青岛266100 

基　　金：中央高校青年教师专项基金项目(201013035) 山东省自然科学基金青年基金项目(ZR2012AQ012)资助 

出 版 物：《中国海洋大学学报（自然科学版）》 (Periodical of Ocean University of China)

年 卷 期：2013年第43卷第7期

页      码：110-114页

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

主 题 词：SPT-LPT机制 排序博弈 纳什均衡解 无秩序代价 

学科分类：12[管理学] 120202[120202] 0202[经济学-财政学类] 02[经济学] 1202[管理学-工商管理类] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

核心收录：

D　O　I：10.16441/j.cnki.hdxb.2013.07.020

馆 藏 号：203565796...