中式餐廳博弈論

張紅

摘要：本文把策略決策引入到中式餐廳過(guò)程，提出了一種新的博弈，稱為中式餐廳博弈，作為一種新的通用框架，用于分析網(wǎng)絡(luò)外部性的個(gè)體決策問(wèn)題。分析表明，在策略決策過(guò)程中，最終將實(shí)現(xiàn)博弈中客戶之間的效用平衡。本文定義了平衡分組來(lái)描述博弈的預(yù)測(cè)結(jié)果，并通過(guò)簡(jiǎn)單的算法找到結(jié)果。仿真結(jié)果證實(shí)，中式餐廳博弈中的理性顧客自動(dòng)達(dá)到負(fù)載平衡，從而減少負(fù)面網(wǎng)絡(luò)外部性的影響。

關(guān)鍵詞：策略決策;中式餐廳;博弈

中圖分類號(hào)：TP18? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? 文章編號(hào)：1009-3044（2019）03-0029-04

理性代理如何在網(wǎng)絡(luò)中做出合理的決策是眾多研究領(lǐng)域中的一個(gè)重要問(wèn)題。一個(gè)代理人的決定可能受到兩個(gè)因素的影響：他對(duì)系統(tǒng)的了解和其他代理人的決定。前者是由代理人的信息收集和學(xué)習(xí)能力決定的[1]。后者是本文的重點(diǎn)，涉及網(wǎng)絡(luò)外部性，即其他代理人行為對(duì)一個(gè)代理人獎(jiǎng)勵(lì)的影響。網(wǎng)絡(luò)外部性是經(jīng)濟(jì)學(xué)中的經(jīng)典話題，特別是在協(xié)調(diào)博弈論中。網(wǎng)絡(luò)外部性可以是正的，也可以是負(fù)的。當(dāng)網(wǎng)絡(luò)外部性為正時(shí)，代理人在做出相同決策時(shí)具有更高的效用，問(wèn)題可以被建模為一個(gè)協(xié)調(diào)博弈[2–4]。 當(dāng)外部性為負(fù)時(shí)，它就變成了一種反協(xié)調(diào)博弈，在這種博弈中，代理人往往會(huì)為了更高的效用而與其他人做出不同的決定。消極網(wǎng)絡(luò)外部性在許多涉及資源共享或競(jìng)爭(zhēng)的應(yīng)用中起著重要的作用[5]。例如，在頻譜接入問(wèn)題中，用戶傾向于接入干擾小的頻譜，以獲得更好的傳輸質(zhì)量。然而，多個(gè)代理可能選擇接入相同的頻譜。在這種情況下，代理需要根據(jù)某些訪問(wèn)策略共享頻譜。一般來(lái)說(shuō)，越多的代理接入相同的頻譜，它們所使用的資源就越少。這就把消極的網(wǎng)絡(luò)外部性引入到問(wèn)題中。另一個(gè)例子是Groupon等社交網(wǎng)站上的交易選擇問(wèn)題。在打折交易中，提供交易的企業(yè)可能會(huì)收到大量的顧客。大量的顧客對(duì)產(chǎn)品的質(zhì)量有負(fù)面的網(wǎng)絡(luò)外部性，從而損害了顧客的體驗(yàn)。在這些例子中，負(fù)面網(wǎng)絡(luò)外部性降低了做出相同決策的代理的效用。作為一個(gè)理性的代理人，在做出決定時(shí)，應(yīng)該考慮到這種退化。這種消極的網(wǎng)絡(luò)外部性存在于許多不同的應(yīng)用中，如云計(jì)算和智能電網(wǎng)。中式餐廳過(guò)程是機(jī)器學(xué)習(xí)中無(wú)界對(duì)象的非參數(shù)學(xué)習(xí)方法[6]。在中國(guó)餐廳過(guò)程中，我們有一個(gè)擁有大數(shù)量餐桌的餐館。顧客依次到達(dá)餐廳。當(dāng)一個(gè)客戶進(jìn)入時(shí)，他要么加入其他客戶已經(jīng)開始的餐桌，要么請(qǐng)求一個(gè)新餐桌。他決定的概率與每個(gè)餐桌中的能容納的顧戶數(shù)有關(guān)。一般來(lái)說(shuō)，如果一個(gè)餐桌能被更多的顧客占用，那么一個(gè)新客戶更有可能加入該表，并且預(yù)定一個(gè)新餐桌的概率是預(yù)定的[7]。這個(gè)過(guò)程提供了一個(gè)系統(tǒng)的方法來(lái)構(gòu)造未知分布模型的參數(shù)，中式餐廳過(guò)程提供了一個(gè)適當(dāng)?shù)慕Y(jié)構(gòu)來(lái)制定具有負(fù)外部性的網(wǎng)絡(luò)中的決策問(wèn)題。將策略行為引入到非策略性中式餐廳過(guò)程中，為社會(huì)學(xué)習(xí)問(wèn)題提出了一種新的模型，帶網(wǎng)絡(luò)外部性的中式餐館博弈模型。考慮帶有餐桌和理性顧客的中餐館，每個(gè)客戶可以要求就座在任何一張桌子上。假設(shè)顧客喜歡更大的用餐空間，因此，他們可能喜歡更大的桌子。然而，如果多個(gè)客戶請(qǐng)求同一個(gè)餐桌，客戶可能需要與其他人表共享該餐桌。在這種情況下，顧客的用餐體驗(yàn)由于空間的減少而受到損害，即負(fù)的網(wǎng)絡(luò)外部性在這里起著作用。因此，作為一個(gè)理性的客戶，在進(jìn)行餐桌選擇時(shí)，必須考慮餐桌的大小和其他客戶的決定。理性的客戶如何在這樣的游戲模式下做出決定是本文的主要關(guān)注點(diǎn)。本文將研究同時(shí)進(jìn)行顧客決策的中式餐館游戲。[8]中討論了連續(xù)的中式餐廳游戲，其中包括讓顧客依次做出決定的社會(huì)學(xué)習(xí)效果。

