运筹学与控制论

恒速机下的有限资源博弈排序最优性研究

摘要

摘要

排序问题是一类组合最优化问题,由于排序问题中的处理机、任务或作业是有限的,绝大部分排序问题是从有限个可行解中找出一个最优解,使目标函数达到极小.

本文主要研究有限资源的博弈排序问题,我们考虑的资源是相同的,博弈的社会成本是实用的.在恒速机博弈排序模型中,每一个工件都可以自主选择一个合适的机器来加工它自己,这样每个工件的目标就是使它自己的成本最小.工件的成本是指它所选择的那台机器的总完工时间.本文的结构安排如下：

第一章为绪论部分,主要介绍了排序问题、博弈论和纳什均衡问题、博弈排序的产生背景和主要内容以及后两章内容需要用到的一些预备知识.

第二章考虑了恒速机下的博弈排序模型.在纳什均衡中,在每个工件的策略都不改变的情况下,任何一个工件都不能通过单方面的改变自己的策略来降低它的成本,但是纳什均衡不一定是最优的,实际上还常常与最优值存在很大差距.在这里我们使用POA（the price of anarchy）和POS（the price of stability）来分析纳什均衡的质量.当目标函数是总完工时间时,求得POA界和POS界.当目标函数是时间表长度时,求得POA界.

第三章考虑了两台和m台带激活费用的恒速机模型,研究的整体目标函数是机器的总完工时间和激活费用之和,最后我们用POA来衡量纳什均衡时的最差的整体目标函数值与最优值之间的差异.两台机器时,我们假设机器的速度分别是1和a,每台机器的激活费用和它的速度相等,.m台机器时,我们假设机器的激活费用都是1,不随每台机器的速度变化,分别求得两种情况下的POA界.

关键词:博弈排序；纳什均衡；恒速机；激活费用；POA

Abstract

Abstract

Scheduling problem is a kind of combinatorial optimization problems, due to the processor task or assignment is limited, so most of the scheduling problems is to find an optimal solution from limited feasible solutions, as to achieve the minimum of the objective function.

In this paper, we investigate resource allocation games for job scheduling when the resource are limited. The resource we considered are identical and the social costs of the games are utilitarian. In terms of machine scheduling, assignment of jobs to machines in which selfish agents, representing individual jobs, select machines for processing the jobs, and each job will be minimize its cost. The structure of this article is as follows:

The first chapter is an introduction, it mainly introduces the combinatorial optimization problems, the background of game scheduling and some preliminary knowledge.

In the second chapter, we consider the load balancing game in uniform machines. A Nash equilibrium(NE) is a strategy profile, in any NE assignment, no job can reduce its cost by unilaterally changing its machine. But in terms of a given social objective, such an Nash equilibrium is not necessarily, indeed can often be far from optimal. We use the notions of the price of anarchy(POA) and the price of stability(POS) to analyze the quality of NE solutions.when the The objective function is Total completion time,we prove thePOAand thePOS. When the objective function is the makespan, we prove the POA.

In the third chapter, we consider a system with two uniform machines and a fixed number mof uniform machines. The social cost is the sum of the system makespan and activation cost of machines. We assess the quality of Nash equilibrium in terms of the POA .we assume that the speed of the machine is 1 and a respectively, and the activation of each machine cost is equal to its speed when there are two machines. we assume that the machine activation cost is 1 and don't change with the speed of each machine when there are mmachines, we prove the POA of two cases.

Keywords： Game scheduling; Nash equilibrium; Uniform machines; activation cost; price of anarchy

目录

摘要 ........................................................................ I

第1章 绪论 ................................................................. 1

1.1 排序问题的介绍 ...................................................... 1

1.2 博弈论和纳什均衡问题的介绍 .......................................... 2

1.3 博弈排序问题的介绍 .................................................. 3

1.4 本文研究的主要内容 .................................................. 4

第2章 无激活费用的恒速机博弈排序模型 ....................................... 6

2.1 引言 ............................................................... 6

2.2 问题描述 ........................................................... 6

2.3 m台恒速机上社会成本为总完工时间的博弈排序问题 ..................... 8

2.4 m台恒速机上社会成本为时间表长度的博弈排序问题 .................... 11

2.5 总结 ............................................................... 12

第3章 带激活费用的恒速机博弈排序 .......................................... 14

3.1 引言 ............................................................... 14

3.2 问题描述 ........................................................... 14

3.3 两台带激活费用的恒速机POA分析 ...................................... 15

