導(dǎo)? 讀

本文是 WINE 2022 接收論文 Optimal Private Payoff Manipulation against Commitment in Extensive-form Games 的解讀。該工作由北京大學(xué)前沿計算研究中心鄧小鐵教授、陳昱蓉和哥倫比亞大學(xué)李毓浩共同完成，入選 WINE 2022最佳學(xué)生論文。

文章討論了拓展形式博弈上的 Stackelberg 均衡中跟隨者的私有信息操縱問題，在多個設(shè)定下完全刻畫了跟隨者可以通過謊報效用函數(shù)來達到的均衡，并給出了跟隨者最優(yōu)謊報策略的多項式時間算法。文章結(jié)果說明了在機器學(xué)習(xí)和數(shù)據(jù)收集過程中考慮數(shù)據(jù)提供者基于自己利益謊報消息的必要性。

論文鏈接：https://arxiv.org/abs/2206.13119

01

概? 述

Stackelberg 均衡是博弈論解概念之一，在實際中有十分廣泛的應(yīng)用?？紤]一個二人博弈，領(lǐng)導(dǎo)者（Leader）會先出策略，跟隨者（Follower）在知道領(lǐng)導(dǎo)者的策略之后，會基于理性選擇對應(yīng)的最優(yōu)反應(yīng)（best response）策略進行應(yīng)對。基于跟隨者的最優(yōu)反應(yīng)函數(shù)，領(lǐng)導(dǎo)者就可以通過求解一個兩階段的優(yōu)化問題得到自己的最優(yōu)先手策略。領(lǐng)導(dǎo)者的最優(yōu)先手策略和跟隨者對應(yīng)的最優(yōu)反應(yīng)策略即稱為一個 Stackelberg 均衡。Stackelberg 均衡下領(lǐng)導(dǎo)者的收益能保證不低于同一博弈納什均衡下的收益，也即領(lǐng)導(dǎo)者獲得了所謂的先手優(yōu)勢。

然而為了求解優(yōu)化問題計算最優(yōu)先手策略，領(lǐng)導(dǎo)者需要知道跟隨者的效用函數(shù)，而這在實際情況下往往是跟隨者的私有信息。故而領(lǐng)導(dǎo)者需要先通過與跟隨者交互來學(xué)習(xí)跟隨者的私有信息，用以計算自己的最優(yōu)先手策略。這則給跟隨者了一個謊報自己效用函數(shù)的機會：跟隨者可以根據(jù)一個虛假的效用函數(shù)與領(lǐng)導(dǎo)者進行交互，使得領(lǐng)導(dǎo)者據(jù)此計算出的最優(yōu)先手策略，最后達到的均衡下，跟隨者的真實效用會高于真實均衡下的真實效用。

一個簡單的例子是“大數(shù)據(jù)殺熟”：現(xiàn)在的一些手機軟件，會通過與用戶的交互建立用戶畫像，對不同的用戶提供不同的產(chǎn)品和不同的價格。而已有用戶會通過建立新賬號、更換信用卡等簡單的手段修改自己的用戶畫像，從而達到修改軟件獲得的效用信息、為自己獲利的目的。

在本篇工作中，我們主要考慮完美信息擴展形式博弈（extensive-form game with perfect information），研究一個跟隨者如何能夠找到一個最優(yōu)的效用函數(shù)，通過謊報的方式最大化自己的收益。具體而言，我們將這個過程建模為兩個階段：第一階段將領(lǐng)導(dǎo)者學(xué)習(xí)跟隨者的過程簡化為跟隨者匯報一個效用函數(shù)；在第二階段，領(lǐng)導(dǎo)者會根據(jù)固定的博弈樹、自己的收益函數(shù)和跟隨者匯報的效用函數(shù)，選擇一個 Stackelberg 均衡，作為這個博弈的結(jié)果。

02

前述知識

?一個拓展形式博弈（extensive-form game）可由一個博弈樹來表示，每個節(jié)點會指定一名玩家選擇策略，節(jié)點上的動作集則是選擇一條出邊前往下一個子樹。玩家的收益由最后到達的葉子結(jié)點上的收益來決定。每個玩家的策略一次性決定在每個由他負責的節(jié)點上，他將會如何決策。

