討價還價博弈均衡出價策略的算法設計

徐齊利

江西財經(jīng)大學 經(jīng)濟學院，南昌 330013

1 引言

在智能時代，博弈論與計算機交叉，形成一門新興學科：算法博弈論[1-3]。博弈論關注的焦點是構建博弈模型和分析博弈均衡[4-5]；算法博弈論關注的焦點則是求解博弈均衡，即如何求解博弈模型的博弈均衡[6-7]。算法博弈論在商業(yè)智能領域具有非常廣闊的應用需求[8-11]。例如，在智能電子商務的討價還價博弈中[12-14]，買賣雙方的均衡出價策略該如何求解。

買賣雙方輪流出價的討價還價博弈屬于典型的動態(tài)博弈，即后行動的人能看到先行動的人其行動的博弈，而求解動態(tài)博弈的基本思想是逆向歸納法[15]。逆向歸納法僅是求解動態(tài)博弈均衡的一般思路，其在計算機上并不具有可實現(xiàn)性。但基于逆向歸納法，可以開發(fā)出具體某類動態(tài)博弈的具體求解算法。針對討價還價博弈，如何求解買賣雙方的均衡出價策略，本文開發(fā)出兩個可計算機實現(xiàn)的算法：基于逆向歸納過程，設計出迭代算法；基于逆向歸納結果，設計出遞歸算法。

從算法的設計思路來看，迭代算法是逆向歸納法的具體實現(xiàn)；而遞歸算法則并不拘泥于逆向歸納法，是一種全新的博弈求解思路。從算法的實驗測試來看，這兩個算法不僅高效、實用，還同時得出均衡出價策略的上下包絡線。從算法的實際應用來看，算法所得的上下包絡線是買賣雙方最優(yōu)出價的控制線，這對電子商務智能出價系統(tǒng)的設計至關重要。因此，本文還將電子商務的討價還價實戰(zhàn)分設司令部、參謀部、作戰(zhàn)部等三個角色模塊，給出應用該算法開發(fā)智能出價決策支持系統(tǒng)的初步設計思路。

2 模型

2.1 博弈案例

某商品，買方的意愿支付為v，即買方最高愿以v的價格購入；賣方的意愿支付為c，即賣方最低愿以c的價格售出；買賣雙方經(jīng)過t=1,2,…輪討價還價之后，最終以p(t)的價格成交。前提假設：買方的意愿支付v、賣方的意愿支付c、買賣雙方最終的成交價格p(t)三者之間的大小關系為v≥p(t)≥c；否則，買賣不可能達成。

買賣雙方之所以會討價還價，表面上看，當然是由于買方想盡量少出錢，賣方想盡量多收錢；實質來看，則是對交易總剩余v-c這個蛋糕的零和博弈。成交后，賣方從中獲得剩余p(t)-c，買方從中獲得剩余v-p(t)。

既然買賣雙方討價還價博弈實質是關于分蛋糕的博弈，不妨設：經(jīng)歷t=1,2,…輪討價還價達成交易后，賣方獲得蛋糕的份額為x1(t)，賣方獲得蛋糕的份額為x2(t)。兩份額函數(shù)滿足關系式：0 ≤x1(t),x2(t)≤1，x1(t)+x2(t)=1。引入份額函數(shù)后，賣方的實際支付結構為p(t)=c+x1(t)(v-c)，買方的實際支付結構為p(t)=v-x2(t)(v-c)，這就是說，買賣雙方最終成交價格p(t)的結構為：

可見，買賣雙方最終的成交價格實際上是買賣雙方意愿支付價格的加權平均，權重為各自在總剩余中所獲剩余的份額。

2.2 博弈規(guī)則

不失一般性，上述買賣雙方討價還價博弈的規(guī)則設定為：第1 輪，賣方出價，買方若接收賣方的出價，則雙方以賣方以此次出價成交，博弈結束；若買方不接受賣方的出價，則博弈進入第2 輪。第2 輪，買方出價，買賣若接收買方的出價，則雙方以買方以此次出價成交，博弈結束；若賣方不接受買方的出價，則博弈進入第3輪。第3輪，賣方出價，買方選擇接受與否，依次決定博弈是否結束；第4 輪，買方出價，賣方選擇是否接受，若還不能達成交易，則買賣雙方如此動態(tài)博弈下去，直到一方表示接受對方的出價為止。