3.4 m台带激活费用的恒速机POA分析 ..................................... 16

3.5 总结 ............................................................... 17

参考文献 ................................................................... 19

在读期间发表的学术论文及研究成果 ........................................... 22

致谢 ....................................................................... 23

第1章 绪论

本章主要介绍了研究问题的背景,有关概念及其相关的研究进展,并简要说明了本文研究的主要成果及创新点.

1.1 排序问题的介绍

排序（scheduling）问题一开始主要应用于机器制造,后来被广泛应用,运输调度、计算机网络系统、生产管理等很多领域都要用到排序的理论和算法.排序是随时间对有限资源进行分配来执行一个给定的工作或活动,排序模型在工厂的应用和计算机系统的应用中起到很重要的作用.其他常见的排序问题有:项目调度,人员安排,制定时间表等.排序问题已经非正式的研究了几个世纪,Gantt Chart用一个图形表示了在第一次世界大战中任务和资源随着时间的推移情形,这是应用排序的第一个正式模型,1950年代首次使用数学模型分析机器的调度问题,1970进一步研究了计算复杂性,现在,排序问题又广泛应用于现代制造业环境和供应链协调中.

排序其实是一类重要的组合优化问题,它是利用一些机器（machine）、处理机（processor）或资源（resource）完成一批给定的任务（task）或作业（job）,使其结果最优,结果最优指的是使目标函数达到最小,而目标函数通常是对工件或任务的完工时间的长短、处理机的利用率、机器的总的费用等的描述.

排序问题的三要素包括处理机、任务或作业和目标函数.处理机的数量类型和环境不同,作业或任务和资源的约束条件更是错综复杂,而且目标函数不同,形成了种类繁多的排序类型.

我们普遍采用Graham等人创立的三参数表示法（three-field representation）来描述一个排序问题[9].一般排序问题表示为：||,其中,域表示的是处理机的数量、环境和类型；域表示的是作业或任务的性质、资源的数量,加工要求或者限制、作业或任务的

域表示的是这个排序问题的目标函种类和对加工的影响等条件,它可以同时包含许多项；

数.

域（机器环境）

1：指的是单处理机（single machine）.

Pm：m个同速机,它指的是每台机器的速度都是一样的.

Qm：m个恒速机,它指的是机器的速度是不一样的,而且每台机器的速度都是一个常数,但是机器的速度并不依赖于被加工的工件.

Rm:m个变速机,它指的是每台机器的速度不同,但是机器的速度依赖于被加工的任务.

域（工件的加工约束和限制）

pj: 任务j的加工时间.

rj：任务的到达时间.如果中不出现rj,则表示所有的工件在0时刻都可以加工. dj：对任务j限定的完工时间.若不按期完工,则有一定惩罚.

j：工件j的权重,它表示工件j相对于其他的工件的重要程度.

域（要优化的目标函数）

Cmax：最大完工时间,即时间表长,它等于排序最后一个工件的完工时间.

C,jCj：总完工时间和,加权总完工时间和. j

Lmax：最大延误,即最大工件延迟时间.

1.2 博弈论和纳什均衡问题的介绍 博弈论是指研究多个个体或团队之间在特定条件制约下的对局中利用相关方的策略,而实施对应策略的学科.它是应用数学的一个分支,也是运筹学的一个重要组成部分,在很多领域都有广泛的应用.一般认为,博弈主要可以分为合作博弈和非合作博弈.合作博弈研究的主要是当人们达成合作协议时如何分配合作所得到的收益,就是所谓的收益分配问题；非合作博弈研究的主要是人们在利益相互制约的资源分配问题中如何选择自己的策略使自己的收益最大,就是策略决策问题.非合作博弈强调的是个人理性,个人的最优决策,其结果可能是有效率的,也可能是无效率的.本文研究的主要是非合作博弈.

博弈广泛应用于资源分配中,例如：在作业调度应用中,任务分配给机器处理,同样,在沟通或交通网络,路由流量分配给网络链接.这些设置就是许多有趣的组合优化问题,但因为他们经常由多个战略用户决定,一个用户的个人收益由其他用户的决策决定,在资源分配分析中,博弈论已经成为一种必不可少的工具.在本文中,我们运用非合作博弈的理论研究资源分配问题,研究工件排序问题,博弈论的核心观点是假设每个客户都有战略上的考虑,都要使自己的成本最小,而不是最优化总体目标.在工件排序设置中,这意味着工件自己选择一个机器,而不是由一个中央管理者分配给一个机器.博弈论关注的是一个特定的环境或者是平衡点的稳定结果.一个纳什均衡是用户策略的组合,没有用户可以通过单方面偏离其策略来降低它的成本（考虑到其他用户的策略不会改变）.

