2019-06-30 | 编辑：文/先进制造部

纳什均衡是一个关于理性行为的解的重要概念，它指的是这样一种状态：没有局中人有动机单方面背离他的选择。为了评估均衡的效率，通常使用的一种标准度量是无政府代价(price of anarchy)，它等于最坏纳什均衡下的社会费用与最优解对应的社会费用之比。

在负载均衡博弈(load balancing game)中，一个随机化调度程序随机地选取一个对所有局中人的排列，并将它作为在所有设施上局中人们的排序。一个局中人的费用不仅依赖于他选择的设施，还依赖于他在这个排序中的位置。粗略地说，对于一个局中人而言，排在他前面的人越多，他所产生的费用就越多。这个模型刻画了实际生活中的很多事例。它可以被看作是对一种分层系统的改进，在这种系统中，高等级的人被赋予优先接受服务的权利。值得注意的一点是，虽然局中人的费用既依赖于他的策略（选择）又依赖于所有局中人的排序，但是社会费用只取决于局中人的选择，而与他们的排序无关。一旦所有人都做出了选择，无论他们的排序是怎样的，社会费用都是确定的——它等于所有在其所选设施上排在末位的局中人的费用的最大值。

在带有随机化调度程序的负载均衡博弈中，人们可能更想要优化某些其他的目标，而不是如上所述的最小化各自的（随机）费用。例如，一个热门节目的购票渠道即将开启，人们可以通过电话订票、网上订票或在售票处排队等不同渠道购票。一方面，主办方希望各个渠道可以均衡分担流量，以免某些渠道因过于拥塞而崩溃，并且这样门票也能够尽快售罄。另一方面，人们根据以往的信用、消费水平或一些随机因素被分为不同的等级，等级越高的人会越早被接待。每个人都想成为所有人中第一个接受服务的人，这样他就可以从尽可能多的可选座位中进行选择。因此，此时每个人的目标都是最大化其成为第一个被接待顾客的可能性。这其实就是‘赢或者回家（win-or-go-home）’准则的一个示例。给定任意一个负载均衡博弈的实例（由局中人、设施以及各设施的费用函数组成），不同的准则通常定义了不同的纳什均衡集，并将由此对无政府代价的值产生影响。

信息技术部陈旭瑾的研究小组最近研究了一类带有随机化调度程序的对称负载均衡博弈，其中，局中人带有单位权重。她们研究了该问题的无政府代价（即所有实例中无政府代价的最大值），其中，所有局中人都遵循以下四个决策准则之一。在‘末位出局（bottom-out）’准则下，每个局中人都力求选择一个最小化其成为输家可能性的设施，输家即产生费用最多的那个人。与之相反，‘赢或者回家（win-or-go-home）’准则代表了另一种极端的态度：最大化成为赢家的可能性，赢家即产生费用最少的那个人。另外两个比较温和的准则分别是‘平均案例分析（average-case-analysis）’和‘最小化最大后悔值（minimax-regret）’。当局中人都遵循‘平均案例分析’准则时，每个人都假设自己会排在所选设施上的所有局中人的中间位置（无论随机化调度程序选择了哪种排序），并且想要最小化其平均费用。而当局中人都遵循‘最小化最大后悔值’准则时，每个人的目标都是最小化他在所有可能排序中的最大后悔值，其中，局中人在一个排序中的最大后悔值等于他当前的费用和他在这个排序下选择另一个设施可能产生的最小费用之间的差值。

她们的研究结果可有助于确定在上述博弈模型中的表现良好的准则。当局中人按照‘末位出局’的准则保守地选择设施时，所有纳什均衡的效率都是令人满意的。而当他们遵循‘赢或者回家’准则时，所有人都争当第一，此时某些纳什均衡可能效率非常低，这意味着就负载均衡而言，过度竞争并不是一件好事。在‘平均案例分析’准则下，纳什均衡是高效率的，这说明一种既不保守也不激进的态度是有利于负载均衡的。而若局中人采用‘最小化最大后悔值’准则，那么当局中人数量远远超过设施数量时，纳什均衡的效率是很高的。

她们的研究论文已经被The 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA'2019)接受。