Answer: \(\text{Polynomial-time solvable}\): an EF1 outcome always exists and can be found using polynomially many oracle queries and bit operations in \(m,k,\tau,L\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any instance with arbitrary monotonic utilities, there exists an EF1 outcome. Moreover, such an outcome can be computed in time $O(mn^3)$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) indivisible goods, \(k\) groups with rational quota shares \(\alpha_i\) summing to \(1\), and a finite set \(T\) of complete utility types with rational masses \(\mu_t\) summing to \(1\), find a partition of the goods into bundles \(A_1,\ldots,A_k\) and nonnegative assignment masses \(x_{t,i}\) such that \(\sum_i x_{t,i}=\mu_t\), \(\sum_t x_{t,i}=\alpha_i\), and whenever \(x_{t,i}>0\), for every group \(j\) there is a set \(B\subseteq A_j\) with \(|B|\leq 1\) and \(u_t(A_i)\geq u_t(A_j\setminus B)\). With value-oracle access to the monotone utilities, can such an outcome be found in time polynomial in \(m\), \(k\), \(|T|\), and the input bit length \(L\)?
Let \(M\) contain \(m\) indivisible goods, and let \(k\geq2\) groups have positive binary-rational quota shares \(\alpha_i\), with \(\sum_i\alpha_i=1\).
A society is given by its support: a list \(T\) of \(\tau\) complete utility types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
Each type has an arbitrary monotone utility \(u_t:2^M\to\mathbb{Q}_{\geq0}\), normalized by \(u_t(\varnothing)=0\), accessible through an exact value oracle. Let \(L\) be the explicit input bit length plus a bound on the bit length of each oracle answer.
An outcome consists of a complete partition \((A_1,\ldots,A_k)\) of \(M\), allowing empty bundles, and rational assignment masses \(x_{t,i}\geq0\) satisfying \(\sum_i x_{t,i}=\mu_t\) and \(\sum_t x_{t,i}=\alpha_i\). Each assigned mass receives the full utility of its group's bundle.
The outcome is EF1 if, whenever \(x_{t,i}>0\), for every \(j\) there exists \(B\subseteq A_j\) with \(|B|\leq1\) and \(u_t(A_i)\geq u_t(A_j\setminus B)\). Ties are permitted; \(B\) may depend on \(t,i,j\).
Can an EF1 outcome always be found using polynomially many oracle queries and bit operations in \(m,k,\tau,L\), or is this search problem NP-hard?
For a finite list of \(n\) agents and prescribed positive integer group sizes, an EF1 outcome always exists for arbitrary normalized monotone utilities and can be computed in \(O(mn^3)\) time with unit-cost value queries. [Source](https://paulgoelz.de/papers/variable.pdf)
No result settling the exact support-and-mass search problem above was identified in the literature search.
An EF1 outcome can always be found using polynomially many oracle queries and bit operations in \(m,k,\tau,L\).
The key is to replace individual-agent cycle elimination with an exact transportation LP. For each partial allocation, optimize over the assignment masses that satisfy EF1. An optimum has no directed envy cycle, so there is an unenvied group to which the next good can be added.
This uses the one-good-at-a-time approach of the [finite-agent theorem](https://paulgoelz.de/papers/variable.pdf), but operates directly on the support and rational masses.
We also consider partial allocations: the bundles are pairwise disjoint but need not yet cover \(M\). The mass constraints remain unchanged.
Fix such an allocation \(A=(A_1,\ldots,A_k)\). For each type \(t\) and group \(j\), define
\[ q_{t,j}(A)=\min_{\substack{B\subseteq A_j\\ |B|\leq1}}u_t(A_j\setminus B), \qquad h_t(A)=\max_{j\in[k]}q_{t,j}(A). \]
Here and below, \([k]=\{1,\ldots,k\}\). Define the acceptable pairs by
\[ E(A)=\{(t,i):u_t(A_i)\geq h_t(A)\}. \]
For a feasible mass assignment \(x\), the outcome \((A,x)\) is EF1 if and only if
\[ x_{t,i}>0\ \Longrightarrow\ (t,i)\in E(A). \]
Indeed, for a fixed positive entry \(x_{t,i}\), EF1 requires \(u_t(A_i)\geq q_{t,j}(A)\) for every \(j\), which is equivalent to \(u_t(A_i)\geq h_t(A)\). Each minimum is attained because its domain is finite.
Consequently, acceptability is preserved by moving a type to a more valuable bundle:
\[ (t,i)\in E(A),\quad u_t(A_j)>u_t(A_i) \quad\Longrightarrow\quad (t,j)\in E(A). \]
Define an integer rank for each type and bundle:
\[ r_{t,i}(A)=\bigl|\{j\in[k]:u_t(A_j)<u_t(A_i)\}\bigr|. \]
These ranks belong to \(\{0,\ldots,k-1\}\). They preserve strict utility comparisons: if \(u_t(A_j)>u_t(A_i)\), then \(r_{t,j}(A)>r_{t,i}(A)\). To see this, every bundle strictly below \(A_i\) is also strictly below \(A_j\), and \(A_i\) itself is strictly below \(A_j\).
Consider the following LP:
\[ \max_x\ \sum_{t\in T}\sum_{i=1}^k r_{t,i}(A)x_{t,i}, \]
subject to
\[ \sum_{i=1}^k x_{t,i}=\mu_t\quad(t\in T), \]
\[ \sum_{t\in T}x_{t,i}=\alpha_i\quad(i\in[k]), \]
\[ x_{t,i}\geq0,\qquad x_{t,i}=0\quad\text{whenever }(t,i)\notin E(A). \]
Its feasible points are exactly the EF1 assignments for \(A\). Whenever it is feasible, its feasible region is compact: it is closed, and every coordinate satisfies \(0\leq x_{t,i}\leq\mu_t\leq1\). Thus an optimum exists.
For an assignment \(x\), define its envy graph on the groups. There is an edge \(i\to j\) precisely when some type \(t\) satisfies
\[ x_{t,i}>0,\qquad u_t(A_j)>u_t(A_i). \]
Lemma. Every optimum of the LP has an acyclic envy graph.
Proof. Suppose an optimum \(x\) has a directed simple cycle
\[ i_1\to i_2\to\cdots\to i_\ell\to i_1. \]
Write \(i_{\ell+1}=i_1\). For each edge, choose a witnessing type \(t_s\), so
\[ x_{t_s,i_s}>0,\qquad u_{t_s}(A_{i_{s+1}})>u_{t_s}(A_{i_s}). \]
Let
\[ \delta=\min_{1\leq s\leq\ell}x_{t_s,i_s}>0. \]
For every \(s\), move mass \(\delta\) of type \(t_s\) from group \(i_s\) to group \(i_{s+1}\).
This preserves every type’s total mass. Each group on the cycle loses and receives exactly \(\delta\), so all quotas are preserved. Nonnegativity also holds: the source groups are distinct, hence every source coordinate is decremented at most once, by at most its original value. The witnessing types need not be distinct.
Each destination pair is acceptable, by the upward-closure property proved in Section 1. The modified assignment is therefore LP-feasible.
Its objective increases by
\[ \delta\sum_{s=1}^{\ell} \bigl(r_{t_s,i_{s+1}}(A)-r_{t_s,i_s}(A)\bigr)>0, \]
because every summand is positive. This contradicts optimality. \(\square\)
A finite acyclic directed graph has a vertex with no incoming edge. Otherwise, repeatedly following incoming edges would eventually repeat a vertex and produce a directed cycle.
Lemma. Suppose \((A,x)\) is EF1, and group \(s\) has no incoming edge in its envy graph. Adding an unallocated good \(g\) to \(A_s\), while keeping \(x\) unchanged, preserves EF1.
Proof. Let \(A'\) be the resulting partial allocation. Fix any \(x_{t,i}>0\).
If \(i=s\), monotonicity gives
\[ u_t(A'_s)\geq u_t(A_s). \]
Every comparison with a different group retains its old EF1 witness, since that group’s bundle is unchanged. The comparison with group \(s\) itself holds with \(B=\varnothing\).
Now suppose \(i\ne s\). Comparisons with groups other than \(s\) retain their old witnesses. Since there is no edge \(i\to s\), we have
\[ u_t(A_i)\geq u_t(A_s). \]
Removing the newly added good from the changed bundle gives
\[ u_t(A'_i)=u_t(A_i) \geq u_t(A_s) =u_t(A'_s\setminus\{g\}). \]
Thus \(B=\{g\}\) witnesses EF1 toward group \(s\). This covers every positive assignment entry and every comparison. \(\square\)
Initially, set every bundle to \(\varnothing\) and use
\[ x_{t,i}=\mu_t\alpha_i. \]
This satisfies both marginal constraints, because the masses and quotas each sum to \(1\). It is EF1 because every empty bundle has utility \(0\).
Repeat the following steps until all goods are allocated:
We prove correctness inductively. Before each iteration, the current assignment is EF1, so it is a feasible point of the LP. An optimum therefore exists and remains EF1. Its envy graph is acyclic by Section 2, so Step 3 is possible. Step 4 preserves EF1 by Section 3.
Each iteration allocates one previously unallocated good. After exactly \(m\) iterations, the bundles form a complete partition, the assignment satisfies all prescribed marginals, and the outcome is EF1. When \(m=0\), the initial outcome already suffices.
At a stage with \(r\) allocated goods, query \(u_t(A_j)\) and \(u_t(A_j\setminus\{g\})\) for each type \(t\), group \(j\), and good \(g\in A_j\). These queries determine all thresholds and ranks.
For a nonempty bundle, monotonicity implies that removing no good cannot yield a smaller value than removing a singleton. For an empty bundle, the threshold is \(0\). Hence at most \(\tau(k+r)\) queries suffice at that stage. Summing over the \(m\) iterations gives at most
\[ \tau\left(mk+\frac{m(m-1)}2\right) =O\bigl(\tau m(k+m)\bigr) \]
oracle queries.
All comparisons involve exact rationals of bit length at most \(L\), and therefore require polynomially many bit operations.
Each LP has:
Its explicit encoding length is polynomial in \(\tau,k,L\). We use the standard theorem that rational LPs can be solved exactly in polynomial bit complexity, returning a rational optimum of polynomial encoding length; see, for example, [Vishnoi’s linear-programming notes](https://nisheethvishnoi.wordpress.com/wp-content/uploads/2018/05/lecture71.pdf). The hypotheses hold here: every LP has rational data, is feasible by the invariant, and has a bounded feasible region.
Crucially, each LP uses the original marginals rather than the previous assignment as numerical input. Thus successive iterations do not cause a recurrence of growing coefficient lengths. Graph construction and finding a vertex with no incoming edge also take polynomial time.
There are \(m\) LP solves, so the entire algorithm uses polynomially many oracle queries and bit operations in \(m,k,\tau,L\), and returns rational assignment masses with polynomial encoding length.
⟨structured verdict parsed — rendered above⟩
The output proves the claimed polynomial-time result. The assignment LP, the acyclicity argument, the EF1 preservation lemma, and the complexity analysis are valid. No major or minor mathematical issues were found.
The argument directly addresses the support-and-mass model in USER_TASK: it permits splitting each type’s mass, preserves the exact rational quotas, and runs in polynomial time in \(m,k,\tau,L\).
The definitions of \(q_{t,j}(A)\), \(h_t(A)\), and \(E(A)\) are well-defined, including for empty bundles. The minimum defining \(q_{t,j}(A)\) always has a nonempty finite domain, since removing no good is permitted.
The claimed equivalence is correct. For each positive assignment entry \(x_{t,i}\), the existential EF1 requirement for a particular group \(j\) is equivalent to
\(u_t(A_i)\geq q_{t,j}(A)\), because the minimum is attained. Requiring this for every group is equivalent to
\(u_t(A_i)\geq h_t(A)\).
This respects the task’s quantifiers: the removed good may depend on the type, its assigned group, and the comparison group.
The upward-closure assertion also follows directly from the threshold definition. Ties cause no problem because acceptable pairs use a weak inequality.
The LP imposes exactly the required row and column marginals and excludes precisely the unacceptable pairs. Thus its feasible assignments are exactly the EF1 assignments for the fixed bundles.
The compactness argument is correct: the feasible region is closed, and nonnegativity together with the row constraints bounds every coordinate by \(\mu_t\). Conditional on feasibility, the linear objective attains its maximum.
The ranks correctly preserve every strict utility comparison. Counting the source bundle among the bundles strictly below the destination proves the claimed strict increase, even when other bundles have tied utilities.
The cycle argument is valid.
The objective-change formula correctly sums the effects of all transfers, including any overlapping coordinates. Every rank difference is strictly positive, so the total change is strictly positive. This contradicts optimality.
There are no self-loops because an edge requires a strict utility increase. The stated finite-graph argument therefore correctly guarantees a group with no incoming edge.
Both cases in the lemma are correctly covered.
For mass assigned to the receiving group, monotonicity preserves all comparisons with other groups. Its comparison with itself holds by removing nothing.
For mass assigned elsewhere, absence of an incoming envy edge guarantees
\(u_t(A_i)\geq u_t(A_s)\) for every relevant type. Removing the newly added good restores exactly the old bundle \(A_s\), furnishing a valid EF1 witness. All other comparisons retain their existing witnesses.
The proof uses only monotonicity, with no hidden additivity assumption.
The initial assignment \(x_{t,i}=\mu_t\alpha_i\) has both required marginals and is rational. Empty bundles make it EF1.
The induction establishes feasibility before every LP solve. Optimization preserves EF1; acyclicity supplies a group with no incoming edge; and adding a good preserves EF1 again.
Exactly one unallocated good is assigned per iteration. Consequently, after \(m\) iterations the bundles form a complete partition. The assignment after the final addition already satisfies EF1, so no additional LP solve is needed.
The case \(m=0\) is explicitly handled. Empty bundles, zero utilities, arbitrarily small positive rational masses, and ties introduce no missing cases.
At a stage with \(r\) allocated goods, querying each bundle and every singleton deletion requires at most \(\tau(k+r)\) queries. These values suffice to compute thresholds, ranks, and envy edges.
The stages have \(r=0,\ldots,m-1\), giving the stated bound
\(\tau\bigl(mk+m(m-1)/2\bigr)\). No final-stage queries are required.
The LP has polynomially many variables and constraints, with integer matrix coefficients, bounded integer objective coefficients, and the original rational marginals. Its encoding length is therefore polynomial in \(\tau,k,L\).
The exact rational LP theorem invoked is applicable: each LP is rational, feasible, and bounded. The cited notes explicitly discuss polynomial-time LP optimization and recovery of an exact rational optimum with bounded encoding length. The prover invokes this general theorem, whose application does not require full dimensionality or a unique optimum. [Vishnoi’s notes, page 2](https://nisheethvishnoi.wordpress.com/wp-content/uploads/2018/05/lecture71.pdf).
Using the original marginals in every LP prevents coefficient-length accumulation. Polynomial-length rational optima also permit exact positivity tests when constructing the envy graph. All remaining comparisons and bundle operations require polynomially many bit operations.
No repair or additional clarification is needed. The finite-agent theorem supplies context; the correctness proof for the support-and-mass algorithm stands independently of it.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.