当每个博弈者选择自己的最优策略（个人最优策略可能依赖于也可能不依赖于他人的战略）,从而使自己的利益达到最大值,而且与此同时,其他所有博弈者也遵循这样的策略,所有博弈者策略构成一个策略组合（Strategy Profile）,这时这个策略组合就被称为纳什均衡.纳什均衡,又称为非合作博弈均衡,是博弈论的重要核心,在非合作博弈理论中,没有成员可以单方面改变策略获得收益,一般来说,一个博弈可能是唯一的、多样的或者不均衡的.约翰·纳什在1994年诺贝尔经济学奖上分享了他关于博弈理论的工作,证明了在有限资源博弈中必须存在至少一个混合策略均衡.

每个客户端和其他参与这一博弈的自私的客户各自都试图使自己的成本最小,我们称之为自私的负载平衡博弈.它不同于传统的负载平衡,然而,客户并不对最优的社会收益感兴趣,相反的,每个客户都有自己的私人目的,这些相互作用的稳定的结果就是纳什均衡（Nash equilibrium）.在这个纳什均衡中,没有一个客户端可以通过单方面的改变自己的策略来提高他的收益.一般来说,一个资源分配的最优解往往是不稳定的,一个或更多的客户可能通过改变他们的策略来提高收益,而这样会导致其他的客户的收益变低.但是另一方面,纳什均衡下的社会成本与最优情况下的社会成本存在很大差距.

1.3 博弈排序问题的介绍

在组合最优化理论中,排序是为加工若干个工件,而对工件及其加工所需要的机器进行分配,在所有工件完工时的目标函数值最优.

博弈是两个或多个局中人之间的博弈,并且假设参与博弈的局中人都是追求利益最大化.强调纳什均衡的存在和质量的博弈理论分析除了在工件排序有很大应用外,还被应用于各种各样的其他实际应用.比如用于费用分摊博弈（Jain and Mahdian 2007[8]）其中引用,比如用于网络路由的设置（Correa et al[5],[6]. 2007,2004; Bonifaci et al[3]. 2010,Cominetti et al[4]. 2009, Awerbuch et al. 2005）,用于网络建造（Fabrikant et al. 2003;Albers et al[2]. 2006, Anshelevich et al[1]. 2004, Epstein et al[7]. 2007）.

因为用户的成本函数引导他们的决策,成本函数的结构是任何博弈问题的一个重要组成部分,成本函数主要分为两类,第一类（如路由选择和工件排序）强调负拥堵效应,假设一个资源的成本随负载增加.相比之下,第二类（如创建网络）强调积极拥堵效应,假定一些固定的激活成本.在资源分配问题中,这两个拥挤效应是相互矛盾的,在现实情况下,激活一个新的“资源”是昂贵的,但与此同时缓解拥堵的负担.

资源分配问题往往涉及决策问题,一个典型的例子就是机器的调度问题,把任务分配到机器上,这里每个工件都是一个自私的代理人,代表个人的工作,选择机器来处理自己的工作.从长远来看,每个代理人的决策出于个人利益,通常会形成一个纳什均衡,这样,在这个资源分配中,没有一个代理可以通过单方面的改变策略获得收益.

我们假设工件相当于独立的局中人,工件自主选择机器进行加工而不是被安排到某台机器上进行加工,工件所选择加工的机器相当于局中人的策略.工件选择使自己的加工费用最少的机器进行加工,这就将可能达到纳什均衡.使目标函数为最优的可行解,称为最优排序（optimal schedule）.在资源分配博弈中,纳什均衡时的总花费往往不是最小的,NE值有时与最优值相差很大,所以,我们常用POA（the price of anarchy）和POS（the price of stability）两个参数来衡量纳什均衡的目标函数值和最优值之间的差距,这两个参数最早是由Koutsoupias和Papadimitriou[13]两个人提出的.

我们把所有可能的工件安排方案记为S,每一种安排方法ss1,,snS,排序s的社会成本函数记为g(s),是所有工件的最高费用,gsmaxjcjs.我们用OPT表示最优的分配方案,OPTminsSgs.