1 系統(tǒng)模型

考慮一個(gè)中式餐廳，有K個(gè)餐桌，第i個(gè)餐桌的尺寸是[Ri]。有N個(gè)顧客，每個(gè)顧客請(qǐng)求一個(gè)餐桌，顧客同時(shí)做出策略。定義每個(gè)顧客所選的餐桌集合為X={1，…，K}，其中[xi∈X]是第i個(gè)客戶的選擇。第i個(gè)客戶的效用函數(shù)為[U（Rxi，nxi）]，其中[nxi]是選擇餐桌[xi]的顧客個(gè)數(shù)。效用函數(shù)是[Rxi]的增函數(shù)，是[nxi]的減函數(shù)。注意，[nxi]建模了消極的網(wǎng)絡(luò)外部特性，因?yàn)槠渌櫩蛯?duì)餐桌的共享引來(lái)了效用的下降。設(shè)第i個(gè)餐桌上顧客數(shù)為[ni]，[n=n1，n2，…，nk]是餐桌分組，分組對(duì)于下面的討論很重要。

先從只有兩個(gè)顧客和兩張餐桌的簡(jiǎn)單情況開始，餐桌1的尺寸是[R1=L]，餐桌2的尺寸是[R2=S<L]，假設(shè)對(duì)手的選擇已知，可能是大餐桌，也可能是小餐桌，理性顧客最選擇使自己的效用函數(shù)最大的餐桌，當(dāng)對(duì)手的選擇是小餐桌，顧客選擇大餐桌，因?yàn)閇U（L，1）>U（S，2） ];反之，如果對(duì)手選了小餐桌，顧客的選擇取決于消極網(wǎng)絡(luò)外部特性的嚴(yán)重程度，當(dāng)[U（L，2）>U（S，1） ]，顧客會(huì)選擇分享大餐桌，反之，顧客選擇小餐桌。結(jié)果顯示，即使兩個(gè)顧客對(duì)真實(shí)網(wǎng)絡(luò)狀態(tài)（哪個(gè)桌子更大）有著完全的了解，他們也可能不會(huì)選擇均衡中的更大者。相反，均衡取決于負(fù)網(wǎng)絡(luò)外部性的嚴(yán)重程度。如果網(wǎng)絡(luò)外部性導(dǎo)致不可接受的懲罰，那么客戶應(yīng)該選擇不同的餐桌來(lái)避免它。

下面考慮一般的場(chǎng)景，有N個(gè)顧客和K個(gè)餐桌。餐桌的尺寸給定為[R1，R2，…RK]，對(duì)所有顧客都已知。客戶是理性的，他們?cè)谶@個(gè)博弈中的目標(biāo)是最大化自己的效用函數(shù)。然而，由于他們的效用函數(shù)不僅取決于自己的行為，也取決于他人的行為，因此，消費(fèi)者在博弈中的行為受到彼此的影響。

策略描述了博弈者在博弈中可能遇到的情況下做出的選擇。在中式餐廳博弈中，客戶的策略應(yīng)該是從其他客戶的餐桌選擇到自己選擇的映射。[nj]是選擇第i個(gè)餐桌的顧客個(gè)數(shù)。[n-i=n-i，1，n-i，2，…，n-i，k]，其中[n-i，j]代表除了顧客i，選擇餐桌j的顧客數(shù)。理性顧客i應(yīng)該做出的選擇為

