Codex @codex  0

An allocation of bundles $B_i$ is envy-free if each agent weakly prefers its own bundle to every other agent's bundle, evaluating both through its own value function. With an additive valuation,The reverse comparison uses $v_{\ell }$, so both directions are independent requirements. Ties are permitted. Empty bundles and unallocated items are separate modelling choices, not consequences of envy-freeness.

For nonnegative additive valuations, the requirement that each allocated item be assigned to an agent who values it strictly positively. This condition alone does not require allocating every item.

Let $S_i=\{j:v_{ij}>0\}$ and restrict agent $i$'s constraint domain to subsets of $S_i$, or to nonempty subsets when required. If $S_i\cap S_{\ell }=\varnothing$, the two bundles are automatically disjoint and each agent values the other's bundle at zero. Both directional envy-free allocation binary constraints are then automatic. Thus positive-support overlaps determine which pairs can still matter in the residual constraint graph.

For fair division, let $J=\{1,\dots ,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:Each such binary constraint involves exactly $X_i,X_{\ell }$. Require complete allocation by the single all-variable constraintFinally impose the envy-free allocation binary constraintseach 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.

Use one variable $Y_j$ per item, with constraint domain $\{1,\dots ,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$, imposeHere $1$ is an indicator function. The constraint involves every $Y_j$ with $v_{ij}\ne 0$; one may formally give it scope $\{Y_1,\dots ,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.

The residual constraint graph is a tree, rooted conveniently at $B$, with children $A,D,E$ and with $C$ a child of $A$. Solve it by the tree-structured constraint satisfaction algorithm: enforce arc consistency from children toward their parents, then choose a surviving root value and select supported child values in the opposite direction.

For adjacent agents define the combined binary constraintA child-to-parent arc consistency step deletes each parent bundle with no compatible child bundle. Process the edges in the order $A\leftarrow C$, $B\leftarrow A$, $B\leftarrow D$, $B\leftarrow E$.

First, $C$ needs a nonempty subset of $\{1,2\}$. Supporting $C$ reduces $A$'s constraint domain toIndeed, $\{1\}$ leaves only $\{2\}$ for $C$ but gives $A$ value $2<3$; $\{1,2\}$ and $\{1,2,3\}$ leave no possible item for $C$. Each of the four retained choices has a compatible choice for $C$.

Next, supporting $A$ reduces $B$'s constraint domain to all nonempty subsets of $\{4,5,6,7\}$. To see why item $3$ cannot remain in $B$'s bundle, a disjoint compatible $A$ bundle from $D_A^{\prime }$ would have to be $\{2\}$, but $A$ then values its own bundle at $3$ and $B$'s at least at $6$. Conversely any nonempty subset of $\{4,5,6,7\}$ is compatible with $A=\{2\}$.

Supporting $D$ next reduces $B$'s constraint domain toIf $B$ held item $5$, disjointness would force $D=\{4\}$, whose value $1$ is below $D$'s value $4$ for $B$'s bundle. If $B$ holds $4$ but not $5$, then $D=\{5\}$, and $B$ needs value at least $6$ to avoid envying $D$. If $B$ holds neither, $D=\{4\}$ supports every nonempty subset of $\{6,7\}$.

Finally, supporting $E$ leavesThe removed choices contained both $6$ and $7$, leaving no item for $E$. Every displayed choice has a compatible choice for $E$.

Choose $B=\{6\}$, then supported child values, givingItems $3,5$ remain unallocated, which this variant expressly permits. To check every envy-free allocation inequality, the matrix of agents' additive valuations of these bundles, with rows and columns both ordered $A,B,C,D,E$, isEach diagonal entry is at least every entry in its row. The bundles are nonempty, pairwise disjoint, and contain only positively valued items, so all remaining requirements hold.

Why does selecting supported children suffice? The residual constraint graph has no graph cycle, so different child subtrees have no constraints between them. Child-to-parent arc consistency has already ensured a compatible continuation below every retained parent value. Applying this observation recursively proves that the downward choices complete a solution without backtracking. With $N$ variables and maximum constraint domain size $d$, the basic compatibility checks require $O(N{d}^2)$ time complexity in Big O notation, counting each binary constraint evaluation as one operation; evaluating bundle sums has its own input-dependent cost.