= Solution
For <fair division>, let $J=\{1,\ldots,m\}$ and let the <additive valuation> of agent $i$ be $v_i(S)=\sum_{j\in S}v_{ij}$. Use one variable $X_i$ per agent, with <constraint domain> $\mathcal P(J)$, the <power set> of the items. Empty bundles are permitted in this original formulation.
Require pairwise <disjoint sets>:
$$
X_i\cap X_\ell=\varnothing\qquad(1\le i<\ell\le n).
$$
Each such <binary constraint> involves exactly $X_i,X_\ell$. Require complete allocation by the single all-variable constraint
$$
\bigcup_{i=1}^{n}X_i=J.
$$
Finally impose the <envy-free allocation> <binary constraints>
$$
v_i(X_i)\ge v_i(X_\ell)\qquad(i\ne\ell),
$$
each on $X_i,X_\ell$. The two directions for a pair use different agents' <additive valuations> and must both hold. These conditions give precisely an ordered <set partition> of the items that is an <envy-free allocation>.
Back to article page