令是一类博弈排序问题,G是这一类博弈排序问题中的一些博弈问题,且G,G是纳什均衡解的集合,如果G,我们用POA表示最差的纳什均衡解与G的最优值的比值,用POS表示最好的纳什均衡解与G的最优值的比值.

POA(G)maxgsG,

sG

POS(G)mingsOPTG. sG

1.4 本文研究的主要内容

本文主要研究有限资源的博弈排序问题,我们考虑的资源是相同的,博弈的社会成本是实用的.在恒速机博弈排序模型中,每一个工件都可以自主选择一个合适的机器来加工它自己,这样每个工件的目标就是使它自己的成本最小.工件的成本是指它所选择的那台机器的总完工时间.本文的结构安排如下：

第一章为绪论部分,主要介绍了排序问题、博弈论和纳什均衡问题、博弈排序的产生背景和主要内容以及后两章内容需要用到的一些预备知识.

第二章考虑了恒速机下的博弈排序模型.纳什均衡不一定是最优的,实际上还常常与最优值差距很大.在纳什均衡中,在每个工件的策略都不改变的情况下,任何一个工件都不能通过单方面的改变自己的策略来降低它的成本,但是纳什均衡不一定是最优的,实际上还常常与最优值存在很大差距.本章考虑了m台恒速机下的博弈排序问题,在这里我们使用POA（the price of anarchy）和POS（the price of stability）来分析纳什均衡的质量.当目标函数是总完工时间时,求得POA

表长度时,求得POA2sm

s1smnsnm1m1.当目标函数是时间1,POS13s1msmm1n.

第三章考虑了两台和m台带激活费用的恒速机模型,研究的整体目标函数是机器的总完工时间和激活费用之和,最后我们用POA来衡量NE时的整体目标函数值与最优值之间的差异.两台机器时,我们假设机器的速度分别是1和a,每台机器的激活费用和它的速度相

等,求得POA1a.m台机器时,我们假设机器的激活费用都是1,每台机器的速度不同, s1s2s3W

s1. sm,求得POAP1nmin

smmn

第2章 无激活费用的恒速机博弈排序模型

2.1 引言

本文中的资源分配博弈我们考虑如下,给定一个工件集1,2,,n,每个工件都有一个加工时间,也叫长度,并且都是由自私的代理商控制,每个代理决定选择同类机中的一个来分配自己的工作.我们考虑这个博弈模型：恒速机博弈排序模型.在这个恒速机博弈排序模型中,给定m台机器,机器的负载就是每个玩家的成本,这里机器的负载就是指被安排的所有工件的长度和.

像许多其他博弈,在资源分配博弈中,纳什算法的成本往往不是最小的,与之相对应的解决方案被称为最优.在这篇文章中,我们使用能被普遍接受的概念POA（the price of anarchy）和P来分析纳什算法的质量.Koutsoupias和Papadimitriou[13]OS（the price of stability）

在1999年,Papadimitriou[14]在2001年都介绍了这一概念,POA(the price of anarchy)表示最差的NE排序的目标函数值与最优值的比值,POS（the price of stability）表示最好的NE排序的目标函数值与最优值的比值.

1999年,Koutsoupias和Papadimitriou给出了新的术语POA(the price of anarchy)替代原来的术语 “coordination ratio”（协调比率）.Vocking[21] 在2007年研究了经典的平行机博弈模型,并且已经被广泛的研究.2012年,Bo Chen和Sinan Gurel[27]分析了同型机博弈模型的效率,他们所考虑的机器是同型机,而本文考虑的机器是恒速机.

2.2 问题描述

有m台机器MM1,M2,,Mm,机器台数m2,每台机器的速度不同,加工n个工件

J1,2,,n.每一个工件jJ都有一个加工时间,即长度pj,且pj0.对于给定的一个分配方案,我们把分配到机器i上的工件分别表示为Ji,分配到机器i上的工件个数表示为ni,这个分配方案下机器i的负载可以表示为LijJipj.在这个恒速机博弈模型中,一个工件的花费就是这个工件被安排的机器的负载,给定的这个分配方案的所有工件的花费为CniLi.

i1m

如果给定的这个分配方案是最优方案,我们就用Ji,ni,L*

i分别表示分配到机器i上

的工件,机器i上的工件个数,机器i上的负载. **

下面给出本章中的一些符号定义：

pj: 第j个工件的加工时间.

c

j

：所有工件的总完工时间.

Li：第i台机器的负载.