由式（1）知，上述討價還價博弈規(guī)則可直接簡化關于蛋糕分配份額(x1(t),x2(t))的博弈：若t=1,3,5,…為奇數(shù)，則(x1(t),x2(t))為賣方提出的分配方案；若t=2,4,6,…為偶數(shù)，則(x1(t),x2(t))為買方提出的分配方案。

貼現(xiàn)因子0 ≤δ1,δ2≤1 分別刻畫賣方和買方在討價還價過程中的耐心程度，耐心程度越大（?。┑囊环剑滟N現(xiàn)因子取值越高（低）。第t=1,2,…輪的分配方案(x1(t),x2(t))，將其貼現(xiàn)到博弈剛開始的第1 輪，則其現(xiàn)值為。

2.3 博弈均衡

若t=1，即討價還價只可經(jīng)歷1 輪，則該博弈的納什均衡①買賣雙方出價的納什均衡是指：雙方都選擇了自己的最優(yōu)出價策略，任何一方偏離該報價策略必將招致自己損失。，以現(xiàn)值(f(t),g(t))表示即為(f( 1),g( 1) )=(1 ,0 )。即賣方提出自己吃獨食的分配方案，買方只有接受賣方吃獨食，否則買方將得不到該商品。

若t=2，即討價還價只可經(jīng)歷2 輪，則該博弈的子博弈精煉納什均衡②買賣雙方出價的子博弈精煉納什均衡是指：雙方的出價策略不僅從中間輪次開始至最終結束的子博弈是納什均衡，而且從最初輪次到最終結束的全博弈也是納什均衡。，以現(xiàn)值(f(t),g(t))表示即為(f( 2),g( 2 ))=(1 -δ2,δ2)。這是因為，根據(jù)動態(tài)博弈求解子博弈精煉納什均衡的逆向歸納法：在t=2 期，買方提出自己吃獨食且賣方只能接受的分配方案(x1( 2),x2( 2) )=( 0,1) ；該分配方案貼現(xiàn)到t=1 期，則買方所獲份額為δ2。在t=1 期，賣方提出份額分配方案(x1( 1),x2( 1) )=(1 -δ2,δ2)則買方不會拒絕的同時賣方也能取得自己力所能及的最大份額。在該期，若賣方提出給買方的份額x2( 1) ＜δ2，則買方會拒絕該分配方案，隨后輪到買方出價時買方會吃獨食。若賣方提出給買方的份額x2( 1) ＞δ2，則買方會接收該分配方案，但該方案對賣方自己卻是并沒有取得自己力所能及的最大份額。因此，(f( 2),g( 2 ))=(1 -δ2,δ2)是2 輪討價還價博弈的子博弈精煉納什均衡。

若t=3，即討價還價只可經(jīng)歷3 輪，則該博弈的子博弈精煉納什均衡，以現(xiàn)值(f(t),g(t))表示即為(f( 3),g( 3 ))=(1 -δ2(1 -δ1),δ2(1 -δ1))。應用逆向歸納法，推導過程如下：在t=3 期，賣方提出自己吃獨食且買方只能接受的分配方案(x1( 3),x2( 3 ))=( 1,0 )；該分配方案貼現(xiàn)到t=2 期，則賣方所獲份額為δ1。在t=2期，買方提出分配方案(x1( 2),x2( 2 ))=(δ1,1-δ1)，則賣方不會拒絕的同時買方也掙到了自己最大的份額；該分配方案貼現(xiàn)到t=1 期，則買方所獲份額為δ2(1 -δ1)。在t=1期，賣方提出分配方案(x1( 1),x2( 1) )=(1-δ2(1 -δ1),δ2(1 -δ1))，則買方不會拒絕的同時賣方也能取得自己力所能及的最大份額。故(f( 3),g( 3 ))=(1-δ2(1 -δ1),δ2(1 -δ1))是3輪討價還價博弈的子博弈精煉納什均衡。