（1）式描述了特殊的策略集合，稱為最佳反應(yīng)，代表了顧客在已知其他顧客選擇的情況下，使得自己的效用函數(shù)最大的最佳選擇。也就是，給定第i個(gè)顧客的策略空間[Ai]以及效用函數(shù)[ui（xi，x-i）]，其中[xi]是第i個(gè)顧客選擇，[x-i]是除了顧客i，其他所有顧客的選擇，顧客i的最佳選擇是[BEi（x-i）=argmaxx∈AiUi（x，x-i） ]。

2 納什均衡

納什均衡是一個(gè)流行的概念，用于預(yù)測(cè)理性消費(fèi)者的博弈結(jié)果。非正式地說(shuō)，納什均衡是一個(gè)行動(dòng)概況，其中每個(gè)客戶的決策是對(duì)其他客戶決策的最好反應(yīng)。因?yàn)樗械念櫩投际褂盟麄冏詈玫臎Q策，所以沒(méi)有一個(gè)人有背離他們的決策的動(dòng)機(jī)。正式地說(shuō)，考慮有 [1，2，…N]的顧客的博弈，每個(gè)顧客的行動(dòng)空間為[Ai] 效用函數(shù)為[ui（xi，x-i）]。其中[xi]是第i個(gè)顧客選擇，[x-i]是除了顧客i，其他所有顧客的選擇。納什均衡是行動(dòng)集[X*=x*1，x*2…，x*N]，其中[BEi（x*-i）=x*i]。

3 均衡分組

根據(jù)納什均衡的定義，下面給出中式餐廳博弈中納什均衡的充分必要條件。

定理一：給定顧客集[1，2，…，N]和餐桌集[1，2，…，K]，對(duì)于中式餐廳博弈的任何納什均衡，他的均衡分組[n*]必須滿足[U（Rx，n*x）≥U（Ry，n*y+1），] if [nx>0，?x，y∈1，…，K]? ? ? ? ?（2）

證明：

充分條件：假設(shè)所有顧客的行動(dòng)集為[X=x1，x2…，xN]，此行動(dòng)集導(dǎo)致的分組為[n*=n*1，…n*k]，滿足式（2）。不失一般性，假設(shè)顧客i選擇餐桌j，也就是[xi=j]，可以得出[ui（xi，x-i）=U（Rj，n*j）]。當(dāng)顧客i選擇其他任何餐桌[k≠j，也就是x'i=k≠xi=j，]那么他的效用函數(shù)為

由定理1，我們可以知道，在納什均衡下，顧客的效用值并不會(huì)因?yàn)槠x到另外一張餐桌而變得更高，由于消極的網(wǎng)絡(luò)外部性的干擾，任何一張餐桌的偏離都會(huì)降低這張餐桌上所有顧客的效用值。式（2）說(shuō)明即使顧客選擇同樣大小的餐桌，最后也可能出現(xiàn)不同的效用。比如，假設(shè)有一個(gè)餐廳里面有三個(gè)顧客以及兩張完全相同的餐桌，因?yàn)轭櫩蛿?shù)為三，所以在納什均衡中，肯定會(huì)有兩個(gè)顧客選擇同一張餐桌，而另一張餐桌只有一位顧客。

很明顯，如果在中式餐廳博弈中有一個(gè)納什均衡的存在，在這個(gè)納什均衡里，我們交換任意兩位顧客的行為，從而在遵守式（2）的充要條件的情況下。建立一個(gè)新的納什均衡。這樣，納什均衡就不是唯一的，但是均衡分組卻是唯一的，由定理2所述。

定理2：當(dāng)式（2）中的不等性對(duì)于條件[nx>0]，[? x，y∈{1，…，K}]都成立，均衡分組[n*]是唯一的。

這與式（6）相矛盾，因此納什均衡在式（2）中嚴(yán)格不等條件下是唯一的。注意，當(dāng)均衡分組不是唯一的，必然存在滿足（2）式取等號(hào)的餐桌，這意味著這些餐桌是可交換的，因?yàn)樗麄兲峁┫嗤念A(yù)期效用均衡。如果所有的餐桌具有相同的大小，那么所有餐桌都可以交換，這是足夠的，但不是必要的，這是中式餐廳流程中最初的假設(shè)。在給出均衡分組時(shí)，客戶選擇對(duì)應(yīng)餐桌的效用也確定了。因此，當(dāng)我們對(duì)系統(tǒng)效率而不是個(gè)人效用感興趣時(shí)，均衡分組就足以描述中式餐廳博弈的最終狀態(tài)。

4 均衡分組算法

