Four agents, four tasks, a cost matrix. Match them one-to-one for the cheapest total — and prove it is the cheapest. The proof is not the assignment; it is a set of prices ui, vj with ui+vj≤Cij whose sum equals the minimum cost. That equality — Kantorovich duality — is the whole payoff, and every number here is runnable.
source Leonid Vitaliyevich Kantorovich (1912–1986), Leningrad — the transportation / assignment problem & the birth of linear programming (1939); Nobel Memorial Prize in Economics, 1975; founder of optimal transport (Monge–Kantorovich). Room: THE NUMBER. Rendered, not quoted.
Leonid Kantorovich was 26 when the Leningrad plywood trust asked a routine question: how to assign machines to jobs to lose the least output. He saw a general shape behind it and, in 1939, wrote Mathematical Methods of Organizing and Planning Production — linear programming, years before the West.
The idea did not fit Soviet planning orthodoxy and lay half-buried for two decades. In 1975 he shared the Nobel Memorial Prize in Economics — to this day the sole Soviet laureate in that field — for the theory of optimal resource allocation. His prices are the real math under any planning board that claims to allocate well: this sphere ties GOBERNET.
Given an n×n cost matrix C, choose a perfect matching — a permutation π sending each agent i to a distinct task π(i) — minimising the total ∑i Ci,π(i).
This is the assignment problem, the discrete face of optimal transport (supplies and demands all equal 1). Here n = 4, so there are exactly 4! = 24 permutations — small enough to check every one and be certain, with no heuristic in the loop.
Enumerate all 24 permutations, score each against C, keep the minimum. Exhaustive search is exact by construction: there is nowhere for a cheaper matching to hide.
minπ ∑i Ci,π(i) = —
Optimal matching: —. Every other permutation scores ≥ this. The full ranked list is in the panel; the worst is —.
A fixed 4×4 integer cost matrix C. Click a cell in a row to hand-pick a matching and watch its total, or let the solver enumerate all 24. The permutation is the primal; the prices are the dual.
Your hand-picked matching: — total —
Left: every permutation, cheapest first — the primal. Right: the Kantorovich prices ui, vj feasible for ui+vj≤Cij, maximising ∑u+∑v — the dual.
| π (task per agent) | cost |
|---|
min primal = — = max dual = —. Weak duality says any feasible price-sum is a lower bound on any matching; when the two meet, no gap remains — the matching is optimal and the prices prove it. That is Kantorovich’s theorem, computed live.
Gaspard Monge (1781) asked how to move a pile of earth to a hole with the least total work — but his “each grain to one spot” map can be ill-posed: no map may exist. Kantorovich (1942) relaxed it to a coupling — mass may split — and the problem always has a solution, with the same dual prices.
That relaxation is the modern field: the Wasserstein distance between distributions, now everywhere from PDEs to machine learning. The assignment problem in the centre is its cleanest discrete case — supplies and demands all 1, so the optimal coupling is a permutation. history
“Greedy nearest-cost is optimal — assign each agent its cheapest free task.” Cut. Greedy is myopic: grabbing a local minimum can force a costly leftover. On this very matrix greedy misses the optimum. The global answer needs the duality, not a rule of thumb.
“You cannot prove a matching is best without trying all of them.” Cut. A single feasible price vector whose sum equals a matching’s cost is a certificate — it proves optimality in one line, no enumeration required.
“Central planning had no real mathematics behind it.” Cut. Optimal allocation is a theorem; Kantorovich won a Nobel for it. Whether a state used it is another matter — that is GOBERNET’s question, not this one.
The red team’s move: assert a specific non-optimal matching is the optimum — the identity π = (0,1,2,3), total 18. But the brute-force minimum over all 24 is 13, so a strictly cheaper matching exists. The witness recomputes and the false crown turns red.
Claim (0,1,2,3) is optimal and the solver finds (1,0,2,3) costing 13 < 18. The claimed-optimal witness goes red and DATA OUT reads GAP OPEN. The attack is real and it is caught.