【儀表網 產品快訊】在政府組織的無線電頻譜拍賣中，多家電信公司需同時對多個頻段提交競價組合。由于每個公司可選擇的出價策略涉及不同頻段的組合定價，其策略空間呈現高維特征。在此博弈中，當所有可能的策略組合及其對應收益均為共同知識時，每家公司都希望確保，即便競爭對手的出價策略存在細微偏差(例如因市場價值誤判導致的非最優出價)，且此類偏差的發生概率與其引發的收益損失呈負相關，自身策略仍能維持最優性。此時，如何確定各公司的最優響應策略成為關鍵問題。
這種互動關系可建模為正則式博弈：每個參與者都有一系列可選策略，所有參與者同時選擇策略后，會根據策略組合獲得相應收益。均衡是一種穩定的策略選擇狀態，在此狀態下，任何參與者都沒有動力單方面改變自己的策略。Myerson于1978年提出的“適當均衡”概念對均衡理論做出了重要拓展：它假設參與者會以極小的概率選擇到非最優策略，且要求選擇到某個非最優策略的概率要和這個策略帶來的損失大小成反比。這一特性恰好刻畫了頻譜拍賣中公司面對對手策略擾動時的穩健決策需求。然而，在參與者數量眾多且策略空間維度較高的復雜博弈中，適當均衡的計算面臨顯著障礙，傳統計算方法往往因計算復雜度高而難以實施。
針對這一難題，西安交通大學管理學院曹譯尹助理教授聯合深圳技術大學陳寅副教授、香港城市大學黨創寅教授開展研究提出了一套系統性的解決方案，并以“A Differentiable Path-Following Method with a Compact Formulation to Compute Proper Equilibria”為題發表將研究成果發表在國際期刊《INFORMS JOURNAL ON COMPUTING》 (UTD 24 期刊)上 。該研究提出了一種可微路徑跟隨方法，結合緊湊公式化表達，來高效計算正則式博弈中的適當均衡。
首先，文章創新性地設計了一種可微路徑跟蹤方法：通過在原始博弈中引入擾動參數和障礙函數，構建一個參數化的新博弈。隨著參數變化，新博弈的均衡會從簡單初始點連續過渡到目標均衡。這種方法就像是為均衡計算鋪設了一條“導航路線”，通過連續調整參數逐步逼近目標，有效避免了傳統方法常見的局部收斂問題。采用該方法對左圖所示的正則式博弈進行求解，得到右圖中的光滑路徑。當參數t趨近于0時，該路徑收斂所得的解集構成一個適當均衡。
然而，由于適當均衡的嚴格定義導致約束條件呈指數級增長，文章進一步提出了緊湊公式化技術。借助排序網絡，將變量和方程數量從指數級降至多項式級。通過嚴格的數學證明這種簡化后的約束系統與原系統等價。這意味著在保證計算結果準確性的同時，計算復雜度得到了顯著降低。這一進展使得算法能夠有效處理高維博弈場景。
該研究更進一步的突破來自概念層面的創新。文章提出了“完美d-適當均衡”這一新概念，通過引入調節參數d，在保持均衡適當性的同時，顯著降低了計算精度的要求。理論證明，當d趨近于零時，新概念會收斂到傳統適當均衡；而實際計算表明，即使d取值較大(如1/5)，仍能得到令人滿意的結果。文章進一步提出了一種計算完美d-適當均衡的可微同倫方法。令d=1/5，應用該方法求解前述左圖中的正則式博弈，得到下圖所示的光滑路徑。當參數t趨近于0時，該路徑收斂所得到的解集不僅構成一個完美d-適當均衡，而且與上文求得的適當均衡一致。
在算法實驗部分，本文在隨機生成的大規模博弈中對這些方法進行了測試。結果顯示：初始的可微路徑跟蹤方法在計算完美d-適當均衡時比計算適當均衡時展現出更高的效率；當結合緊湊公式化技術后，計算完美d-適當均衡的速度得到進一步提升。
整套方案就像是為適當均衡計算打造了一個“導航系統”，不僅修了一條高速公路(可微路徑)，還設置了簡化路標(緊湊公式化)，甚至允許司機靈活繞行(完美d-適當均衡)。實驗數據證實，這一系統不僅能夠快速精準地抵達目的地(適當均衡)，更能應對復雜路況(大規模博弈場景)，為實際決策應用提供了強有力的計算工具。
作者信息：
曹譯尹，西安交通大學管理學院助理教授，主要研究方向：博弈論，計算經濟學，供應鏈管理
陳寅，深圳技術大學副教授；黨創寅，香港城市大學教授。
所有評論僅代表網友意見，與本站立場無關。