若t=4，即討價還價只可經(jīng)歷4 輪，則該博弈的子博弈精煉納什均衡，以現(xiàn)值(f(t),g(t))表示即為(f( 4),g( 4 ))=(1 -δ2(1 -δ1(1 -δ2)),δ2(1 -δ1(1 -δ2)))。此結果是應用逆向歸納法進行迭代計算而來：在t=4期，買方提出自己吃獨食且賣方只能接受的分配方案(x1( 4),x2( 4 ))=( 0,1) ；基于此分配結果逆向迭代，在t=3 期，賣方提出分配方案(x1( 3),x2( 3 ))=(1 -δ2,δ2)，則買方不會拒絕的同時賣方自己也掙到了自己在此時力所能及的最大份額；基于此分配結果再次逆向迭代，在t=2 期，買方提出分配方案(x1( 2),x2( 2 ))=(δ1(1 -δ2),1-δ1(1 -δ2))，則賣方不會拒絕的同時買方也掙到了自己最大的份額；基于此分配結果繼續(xù)逆向迭代，在t=1 期，賣方提出分配方案(x1( 1),x2( 1) )=(1-δ2(1 -δ1(1 -δ2)),δ2(1 -δ1(1 -δ2)))，則買方不會拒絕的同時賣方自己也能取得自己力所能及的最大份額。

同理，對任意有限輪(0 ＜t＜∝ )的討價還價模型，由逆向歸納法皆可得其子博弈精煉納什均衡(f(t),g(t))。結合式（1）知，由均衡的剩余分配策略(f(t),g(t))得，討價還價博弈中買賣雙方的均衡出價策略為：

3 算法

3.1 迭代算法

如何求解討價還價模型子博弈精煉納什均衡，即如何得出討價還價博弈中買賣雙方的均衡出價策略?；谏鲜瞿嫦驓w納法的思維過程，設計出迭代算法；基于上述逆向歸納法的求解結果，設計出遞歸算法。

迭代算法設計如下：

步驟1初值

ift為奇數(shù)

x1(t)=1；

x2(t)=0；

ift為偶數(shù)

x1(t)=0；

x2(t)=1；

end if

步驟2迭代

fori=t-1:-1:1

ifi為奇數(shù)

x2(i)=δ2x2(i+1) ；

x1(i)=1-x2(i)；

ifi為偶數(shù)

x1(i)=δ1x1(i+1) ；

x2(i)=1-x1(i)；

end if

end for

步驟3結果

f(t)=x1( 1) ；

g(t)=x2( 1) ；

p(t)=f(t)v+g(t)c

整個迭代過程就是逆向歸納法在討價還價博弈中的實現(xiàn)過程，4個關鍵點：第一，迭代前的初值設置，出價者首先提出的報價是一種自己吃獨食的分配方案，若談判次數(shù)僅此一輪，則對方只能被動接受此方案；否則，對方會否定于己則一無所得的方案，博弈進入迭代程序。第二，迭代中的進程次序，一是逆向迭代，即t→(t-1) →(t-2) →…→3 →2 →1；二是交替迭代，即賣方→買方→賣方→買方→…或買方→賣方→買方→賣方→…。第三，迭代中的遞推關系，輪到賣方出價時，遞推關系為買方所得份額的一次貼現(xiàn)；輪到買方出價時，遞推關系為賣方所得份額的一次貼現(xiàn)。第四，迭代后的結果輸出，一要得出均衡的剩余分配策略(f(t),g(t))，二要得出均衡的出價策略p(t)。

圖1 列舉了部分輪次討價還價博弈剩余分配策略的迭代算法求解結果。依據(jù)該算法：如果討價還價只進行1次，即t=1，則賣方竟得全部剩余f( 1) =1，買方?jīng)]有剩余可得g( 1) =0，此時均衡的市場成交價p( 1) =v；如果討價還價進行2 次，即t=2，則賣方竟得剩余份額f( 2 )=1-δ2，買方竟得剩余份額g( 2 )=δ2，此時均衡的市場成交價p( 2 )=(1 -δ2)v+δ2c；如果討價還價進行3次，即t=3，則賣方竟得剩余份額f( 3 )=1-δ2(1 -δ1)，買方竟得剩余份額g( 3) =δ2(1 -δ1)，此時均衡的市場成交價p( 3 )=(1 -δ2(1 -δ1))v+δ2(1 -δ1)c；如果討價還價進行4 次，即t=4 ，則賣方竟得剩余份額f( 4 )=1-δ2(1 -δ1(1 -δ2))，買方竟得剩余份額g( 4 )=δ2(1-δ1(1 -δ2))，此時均衡的市場成交價p( 4 )=(1-δ2(1-δ1(1 -δ2)))v+δ2(1 -δ1(1 -δ2))c?？梢?，依迭代算法所得的剩余分配策略(f(t),g(t))與上文枚舉法所得結果完全一致。