si: 第i台机器的速度. ni：第i台机器上工件的个数.

Ci：第i台机器上工件的完工时间之和.

Cmax：机器的最大完工时间. P：所有工件的加工时间. 本章所研究的问题如下：

（1）Q即m台恒速机上社会成本为总完工时间的博弈排序问题,这个mutcjcj模型为m台恒速机,每台机器的速度分别为s1,s2,sm,且s1器没有激活费用,要优化的目标函数为总完工时间.

s2s3sm,每台机

Q（2）mutcjCmax即m台恒速机上社会成本为时间表长度的博弈排序问题,这个

模型为m台恒速机,每台机器的速度分别为s1,s2,sm,且s1机器没有激活费用,要优化的目标函数为最大完工时间.

定义2.1 如果G,POA(the price of anarchy)表示最差的纳什均衡排序的目标函数值与最优值的比值,即

POA(G)maxgsOPTG.

sG

s2s3sm,每台

POS（the price of stability）表示最好的纳什均衡排序的目标函数值与最优值的比值,即

POS(G)mingsOPTG.

sG

2.3 m台恒速机上社会成本为总完工时间的博弈排序问题

定理2.1 在任意纳什均衡排序中,机器的负载都满足：

LiLk

pj

sk,

jJi,1i,km.

其中,Ji表示第i台机器上的工件.

定理2.1简单的说就是,在任意纳什排序中,没有工件可以通过单方面的改变机器来减少它的费用.下面,我们根据理2.1来证明C1的上界,我们这里所说的C1指的是纳什排序中所有任务的总的花费.

定理2.2 在任意纳什均衡排序中,机器的总的费用满足：

e

e

n1

CniLiPmss

i1k1

e1

m. 

证明：对于任意常数i1im,我们选择引理2.1中的k和j,得到下面不等式

L

k

min1km

L

k



P



m

si

i1

,

pjminpj

jJi

Lisi

. ni

其中任意常数i表示第i台机器,Lk表示第k台机器的负载,j表示第i台机器上其中一个工件. 上面两个不等式很明显,因此,我们得到

LiLk



pjsk Lisi

. nisk

P

s

i1

m

i

定理2.2中C1的上界取决于所有工件的总长度,工件的个数,机器的个数.下面我们得到结果

m

e

C

e1



nL

i

i1

i

m

ni

i1

P

s

i1

m



i1

m

i

Lisi

sk

n

P

s

i1

m



i

1

P sk

n1

mssP,

1k

证毕 然而在最优排序中,所有任务的总的花费为：

Cni*L*i

*

1

i1

m

L*i

i1

m



jJ1

p

s1

j



jJ2

p

s2

j



jJm

p

sm

j



P

. sm

下面我们用最差的纳什均衡的目标函数值与最优值之间的比值来衡量纳什排序的质量,即POA.

n1Pe

msskC11 *

PC1

sm

smnsmms1sk

smn1. s1m

因为上述不等式对于恒速机下的问题J,M的所有例子都成立,所以

POA

smn

1, s1m

得证 以上分析我们得到 POA

下面我们考虑一个例子来求POS的下界.

例子2.1 有m台机器,m1个长度为si的大工件,n个长度为

smn1. s1m

sm

的小工件.假设n

nm,n是mm1的倍数,即nkmm1.

考虑纳什状态下的任务分配：每个大工件分别安排在前m1个机器上,所有的小工件都安排在最后一台机器上.所以,纳什状态下的总费用为：

C1em1

sm1

nn nsm

m1n.

考虑这样一种分配：所有的大工件都安排在一台机器上,所有的小工件安排在剩下的机器上.这个分配得到最优状态下总费用的上界.

s2s3sm1sm1sm1

C1*1m1kmkmkmkm sss1ns2nsm11

s1s2sm1kmsmsmsmm1  sm1sss13m2

2

m1sm1

s1

kmsmm1

m1s2



sm

m12km. s1



下面我们用最好的纳什均衡的目标函数值与最优值之间的比值来衡量纳什排序的质量,即POS.

C1em1n

 *

2C1m

m1kms1



所以,以上分析我们得到POS

s1m1nm1, smm13n

s1nm1m1. smm13n

2.4 m台恒速机上社会成本为时间表长度的博弈问题

这个模型中有

m台恒速机,每台机器的速度分别为s1,s2,sm,且

s1s2s3sm,机器没有激活费用,要优化的目标函数为最大完工时间.

e

