【儀表網(wǎng) 產(chǎn)品快訊】在政府組織的無線電頻譜拍賣中，多家電信公司需同時對多個頻段提交競價組合。由于每個公司可選擇的出價策略涉及不同頻段的組合定價，其策略空間呈現(xiàn)高維特征。在此博弈中，當(dāng)所有可能的策略組合及其對應(yīng)收益均為共同知識時，每家公司都希望確保，即便競爭對手的出價策略存在細微偏差(例如因市場價值誤判導(dǎo)致的非最優(yōu)出價)，且此類偏差的發(fā)生概率與其引發(fā)的收益損失呈負相關(guān)，自身策略仍能維持最優(yōu)性。此時，如何確定各公司的最優(yōu)響應(yīng)策略成為關(guān)鍵問題。
 

　　這種互動關(guān)系可建模為正則式博弈：每個參與者都有一系列可選策略，所有參與者同時選擇策略后，會根據(jù)策略組合獲得相應(yīng)收益。均衡是一種穩(wěn)定的策略選擇狀態(tài)，在此狀態(tài)下，任何參與者都沒有動力單方面改變自己的策略。Myerson于1978年提出的“適當(dāng)均衡”概念對均衡理論做出了重要拓展：它假設(shè)參與者會以極小的概率選擇到非最優(yōu)策略，且要求選擇到某個非最優(yōu)策略的概率要和這個策略帶來的損失大小成反比。這一特性恰好刻畫了頻譜拍賣中公司面對對手策略擾動時的穩(wěn)健決策需求。然而，在參與者數(shù)量眾多且策略空間維度較高的復(fù)雜博弈中，適當(dāng)均衡的計算面臨顯著障礙，傳統(tǒng)計算方法往往因計算復(fù)雜度高而難以實施。
 

　　針對這一難題，西安交通大學(xué)管理學(xué)院曹譯尹助理教授聯(lián)合深圳技術(shù)大學(xué)陳寅副教授、香港城市大學(xué)黨創(chuàng)寅教授開展研究提出了一套系統(tǒng)性的解決方案，并以“A Differentiable Path-Following Method with a Compact Formulation to Compute Proper Equilibria”為題發(fā)表將研究成果發(fā)表在國際期刊《INFORMS JOURNAL ON COMPUTING》 (UTD 24 期刊)上 。該研究提出了一種可微路徑跟隨方法，結(jié)合緊湊公式化表達，來高效計算正則式博弈中的適當(dāng)均衡。
 

　　首先，文章創(chuàng)新性地設(shè)計了一種可微路徑跟蹤方法：通過在原始博弈中引入擾動參數(shù)和障礙函數(shù)，構(gòu)建一個參數(shù)化的新博弈。隨著參數(shù)變化，新博弈的均衡會從簡單初始點連續(xù)過渡到目標(biāo)均衡。這種方法就像是為均衡計算鋪設(shè)了一條“導(dǎo)航路線”，通過連續(xù)調(diào)整參數(shù)逐步逼近目標(biāo)，有效避免了傳統(tǒng)方法常見的局部收斂問題。采用該方法對左圖所示的正則式博弈進行求解，得到右圖中的光滑路徑。當(dāng)參數(shù)t趨近于0時，該路徑收斂所得的解集構(gòu)成一個適當(dāng)均衡。
 

　　然而，由于適當(dāng)均衡的嚴(yán)格定義導(dǎo)致約束條件呈指數(shù)級增長，文章進一步提出了緊湊公式化技術(shù)。借助排序網(wǎng)絡(luò)，將變量和方程數(shù)量從指數(shù)級降至多項式級。通過嚴(yán)格的數(shù)學(xué)證明這種簡化后的約束系統(tǒng)與原系統(tǒng)等價。這意味著在保證計算結(jié)果準(zhǔn)確性的同時，計算復(fù)雜度得到了顯著降低。這一進展使得算法能夠有效處理高維博弈場景。
 

　　該研究更進一步的突破來自概念層面的創(chuàng)新。文章提出了“完美d-適當(dāng)均衡”這一新概念，通過引入調(diào)節(jié)參數(shù)d，在保持均衡適當(dāng)性的同時，顯著降低了計算精度的要求。理論證明，當(dāng)d趨近于零時，新概念會收斂到傳統(tǒng)適當(dāng)均衡；而實際計算表明，即使d取值較大(如1/5)，仍能得到令人滿意的結(jié)果。文章進一步提出了一種計算完美d-適當(dāng)均衡的可微同倫方法。令d=1/5，應(yīng)用該方法求解前述左圖中的正則式博弈，得到下圖所示的光滑路徑。當(dāng)參數(shù)t趨近于0時，該路徑收斂所得到的解集不僅構(gòu)成一個完美d-適當(dāng)均衡，而且與上文求得的適當(dāng)均衡一致。
 

　　在算法實驗部分，本文在隨機生成的大規(guī)模博弈中對這些方法進行了測試。結(jié)果顯示：初始的可微路徑跟蹤方法在計算完美d-適當(dāng)均衡時比計算適當(dāng)均衡時展現(xiàn)出更高的效率；當(dāng)結(jié)合緊湊公式化技術(shù)后，計算完美d-適當(dāng)均衡的速度得到進一步提升。
 

　　整套方案就像是為適當(dāng)均衡計算打造了一個“導(dǎo)航系統(tǒng)”，不僅修了一條高速公路(可微路徑)，還設(shè)置了簡化路標(biāo)(緊湊公式化)，甚至允許司機靈活繞行(完美d-適當(dāng)均衡)。實驗數(shù)據(jù)證實，這一系統(tǒng)不僅能夠快速精準(zhǔn)地抵達目的地(適當(dāng)均衡)，更能應(yīng)對復(fù)雜路況(大規(guī)模博弈場景)，為實際決策應(yīng)用提供了強有力的計算工具。
 

　　作者信息：
 

　　曹譯尹，西安交通大學(xué)管理學(xué)院助理教授，主要研究方向：博弈論，計算經(jīng)濟學(xué)，供應(yīng)鏈管理
 

　　陳寅，深圳技術(shù)大學(xué)副教授；黨創(chuàng)寅，香港城市大學(xué)教授。