信息設計學習筆記系列。

The Persuasion Duality

如果 concavification 比较难做的时候怎么办呢? Dworczak, P., & Kolotilin, A. (2024) 这篇文章提供了一个比较 general 的 duality 方法。

預備知識

The Primal and the Dual problem

The primal problem 是给目标函数寻找 concave closure。什么是 concave closure 呢?就是通过在函数图像上的点的凸组合来逼近目标函数,通过取凸组合、即“连线”来把原本不是凹函数的目标函数给抹平,即最原本的 Bayesian Persuasion 问题。在 Dworczak, P., & Kolotilin, A. (2024) 文中,他们称为 inner construction。文中 Figure 1 里为红线。

The dual problem 是给目标函数寻找 concave envelope。什么是 concave envelope 呢?就是用凹函数从上方来逼近目标函数,即对那些逐点大于目标函数的仿射函数取下确界,这些仿射函数具有不同的斜率,从上方逼近目标函数的过程就是把这些仿射函数往下拉,来贴近目标函数。他们称为 outer construction。为蓝线。

两者有什么共同点呢?它们都是在构建 convex hull。即,把目标函数的图变成一个凸集。

Supergradient

参见 一些簡單的凸分析

令 CC 为 凸集,ff 为定义在 CC 上的凹函数。称向量 pp 是函数 ff 在点 x∈Cx\in C 处的 supergradient, 如果对于任何向量 yy,都有 f(x)+p⋅(y−x)≥f(y)f (x) + p · (y − x) \geq f (y)。

这是对于 gradient 的推广。如果 ff 本身是可微的,那么不等式就是我们常见的 f(x)+f′(x)⋅(y−x)≥f(y)f (x) + f'(x) · (y − x) \geq f (y)。

(一个 loosely 的理解方法:如果ff 本身是二阶连续可导的单变量函数,那么的对 f(y)f(y) 在 xx 点做二阶 Taylor expansion,那么 f(y)=f(x)+f′(x)(y−x)+12f′′(x)(y−x)2f(y)=f(x)+f'(x)(y-x)+\frac{1}{2}f''(x)(y-x)^{2},而凹函数f′′(x)≤0f''(x)\leq 0,所以 f(x)+f′(x)(y−x)≥f(y)f(x)+f'(x)(y-x)\geq f(y))

这篇文章表明,最优的 dual variable 就是目标函数的 concave closure (本来是与 Primal 相联系的)在先验信念处的 supergradient。我们前面的定义里 ff 需要是 concave 的,但是目标函数却未必是 concave 的(即,目标函数本身不是我们定义里的 ff),所以需要取 concave closure,使得我们的新目标函数 ff 变成 concave 的。既然新目标函数是通过取 concave closure 得到的,那么就意味著新目标函数逐点不低于原本的目标函数:退化信息结构本身就是可行的,所以凹化后的值至少等于原目标函数在同一点的值。先验信念就是此处的 xx,对于任何信念 yy 来说,这个 optimal dual variable pp 给出了凹化值函数在 xx 处的支撑超平面。

weak⋆\text{weak}^{\star}拓撲

給定向量空間XX,將定義在XX上的所有連續線性泛函(強調連續是因為XX可能是無限維空間,此時線性函數並不自動就是連續的,預設採用範數引致的度量拓撲)f:X→Rf:X\rightarrow\mathbb{R}們記為X⋆X^{\star},那麼使得所有這些f∈X⋆f\in X^{\star}連續的、最小的(如果不要求最小,那麼它們本來在範數引致的度量拓撲下就已經是連續的)在XX上的拓撲,就是XX上的 weak topology,記為σ(X,X⋆)\sigma(X,X^{\star});

進而,給定X⋆X^{\star},同樣將那些使得連續線性泛函g:X⋆→Rg:X^{\star}\rightarrow\mathbb{R}們g∈X⋆⋆g\in X^{\star\star}連續的最小拓撲為σ(X⋆,X⋆⋆)\sigma(X^{\star},X^{\star\star}),這一拓撲是定義在X⋆X^{\star}上的weak topology;

最後,由於X⊂X⋆⋆X\subset X^{\star\star},將σ(X⋆,X⋆⋆)\sigma(X^{\star},X^{\star\star})削弱為σ(X⋆,X)\sigma(X^{\star},X),則得到了在X⋆X^{\star}上的weak⋆\text{weak}^{\star} topology。

