<p>I think you are right that the dual problem is a story about selfish agents and the primal about selfless ones.</p>
<p>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.</p>
<p>The dual problem is to assign numbers to objects, i.e. assign prices to items and utilities to people. (It is <strong>not</strong> to match people to items.) The hypothetical scenario is that people get handed a bunch of money, the <span class="math-container">$u_j$</span>s, and the items also get pricetags <span class="math-container">$p_i$</span>. According to the constraints, the people prefer keeping their free money <span class="math-container">$u_j$</span> over having to pay <span class="math-container">$p_i$</span> for an item and getting utility <span class="math-container">$v_{ij}$</span> for it. In other words, the constraints are of the form <span class="math-container">$u_j \geq v_{ij} - p_i$</span>, 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.</p>
<p>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.</p>
<p>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.</p>
<p>(There are multiple interpretations. I wrote this as if it was &quot;the&quot; correct answer, but in reality, there could be other correct answers that contradict some interpretations I made.)</p>

CC BY-SA 4.0
2023-02-11T15:27:14.767Z
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.
usul
CC BY-SA 4.0
2023-02-11T18:35:31.850Z
Thanks!! super helpful :-)
Noah Singer
CC BY-SA 4.0
2023-02-11T15:25:35.003Z
2023-02-11T15:25:35.003Z
usul
<p>I recently learned about the Hungarian algorithm for maximum-weight matching in bipartite graphs and the &quot;market&quot; interpretation of the primal and dual LPs. (See also <a href="http://www.cs.cmu.edu/%7E15850/notes/lec9.pdf" rel="nofollow noreferrer">these notes</a>.)</p>
<p>The setup: We have a bipartite graph <span class="math-container">$G = (L,R,E)$</span> with nonnegative edge-weights, and we want to find a matching <span class="math-container">$M$</span> maximizing <span class="math-container">$\sum_{i \sim j \in M} v_{ij}$</span>, where <span class="math-container">$v_{ij}$</span> is the edge weight. We can write this as an LP, which turns out to be integral, and its dual is to find <span class="math-container">$\vec{p} \in \mathbb{R}_{\geq 0}^L$</span> minimizing <span class="math-container">$\sum_i p_i + \sum_{j} u_j(\vec{p})$</span> where we define <span class="math-container">$u_j(\vec{p}) = \min_i (v_{ij} - p_i)$</span>.</p>
<p>These both have a &quot;market&quot; interpretation. We can view <span class="math-container">$L$</span> as items and <span class="math-container">$R$</span> as buyers. In the primal problem, we want to match each buyer to a unique item; <span class="math-container">$v_{ij}$</span> represents how much buyer <span class="math-container">$j$</span> wants item <span class="math-container">$i$</span>; and the objective <span class="math-container">$\sum_{i\sim j\in M} v_{ij}$</span> is the &quot;social welfare&quot;, representing how &quot;collectively happy&quot; the buyers are with the matching. In the dual problem, we view <span class="math-container">$p_i$</span> as a &quot;price&quot; and <span class="math-container">$u_j(\vec{p})$</span> as the &quot;utility&quot; of buyer <span class="math-container">$j$</span> when buying their most preferred item.</p>
<p>By duality, any setting of <span class="math-container">$\vec{p}$</span> 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 &quot;hypothetical scenario&quot; 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 <span class="math-container">$\sum_i p_i$</span> term, which seems to correspond to a &quot;seller&quot; who pays the price <span class="math-container">$p_i$</span> exactly once per item, regardless of which the buyers actually want to buy.</p>
<p>Is there an example (maybe even an &quot;everyday life&quot; 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.</p>

CC BY-SA 4.0
2023-02-10T12:21:28.667Z
Related: https://cstheory.stackexchange.com/q/16206/8237
Neal Young
CC BY-SA 4.0
2023-02-11T13:55:56.733Z
Yes! But actually I understand LP duality in general - I am just having trouble understanding this particular "interpretation" given to it
Noah Singer
<linear-programming><matching>
"Market" intuition for the dual of the max-weight matching LP
Noah Singer
# "Market" intuition for the dual of the max-weight matching LP

(Asked by: username_0 on 2023-02-09)

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](http://www.cs.cmu.edu/%7E15850/notes/lec9.pdf).)

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.

**Tags:** linear-programming, matching

> **Comments:**
> **username_1**: Related: https://cstheory.stackexchange.com/q/16206/8237  
> **username_0**: Yes! But actually I understand LP duality in general - I am just having trouble understanding this particular "interpretation" given to it  

---

## 1 answers

### Answer by username_2 on 2023-02-11. Score: 2 | Accepted answer

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

> **Comments:**
> **username_2**: 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.  
> **username_0**: Thanks!! super helpful :-)  

---