定理2.4 在任意纳什排序中,机器的最大完工时间满足：Cmax

Pp

min. ms1s1

证明：在纳什排序中

m

, 1im

CiminCi

P

p j  p min ,

由上面两个不等式,我们得到

s

i1

i

C

e

max

Ci



P

pjsk



s

i1

m

i

pminsk

Ppmin

ms1 s1

,

得证

而在最优排序中,机器的最大完工时间满足

*Lii1m

Cmax

*

m

jJ1

j

p

s1





jJm

p

sm

j



jJ1

p

sm

j



jJm

p

sm

j



P. msm

下面我们用最差的纳什均衡的目标函数值与最优值之间的比值来衡量纳什排序的质量,即POA.

e

PCmaxpminmsm *Cmaxms1s1P





smmpmin1s1P

根据以上分析我们得到

sms1P1P

sm2

s1

,

sms1

POA2

.

2.5 总结

纳什均衡不一定是最优的,实际上还常常与最优值差距很大.在纳什均衡中,在每个工件的策略都不改变的情况下,任何一个工件都不能通过单方面的改变自己的策略来降低它的成本,但是纳什均衡不一定是最优的,实际上还常常与最优值存在很大差距.本章考虑了

m台恒速机下的博弈排序问题,在这里我们使用POA（the price of anarchy）和POS（the

price of stability）来分析纳什均衡的质量.当目标函数是总完工时间时,求得

POA

smnsnm1m1sm

.当目标函数是时间表长度时,求得1,POS1POA2

s1msmm13ns1

.

第3章 带激活费用的恒速机博弈排序

本章研究了两台和m台恒速机情形下的资源分配问题.有两台机器时,我们假设机器

的速度是1和a,每台机器的激活费用和它的速度相等；有m台机器时,我们假设每台机器的速度都不同,每台机器的激活费用都为1.研究的整体目标函数是机器的总完工时间和激活费用之和.我们用POA来衡量纳什均衡时的最差的整体目标函数值与最优值之间的差异.

3.1引言

不同人员之间成本花费的分配是一个常见的问题,所以大量的分配规则被提出（Moulin and Shenker[17][18]1992,2001; Herzog, shenker and Estrin [16]1997),这些分配规则都注重效率和公平.一些学者研究的重点是基于自私代理行为和不同的费用分摊规则下的纳什均衡的存在和效率问题（Perakis[19] 2007, Perakis and Roels[20] 2007, Bernstein and Federgruen[15] 2001）. 在这个模型中,我们假设有有限台恒速机,每台机器使用时都有额外的激活费用.工件自主选择机器进行加工,而不是被特定安排到某台机器上进行加工.在本章中,我们研究的整体目标函数为所有被激活机器的总完工时间和总的激活费用之和.

3.2 问题描述

本章中要用到的数学符号如下：

pj: 第j个工件的加工时间.

B：机器的激活费用.

bjs：在s这种排序下,工件j的分担激活费用. pj: 第j个工件Jj的加工所用的时间.

cjs:在s这种排序下,工件j的完工时间.

ni：第i台机器上工件的个数.

Li(s)：在s这种排序下,工件Jj在机器i上的负载.

工件j的个体费用函数(Individual cost function)为：cjsLisbjs, 其中,bjs

pjLisB.

举一个例子：激活费用B18,两个长度分别为1和2的工件.则每个工件的完工时间分别c1(s)39,c2(s)32315.

引理3.1（Michal Feldman, Tami Tamir 2012）在任意纳什排序s中,对于任意工件

j,cj(s)pjB.

引理3.2（Michal Feldman, Tami Tamir 2012）长度为pj的工件被安排在负载小于激活费用B的机器上,且pjB,不能通过转移到负载大于B的机器上或者用一台专用机减少它的花费.

引理3.3（Michal Feldman, Tami Tamir 2012）如果激活费用Bjpj,在纳什排序s中所有工件被安排到一台机器上.

3.3 两台带激活费用的恒速机POA分析

1,2,,n.设第一台机器M1的速度为1,激 有两台机器MM1,M2,加工n个工件J

活费用也为1,设第二台机器的速度为a,激活费用也为a,且a1.W为所有工件的加工时间之和,Wpj.

j1n

S表示问题J,M的所有排序

sS

s的集合,则最优排序的整体目标函数值为：

OPTminSCs.G是纳什均衡解的集合,如果G,我们用POA表示最差的纳什均衡解与G的最优值的比值,即

POA(G)maxgsG.