更弱的拓撲具有更少的開集、更多的閉集和緊集、更多的連續函數。

Riesz-Markov-Kakutani representation theorem

在本文使用的 weak⋆^\star 拓撲下,Δ(Ω)⊂C(Ω)⋆\Delta(\Omega)\subset C(\Omega)^\star。因此 Δ(Ω)\Delta(\Omega) 上由 weak⋆^\star 連續線性泛函限制而來的連續仿射函數,可以寫成「常數加上一個評估泛函」的形式;也就是存在 c∈Rc\in\mathbb{R} 與 P∈C(Ω)P\in C(\Omega),使得

H(μ)=c+∫ΩP(ω)dμ(ω).H(\mu)=c+\int_{\Omega}P(\omega)d\mu(\omega).

如果把常數項吸收到 PP 的歸一化中,也常簡寫為 H(μ)=∫ΩP(ω)dμ(ω)H(\mu)=\int_{\Omega}P(\omega)d\mu(\omega)。

這個只是本文夠用的 weak⋆^\star 評估泛函版本;完整的 RMK 表示定理說的是連續函數空間上的正線性泛函可以由正則 Borel 測度表示,底層空間Ω\Omega也可放寬為局部緊 Hausdorff 空間,取值還可以推廣到複數情形,可見 Rudin (1987)。

凸序

對於兩個隨機變數AA和BB,如果任給凸函數uu,都有E[u(A)]≤E[u(B)]\mathbb{E}[u(A)]\leq\mathbb{E}[u(B)],則稱AA在凸序意義下小於BB,記為A≤cxBA\leq_{cx}B。

模型

狀態空間Ω\Omega為緊度量空間。令Δ(Ω)\Delta(\Omega)為Ω\Omega上的 Borel 機率測度的集合,並具有weak⋆\text{weak}^{\star} topology。先驗信念μ0\mu_{0}具有全支撐。目標函數V:Δ(Ω)→RV:\Delta(\Omega)\rightarrow\mathbb{R}為上半(semi)連續的。

那麼,為什麼我們需要在Δ(Ω)\Delta(\Omega)上的weak⋆\text{weak}^{\star} topology 呢?後面我們會看到,因為我們需要使得Δ(Ω)\Delta(\Omega)是個緊度量空間、從而保證最優化問題解的存在性。並且,雖然機率測度並不是線性的,但構成我們問題的積分操作是線性的。但這一設定也會帶來一些問題,後面會詳述。

Primal Problem

(P)

選擇τ∈Δ(Δ(Ω))\tau\in\Delta(\Delta(\Omega)),來最大化

∫Δ(Ω)V(μ)dτ(μ)s.t.∫Δμdτ(μ)=μ0\begin{align} \int_{\Delta(\Omega)}V(\mu)d\tau(\mu)\\ s.t.\int_{\Delta}\mu d\tau(\mu)=\mu_{0} \end{align}

Dual Problem

(D)

選擇P∈C(Ω)P\in C(\Omega),其中C(Ω)C(\Omega)為Ω\Omega上連續函數的集合,來最小化

∫ΩP(ω)dμ0(ω)s.t.∫ΩP(ω)dμ(ω)≥V(μ)∀μ∈Δ(Ω)\begin{align} \int_{\Omega}P(\omega)d\mu_{0}(\omega)\\ s.t.\int_{\Omega}P(\omega)d\mu(\omega)\geq V(\mu)\\ \forall\mu\in\Delta(\Omega) \end{align}

原問題解的存在性

首先,我們表明,當Ω\Omega為緊度量空間時,Δ(Ω)\Delta(\Omega)在weak⋆\text{weak}^{\star}拓撲下也是緊的,並且是可度量化的。

Lemma 1. 緊Hausdorff空間X是可度量化的,當且僅當C(X)C(X)是可分的Banach格。

格範數是一個關於向量絕對值單調的範數,賦範Riesz空間是結合了格範數的Riesz空間。如果這個範數還具有完備性,則這個空間就成為了Banach格。

因為Ω\Omega為度量空間,根據定義,Ω\Omega是可度量化的 Hausdorff 空間。因此,C(X)C(X)是一個可分的 Banach 格。