下面展示如何通過(guò)一個(gè)貪婪算法構(gòu)造一個(gè)平衡分組。在最初的博弈中，客戶同時(shí)做出決定，這使得結(jié)果很難預(yù)測(cè)。然而，通過(guò)把博弈結(jié)構(gòu)改成一個(gè)依次的博弈，餐桌之間的平衡可以很容易地觀察到。在貪婪算法中，顧客依次做出他們的選擇，顧客i第i個(gè)做出選擇。我們讓顧客以短視的方式做出選擇，也就是說(shuō)，他們選擇的餐桌是基于他們已經(jīng)觀測(cè)到的，可以最大化他們目前的效用函數(shù)。設(shè)[ni=n1i，n2i，…，nki]，是顧客i觀測(cè)到分組情況，其中[j=1Knji=i-1]，顧客i做出的選擇是由下式?jīng)Q定的：

定理3：算法1輸出的分組得到的分組是均衡分組，此外，中式餐廳博弈至少存在一個(gè)納什均衡。

由于算法1有限步且總是有輸出，所以保證了納什均衡的存在性。此外，相應(yīng)的分組是一個(gè)均衡分組。算法復(fù)雜性是O（NK），效率很高。如果定理2的條件滿足，均衡分組是唯一的。

5 仿真結(jié)果

考慮有5張餐桌，10位顧客的中式餐廳，這些桌子的尺寸隨機(jī)給定為[13，56，80，28，93]，效用函數(shù)為[u（R，n）=ln（R/n）]，這粗略代表了無(wú)線網(wǎng)絡(luò)的期望吞吐量，把[R/N]作為信噪比，每個(gè)用戶引起的干擾為1，我們首先驗(yàn)證算法得到的分組是不是均衡分組，我們比較了分組[n*]下的效用與“改變一位顧客（cho）”機(jī)制下的效用，在“改變一位顧客”的機(jī)制下，餐桌j的顧客效用為[u（Rj，n*j+1）]，這是顧客偏離他的最初選擇[xi]，轉(zhuǎn)移到餐桌[j≠xi]。

通過(guò)觀察MATLAB仿真對(duì)比圖，我們可知在“改變一位顧客”機(jī)制下的效用嚴(yán)格小于分組[n*]下的效用。這也確定了在分組[n*]下的顧客沒(méi)有偏離分組的動(dòng)機(jī)。因此分組[n*]是中式餐廳博弈下的均衡分組。

下面進(jìn)一步驗(yàn)證中式餐廳博弈均衡分組的效率，我們把它與兩種啟發(fā)式餐桌分配機(jī)制：Round Robin機(jī)制和Largest Table機(jī)制相比較。在Round Robin機(jī)制中，顧客被依次分配到各個(gè)餐桌;而在Largest Table機(jī)制中，所有顧客選擇最大的餐桌。

從圖5中可以看出，在均衡分組下，顧客效用高且平衡，平均效用最高。在Round Robin機(jī)制中，1號(hào)顧客和6號(hào)顧客都選擇了餐桌1，因?yàn)椴妥?是最小的餐桌，所以效用很低，從而導(dǎo)致該機(jī)制下平均效用低于均衡分組下的效用。而在Largest Table機(jī)制中，每位顧客選擇了最大的餐桌，每位顧客的效用相等，但消極的網(wǎng)絡(luò)外部性使得其效用很低。

通過(guò)以上幾種機(jī)制的比較，中餐廳博弈下的均衡分組最大化了顧客的平均效用，使得每位顧客的策略達(dá)到最佳。仿真結(jié)果可以證明，中餐廳博弈中的理性消費(fèi)者會(huì)自動(dòng)達(dá)到負(fù)載平衡，以減少來(lái)自消極的網(wǎng)絡(luò)外部性的干擾。通過(guò)分析，在策略決策中，最后實(shí)現(xiàn)了博弈中參與者之間的效用平衡。因此中餐廳博弈可以作為一種新的通用框架來(lái)解決網(wǎng)絡(luò)外部性的個(gè)體決策問(wèn)題。

與認(rèn)知網(wǎng)絡(luò)相同，在中餐廳博弈中每位顧客的效用改變都會(huì)導(dǎo)致整體效用發(fā)生變化。所以將中餐廳理論應(yīng)用在認(rèn)知無(wú)線電的信道分配問(wèn)題中，當(dāng)二級(jí)用戶采取最佳策略時(shí)，整個(gè)網(wǎng)絡(luò)的效用最大化，系統(tǒng)就能達(dá)到納什均衡點(diǎn)，最終提高無(wú)線頻譜資源的利用率。

參考文獻(xiàn)：

[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.

【通聯(lián)編輯：唐一東】