我們稱這樣的策略為純策略（pure strategy），若在每個節(jié)點上，該策略需要明確確定性的一條邊的時候；如果允許在每個節(jié)點以概率選擇哪條邊，則這樣的策略成為行為策略（behavioral strategy）；我們考慮了領(lǐng)導(dǎo)者的策略集合為純先手策略（pure commitment）和行為先手策略（behavioral commitment）的情況。

考慮到上述考慮的所有策略對最后都會對應(yīng)于葉子結(jié)點上的概率分布，而這些概率分布最終直接決定了玩家的收益。我們將其作為研究跟隨者謊報行為的研究對象。我們稱一個分布是可被誘導(dǎo)的（inducible），如果存在一個跟隨者的效用函數(shù)，使得謊報該效用函數(shù)后存在一個均衡可實現(xiàn)這個分布；而如果存在一個函數(shù)使得所有的均衡都實現(xiàn)這個分布，也就是這個分布就是這個博弈唯一的結(jié)果，我們稱該分布是強可被誘導(dǎo)的（strongly inducible）。

03

主要結(jié)論

對于純先手策略和行為先手策略兩個情況，我們

1. ?提供了可在多項式時間內(nèi)驗證的可誘導(dǎo)分布和強可誘導(dǎo)分布的完全的刻畫；

2.? 我們?yōu)楦S者提供了多項式的算法，使得

? ? a. ?對于任意一個（強）可誘導(dǎo)分布，構(gòu)造一個對應(yīng)的效用函數(shù)來誘導(dǎo)它；

? ? b. ?找到最優(yōu)的（強）可誘導(dǎo)分布；當最優(yōu)的強可誘導(dǎo)分布不存在時，我們可找到近似最優(yōu)的那個。

進一步，我們對于同一個博弈四個不同的設(shè)定中，跟隨者通過謊報能夠獲得的最優(yōu)效用進行了比較：

3. ?關(guān)于可誘導(dǎo)性和強可誘導(dǎo)性：我們刻畫了兩個設(shè)定下跟隨者的最優(yōu)函數(shù)；我們稱這樣的博弈滿足 Utility Supremum Equivalence (USE) 性質(zhì)；

4. ?關(guān)于純先手策略和行為先手策略：我們證明了當領(lǐng)導(dǎo)者可出行為策略時，跟隨者的最優(yōu)收益反而會高于領(lǐng)導(dǎo)者只能出純策略時的跟隨者最優(yōu)收益。

具體的，當領(lǐng)導(dǎo)者只出純先手策略（pure commitment），而跟隨者只考慮可誘導(dǎo)性的情況下，我們證明了一個分布可被誘導(dǎo)，當且僅當領(lǐng)導(dǎo)者在該分布下的效用不小于他的最大化最小收益（maximin value）。這既是納什均衡收益的下界，也是一個玩家在博弈中能夠保證自己一定拿到的最大收益。這一結(jié)論說明了，當跟隨者可以謊報時，領(lǐng)導(dǎo)者的先手優(yōu)勢蕩然無存。

04

總結(jié)與展望

我們的結(jié)果說明了：

1. ?在信息不對稱的情況下，跟隨者能夠獲得更多的權(quán)力，并且完全扭轉(zhuǎn)領(lǐng)導(dǎo)者的先手優(yōu)勢；

2. ?跟隨者的謊報能力、其可通過謊報到達的博弈結(jié)果以及構(gòu)造效用函數(shù)的方式與領(lǐng)導(dǎo)者的最大化最小值和最大化最小策略有緊密的聯(lián)系。

在擁有海量數(shù)據(jù)和機器學(xué)習(xí)技術(shù)廣泛應(yīng)用的今天，我們是時候考慮所用的數(shù)據(jù)是否可用。由于算法結(jié)果最終可能會影響到數(shù)據(jù)提供者自身的利益，數(shù)據(jù)提供者有動機去提供虛假信息來提高自己的真實利益。研究讓數(shù)據(jù)提供者誠實提供數(shù)據(jù)的機制和激勵相容的機器學(xué)習(xí)算法變得重要。