Lemma 2. (Alaoglu’s Thm)一個賦範空間的範數對偶上的閉單位球,是weak⋆\text{weak}^{\star}緊的。從而,範數對偶的一個子集是weak⋆\text{weak}^{\star}緊的當且僅當它是weak⋆\text{weak}^{\star}閉且範數有界的。

Lemma 3. 一個賦範空間是可分的,當且僅當其對偶空間的閉單位求是weak⋆\text{weak}^{\star}可度量化的。

因此,C(X)C(X)中的閉單位球是weak⋆\text{weak}^{\star}緊且weak⋆\text{weak}^{\star}可度量化的。作為這個閉單位球的子集,Δ(Ω)\Delta(\Omega)是weak⋆\text{weak}^{\star}緊且weak⋆\text{weak}^{\star}可度量化的。進而,Δ(Δ(Ω))\Delta(\Delta(\Omega))是weak⋆\text{weak}^{\star}緊且weak⋆\text{weak}^{\star}可度量化的。因為τ→∫Δ(Ω)μdτ(μ)\tau\rightarrow\int_{\Delta(\Omega)}\mu d\tau(\mu)是連續函數,滿足約束∫Δ(Ω)μdτ(μ)=μ0\int_{\Delta(\Omega)}\mu d\tau(\mu)=\mu_{0}的那些分佈τ\tau們是個閉集(單點集μ0\mu_{0}是閉集,而連續函數使得閉集的原像閉),而緊空間的閉子集是緊集,因此那些可行的τ\tau們構成一個緊集。

Def. 令Ω\Omega為度量空間,並賦予 Borel σ\sigma代數Σ\Sigma。稱(Ω,Σ)(\Omega,\Sigma)上的機率測度序列μn\mu_{n}弱⋆\star收斂於(Ω,Σ)(\Omega,\Sigma)上的機率測度μ\mu,如果對於任何 usc 且上有界的函數ff,都有lim⁡sup⁡Enf(x)≤Ef(x)\lim\sup\mathbb{E}_{n}f(x)\leq \mathbb{E}f(x)。其中En\mathbb{E}_{n}是函數f(x)f(x)關於μn\mu_{n}的期望,E\mathbb{E}是關於μ\mu的。

根據假設,VV在採用weak⋆\text{weak}^{\star}拓撲下是上半連續的,由於其定義域Δ(Ω)\Delta(\Omega)為緊集,因此其為上有界的,因此函數∫Δ(Ω)V(μ)dτ(μ)\int_{\Delta(\Omega)}V(\mu)d\tau(\mu)也是上半連續的。

從而,根據 Weierstrass 定理,緊集{τ∈Δ(Δ(Ω)):∫Δ(Ω)μdτ(μ)=μ0}\{\tau\in\Delta(\Delta(\Omega)):\int_{\Delta(\Omega)}\mu d\tau(\mu)=\mu_{0}\}上的上半連續函數∫Δ(Ω)V(μ)dτ(μ)\int_{\Delta(\Omega)}V(\mu)d\tau(\mu)可以取到最大值。

對偶

Thm 1. 弱對偶

如果某個τ∈Δ(Δ(Ω))\tau\in\Delta(\Delta(\Omega))對於問題(P)可行,且某個P∈C(Ω)P\in C(\Omega)對於問題(D)可行,則

(G)

∫ΩP(ω)dμ0(ω)≥∫Δ(Ω)V(μ)dτ(μ)\int_{\Omega}P(\omega)d\mu_{0}(\omega)\geq\int_{\Delta(\Omega)}V(\mu)d\tau(\mu)

此外,如果(G)以等式成立,即

(0)

∫ΩP(ω)dμ0(ω)=∫Δ(Ω)V(μ)dτ(μ)\int_{\Omega}P(\omega)d\mu_{0}(\omega)=\int_{\Delta(\Omega)}V(\mu)d\tau(\mu)

則前述τ\tau和PP分別為問題(P)和問題(D)的最優解。

Prop 1. 無對偶缺口

Def 1. 正則性

如果V^\hat{V}在先驗信念μ0\mu_{0}處是超可微的,則稱勸說問題為正則的。當勸說問題正則時,存在仿射連續函數Vˉ:Δ(Ω)→R\bar{V}:\Delta(\Omega)\rightarrow\mathbb{R}使得Vˉ(μ0)=V^(μ0)\bar{V}(\mu_{0})=\hat{V}(\mu_{0})且對於任何μ∈Δ(Ω)\mu\in\Delta(\Omega)都有Vˉ(μ)≥V^(μ)\bar{V}(\mu)\geq\hat{V}(\mu)。

