引き続き今年のフィールズ賞ネタ。A Fine Theoremブログが、今回フィールズ賞を受賞したアレッシオ・フィガリとネヴァンリンナ賞を受賞したコンスタンティノス・ダスカラキスの業績と経済学との関連について、表題のエントリ（原題は「The 2018 Fields Medal and its Surprising Connection to Economics! 」）で説明している。
...what is the cheapest way to move mass from X to Y, such as moving apples from a bunch of distribution centers to a bunch of supermarkets. It turns out that without convexity or linearity assumptions, this problem is very hard, and it was not solved until the late 20th century. Leonid Kantorovich, the 1975 Nobel winner in economics, paved the way for this result by showing that there is a “dual” problem where instead of looking for the map from X to Y, you look for the probability that a given mass in Y comes from X. This dual turns out to be useful in that there exists an object called a “potential” which helps characterize the optimal transport problem solution in a much more tractable way than searching across any possible map.
Note the link between this problem and our optimal auction problem above, though! Instead of moving mass most cheaply from X to Y, we are looking to maximize revenue by assigning objects Y to people with willingness-to-pay drawn from X. So no surprise, the solution to the optimal transport problem when X has a particular structure and the solution to the revenue maximizing mechanism problem are tightly linked. And luckily for us economists, many of the world’s best mathematicians, including 2010 Fields winner Cedric Villani, and this year’s winner Alessio Figalli, have spent a great deal of effort working on exactly this problem. Ivar Ekeland has a nice series of notes explaining the link between the two problems in more detail.
In a 2017 Econometrica, this year’s Nevanlinna winner Daskalakis and his coauthors Alan Deckelbaum and Christos Tzamos, show precisely how to use strong duality in the optimal transport problem to solve the general optimal mechanism problem when selling multiple goods. The paper is very challenging, requiring some knowledge of measure theory, duality theory, and convex analysis. That said, the conditions they give to check an optimal solution, and the method to find the optimal solution, involve a reasonably straightforward series of inequalities. In particular, the optimal mechanism involves dividing the hypercube of potential types into (perhaps infinite) regions who get assigned the same prices and goods (for example, “you get good A and good B together with probability p at price X”, or “if you are unwilling to pay p1 for A, p2 for B, or p for both together, you get nothing”).
（拙訳）
・・・リンゴを配送センターの集合からスーパーマーケットの集合に移動させるといったような、一塊の物をXからYに移動させる最も安価な方法は何だろうか？ 凸性や線形性の仮定が無ければ、この問題は非常に難しいことが判明し、20世紀後半まで解かれることは無かった。1975年にノーベル経済学賞を受賞したレオニート・カントロヴィチは、XからYへの地図写像を求める代わりに、Yのある塊がXから来た確率を求めるという「双対」問題の存在を示して、解決への道を拓いた。可能性のある地図写像をすべて探しまわるよりも遥かに容易な形で最適輸送問題の解を特徴付けるのに役立つ「ポテンシャル」という変数が存在するという点で、この双対問題は有用であることが判明した。
なお、この問題と前述の最適オークション問題との関連に注意されたい！ 一塊の物をXからYに最も安価に移動させる代わりに、我々はXから抜き出された支払う気のある人に対象Yを割り当てて収入を最大化しようとしていた。従って、驚くべきことではないが、Xに特定の構造がある最適輸送問題の解と、収入を最大化するメカニズムの解との間には密接な関連がある。そして我々経済学者にとって幸運なことに、2010年のフィールズ賞受賞者セドリック・ヴィラニや今年の受賞者のアレッシオ・フィガリといった世界最良の数学者の多くが、まさにこの問題の研究に多大な努力を注ぎ込んだ。イヴァール・エクランドがその2つの問題の関連をさらに詳しく解説した素晴らしい一連のメモを書いている。
2017年のエコノメトリカで今年のネヴァンリンナ賞受賞者ダスカラキスと共著者アラン・デッケルバウムとクリストス・ザモスは、複数の商品を売る際の一般的な最適メカニズム問題を解くために最適輸送問題の強双対性を使う方法を正確に示している。同論文は非常に敷居が高く、測度論、双対理論、および凸解析に関する知識が要求される。とは言え、彼らが示した最適解を確認する条件、および、最適解を見つける手法は、かなり直接的な一連の不等式を含んでいる。具体的には、最適メカニズムは、可能な購入形態の超立方体を、同じ価格と商品が割り当てられる（おそらくは無限の）領域（例えば、「商品Aと商品Bを確率pで価格Xで同時に入手する」とか「Aにp1、Bにp2支払うか、もしくは両者セットでpを支払うかしなければ、何も買えない」など）に分割する、という手続きを踏むことになる。