sG

定理3.1 若有两台带激活费用的恒速机可被激活,速度分别为1和a,则POA1a. 证明 当Wa时,OPT1W,则

POA

1aW 1W



1a(1aW)

1W

1a,

当Wa时,OPTmina



WW

,1a,则 a1a

POA

1aW

WW

mina,1a

a1a

1aW1aW

max, a1a

a1a

a2aaW1a21aW max,22

aW1aW

a21a1aW1a31aW

max,22

aW1aW

1a, 所以,我们得到POA1a.

3.4 m台带激活费用的恒速机POA分析

研究了有限台恒速机的情形,整体目标函数为所有被激活机器的总完工时间和总的激

活费用之和.有m台机器MM1,M2,,Mm,机器台数m2,每台机器的速度不同,加工n个工件J1,2,,n.每一个工件jJ都有一个长度pj,pj0,B表示机器的激活费用,不失一般性,可设m台恒速机的激活费用均为1,即B1. 定理3.1 若WB,激活一台机器,SCsOPT,则POA1.

W

s1

定理3.2 若有m台带激活费用的恒速机可被激活,则POA

P1nmin

sm

mn

证明: 设有m台机器,n个工件,每台机器的速度分别为s1,s2,s3,sm,且

s1s2s3sm.

所有机器都激活时工件的加工时间之和为W,激活费用为B,令B1

WcjniLin1

jJ1

ps1

j

n2

jJ2

ps2

j

nm

jJm

psm

j

.

Wi表示激活i台机器时工件的加工时间之和.

排序s的整体目标函数定义如下：

gscjms,

其中cj为排序s下工件的总完工时间,ms表示被激活机器的台数.

对于任意的排序s,有

WmnmaxgssmsGOPTGminiWi

W

s1Pmininmin1imsmmn

W

s1 max1imPmininsmmn

Wmns1P1nmin

sm

POA(G)maxgsG

sG

W mns1由上述不等式,我们得到 POA 1nmin

sm

3.5 总结

本章考虑了两台和m台带激活费用的恒速机模型,研究的整体目标函数是机器的总完

工时间和激活费用之和,最后我们用POA来衡量纳什均衡时的最差的整体目标函数值与最

优值之间的差异.两台机器时,我们假设机器的速度分别是1和a,每台机器的激活费用和

它的速度相等,求得POA1a.m台机器时,我们假设机器的激活费用都是1,每台机器的

mn速度不同,s1s2s3sm,求得s1POAPW

1nminsm

参考文献

[1] Anshelevich E, Dasgupta A, Kleinberg JM, Wexler T, Roughgarden T. The price of stability

for network design with fair cost allocation[J]. Sympos. IEEE Computer Society, 2004,

295-304.

[2] Albers S, Elits S, Even-Dar E, Mansour Y, Roditty L. On Nash equilibria for a network

creation game. Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (ACM, New

York). 2006, 84-93.

[3] Bonifaci V, Harks T, Schafer G. Stackelberg routing in arbitrary networks [J]. Mathematics of

Operations Research, 2010, 35(2): 330-346.

[4] Cominetti R. Correa JR, Stier-Moses NE. The impact of oligopolistic competition in

networks.[J]. Operations Research,2009, 57(6): 1421-1437.

[5] Correa JR, Schulz AS, Stier-Moses NE. Selfish routing in capacitated networks.[J].

Mathematics of Operations Research, 2004, 29(4): 961-976.

[6] Correa JR, Schulz AS, Stier-Moses NE. Fast, fair, and efficient flows in networks. [J].

Operations Research, 2007,55(2):215–225.

[7] Epstein Amir, Michal Feldman, and Yishay Mansour. Strong Equilibrium in Cost Sharing

Connection Games[J]. Proceedings of the 8th ACM conference on Electronic commerce,

2007,67(1):51-68 .

[8] Jain K, Mahdian M. Cost sharing[J]. Algorithmic Game Theory (Cambridge University Press,

New York), 2007,385–410.

[9] 唐恒永,赵传立. 排序引论 [M]. 北京：科学出版社, 2002.

[10] 唐国春,樊保强,刘丽丽. 排序博弈的分类、进展和展望[J]. 重庆师范大学学

报,2014,31(1):6-14.

[11] Feigenbaum, J., Papadimitriou, C. H., & Shenker, S. Sharing the cost of multicast

transmissions[J]. Journal of Computer and System Sciences,2001, 63(1):21–41.

