Past exam of the computer science course of the University of Oxford / 2023 / Artificial intelligence / 3 / e / Solution

Restrict each agent to nonempty bundles of items that they value positively. Let the positive-value supports beThe residual constraint domains are $D_i=\mathcal{P}(S_i)\setminus \{\varnothing \}$, with sizes $7,31,3,3,3$, respectively. The no-waste allocation and nonempty-bundle requirements are now built into these constraint domains.

If $S_i\cap S_{\ell }=\varnothing$, every pair $X_i\in D_i$, $X_{\ell }\in D_{\ell }$ is disjoint. Moreover, $v_i(X_{\ell })=v_{\ell }(X_i)=0$, so both envy-free allocation inequalities hold automatically because all values are nonnegative. Thus all three binary constraints disappear for the pairsThe only positive-support overlaps, and hence the remaining constraint graph edges, arewhere parentheses list the shared items.

Each listed pair really retains restrictions. For $AC$, $AB$, $BD$, $BE$, respectively, let both endpoints choose $\{1\}$, $\{3\}$, $\{4\}$, $\{6\}$: this violates disjointness while belonging to both residual constraint domains. The directional envy-free allocation inequalities are also individually nontrivial. For example, for $AB$, choosing $X_A=\{1\}$ and $X_B=\{3\}$ makes $A$ envious, while choosing $X_A=\{3\}$ and $X_B=\{4\}$ makes $B$ envious. The analogous shared-item comparisons apply on the other three edges.