不求甚解學經濟-信息設計-The Persuasion Duality

信息設計學習筆記係列。

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

参见 一些簡單的凸分析

令 $C$ 为 凸集，$f$ 为定义在 $C$ 上的凹函数。称向量 $p$ 是函数 $f$ 在点 $x\in C$ 处的 supergradient， 如果对于任何向量 $y$，都有 $f (x) + p · (y − x) \geq f (y)$。

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

（一个 loosely 的理解方法：如果$f$ 本身是二阶连续可导的单变量函数，那么的对 $f(y)$ 在 $x$ 点做二阶 Taylor expansion，那么 $f(y)=f(x)+f'(x)(y-x)+\frac{1}{2}f''(x)(y-x)^{2}$，而凹函数$f''(x)\leq 0$，所以 $f(x)+f'(x)(y-x)\geq f(y)$）

这篇文章表明，最优的 dual variable 就是目标函数的 concave closure （本来是与 Primal 相联系的）在先验信念处的 supergradient。我们前面的定义里 $f$ 需要是 concave 的，但是目标函数却未必是 concave 的（即，目标函数本身不是我们定义里的 $f$），所以需要取 concave closure，使得我们的新目标函数 $f$ 变成 concave 的。既然新目标函数是通过取 concave closure 得到的，那么就意味着新目标函数逐点不高于原本的目标函数，而先验信念就是此处的 $x$，对于任何信念 $y$ 来说，这个 optimal dual variable $p$ 使得

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

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

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

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

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

Riesz-Markov-Kakutani representation theorem

任一線性連續(等價於線性有界)泛函$H\in\Delta(\Omega)$都可以用某個$P\in C(\Omega)$錶示為$H(\mu)=\int_{\Omega}P(\omega)d\mu(\omega)$。

這個隻是夠用的版本，實際的 RMK 錶示定理適用範圍更廣，比如$\Delta(\Omega)$可以推廣為任何局部緊的Hausdorff空間、取值可以為複數等等，可見Rudin (1987)。

凸序

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

模型

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

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

Primal Problem

(P)

選擇$\tau\in\Delta(\Delta(\Omega))$，來最大化

$$\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\in C(\Omega)$，其中$C(\Omega)$為$\Omega$上連續函數的集合，來最小化

$$\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)$在$\text{weak}^{\star}$拓撲下也是緊的，並且是可度量化的。

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

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

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

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

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

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

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

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

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

對偶

Thm 1. 弱對偶

如果某個$\tau\in\Delta(\Delta(\Omega))$對於問題(P)可行，且某個$P\in C(\Omega)$對於問題(D)可行，則

(G)

$$\int_{\Omega}P(\omega)d\mu_{0}(\omega)\geq\int_{\Delta(\Omega)}V(\mu)d\tau(\mu)$$

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

(0)

$$\int_{\Omega}P(\omega)d\mu_{0}(\omega)=\int_{\Delta(\Omega)}V(\mu)d\tau(\mu)$$

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

Prop 1. 無對偶缺口

Def 1. 正則性

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

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

回憶超梯度的定義：考慮有限維情況，給定$f$是凸集$C\in\mathbb{R}^{n}$上的凹函數，那麼我們稱一個嚮量$p\in\mathbb{R}^{n}$是$f$在點$x$處的超梯度，若嚮量$p$滿足，對於任何$y$有如下超梯度不等式：

$$f(x)+p(y-x)\geq f(y)$$

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

但由於我們當前考慮的是無限維情況，需要對前述$p(y-x)$的錶述做進一步推廣。這就要用到 Riesz-Markov-Kakutani representation theorem，根據這一定理，任一線性連續(等價於線性有界)泛函$H\in\Delta(\Omega)$都可以用某個$P\in C(\Omega)$錶示為$H(\mu)=\int_{\Omega}P(\omega)d\mu(\omega)$，從而超梯度不等式變為，對於所有$\mu\in\Delta(\Omega)$

$$\hat{V}(\mu_{0})+\int_{\Omega}P(\omega)d\mu(\omega)\geq\hat{V}(\mu)$$

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

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

Thm 2. 強對偶

Primal問題與Dual問題具有相同的解並滿足強對偶性，當且僅當勸說問題是正則的。

Corollary 1. 互補鬆弛性

Primal 問題的某個可行分佈$\tau$與 Dual 問題的某個可行價格$P$分別為兩個問題的解，當且僅當

$$\text{support}(\tau)\subset\{\mu\in\Delta(\Omega):\int_{\Omega}P(\omega)d\mu(\omega)=V(\mu)\}$$

證明：