[12] Feldman, M., & Tamir, T. Conflicting congestion effects in resource allocation games[J].

Operations Research, 2012,60(3):529-540.

[13] Koutsoupias E, Papadimitriou C. Worst-case equilibria. Comput[J]. Sci. Rev.

1999,3(2):65–69.

[14] Papadimitriou C. Algorithms, games, and the Internet[J]. Proc. 33rd ACM Sympos. Theory

Comput. (STOC) (ACM, New York), 2001,749–753.

[15] Bernstein F, Federgruen A. Decentralized supply chains with competing retailers under

demand uncertainty[J]. Management Sci, 2001,51(1):18–29.

[16] Herzog S, Shenker S, Estrin D. Sharing the “cost” of multicast trees: An axiomatic

analysis[J]. IEEE/ACM Trans. Networking, 1997,5(6):847–860.

[17] Moulin, Herve, and Scott Shenker. Serial cost sharing[J]. Econometrica: Journal of the

Econometric Society, 1992, 60(5):1009–1037.

[18] Moulin H, Shenker S. Strategyproof sharing of submodular costs: Budget balance versus

efficiency[J]. Econom. Theory, 2001,18(3):511–533.

[19] Perakis G. The “price of anarchy” under nonlinear and asymmetric costs[J]. Math. Oper. Res,

2007),32(3):614–628.

[20] Perakis G, Roels G, The price of anarchy in supply chains: Quantifying the efficiency of

price-only contracts[J]. Management Sci, 2007,53(8):1249–1268.

[21] Vöcking B, In Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay Vazirani, eds. Selfish

load balancing[J]. Algorithmic Game Theory, 2007,517–542.

[22] B. Chen and S. Gurel. Resource Allocation Games of Utilitarian Social Objectives[J].

Journal of Scheduling, 2011,1-8.

[23] C. Imreh and J. Noga. Scheduling with machine cost[M]. Randomization, Approximation,

and Combinatorial Optimization. Algorithms and Techniques. 1999,168-176.

[24] E. Anshelevich, A. Dasgupta, J. M. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden.

The price of stability for network design with fair cost allocation[J]. Foundations of Computer Science,2004.45th Annual IEEE Symposium on Foun- dations of Computer Science, 2004, 295-304 .

[25] Fotakis D, Mavronicolas M, Kontogiannis S, Spiraklis P . The structure and complexity of

Nash equilibria for a selfish routing game[J]. Internat. Colloquium on Automata, Languages, and Programming (ICALP) (Springer, Berlin),2002, 510–519.

[26] Bo Chen, Sinan Gurel. Efficiency analysis of load balancing games with and without

activation costs[J]. Journal of Scheduling, 2012,15:157-164.

[27] Heydenreich, B., Müller, R., & Uetz, M. Games and mechanism design in machine

scheduling introduction[J]. Production and Operations Management, 2007,16(4), 437–454.

[28] Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., & Rode, M. Nash equilibria in

discrete routing games with convex latency functions[J]. Journal of Computer and System Sciences. 2008, 74:1199–1225.

[29] Aland, S., Dumrauf, D., Gairing, M., Monien, B., & Schoppmann, F. Exact price of anarchy

for polynomial congestion games[J]. Berlin: Springer. 2006, 218–229.

[30] Roughgarden T. Intrinsic robustness of the price of anarchy[C],Proceedings of the

forty-first annual ACM symposium on Theory of computing. ACM, 2009: 513-522.

[31] YuZhong Zhang, SongSong Li. Strong stability of Nash equilibria in load balancing

games[J]. Science China Mathematics, 2014,57(7):1361-1374.

在读期间发表的学术论文及研究成果

在读期间发表的学术论文及研究成果

[1] 张玉忠,李雨洁. 无激活费用的恒速机博弈模型分析 已完成

致谢

致谢

本论文是在曲阜师范大学管理学院张玉忠教授的悉心指导下完成的.张老师作为一名优秀的、经验丰富的教师,具有丰富的知识和经验,在整个论文写作过程中,对我进行了耐心的指导和帮助,提出严格要求,引导我不断开阔思路,为我答疑解惑,鼓励我大胆创新,使我在这一段宝贵的时光中,既增长了知识、开阔了视野、锻炼了心态,又培养了良好的科研精神.在此,我向我的指导老师表示最诚挚的谢意！

在三年学习期间也得到了其他各位老师的关心和帮助,在此一并向他们表示衷心的感

谢！