英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料
在可视的重试单服务器队列中的均衡止步策略
摘要
我们认为马尔可夫单服务器队列在开和关周期之间交替。到达后，客户观察队列长度并决定进入或者止步。在两种情况下，根据服务器状态的信息，我们得出平衡阈值止步策略。
关键词：排队 止步 不可靠服务器 平衡策略 部分信息水平
第1章 引言
在过去几十年中，人们对排队系统的经济分析已经出现了兴趣。这些想法至少回溯到Naor [8]和Edelson和Hildebrand [2]的开创性作品。在这样的经济分析中，客户被允许采取他们自己的决定，因此系统可以被建模为客户之间的博弈。基本问题是确定纳什均衡。有关该领域的介绍，请参见[5]。
在排队系统的博弈理论分析中的文献的重要部分专注于二维马尔可夫模型（参见例如[3,4,1]）。在这样的模型中，系统的状态由对应于客户的数量和一些附加信息的两个变量表示。具有一般服务时间的系统的分析非常复杂（参见例如[7,6]中的M /G /1队列的分析）。 因此，二维系统的分析局限于几乎所有相关论文中的马尔可夫情况。
在本文中，我们考虑具有不可靠服务器的马尔可夫单服务器队列。客户观察队列长度，然后决定是加入还是止步。 我们分别考虑两个信息案例，并且我们确定（纳什）均衡分界策略。
本文的结构如下。在第2节，我们描述模型和决策结构。在第3节，我们确定均衡策略。最后，在第4节，我们讨论一些定性的影响并且指出可能的概括。
第2章 模型
我们认为单服务器队列具有无限的等待室，受到具有速率lambda;的泊松到达过程。我们假设服务时间是以速率mu;的指数分布的。服务器在开和关周期之间交替也是分别以速率lambda;和mu;的指数分布的。
我们用(N(t),I(t))来表示t时刻系统的状态，其中(N(t),I(t))表示客户的数量，(0:关闭，1：开启)表示服务器的状态，过程{(N(t),I(t)):tge;0}是具有非零转变速率的连续时间马尔可夫链
我们假设客户被允许决定是否加入或阻止他们的到来。每个客户获得R单位的收益，以完成服务。此外，存在从她/他到达系统的时间到他/她在被服务之后离开的时间连续累积的每单位时间的C单位的等待成本。客户希望最大化其预期净收益。他们的决定只有在他们的到来时刻，他们是不可撤销的，在这种意义上，不允许重复客户和退出进入客户。
我们考虑可视的情况，其中客户在到达时被告知队列长度。我们分别研究关于客户是否还观察服务器的状态（完全可观察和几乎可观察的情况）的两个信息情况。这种情况可以被模拟为客户中的对称博弈。直觉上，如果一个策略是对自身的最佳响应，则它是一个平衡。 如果策略是针对任何策略的最佳反应，则此策略是弱势主导的。
第三章 平衡阈值策略
在本节中，我们将展示我们在上面定义的两个信息案例中存在阈值类型的均衡策略。
在完全可察情况下，一个纯阈值策略由一对(ne(0),ne(1))和在t时刻来到，观察(N(t),I(t))的形式表出。如果N(t)le;ne(I(t))则选择进入，否则拒绝进入。在几乎可察情况下，一个纯阈值策略由单个数ne和在t时刻来到，观察(N(t)，如果N(t)le;ne则选择进入，否则拒绝进入的形式表出。我们将分别处理这两种情况关于客户的信息水平。
在第一种情况下，我们有以下结果。
定理3.1在具有重试的完全可视的M/M/1队列中存在一对阈值
(1)
使得策略“在t时刻来到，观察(N(t),I(t))；如果N(t)le;ne(I(t))则选择进入，否则拒绝进入”是一个弱势主导策略。
证明 考虑进入系统的客户。如果她/他进入，她/他的预期净收益
其中
表示表示她/他预计平均逗留时间，在她/他到来之前的状态(n,i)时发现该系统。
通过第一步的论证，我们有系统
（3）
（4）
（5）
解决当n=0时（3）的系统结合（4）我们得到T(0,0)和T(0,1)。把（3）代入（5）中我们显然得到T(n,1)的一阶递归关系。我们可以迭代它来计算T(n,1)，接着我们再次用（3）来得到T(n,0)。因此，我们很容易得出结论
（6）
当S(n,i)gt;0时，顾客会倾向于进入系统，当S(n,i)=0时，顾客会选择进入或者不进入。通过求解S(n,i)ge;0，运用（2）和（6），我们得到到达的客户倾向于进入系统当且仅当nle;ne(i),其中(ne(0), ne(1))由（1）给出。这种策略是优选的，独立于其他顾客所做的选择，即它是一个弱势主导策略。
我们现在进行几乎可视的情况，其中到达的客户在到达时观察客户的数量，而不是服务器的状态。我们将在纯阈值策略类别中寻求均衡策略。为此，当客户遵循给定的纯阈值策略时，我们需要首先获得系统的稳定分布。我们有以下结果
命题3.2.考虑几乎可视的重试M/M/1队列，其中客户根据阈值策略“在t时刻来到，观察N(t)；如果N(t)le;ne则选择进入，否则拒绝进入”来进入系统。然后固定分布(p(n,i):(n,i)isin;{0,1,2hellip;hellip;,ne 1}times;{0,1})由：
（7）
（8）
（9）
（10）
其中A使用标准化方程和
（11）
（12）
证明 稳态分布(p(n,i))由平衡方程得到：
（13）
（14）
（15）
（16）
对于p(n,1)求解（14）并代入（16）我们得到
这是具有解的均匀二阶差分方程
（17）
由（11）给出的rho;1，rho;2是特征方程的根，c1，c2是要被确定的。我们可以容易地看到rho;1ne;rho;2。把（17）代入（14）我们可以得到
（18）
其中vi是由（12）给出的。将（17）和（18）中给出的p(n,0)和p(n,1)代入到（13）和（15）中我们得到
然后，使用标准化方程作为显式但涉及总和来计算唯一未知常数c1。使A= c1/rho;1我们有c1=Arho;1，c2=-Arho;2，稳态概率由（7）-（10）给出。
我们现在能够找到一个客户的预期净收益，该客户在她/他之前观察到n个客户并决定进入。 我们有以下结果。
命题3.3考虑几乎可视的重试M/M/1队列，其中客户根据阈值策略“在t时刻来到，观察N(t)；如果N(t)le;ne则选择进入，否则拒绝进入”来进入系统。观察n个客户并决定进入的客户的净收益由下式给出
（19）
（20）
其中
证明 如果她/他进入，对于观察到n个客户的客户，期望的净收益是
（21）
其中
表示她/他的预期平均逗留时间, 她/他在她/他的到来之前看到系统中的有n个顾客。调节她/他在到达时发现的服务器的状态并考虑（3）我们得到
（22）
i=1时T(n,1)由（6）给出。概率由客户发现服务器在她/他到达时处于不活动状态给出，她/他在她/他面前发现有n个客户的概率为
使用命题3.2中的稳态概率我们可以得到概率
使
使用（6）和（22）我们可以得到结论
（23）
（24）
现在T(n)的替代物在（21）中产生（19）和（20）。
为了排除客户不进入系统的琐碎情况，即使她/他在她/他面前没有找到顾客，我们假设（19）对于n=0是正的。在一些代数运算之后，我们看到这等同于条件
（25）
我们从现在开始假设。接下来，我们描述了在几乎可观察的情况下的平衡扰动纯阈值策略。我们有以下结果。
定理3.4. 定义序列(f1(n):n=0,1,2hellip;)和(f2(n):n=0,1,2hellip;)
（26）
（27）
然后存在有限的非负整数nLle;nU使得
（28）
（29）
或者
（30）
在几乎可视的重试M/M/1队列中，客户根据阈值策略“在t时刻来到，观察N(t)；如果N(t)le;ne则选择进入，否则拒绝进入”来进入系统的纯阈值策略对于neisin;{nL，nL 1，hellip;,nU}来说都是均衡策略。
证明 由（25）我们得到f1(0)gt;0。另外我们还能得到
所以如果nU 1是序列(f1(n))的第一个非正项的下标，我们得到条件（28）成立的有限数nU。还要注意（26）给出的f1(n)能被下述形式替代地写出
（31）
这是比较f1(n)和f2(n)的关键关系。的确，根据（31）中f1(n)的替代关系和（27）中f2(n)的定义，显然可得
（32）
特别地，我们得出结论
我们开始向后，从下标nU 1开始直到0，并且让nL成为序列(f2(n))的第一个正项下标。然后我们得到（29）。如果(f2(n))中从nU 1到0的所有项都是非正的，我们便得到（30）。
假设现在我们有一个模型，客户遵循一个纯粹的阈值策略“在t时刻来到，观察N(t)；如果N(t)le;ne则选择进入，否则拒绝进入”对一些固定阈值neisin;{nL，nL 1，hellip;,nU}。我们认为一个标记的客户在她/他的到来时刻。那么如果她/他观察到n个顾客并决定进入，她/她的净收益是由（19）和（20）给出。然后很容易看到，基于（19），（26）和（28），客户喜欢在她/他找到客户数nle;ne时进入排队系统。类似的，基于（20），（27）跟（29）或者（30）。我们发现她/他倾向于拒绝进入当她/他发现顾客数n=ne 1时。因此，我们得出结论，这样的策略确实是对自身的最好的反应，即平衡。
定理3.4提供了一种算法，以确定几乎可视的模型的均衡策略。必须开始计算f1(n)直到第一个否定项。这种“向前”过程产生最高的平衡阈值nU。然后，必须开始计算f2(n)从f2(nU 1)开始计算，并向前到0，直到第一个正项。这种“向后”过程产生最低的平衡阈值nL。
第四章 讨论和未来研究
虽然在完全可视的情况下存在一个独特的弱主导策略完全解决了问题，在几乎可视的情况下多重均衡的存在使得客户行为的问题具有开放性。在这个意义上，期望用于比较各种平衡的理论框架。另一个感兴趣的问题是存在这种类型的平衡混合阈值策略“在t时刻来到，观察N(t)；如果N(t)le;ne-1则选择进入；如果N(t)=ne则以qe的概率进入，否则拒绝进入”。在本模型中，我们有一个“跟随人群”（FTC）情况，在平衡中，客户倾向于采用其他客户的行为。因此，在每两个连续的平衡纯阈值策略之间存在平衡混合阈值策略（参见[5]，第1章）。根据定义，我们有一个FTC的情况对所有其他人采用的战略x的最优反应是x在增加。在本模型中，让我们考虑由（21）给出的函数Sne(n)，其给出当其他人遵循阈值策略ne时，观察队列长度n之后进入的客户的预期净收益。假设现在其他客户采用策略ne 1。然后被标记的客户的利益函数Sne 1(n)与Sne(n)一致，对所有的n=0,1,hellip;,ne，并且
（由（21），（23），（24）和（32）得到）。由此我们可以得出结论，当其他人遵循策略ne<!-- 剩余内容已隐藏，支付完成后下载完整资料
资料编号：[141901]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
课题毕业论文、外文翻译、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
