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

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

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

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

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

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

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

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

　　作者信息：
 

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

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