張紅

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

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

中圖分類號：TP18? ? ? ? 文獻標識碼：A? ? ? ? 文章編號：1009-3044（2019）03-0029-04

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

1 系統(tǒng)模型

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

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

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

策略描述了博弈者在博弈中可能遇到的情況下做出的選擇。在中式餐廳博弈中，客戶的策略應(yīng)該是從其他客戶的餐桌選擇到自己選擇的映射。[nj]是選擇第i個餐桌的顧客個數(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個顧客的策略空間[Ai]以及效用函數(shù)[ui（xi，x-i）]，其中[xi]是第i個顧客選擇，[x-i]是除了顧客i，其他所有顧客的選擇，顧客i的最佳選擇是[BEi（x-i）=argmaxx∈AiUi（x，x-i） ]。

2 納什均衡

納什均衡是一個流行的概念，用于預(yù)測理性消費者的博弈結(jié)果。非正式地說，納什均衡是一個行動概況，其中每個客戶的決策是對其他客戶決策的最好反應(yīng)。因為所有的顧客都使用他們最好的決策，所以沒有一個人有背離他們的決策的動機。正式地說，考慮有 [1，2，…N]的顧客的博弈，每個顧客的行動空間為[Ai] 效用函數(shù)為[ui（xi，x-i）]。其中[xi]是第i個顧客選擇，[x-i]是除了顧客i，其他所有顧客的選擇。納什均衡是行動集[X*=x*1，x*2…，x*N]，其中[BEi（x*-i）=x*i]。

3 均衡分組

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

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

證明：

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

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

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

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

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

4 均衡分組算法

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

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

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

5 仿真結(jié)果

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

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

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

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

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

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

參考文獻：

[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)編輯：唐一東】