"Market" intuition for the dual of the max-weight matching LP

Question

I recently learned about the Hungarian algorithm for maximum-weight matching in bipartite graphs and the "market" interpretation of the primal and dual LPs. (See also these notes.)

The setup: We have a bipartite graph $G = (L,R,E)$ with nonnegative edge-weights, and we want to find a matching $M$ maximizing $\sum_{i \sim j \in M} v_{ij}$, where $v_{ij}$ is the edge weight. We can write this as an LP, which turns out to be integral, and its dual is to find $\vec{p} \in \mathbb{R}_{\geq 0}^L$ minimizing $\sum_i p_i + \sum_{j} u_j(\vec{p})$ where we define $u_j(\vec{p}) = \min_i (v_{ij} - p_i)$.

These both have a "market" interpretation. We can view $L$ as items and $R$ as buyers. In the primal problem, we want to match each buyer to a unique item; $v_{ij}$ represents how much buyer $j$ wants item $i$; and the objective $\sum_{i\sim j\in M} v_{ij}$ is the "social welfare", representing how "collectively happy" the buyers are with the matching. In the dual problem, we view $p_i$ as a "price" and $u_j(\vec{p})$ as the "utility" of buyer $j$ when buying their most preferred item.

By duality, any setting of $\vec{p}$ witnesses an upper bound on the best possible matching. But from the market perspective, I don't understand why this should be the case. It means that we can prove that the buyers cannot collectively be very happy (in the primal) by imagining a "hypothetical scenario" where the items are assigned prices (in the dual). In this hypothetical scenario, the buyers can behave selfishly (i.e., they take their most preferred item), and the objective contains a $\sum_i p_i$ term, which seems to correspond to a "seller" who pays the price $p_i$ exactly once per item, regardless of which the buyers actually want to buy.

Is there an example (maybe even an "everyday life" one), or any sort of reasoning, that shows why this makes any sense? My only intuition is that in the primal buyers may have to be selfless, while in the dual they can be selfish.

Answer 1

I think you are right that the dual problem is a story about selfish agents and the primal about selfless ones.

It might help to emphasize that the primal and dual are solving different problems. The primal problem is to match people to items. The constraints just say: one person, one item. And the objective function is a global one: social welfare. Individual choice does not enter the problem, i.e. we need people to selflessly accept the globally optimal configuration.

The dual problem is to assign numbers to objects, i.e. assign prices to items and utilities to people. (It is not to match people to items.) The hypothetical scenario is that people get handed a bunch of money, the $u_j$s, and the items also get pricetags $p_i$. According to the constraints, the people prefer keeping their free money $u_j$ over having to pay $p_i$ for an item and getting utility $v_{ij}$ for it. In other words, the constraints are of the form $u_j \geq v_{ij} - p_i$, selfish or local preference constraints. The objective is to minimize this: the money we have to hand out plus the prices we have to set.

Weak duality essentially says that the total welfare in the free-money world is higher than the total welfare in the matching world. More precisely, the total sum of payments and prices in the free-money world is higher than the sum of utilities in the matching world. Weak duality makes sense because in free-money world, everyone is choosing not to match to any items, so any primal matching must make everyone in it less happy than they were in free-money world.

Strong duality implies that if we set prices and free-money handouts just right, everyone is indifferent between the free money and matching along their assigned edge in the primal OPT. This is a surprising local-to-global fact: there is a way to align incentives with prices such that local selfish behavior matches up with globally optimal behavior.

(There are multiple interpretations. I wrote this as if it was "the" correct answer, but in reality, there could be other correct answers that contradict some interpretations I made.)