(即仿射函數Vˉ\bar{V} majorize 了V^\hat{V},此時這一仿射函數的斜率就是V^\hat{V}在μ0\mu_{0}處的超梯度。

回憶超梯度的定義:考慮有限維情況,給定ff是凸集C∈RnC\in\mathbb{R}^{n}上的凹函數,那麼我們稱一個向量p∈Rnp\in\mathbb{R}^{n}是ff在點xx處的超梯度,若向量pp滿足,對於任何yy有如下超梯度不等式:

f(x)+p(y−x)≥f(y)f(x)+p(y-x)\geq f(y)

並且當給定xx時,仿射函數f(x)+p(y−x)f(x)+p(y-x)就是函數ff在xx點處的超微分。而在有限維情況下,凹函數在每個內點處都是超可微的。由於我們假設全支撐,μ0\mu_{0}就是內點。因此V^\hat{V}在先驗信念μ0\mu_{0}處必然是超可微的,正則性自然成立。同樣地,也可以將這一仿射函數理解為V^\hat{V}在μ0\mu_{0}處的支撐超平面。

但由於我們當前考慮的是無限維情況,需要對前述p(y−x)p(y-x)的表述做進一步推廣。這就要用到 weak⋆^\star 拓撲下的評估泛函表述:存在某個P∈C(Ω)P\in C(\Omega),使得線性部分可以寫成∫ΩP(ω)d(μ−μ0)(ω)\int_{\Omega}P(\omega)d(\mu-\mu_{0})(\omega),從而超梯度不等式變為,對於所有μ∈Δ(Ω)\mu\in\Delta(\Omega)

V^(μ0)+∫ΩP(ω)d(μ−μ0)(ω)≥V^(μ).\hat{V}(\mu_{0})+\int_{\Omega}P(\omega)d(\mu-\mu_{0})(\omega)\geq\hat{V}(\mu).

等價地,令

Pˉ(ω)=P(ω)+V^(μ0)−∫ΩP(ω)dμ0(ω),\bar P(\omega)=P(\omega)+\hat{V}(\mu_{0})-\int_{\Omega}P(\omega)d\mu_{0}(\omega),

則有

∫ΩPˉ(ω)dμ(ω)≥V^(μ),∀μ∈Δ(Ω),\int_{\Omega}\bar P(\omega)d\mu(\omega)\geq\hat{V}(\mu),\quad \forall\mu\in\Delta(\Omega),

這正是 dual problem 中可行價格函數的形式。

但在Ω\Omega為無窮集的情況時,機率測度的集合在weak⋆\text{weak}^{\star}拓撲下的相對內部是空集,任何μ0\mu_{0}即使是全支撐也是邊界點,此時“支撐超平面”可能是垂直的,這種情況下其實所謂的支撐超平面(根據定義,斜率應為有限值,但垂直對應於“斜率”為無窮大)是不存在的。一般地,在無限維空間中,凹性和上半連續不足以保證即使在內點處支撐超平面的存在。因此需要特別地假設正則性,而非像有限維情況下那般自然成立。

由於可能出問題的情況是“支撐超平面”具有無窮“斜率”,因此保證正則性的一個自然地條件就是關於函數V^\hat{V}本身在μ0\mu_{0}處斜率的限制,如果這個斜率是有限值,那麼其相應的支撐超平面也具有有限斜率,這種對於斜率的限制可以通過施加 Lipschitz 條件來實現:即,要求V^\hat{V}的 Lipschitz 常數為有限值,或者說,V^\hat{V}是 Lipschitz 連續的。)

Thm 2. 強對偶

Primal問題與Dual問題具有相同的最優值,並存在滿足互補鬆弛條件的最優解,當且僅當勸說問題是正則的。

Corollary 1. 互補鬆弛性

Primal 問題的某個可行分佈τ\tau與 Dual 問題的某個可行價格PP分別為兩個問題的解,當且僅當

support(τ)⊂{μ∈Δ(Ω):∫ΩP(ω)dμ(ω)=V(μ)}\text{support}(\tau)\subset\{\mu\in\Delta(\Omega):\int_{\Omega}P(\omega)d\mu(\omega)=V(\mu)\}

證明: