3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Related: cstheory.stackexchange.com/q/16206/8237 $\endgroup$
    – Neal Young
    Feb 10 at 12:21
  • $\begingroup$ Yes! But actually I understand LP duality in general - I am just having trouble understanding this particular "interpretation" given to it $\endgroup$ Feb 11 at 13:55

1 Answer 1

2
$\begingroup$

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.)

$\endgroup$
2
  • 1
    $\begingroup$ A similar story for the dual is that somebody (say Phil) wants all the items, so he offers to give each person $u_j$ and pay $p_i$ for each item. Everybody agrees to the deal if $u_j \geq v_{ij} - p_i$. Phil wants to minimize the total payments he's making, while still incentivizing each selfish agent to individually accept the deal. $\endgroup$
    – usul
    Feb 11 at 15:27
  • $\begingroup$ Thanks!! super helpful :-) $\endgroup$ Feb 11 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.