坎托罗维奇对偶定理

命题陈述

对于 $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)$ 恰好沿着最优方案实际使用的路径成立。

用到此定理的主题

分步证明

该定理暂无分步证明。