= Solution
Regard the two kinds of agents as the two sides of a <complete bipartite graph>, with <edge weight> $c_{ij}$. Pairing everyone is a <perfect matching>, and its maximum total weight is $P$. Consider the capacitated <linear program>
$$
\begin{aligned}
P_{\rm LP}=\max\quad&\sum_{i,j}c_{ij}x_{ij}\\
\text{subject to}\quad&\sum_jx_{ij}\leq1\quad(1\leq i\leq n),\\
&\sum_ix_{ij}\leq1\quad(1\leq j\leq n),\qquad x_{ij}\geq0.
\end{aligned}
$$
It is feasible and bounded. Every optimum has all row and column sums equal to one: otherwise the equal total deficits of the two sides give a row $i$ and column $j$ both below one. Increasing $x_{ij}$ by the smaller of their positive deficits remains feasible and increases the objective because $c_{ij}>0$, a contradiction.
Thus an optimum is a <doubly stochastic matrix>. By the <Birkhoff-von Neumann theorem> it is a <convex combination> of <permutation matrices>, so at least one corresponding <perfect matching> has weight at least its objective. Conversely every such <perfect matching> gives a feasible <matrix>. Hence $P_{\rm LP}=P$. One way to justify the decomposition is to apply <Hall's marriage theorem> to the positive-entry support, subtract the smallest entry on a supported <perfect matching>, and repeat after rescaling the nonzero remainder; each subtraction removes a positive entry, so the process terminates.
The <dual linear program> assigns nonnegative <dual variables> $p_i,q_j$ to the row and column capacity constraints:
$$
\boxed{\min\sum_i p_i+\sum_jq_j\quad\text{subject to}\quad p_i+q_j\geq c_{ij},\qquad p_i,q_j\geq0.}
$$
These are exactly the permitted payments and all the pairwise acceptance conditions, so its optimal value is $Q$. It is feasible, for example by taking $p_i=\max_jc_{ij}$ and $q_j=0$. <Strong duality> now gives \b[$P=P_{\rm LP}=Q$]. In particular, the nonnegative payment restriction has been retained throughout; using capacity inequalities rather than equality constraints avoids introducing unrestricted prices.
For a direct <weak duality> check, sum $p_i+q_{\pi(i)}\geq c_{i,\pi(i)}$ over any pairing $\pi$. Its revenue never exceeds the company's total offered payment. The <linear programming duality> and integrality argument prove that this lower bound on payments is attained.
Back to article page