3.2 遞歸算法

眾所周知，逆向歸納法是求解子博弈精煉納什均衡的基本思想。上述迭代算法就是逆向歸納法在討價還價博弈問題上的具體實現(xiàn)，下面提出的遞歸算法在討價還價博弈問題上則并不拘泥于逆向歸納法。

第一，均衡分配策略遞歸算法的遞推關系。針對圖1 所列部分輪次討價還價博弈均衡的剩余分配策略(f(t),g(t))，不難發(fā)現(xiàn)，買賣雙方均衡的分配策略在不同博弈輪次之間的遞推關系存在兩種模式：自遞歸模式和交叉遞歸模式。

自遞歸模式：當3 ≤t＜∞ ，則：

交叉遞歸模式：當3 ≤t＜∞，則：

這兩種遞推關系皆能通過數(shù)學歸納法證明其成立。

第二，均衡分配策略遞歸算法的邊界條件。由式（3）、（4）皆為跨兩步遞推知，均衡分配策略遞歸算法的邊界條件則需2 個，即(f( 1),g( 1) )和(f( 2),g( 2 ))。由圖1知，這兩個均衡分配策略的具體取值為：

對于如何得出均衡出價策略，自然可與按照迭代算法的思路同理，在遞歸之后所得均衡出價策略f(t)和g(t)具體取值的基礎上，按照式（2）得出均衡出價策略p(t)的具體取值。例如，可以按照如下的結構對賣方均衡的剩余分配進行遞歸：

以此得到均衡出價策略及買賣雙方所得的剩余分配策略。當然，也可以根據(jù)式（3）或式（4）均衡出價策略的遞推關系，按照式（2）構建均衡出價策略的遞推關系，進而形成均衡出價策略的遞歸算法。均衡出價策略遞歸算法具體設計如下。

第三，均衡出價策略遞歸算法的遞推關系。將式（3）或式（4）均衡出價策略的遞推關系代入式（2）得到，均衡出價策略的遞推關系：當3 ≤t＜∞，則：

后經(jīng)數(shù)據(jù)歸納法證明知均衡出價策略的該遞推關系確實成立。

第四，均衡出價策略遞歸算法的邊界條件。將式（5）代入式（2）得均衡出價策略遞歸算法其邊界條件p(1 ),p( 2 )具體取值的計算公式為：

利用式（6）、（7）設計的遞歸算法，圖2 給出部分輪次討價還價博弈均衡出價策略p(t)的解析表達式。圖2與圖1按照式（2）完全吻合，說明遞歸算法和迭代算法所得結果是一致的。在隨后的實驗測試階段就要對這種一致性關系進行驗證，此對兩種算法進行校驗。

圖2 討價還價模型的子博弈精煉納什均衡：均衡報價策略

3.3 算法的收斂性

Rubinstein[15]指出，在無限輪討價還價博弈中，剩余分配策略(f,g)唯一的子博弈精煉納什均衡結果為應用該結論，如果設計的算法在t→∞時均衡的剩余分配策略(f(t),g(t))不收斂到，則說明所設計的算法是錯誤的。

為考察均衡分配策略算法的收斂性，根據(jù)式（3）或式（4）建立如下方程組：

或

解方程組得：

式（9）表明，就收斂性而言，所設計的均衡分配策略算法是合理的。

進而考察均衡出價策略算法的收斂性，根據(jù)式（6）建立如下方程：

解方程得：

式（9）與式（8）之間滿足關系式：

該式與式（2）完全吻合，說明，就收斂性而言，所設計的均衡出價策略算法也是合理的。在接下來的實驗測試階段，算法的實現(xiàn)過程需要充分體現(xiàn)式（8）、（9）的收斂性。

4 實驗

4.1 均衡分配策略

