= Solution
Use one variable $Y_j$ per item, with <constraint domain> $\{1,\ldots,n\}$. Its value is the recipient agent. Every assignment automatically allocates each item exactly once, so separate coverage and disjointness constraints are unnecessary.
For every ordered pair $i\ne\ell$, impose
$$
\boxed{\sum_{j=1}^{m}v_{ij}\mathbf1_{\{Y_j=i\}}
\ge
\sum_{j=1}^{m}v_{ij}\mathbf1_{\{Y_j=\ell\}}.}
$$
Here $\mathbf1$ is an <indicator function>. The constraint involves every $Y_j$ with $v_{ij}\ne0$; one may formally give it scope $\{Y_1,\ldots,Y_m\}$, since zero coefficients make the other variables irrelevant. These constraints state <envy-free allocation> using the comparing agent's <additive valuation> on both sides. In contrast to part (a), they generally involve more than two variables.
Back to article page
