今天我們介紹一篇經典的近似計算納什均衡的論文「An Optimization Approach for Approximate Nash Equilibria」。該論文針對兩個收益矩陣R,C的每個元素均在[0,1]的情況下給出了一個每名玩家在不改變自己策略情況下至多比假設對面不變、自己改到最優的收益減去0.3393的算法及其證明。本篇文章將略去其使用對偶線性規劃的部分介紹其證明，同時試圖說明為何這篇文章所採用的這種方法十餘年來無法被改進。
定義與背景
首先簡單介紹一下問題定義：
然後我們來討論一下納什均衡的背景，事實上，求解納什均衡的複雜度被證明是PPAD-complete，而後者可以在某種程度上理解為對某個組合圖形，我們知道其必有一個子部分滿足某種性質，試圖尋找算法找到這個子部分。顯然PPAD這個類在P與NP之間，目前求解PPAD的在實際應用中的最好方法依然是指數級別的二分方法。
精確求解納什均衡的困難本質上源於不知道哪些策略是可以被直接扔掉的，因為一旦我們確定了行玩家和列玩家的最小的support，我們就能知道行玩家按某個比例選其support中的策略時（設有m個線性無關策略），列玩家在其support中的每個策略的收益必然是期望相同的（易知有且僅有m個線性無關策略），由此便能利用基本的線性方程組解出行玩家的比例，同理可解得列玩家的比例得到納什均衡。
之前近似納什均衡的嘗試主要集中在低秩解的求解上，想法很單純：假設每個玩家最終都會在所有可能的選項中選出k個來構造自己的策略，遍歷所有可能的k元集，找到其中性質最好的解作為近似的納什均衡。但用這種方法得到的誤差可能有0.75或0.5，即某一方可能不接受算法所給出的納什均衡而選擇自己的最優策略，最多可額外獲得0.75或0.5的收益，這對理論收益上限為1的納什均衡來說理論保障很差。
本文作者提出通過直接把目標函數用對偶線性規劃優化，並結合待定係數法得到一個接近1/3的誤差，目前0.3393的界仍然無法被改進。
主要方法
這篇文章的精華之處在於其對(\Tilde(x),\Tilde(y))的選取，事實上，在僅用其所定義的x，y以及線性規劃中所出現的w，z運用待定係數法，經過艱苦的計算可以發現這一係數已經是取得最優的了。雖然我們接下來可以看到作者們在一些核心步驟上的放縮上會把一些數直接放到0或1，但遺憾的是，如果我們通過待定係數優化其中的一部分，那麼所產生的代價因為無法用λ和μ所控制，依然只能放到1，最終導致結果不比其所選擇的係數好：
事實上，只能放到1的根本原因是由於為了使stationary point本身能夠有一個上界，λ和μ的定義中必須包含本質上和對偶線性規劃的解幾乎沒有聯繫的S_C(x)和S_R(y)，而這就導致了可供選擇的待定係數的項非常少。雖然我們直覺上會認為進行加權平均後，某些項會因為f的上界有比1更好的估計，但待定係數帶來的項幾乎總和S_C(x)和S_R(y)完全無關。
因此這一方法的核心問題是所解得的stationary point本身性質不是很好，需要通過對偶線性規劃的解作為備選方案強行說明兩個點上不會同時得到很壞的解來得到放縮。筆者認為stationary point的問題在離散的線性規劃的眼光下本質上無法再改進，而除了對偶線性規劃的解以外，也很難找到和stationary point相關的點來進行差值。因此要改進這篇論文只有兩種可能：
第一種是找到某些stationary point所滿足的特有的恆等式或不等式，直接說明stationary point在大部分情況下表現良好，即使在表現不好的點，也會因為恆等式或不等式的性質說明在隨機初始化或者加隨機擾動的情況下可以避開表現不好的位置。當然這種方法比較heuristic，關鍵是不等式或恆等式如果找不到就完全變成了模擬退火等無理論基礎的分析。
第二種方法就是整個改變算法，不能將誤差距離直接變成優化目標，可以考慮優化一個加權平均或者一個看似與目標毫無關係的函數，但最後也能通過stationary point和待定係數的方法得到一個更好的界。（例如通過簡單嘗試知道如果我們優化的是雙方誤差的平均值，容易說明有一種方法使雙方誤差平均值不超過1/3，即和不超過2/3，與本文結果相比在某些情況下強一點）但筆者傾向於認為這種方法要超越1/3十分困難，直覺上說來，在引入兩個自由變量後所能期待三項的最大值最小也只能期待到1/3.
總體來說，要找到某些刻畫「能量」之類的不變量，進而用第一種方法改進的難度在於找不到合適的量，而用第二種方法的難點在不知道優化什麼好，得到的結論也不能和問題直接相關。