Answer: \(\mathrm{P}\) for decision, with polynomial-time construction of a polynomial-size rational allocation.
Theorem 6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIn every setting with partition matroids with binary valuations (possibly het- erogeneous capacities and heterogeneous valuations), an F-EF1 allocation exists and can be computed efficiently by the Iterated Priority Matching Algorithm (Algorithm 5). Two key tools we use are the agent-item graph and the priority matching, defined next. Definition 13 (Agent-item graph). Given a category h and a partial allocation X, the agent-item graph is a bipartite graph Gh, where one side consists of the agents with remain- ing capacity (i.e., agents such that |Xh i | < kh i ), and one side consists of the unallocated items of Ch.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given recurring slot types \(G\) partitioned into categories \(C_h\), rational type masses \(\mu_t\), rational per-capita supplies \(\rho_g\), binary values \(v_t(g)\), and capacities \(k_{t,h}\), find nonnegative masses \(y_{t,B}\) over integral feasible configurations \(B\in\mathcal B_t\) satisfying \(\sum_B y_{t,B}=\mu_t\), \(\sum_{t,B} b_g(B)y_{t,B}=\rho_g\), and, for every positive-mass pair \(t,u\), \(\frac{1}{\mu_t}\sum_B y_{t,B}v_t(B)\ge\frac{1}{\mu_u}\sum_B y_{u,B}e_t(B)\), where \(e_t(B)=\min_{Y\subseteq B,\ |Y|\le1}\max_{S\subseteq B\setminus Y,\ S\in\mathcal B_t}v_t(S)\); decide whether such a complete type-\(\mathrm{F\text{-}EF1}_\infty\) allocation exists and construct it if so.
Let \(G\) be recurring slot types partitioned into categories \(C_h\). Each population type \(t\) has rational mass \(\mu_t>0\), binary per-copy values \(v_t(g)\), and category capacities \(k_{t,h}\). An integral configuration \(B\in\mathcal B_t\) has counts \(b_g(B)\in\mathbb Z_{\ge0}\) with \(\sum_{g\in C_h}b_g(B)\le k_{t,h}\); its value is \(v_t(B)=\sum_g b_g(B)v_t(g)\). Define \(e_t(B)=\min_{Y\subseteq B,\ |Y|\le1}\max_{S\subseteq B\setminus Y,\ S\in\mathcal B_t}v_t(S)\), where \(Y\) removes at most one copy.
Given rational per-capita supplies \(\rho_g\), seek nonnegative masses \(y_{t,B}\) satisfying \(\sum_B y_{t,B}=\mu_t\), \(\sum_{t,B}b_g(B)y_{t,B}=\rho_g\), and, for every \(t,u\), \(\frac{\sum_B y_{t,B}v_t(B)}{\mu_t}\ge\frac{\sum_B y_{u,B}e_t(B)}{\mu_u}\). The equalities require complete allocation; the inequalities define type-\(\mathrm{F\text{-}EF1}_\infty\).
Is deciding whether such an allocation exists, and constructing one when it does, in \(\mathrm P\) or \(\mathrm{NP}\)-hard?
For finite agents with shared categories, heterogeneous capacities, and binary values, a complete feasible \(\mathrm{F\text{-}EF1}\) allocation can be found in polynomial time. Related divisible-goods work establishes envy-free fractional allocations under linear constraints, but does not address masses over integral configurations with the fairness inequalities above.
The problem is in \(\mathrm P\), including construction of an allocation with polynomial support and polynomial encoding length. In fact, the construction satisfies the stronger condition of expected feasible envy-freeness without removing a copy.
Let \(T\) be the set of population types. Capacities are nonnegative integers; if a capacity is given as a nonnegative rational, replace it by its floor, which leaves the integral configuration family unchanged.
Theorem. A requested allocation exists if and only if supplies are nonnegative and, for every category \(h\),
\(\displaystyle \sum_{g\in C_h}\rho_g\le \sum_{t\in T}\mu_t k_{t,h}.\)
When these conditions hold, an allocation can be constructed in polynomial time with at most \(|G|+1\) configurations per population type.
Necessity. Any feasible configuration-mass allocation satisfies
\(\displaystyle \sum_{g\in C_h}\rho_g =\sum_{t\in T}\sum_{B\in\mathcal B_t}y_{t,B}\sum_{g\in C_h}b_g(B) \le\sum_{t\in T}k_{t,h}\sum_{B\in\mathcal B_t}y_{t,B} =\sum_{t\in T}\mu_t k_{t,h}. \)
Nonnegativity of supplies also follows from the supply equalities. We prove sufficiency constructively below.
We first construct nonnegative rational per-capita quantities \(x_{t,g}\) satisfying
\(\displaystyle \sum_t\mu_t x_{t,g}=\rho_g, \qquad \sum_{g\in C_h}x_{t,g}\le k_{t,h}. \)
They will additionally satisfy, for every \(t,u,h\),
\[\displaystyle \sum_{g\in C_h}v_t(g)x_{t,g} \ge \min\!\left\{k_{t,h},\sum_{g\in C_h}v_t(g)x_{u,g}\right\}. \tag{1} \]
Process categories independently. Fix a category \(h\), initially with its full supply unallocated.
All types start at time zero. A type is active while it has remaining category capacity and some positively supplied good in this category that it values at one.
Each active type \(t\) selects any such good and consumes it at aggregate rate \(\mu_t\). Thus every active type consumes at per-capita rate one. A type switches goods when its selected good is exhausted. It stops permanently when either its capacity is reached or all goods it values in this category are exhausted.
This procedure has a finite event implementation. If \(r_g\) denotes residual supply, \(z_t\) denotes the per-capita amount already consumed, and each active type has selected one good, let
\(\displaystyle R_g=\sum_{\substack{t\text{ active}\\t\text{ selected }g}}\mu_t.\)
Advance time by
\(\displaystyle \Delta= \min\!\left( \{k_{t,h}-z_t:t\text{ active}\} \cup \{r_g/R_g:R_g>0\} \right). \)
Every event exhausts a good or fills a type’s capacity. Neither event can be reversed, so there are at most \(|C_h|+|T|\) events.
After consumption stops, assign the remaining supply arbitrarily within the remaining aggregate capacities.
This is possible: consumption decreases total supply and total available capacity by exactly the same amount, so the category feasibility inequality continues to hold. Since every type can receive every good in the category subject only to its category capacity, a greedy assignment suffices.
Furthermore, any type with unused capacity values all remaining goods at zero. Otherwise that type would still be active.
Fix types \(t,u\). Let \(\tau_t\) be the time at which type \(t\) stops consuming.
If \(t\) reaches its capacity, all its consumed goods have value one, so its final own value in this category is \(k_{t,h}\). Inequality (1) follows immediately.
Otherwise, \(t\) stops because every good it values in the category has been exhausted. Until that time, \(t\) has consumed continuously at per-capita rate one. Consequently, its final own value in the category is exactly \(\tau_t\); the completion stage gives it no positively valued goods.
Every good valued by \(t\) that is allocated to \(u\) must have been allocated by time \(\tau_t\). Type \(u\) consumes at per-capita rate at most one, and hence
\(\displaystyle \sum_{g\in C_h}v_t(g)x_{u,g}\le\tau_t =\sum_{g\in C_h}v_t(g)x_{t,g}. \)
This proves (1), including the case where \(t\) has no valued supply initially and \(\tau_t=0\).
Fix a type \(t\) and its fractional bundle \(x_t\). We now construct a distribution over \(\mathcal B_t\) with coordinate expectations \(x_{t,g}\).
Order the goods in each category as \(g_{h,1},\ldots,g_{h,m_h}\), and define prefix sums
\(\displaystyle S_{h,0}=0, \qquad S_{h,j}=\sum_{\ell=1}^{j}x_{t,g_{h,\ell}}. \)
For a parameter \(\theta\in[0,1)\), define an integral configuration by
\[\displaystyle b_{g_{h,j}}(\theta) = \lfloor S_{h,j}+\theta\rfloor - \lfloor S_{h,j-1}+\theta\rfloor. \tag{2} \]
Use the same parameter \(\theta\) for every category.
These counts are nonnegative integers because the prefix sums are nondecreasing. Moreover,
\(\displaystyle \sum_{g\in C_h}b_g(\theta) =\lfloor S_{h,m_h}+\theta\rfloor \le k_{t,h}, \)
where the last inequality uses \(S_{h,m_h}\le k_{t,h}\), integrality of \(k_{t,h}\), and \(\theta<1\). Thus every resulting configuration belongs to \(\mathcal B_t\).
For uniform \(\theta\in[0,1)\), the identity
\(\displaystyle \mathbb E[\lfloor s+\theta\rfloor]=s \qquad(s\ge0)\)
holds: writing \(s=q+r\) with integer \(q\) and \(r\in[0,1)\), the floor equals \(q+1\) on an interval of length \(r\), and equals \(q\) elsewhere. Applying this identity to (2) gives
\[\displaystyle \mathbb E[b_g(\theta)]=x_{t,g}.\tag{3}\]
This distribution has a polynomial-size explicit representation. Its configuration can change only at a point
\(\displaystyle \theta=1-\{S_{h,j}\}\)
for a nonintegral prefix sum, where \(\{s\}=s-\lfloor s\rfloor\). There are at most \(|G|\) such points across all categories. Sort them together with the endpoints \(0,1\). Each consecutive interval contributes its length as probability and its constant configuration, evaluated at the interval’s midpoint.
Consequently, the distribution has at most \(|G|+1\) configurations. All probabilities are rational. Let \(p_{t,B}\) denote the resulting probabilities, merging identical configurations if necessary, and set
\(\displaystyle y_{t,B}=\mu_t p_{t,B}.\)
The population equalities follow from \(\sum_Bp_{t,B}=1\). Equation (3) yields the exact supply equalities:
\(\displaystyle \sum_{t,B}b_g(B)y_{t,B} =\sum_t\mu_t x_{t,g} =\rho_g. \)
For an arbitrary integral multiset \(B\), define its feasible value to type \(t\), without removal, by
\(\displaystyle f_t(B)= \max_{\substack{S\subseteq B\\S\in\mathcal B_t}}v_t(S). \)
Binary values and independent category capacities imply the exact formula
\[\displaystyle f_t(B) = \sum_h \min\!\left\{ k_{t,h}, \sum_{g\in C_h}v_t(g)b_g(B) \right\}. \tag{4} \]
Indeed, in each category an optimal feasible subset takes as many positively valued copies as possible, up to that category’s capacity. Choices in different categories are independent.
Fix \(t,u\), and draw \(B\) from the constructed distribution \(p_{u,\cdot}\). For any nonnegative random variable \(Z\),
\(\displaystyle \mathbb E[\min\{k,Z\}]\le\min\{k,\mathbb E[Z]\},\)
because the random variable inside the expectation is bounded above both by \(k\) and by \(Z\). Therefore, using (4), the marginal identity (3), and then (1),
\(\displaystyle \mathbb E_{B\sim p_u}[f_t(B)] \le \sum_h\min\!\left\{ k_{t,h}, \sum_{g\in C_h}v_t(g)x_{u,g} \right\} \le \sum_h\sum_{g\in C_h}v_t(g)x_{t,g}. \)
Linearity of the own valuation gives
\(\displaystyle \sum_h\sum_{g\in C_h}v_t(g)x_{t,g} = \mathbb E_{B\sim p_t}[v_t(B)]. \)
Finally, \(e_t(B)\le f_t(B)\), since removing no copy is permitted in the minimization defining \(e_t\). Hence
\(\displaystyle \frac{\sum_B y_{t,B}v_t(B)}{\mu_t} \ge \frac{\sum_B y_{u,B}f_t(B)}{\mu_u} \ge \frac{\sum_B y_{u,B}e_t(B)}{\mu_u}. \)
These are the required inequalities. The first inequality proves the stated stronger fairness guarantee.
The category feasibility conditions can be checked using exact rational arithmetic.
The consumption procedure uses at most \(|C_h|+|T|\) events per category. Greedy completion also uses at most \(|C_h|+|T|\) assignments: each assignment exhausts a residual good or fills a residual type capacity. These counts are independent of the numerical magnitudes of capacities and supplies.
For completeness, rational arithmetic also has polynomial bit complexity. Choose a common denominator \(Q\) of all masses and supplies, and write
\(\displaystyle a_t=Q\mu_t,\qquad c_g=Q\rho_g.\)
The integers \(Q,a_t,c_g\) have polynomial encoding length; choosing the product of input denominators suffices.
Measure residual aggregate supplies in these scaled units. During consumption, a good’s positive aggregate rate is an integer of the form \(\sum_{t\in A}a_t\). At each event, a common denominator of all evolving quantities need only be multiplied by such a rate; a capacity event requires no additional factor. During greedy completion, it need only be multiplied by an \(a_t\). There are polynomially many events, and every factor has polynomial bit length. Thus a common denominator throughout has polynomial bit length. Quantities remain bounded by the supplied amounts and capacities, so their numerators also have polynomial bit length.
The decomposition requires only rational prefix sums, floors, sorting at most \(|G|\) breakpoints per type, and evaluating the resulting configurations. Large counts are written in binary; individual copies are never enumerated.
The algorithm therefore outputs at most \(|T|(|G|+1)\) nonzero configuration masses, with total encoding length and running time polynomial in the input size. This completes both the decision and construction proofs.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes the stated feasibility criterion, polynomial-time construction, and the stronger expected feasible envy-freeness guarantee. I found no major or minor issues requiring correction.
Summing the supply equalities within a category and applying each configuration’s capacity constraint gives exactly
\(\sum_{g\in C_h}\rho_g\le\sum_t\mu_t k_{t,h}\).
Nonnegative supplies are necessary because all configuration counts and masses are nonnegative. Both arguments are valid.
The stated flooring convention for nonnegative rational capacities preserves the integral configuration family: an integer category count is at most a rational capacity precisely when it is at most its floor.
An active type has positive remaining capacity and selects a good with positive residual supply. Thus every candidate event time is positive, and every selected good has positive aggregate consumption rate because \(\mu_t>0\).
The specified minimum prevents either exceeding a capacity or making a residual supply negative. Each event exhausts at least one previously unexhausted good or fills at least one previously unfilled type capacity. Exhaustion and capacity saturation are permanent. Consequently, the bound of \(|C_h|+|T|\) events is valid, including simultaneous events.
A type that has stopped cannot become active again: capacities do not increase, and residual supplies only decrease. This also justifies the continuous-consumption property used later.
During consumption, aggregate supply and aggregate remaining capacity decrease by the same quantity. Hence the initial category feasibility inequality guarantees sufficient aggregate capacity for completion.
There are no additional restrictions on which goods a type may receive within the category. The asserted greedy completion is therefore valid. An assignment can exhaust a residual good or fill a residual type capacity, giving the stated polynomial assignment bound.
Any type with unused capacity at termination values every residual good at zero; otherwise it would still be active. Thus completion does not increase that type’s own valued quantity. Types already at capacity receive no completion goods.
If type \(t\) reaches capacity, its own value is \(k_{t,h}\), since all consumption-stage goods it receives have value one. This dominates the right-hand side of inequality (1).
Otherwise, type \(t\) consumes continuously at per-capita rate one until \(\tau_t\), when all goods it values are exhausted. Its final own value is therefore \(\tau_t\).
Every positively valued copy for \(t\) received by \(u\) was allocated during consumption by that time. Since \(u\)’s total per-capita consumption rate is at most one, its quantity valued by \(t\) is at most \(\tau_t\). This establishes (1) with the correct per-capita normalization, despite heterogeneous population masses.
Zero capacity is covered by the capacity case. No initially valued supply is covered by \(\tau_t=0\).
Formula (2) gives nonnegative integers by monotonicity of prefix sums. Within each category, the counts telescope to
\(\lfloor S_{h,m_h}+\theta\rfloor\), because \(\lfloor\theta\rfloor=0\). This is at most the integer capacity for every \(\theta\in[0,1)\).
The floor-expectation identity is correctly calculated, including integral prefix sums. It yields the required coordinate expectations.
Each nonintegral prefix sum produces at most one breakpoint, so there are at most \(|G|\) breakpoints and \(|G|+1\) intervals. Using a common parameter across categories preserves all marginal expectations and category constraints; independence is unnecessary.
Midpoint evaluation correctly represents each interval’s constant configuration. Breakpoint values have probability zero and do not affect expectations. Interval lengths sum to one, and multiplying them by \(\mu_t\) gives the population and supply equalities exactly.
Formula (4) correctly describes the maximum feasible value of any integral multiset, even when that multiset is feasible for a different type. Binary values and independent category constraints are exactly the hypotheses needed.
The expectation inequality is valid: the truncated random variable is bounded above by both the capacity and the original random variable. Applying it categorywise, then using the marginal identities and (1), gives
\(\mathbb E_{p_u}[f_t(B)]\le\mathbb E_{p_t}[v_t(B)]\).
Allowing the empty removal in the definition of \(e_t\) gives \(e_t(B)\le f_t(B)\). Substituting \(y_{t,B}=\mu_t p_{t,B}\) therefore yields precisely the requested fairness inequalities for every ordered pair \(t,u\), including \(t=u\).
The product of input denominators has polynomial bit length. After scaling, aggregate consumption rates are sums of integer masses with polynomial bit length.
At a supply-exhaustion event, dividing by such a rate requires only the stated denominator factor. Capacity events introduce no additional denominator factor. Greedy completion requires at most division by a scaled positive mass.
There are polynomially many such operations, so accumulated denominator bit lengths remain polynomial. The evolving quantities are bounded by input supplies, capacities, and their scaled counterparts, which also gives polynomial numerator bit lengths.
Prefix sums, floors, rational comparisons, sorting, and configuration evaluation consequently have polynomial bit complexity. Binary count representation avoids enumeration proportional to capacity magnitudes. The claimed total support bound follows.
No additional clarification or repair is needed.
⟨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.