為測試上述迭代算法和遞歸算法的有效性，實驗用的參數(shù)設置為：買方的意愿支付v=100，賣方的意愿支付c=50，賣方的貼現(xiàn)因子δ1=0.8，買方的貼現(xiàn)因子δ2=0.8。

迭代算法和遞歸算法所得均衡分配策略(f(t),g(t))隨討價還價輪次t變化的路徑皆如圖3 所示。圖中，實線表示的曲線是賣方所得份額f(t)隨討價還價輪次t變化的路徑；穿過該曲線的水平直線是函數(shù)f(t)的水平漸近線，該漸近線在縱軸上的取值剛好等于無限輪討價還價博弈在納什均衡時賣方所得份額(1 -δ2)(1 -δ1δ2)=0.555 6。虛線表示的曲線是買方所得份額g(t)隨討價還價輪次t變化的路徑；穿過該曲線的水平直線是函數(shù)g(t)的水平漸近線，該漸近線在縱軸上的取值剛好等于無限輪討價還價博弈在納什均衡時買方所得份額δ2(1 -δ1)(1 -δ1δ2)=0.444 4?？梢姡途夥峙洳呗远?，實驗測得算法收斂性恰是式（8）理論所示算法收斂性的具體反映。

圖3 (f ( t ),g( t ))隨t 的變化路徑

算法出現(xiàn)收斂性僅是對均衡分配策略未來命運的刻畫，討價還價畢竟不能無限輪沒完沒了地持續(xù)下去，經(jīng)歷有限輪討價還價即可達成交易才是現(xiàn)實常態(tài)。圖3的測算結果顯示：若經(jīng)歷奇數(shù)輪討價還價，則先出價的賣方所得份額多；若經(jīng)歷偶數(shù)輪討價還價，則后出價的買方所得份額多。由此可見，所設計的算法完全體現(xiàn)了有限輪討價還價博弈的基本理論：奇數(shù)輪討價還價，先發(fā)有優(yōu)勢，后發(fā)優(yōu)劣勢；偶數(shù)輪討價還價，先發(fā)有劣勢，后發(fā)有優(yōu)勢。這就是說，利用該算法，就可以在電子商務的討價還價智能談判中關于雙方的盈余分配不僅能做到“知己知彼”，還能做到“趨利避害”。

4.2 均衡出價策略

迭代算法和遞歸算法所得均衡出價策略p(t)隨討價還價輪次t變化的路徑皆如圖4的實線所示。圖中，曲線p(t)上包絡線為奇數(shù)輪討價還價所形成的均衡價格，該價格對賣方有利；曲線p(t)下包絡線為偶數(shù)輪討價還價所形成的均衡價格，該價格對買方有利；穿過該曲線p(t)的水平直線是函數(shù)p(t)及其上下包絡線的水平漸近線，該漸近線在縱軸上的取值剛好等于無限輪討價還價所形成的均衡價格[( 1 -δ2)v+δ2(1 -δ1)c](1 -δ1δ2)=78.777 8?？梢?，就均衡出價策略而言，實驗測得算法收斂性恰是式（9）理論所示算法收斂性的具體反映。

圖4 p( t )隨t 的變化路徑

圖3、圖4共同反映，即便買賣雙方耐心程度和談判能力完全一樣，只要討價還價的輪次足夠長，均衡的成交價格總是高于公平價格（本例的公平價格(v-c)2=75.00），此時，賣方總是處于獲得較多盈余的有利地位，買方總是處于獲得較少盈余的不利地位。這恰是算法的收斂性式（8）、（9）在貼現(xiàn)因子δ1=δ2=δ時所能揭示的。

5 應用

在電子商務的討價還價實戰(zhàn)中，應用該算法的商業(yè)智能決策支持系統(tǒng)該如何開發(fā)，下面分商業(yè)實戰(zhàn)的司令部、參謀部、作戰(zhàn)部等三個角色模塊，給出初步的設計思路。

對商業(yè)實戰(zhàn)的司令部而言，可按照該算法的上下包絡來部署戰(zhàn)略決策：（1）在奇數(shù)輪討價還價中，先出價的賣方當選擇輪次少的速決戰(zhàn)，后出價的買方當選擇輪次多的持久戰(zhàn)；（2）在偶數(shù)輪討價還價中，先出價的賣方當選擇輪次多的持久戰(zhàn)，后出價的買方當選擇輪次少的速決戰(zhàn)；（3）不管是輪次少的速決戰(zhàn)，還是輪次多的持久戰(zhàn)，先出價的賣方都應選擇奇數(shù)輪次討價還價，后出價的買方都應選擇偶數(shù)輪次討價還價。

