カントロビッチ双対定理

内容

$X$ 上の確率測度 $\mu$、$Y$（ともにポーランド空間）上の確率測度 $\nu$、および連続で下に有界な費用 $c$ に対して、カントロビッチ問題は、各点で $\varphi(x) + \psi(y) \le c(x,y)$ を満たすカントロビッチ・ポテンシャルの組 $\varphi:X\to\mathbb R$、$\psi:Y\to\mathbb R$ にわたる双対最大化問題に等しい：$\min_{\gamma\in\Pi(\mu,\nu)}\int_{X\times Y} c\,d\gamma \;=\; \sup_{\varphi(x)+\psi(y)\le c(x,y)}\left(\int_X\varphi\,d\mu+\int_Y\psi\,d\nu\right),$ 最小値と上限はともに達成される。

なぜ正しいのか?

$\varphi(x)$ を $x$ で質量を引き取る際に課される価格、$\psi(y)$ を $y$ で引き渡す際に支払われる価格とみなし、独立した運送業者たちによる分散市場を考えてみよう。どの業者も直接輸送のルートを出し抜いて利益を得ることはできない：$\varphi(x)$ で買い $\psi(y)$ で売る取引は、実際に質量を運んで $c(x,y)$ を支払うことに決して勝てない——これがまさに制約 $\varphi(x)+\psi(y)\le c(x,y)$ である。市場が最適に清算されるとき、等式 $\varphi(x)+\psi(y)=c(x,y)$ は最適な計画が実際に使う経路上でちょうど成り立つ。

この定理を使うトピック

ステップごとの証明

この定理のステップごとの証明はまだありません。