$\newcommand\E{\mathbb E}$ $\newcommand\eps\varepsilon$
In Cedric Villani’s book, he explains optimal transport with bread.
Imagine if you owned a bunch of bread factories and a bunch of cafes. Every piece of bread you make is identical.
Each factory has a certain output and each cafe has a certain demand, and there is a cost $c(i, j)$ associated to moving one piece of bread from factory $i$ to cafe $j$.
We wish to minimize the average cost: i.e. $$\E_{\text{bread}} c(X, Y)$$ where each piece of bread gets sent from factory $X$ to factory $Y$.
One day, a contractor comes to you and offers you a deal - presumably he has a way to circumvent the transport costs. He buys each bread at factory $i$ for $f(i)$ and sells it back to you at cafe $j$ for $g(j)$. So instead, you earn ( on average) $$\E g(Y) - \E f(X)$$ Of course, one caveat is that for any factory-cafe pair it should cost you less per bread than it does for you to do it yourself, i.e. $g(j) - f(i) \le c(i,j)$.
It’s immediately clear that you’ve saved money via the contractor, but the amazing fact is that across all possible contractors, the one that has the highest average cost will match the best plan that you have: $$\max_{g-f\le c} \E[g(Y) - f(X)] = \min_{X\to Y} \E[c(X,Y)]$$
We haven’t explained why we suspect this is true. We would need:
First, we want to get a bread plan that has no “cycles”. The basic reason is that if along a cycle, the odd edges and the even edges perform the same overall bread movement. If one of them costs less, then we can switch both to that and reduce the cost. Hence both of them cost the same, but that means we can switch one over to the other without changing the cost.
If you believe that this process terminates, then eventually we get a “tree”. Then, we should be able to start somewhere, fix a price (e.g. 0), and then fix all the other prices to match it up with the plans.
So, along the pairs of the plan $X\to Y$, $c(x,y) = g(y) - f(x)$ so we have a valid contractor pricing.
This is trickier.
When does the contractor have the best pricing? For instance, he might try to raise $g(j)$, but if the pricing was truly the best he must have failed the cost condition. So, there’s some $i$ where $g(j) = c(i,j) + f(i)$
In general, if we look at $m$ cafes anywhere and attempt to raise all their prices by $\eps$, then the factories where the profits are taut must have at least that many bread, since otherwise we can raise their prices by slightly less than $\eps$.
Then now some variant of Hall’s matching lemma tells us we can match cafe bread demand to factory bread supply.
One simplification: surely we want $g$ to be as large as possible while $g-f \le c$, so $$g(j) = \min_i \{ f(i) + c(i,j) \}$$ We will notate this $f^c(j)$. So this is telling us that $$\max_f\E[f^c(j) - f(i)] = \min_{X\to Y} \E[c(x,y)] $$
Surely, we can also do the flip-side: if $f$ is as small as possible, then $$f(i) = \max_j \{g(j) - c(i,j)\}$$ We will notat this $g^c(i)$. This seems kind of confusing, but do remember that the type signatures: $$ \begin{align*} f &: \{\text{factory}\} \to \R \\ g &: \{\text{cafe}\} \to \R \end{align*} $$
One notes that both $$ \begin{align*} \E[g(j) - f(i)] &\le \E[f^c(j) - f(i)]\\ \E[g(j) - f(i)] &\le \E[g(j) - g^c(i)] \end{align*} $$ so one imagines a process where we can get progressively better functions: $$(f,g) \to (f, f^c) \to (f^{cc}, f^c) \to ...$$ Does this stop? Actually, yes.
Thm. / Exercise. Show that $f^{ccc} = f^c$.