GPT 6 Astra Ultra attempt on Econ-92

Proof: Query $T=V([0,1])$. Enumerate every complete item partition $O$ and every subset $J\subseteq[n]$ proposed to receive positive cake value. For fixed $O$ write \[ a_{ij}=v_i(O_j)-v_i(O_i),\qquad h_{ij}=\max\left(\{v_{ig}:g\in O_j\}\cup\{0\}\right). \] Seek cake masses $t_i\geq0$ with $\sum_i t_i=T$. Set $t_j=0$ for $j\notin J$. For each $j\in J$ impose \[ t_i-t_j\geq a_{ij}\quad\text{for all }i. \] For each $j\notin J$ impose \[ t_i\geq a_{ij}-h_{ij}\quad\text{for all }i. \] These are exactly the weak-EFM inequalities for this support. In the zero-cake case, removing the most valuable item of $O_j$ is the best deletion for $i$; if $O_j$ is empty, the displayed inequality is simply no envy. Allowing no envy as a separate branch gives the same condition because $h_{ij}\geq0$.

If $J$ is nonempty, introduce $0\leq e\leq T$ and $t_j\geq e$ for all $j\in J$, and maximize $e$. Accept this case precisely when its optimum is strictly positive. This tests strict positivity exactly: a feasible finite list of positive masses has a positive minimum, and conversely $e>0$ forces every declared positive mass to be positive. The feasible region is bounded and closed, so a feasible program attains its optimum. If $J$ is empty, test the displayed system directly, necessarily with $T=0$.

This finite enumeration finds masses whenever a weak-EFM allocation exists, because every actual allocation has one enumerated item partition and a cake-value support $J$. Existence in the present additive-goods domain is the established EFM existence theorem of Bei et al. [bei]; their stronger physical-cake version implies the weak condition used here. This existence input is not a new theorem of this note.

Realize the accepted masses with sequential cuts. For each $i<n$, cut a piece of value $t_i$ from the current left endpoint, skipping zero requests if convenient. Assign the remainder to agent $n$. Each request is admissible because remaining mass equals the sum of the remaining $t_i$. Continuity of the cumulative density integral guarantees a cut, and the prescribed leftmost answer still has exactly the requested value. Null tails and endpoints may be included in the final piece. Thus the returned intervals form a complete partition, and the linear inequalities certify weak EFM. There are at most $n-1$ cut queries after the initial evaluation. ∎

Proof: Assign items sequentially to a currently minimum-load bundle, and denote final item loads by $\ell_i$. This allocation is EF1. To see this, fix $i,j$ and take the last item $g$ assigned to $j$. Immediately before that assignment, $j$ had minimum load, at most the then load of $i$, which is at most $i$'s final load by nonnegativity. Thus $\ell_j-w_g\leq\ell_i$. Empty compared bundles cause no envy.

For $T>0$, choose the unique level $z>\min_i\ell_i$ satisfying $\sum_i(z-\ell_i)_+=T$, and set $t_i=(z-\ell_i)_+$. For $T=0$ set all masses to zero. Every positive-cake recipient has final value $z$, while every other agent has final value at least $z$. Hence no agent envies a positive-cake recipient. For a zero-cake recipient, the original EF1 deletion witness remains valid because the envying agent's own utility has only increased. This is weak EFM. Realize the masses by the same sequential cuts as in the theorem. ∎