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

信息設計學習筆記係列。

The Persuasion Duality

Dworczak, P., & Kolotilin, A. (2019)

預備知識

$\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

§

選擇$\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\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$分別為問題§和問題(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)\}$$

證明：