對商業(yè)實戰(zhàn)的參謀部而言，可按照該算法的動態(tài)曲線來提供決策支持：（1）在沙盤模擬推演過程中，為做到“知己知彼，百戰(zhàn)不殆”，既要演示均衡報價策略，也要演示均衡分配策略；既要報告賣方的均衡策略，也要報告買方的均衡策略。（2）在輔助司令部的戰(zhàn)略決策方面，若司令部注重博弈的決策過程，則重點使用迭代算進行現(xiàn)場推演；若司令部注重博弈的決策結果，則重點使用遞歸算法進行現(xiàn)場推演。（3）在輔助作戰(zhàn)部的戰(zhàn)術決策方面，事前需充分挖掘以往討價還價商業(yè)實戰(zhàn)的大數(shù)據(jù)信息，借助博弈計量經(jīng)濟學，預估本次討價還價的輪次將是多少和買賣雙方的貼現(xiàn)因子各是多少。

對商業(yè)實戰(zhàn)的作戰(zhàn)部而言，可按照該算法的上下包絡來做出戰(zhàn)術決策：（1）作為賣方，不管博弈將要進行多少輪，可沿循均衡出價策略的上包絡線依次降價，直到買方接受我賣方的出價為止。（2）作為買方，不管博弈將要進行多少輪，可沿循均衡出價策略的下包絡線依次漲價，直到賣方接受我買方的出價為止。（3）在討價還價過程中做好偵察與反偵察，不斷獲取對方出價行為的大數(shù)據(jù)，基于偵察到的后驗信息，對對方貼現(xiàn)因子的先驗估計予以貝葉斯修正；在沿著包絡線依次出價的過程中，適當隨機化，制造噪聲，以此手段進行反偵察，可防對方過早得知我方的貼現(xiàn)因子。

6 結論

算法博弈論是博弈論與計算機交叉而成的一個新興學科，其在商業(yè)智能時代有著廣泛的應用需求。例如，在智能電子商務的討價還價博弈中，買賣雙方的均衡出價策略該如何求解。本文在求解動態(tài)博弈的基本思想，即逆向歸納法的基礎上，開發(fā)出兩個高效且實用的算法：迭代算法與遞歸算法。

基于逆向歸納過程，設計出迭代算法：（1）迭代的進程次序，一是由后往前逆向迭代，二是買賣雙方交替迭代；（2）迭代的遞推關系，輪到賣方（買方）出價時，買方（賣方）本輪所得份額是上輪所得份額的一次貼現(xiàn)，賣方（買方）獲得對方貼現(xiàn)后的剩余份額。

基于逆向歸納結果，設計出遞歸算法：（1）遞歸的進程次序，由大到小，每次間隔兩步，形成一條奇數(shù)遞歸路線和一條偶數(shù)遞歸路線；（2）遞歸的遞推關系，既可采取賣方與賣方、買方與買方的自遞歸模式，也可采取賣方與買方、買方與賣方的交叉遞歸模式。

從算法的設計思路來看，迭代算法是逆向歸納法的具體實現(xiàn)；而遞歸算法并不拘泥于逆向歸納法，是一種全新的博弈求解思路。從算法的實驗測試來看，這兩個算法不僅高效、實用，還同時得出均衡出價策略的上下包絡線。從算法的實際應用來看，算法所得均衡出價策略的上下包絡線是買賣雙方最優(yōu)出價的控制線，這對設計電子商務智能出價系統(tǒng)至關重要。

基于此，本文還將電子商務的討價還價實戰(zhàn)分設司令部、參謀部、作戰(zhàn)部等三個角色模塊，給出應用該算法開發(fā)智能出價決策支持系統(tǒng)的初步設計思路為：司令部可按照該算法的上下包絡來部署戰(zhàn)略決策，參謀部可按照該算法的動態(tài)曲線來提供決策支持，作戰(zhàn)部可按照該算法的上下包絡來做出戰(zhàn)術決策。