| 标题 | 中式餐厅博弈论 |
| 范文 | 张红 摘要：本文把策略决策引入到中式餐厅过程，提出了一种新的博弈，称为中式餐厅博弈，作为一种新的通用框架，用于分析网络外部性的个体决策问题。分析表明，在策略决策过程中，最终将实现博弈中客户之间的效用平衡。本文定义了平衡分组来描述博弈的预测结果，并通过简单的算法找到结果。仿真结果证实，中式餐厅博弈中的理性顾客自动达到负载平衡，从而减少负面网络外部性的影响。 关键词：策略决策;中式餐厅;博弈 中图分类号：TP18? ? ? ? 文献标识码：A? ? ? ? 文章编号：1009-3044（2019）03-0029-04 理性代理如何在网络中做出合理的决策是众多研究领域中的一个重要问题。一个代理人的决定可能受到两个因素的影响：他对系统的了解和其他代理人的决定。前者是由代理人的信息收集和学习能力决定的[1]。后者是本文的重点，涉及网络外部性，即其他代理人行为对一个代理人奖励的影响。网络外部性是经济学中的经典话题，特别是在协调博弈论中。网络外部性可以是正的，也可以是负的。当网络外部性为正时，代理人在做出相同决策时具有更高的效用，问题可以被建模为一个协调博弈[2–4]。 当外部性为负时，它就变成了一种反协调博弈，在这种博弈中，代理人往往会为了更高的效用而与其他人做出不同的决定。消极网络外部性在许多涉及资源共享或竞争的应用中起着重要的作用[5]。例如，在频谱接入问题中，用户倾向于接入干扰小的频谱，以获得更好的传输质量。然而，多个代理可能选择接入相同的频谱。在这种情况下，代理需要根据某些访问策略共享频谱。一般来说，越多的代理接入相同的频谱，它们所使用的资源就越少。这就把消极的网络外部性引入到问题中。另一个例子是Groupon等社交网站上的交易选择问题。在打折交易中，提供交易的企业可能会收到大量的顾客。大量的顾客对产品的质量有负面的网络外部性，从而损害了顾客的体验。在这些例子中，负面网络外部性降低了做出相同决策的代理的效用。作为一个理性的代理人，在做出决定时，应该考虑到这种退化。这种消极的网络外部性存在于许多不同的应用中，如云计算和智能电网。中式餐厅过程是机器学习中无界对象的非参数学习方法[6]。在中国餐厅过程中，我们有一个拥有大数量餐桌的餐馆。顾客依次到达餐厅。当一个客户进入时，他要么加入其他客户已经开始的餐桌，要么请求一个新餐桌。他决定的概率与每个餐桌中的能容纳的顾户数有关。一般来说，如果一个餐桌能被更多的顧客占用，那么一个新客户更有可能加入该表，并且预定一个新餐桌的概率是预定的[7]。这个过程提供了一个系统的方法来构造未知分布模型的参数，中式餐厅过程提供了一个适当的结构来制定具有负外部性的网络中的决策问题。将策略行为引入到非策略性中式餐厅过程中，为社会学习问题提出了一种新的模型，带网络外部性的中式餐馆博弈模型。考虑带有餐桌和理性顾客的中餐馆，每个客户可以要求就座在任何一张桌子上。假设顾客喜欢更大的用餐空间，因此，他们可能喜欢更大的桌子。然而，如果多个客户请求同一个餐桌，客户可能需要与其他人表共享该餐桌。在这种情况下，顾客的用餐体验由于空间的减少而受到损害，即负的网络外部性在这里起着作用。因此，作为一个理性的客户，在进行餐桌选择时，必须考虑餐桌的大小和其他客户的决定。理性的客户如何在这样的游戏模式下做出决定是本文的主要关注点。本文将研究同时进行顾客决策的中式餐馆游戏。[8]中讨论了连续的中式餐厅游戏，其中包括让顾客依次做出决定的社会学习效果。 1 系统模型 考虑一个中式餐厅，有K个餐桌，第i个餐桌的尺寸是[Ri]。有N个顾客，每个顾客请求一个餐桌，顾客同时做出策略。定义每个顾客所选的餐桌集合为X={1，…，K}，其中[xi∈X]是第i个客户的选择。第i个客户的效用函数为[U（Rxi，nxi）]，其中[nxi]是选择餐桌[xi]的顾客个数。效用函数是[Rxi]的增函数，是[nxi]的减函数。注意，[nxi]建模了消极的网络外部特性，因为其他顾客对餐桌的共享引来了效用的下降。设第i个餐桌上顾客数为[ni]，[n=n1，n2，…，nk]是餐桌分组，分组对于下面的讨论很重要。 先从只有两个顾客和两张餐桌的简单情况开始，餐桌1的尺寸是[R1=L]，餐桌2的尺寸是[R2=S<L]，假设对手的选择已知，可能是大餐桌，也可能是小餐桌，理性顾客最选择使自己的效用函数最大的餐桌，当对手的选择是小餐桌，顾客选择大餐桌，因为[U（L，1）>U（S，2） ];反之，如果对手选了小餐桌，顾客的选择取决于消极网络外部特性的严重程度，当[U（L，2）>U（S，1） ]，顾客会选择分享大餐桌，反之，顾客选择小餐桌。结果显示，即使两个顾客对真实网络状态（哪个桌子更大）有着完全的了解，他们也可能不会选择均衡中的更大者。相反，均衡取决于负网络外部性的严重程度。如果网络外部性导致不可接受的惩罚，那么客户应该选择不同的餐桌来避免它。 下面考虑一般的场景，有N个顾客和K个餐桌。餐桌的尺寸给定为[R1，R2，…RK]，对所有顾客都已知。客户是理性的，他们在这个博弈中的目标是最大化自己的效用函数。然而，由于他们的效用函数不仅取决于自己的行为，也取决于他人的行为，因此，消费者在博弈中的行为受到彼此的影响。 策略描述了博弈者在博弈中可能遇到的情况下做出的选择。在中式餐厅博弈中，客户的策略应该是从其他客户的餐桌选择到自己选择的映射。[nj]是选择第i个餐桌的顾客个数。[n-i=n-i，1，n-i，2，…，n-i，k]，其中[n-i，j]代表除了顾客i，选择餐桌j的顾客数。理性顾客i应该做出的选择为 （1）式描述了特殊的策略集合，称为最佳反应，代表了顾客在已知其他顾客选择的情况下，使得自己的效用函数最大的最佳选择。也就是，给定第i个顾客的策略空间[Ai]以及效用函数[ui（xi，x-i）]，其中[xi]是第i个顾客选择，[x-i]是除了顾客i，其他所有顾客的选择，顾客i的最佳选择是[BEi（x-i）=argmaxx∈AiUi（x，x-i） ]。 2 纳什均衡 纳什均衡是一个流行的概念，用于预测理性消费者的博弈结果。非正式地说，纳什均衡是一个行动概况，其中每个客户的决策是对其他客户决策的最好反应。因为所有的顾客都使用他们最好的决策，所以没有一个人有背离他们的决策的动机。正式地说，考虑有 [1，2，…N]的顾客的博弈，每个顾客的行动空间为[Ai] 效用函数为[ui（xi，x-i）]。其中[xi]是第i个顾客选择，[x-i]是除了顾客i，其他所有顾客的选择。纳什均衡是行动集[X*=x*1，x*2…，x*N]，其中[BEi（x*-i）=x*i]。 3 均衡分组 根据纳什均衡的定义，下面给出中式餐厅博弈中纳什均衡的充分必要条件。 定理一：给定顾客集[1，2，…，N]和餐桌集[1，2，…，K]，对于中式餐厅博弈的任何纳什均衡，他的均衡分组[n*]必须满足[U（Rx，n*x）≥U（Ry，n*y+1），] if [nx>0，?x，y∈1，…，K]? ? ? ? ?（2） 证明： 充分条件：假设所有顾客的行动集为[X=x1，x2…，xN]，此行动集导致的分组为[n*=n*1，…n*k]，满足式（2）。不失一般性，假设顾客i选择餐桌j，也就是[xi=j]，可以得出[ui（xi，x-i）=U（Rj，n*j）]。当顾客i选择其他任何餐桌[k≠j，也就是x'i=k≠xi=j，]那么他的效用函数为 由定理1，我们可以知道，在纳什均衡下，顾客的效用值并不会因为偏离到另外一张餐桌而变得更高，由于消极的网络外部性的干扰，任何一张餐桌的偏离都会降低这张餐桌上所有顾客的效用值。式（2）说明即使顾客选择同样大小的餐桌，最后也可能出现不同的效用。比如，假设有一个餐厅里面有三个顾客以及两张完全相同的餐桌，因为顾客数为三，所以在纳什均衡中，肯定会有两个顾客选择同一张餐桌，而另一张餐桌只有一位顾客。 很明显，如果在中式餐厅博弈中有一个纳什均衡的存在，在这个纳什均衡里，我们交换任意两位顾客的行为，从而在遵守式（2）的充要条件的情况下。建立一个新的纳什均衡。这样，纳什均衡就不是唯一的，但是均衡分组却是唯一的，由定理2所述。 定理2：当式（2）中的不等性对于条件[nx>0]，[? x，y∈{1，…，K}]都成立，均衡分组[n*]是唯一的。 这与式（6）相矛盾，因此纳什均衡在式（2）中严格不等条件下是唯一的。注意，当均衡分组不是唯一的，必然存在满足（2）式取等号的餐桌，这意味着这些餐桌是可交换的，因为他们提供相同的预期效用均衡。如果所有的餐桌具有相同的大小，那么所有餐桌都可以交换，这是足够的，但不是必要的，这是中式餐厅流程中最初的假设。在给出均衡分组时，客户选择对应餐桌的效用也确定了。因此，当我们对系统效率而不是个人效用感兴趣时，均衡分组就足以描述中式餐厅博弈的最终状态。 4 均衡分组算法 下面展示如何通过一个贪婪算法构造一个平衡分组。在最初的博弈中，客户同时做出决定，这使得结果很难预测。然而，通过把博弈结构改成一个依次的博弈，餐桌之间的平衡可以很容易地观察到。在贪婪算法中，顾客依次做出他们的选择，顾客i第i个做出选择。我们让顾客以短视的方式做出选择，也就是说，他们选择的餐桌是基于他们已经观测到的，可以最大化他们目前的效用函数。设[ni=n1i，n2i，…，nki]，是顾客i观测到分组情况，其中[j=1Knji=i-1]，顾客i做出的选择是由下式决定的： 定理3：算法1输出的分组得到的分组是均衡分组，此外，中式餐厅博弈至少存在一个纳什均衡。 由于算法1有限步且总是有输出，所以保证了纳什均衡的存在性。此外，相应的分组是一个均衡分组。算法复杂性是O（NK），效率很高。如果定理2的条件满足，均衡分组是唯一的。 5 仿真结果 考虑有5张餐桌，10位顾客的中式餐厅，这些桌子的尺寸随机给定为[13，56，80，28，93]，效用函数为[u（R，n）=ln（R/n）]，这粗略代表了无线网络的期望吞吐量，把[R/N]作为信噪比，每个用户引起的干扰为1，我们首先验证算法得到的分组是不是均衡分组，我们比较了分组[n*]下的效用与“改变一位顾客（cho）”机制下的效用，在“改变一位顾客”的机制下，餐桌j的顾客效用为[u（Rj，n*j+1）]，这是顾客偏离他的最初选择[xi]，转移到餐桌[j≠xi]。 通过观察MATLAB仿真對比图，我们可知在“改变一位顾客”机制下的效用严格小于分组[n*]下的效用。这也确定了在分组[n*]下的顾客没有偏离分组的动机。因此分组[n*]是中式餐厅博弈下的均衡分组。 下面进一步验证中式餐厅博弈均衡分组的效率，我们把它与两种启发式餐桌分配机制：Round Robin机制和Largest Table机制相比较。在Round Robin机制中，顾客被依次分配到各个餐桌;而在Largest Table机制中，所有顾客选择最大的餐桌。 从图5中可以看出，在均衡分组下，顾客效用高且平衡，平均效用最高。在Round Robin机制中，1号顾客和6号顾客都选择了餐桌1，因为餐桌1是最小的餐桌，所以效用很低，从而导致该机制下平均效用低于均衡分组下的效用。而在Largest Table机制中，每位顾客选择了最大的餐桌，每位顾客的效用相等，但消极的网络外部性使得其效用很低。 通过以上几种机制的比较，中餐厅博弈下的均衡分组最大化了顾客的平均效用，使得每位顾客的策略达到最佳。仿真结果可以证明，中餐厅博弈中的理性消费者会自动达到负载平衡，以减少来自消极的网络外部性的干扰。通过分析，在策略决策中，最后实现了博弈中参与者之间的效用平衡。因此中餐厅博弈可以作为一种新的通用框架来解决网络外部性的个体决策问题。 与认知网络相同，在中餐厅博弈中每位顾客的效用改变都会导致整体效用发生变化。所以将中餐厅理论应用在认知无线电的信道分配问题中，当二级用户采取最佳策略时，整个网络的效用最大化，系统就能达到纳什均衡点，最终提高无线频谱资源的利用率。 参考文献： [1] R.W. Cooper. Coordination games： Complementarities and macroeconomics. Cambridge University Press， 1999. [2] M.L. Katz and C. Shapiro. Technology adoption in the presence of network externalities. The journal of political economy， pages 822–841， 1986. [3] W.H. Sandholm. Negative externalities and evolutionary implementation. Review of Economic Studies， 72（3）：885–915，2005. [4] G. Fagiolo. Endogenous neighborhood formation in a local coordination model with negative network externalities. Journal of Economic Dynamics and Control， 29（1-2）：297–319， 2005. [5] C.Y Wang， Y. Chen， and K. J. R. Liu. Chinese Restaurant Game-Part II：Applications to Cognitive Radio， Cloud Computing， and Online Social Networking. Arxiv preprint arXiv：1112.2187， 2011. [6] D. Aldous， I. Ibragimov， J. Jacod， and D. Aldous. Exchangeability and related topics. In Lecture Notes in Mathematics， volume 1117， pages 1–198. Springer Berlin / Heidelberg， 1985. 10.1007/BFb0099421. [7] J. Pitman. Exchangeable and partially exchangeable random partitions. Probability Theory and Related Fields， 102（2）：145–158， 1995. [8] C.Y Wang， Y. Chen， and K. J. R. Liu， Sequential Chinese Restaurant Game， IEEE Trans. Signal Process， 61（3）：571-584 · February 2013. 【通聯编辑：唐一东】 |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。