Approximation Algorithm for Computing Budget-Feasible EF1 Allocations

I think there is a good, qualified positive case. The right mirror is not “fractional goods for a few agents”; it is a high-multiplicity market with many exchangeable agents, repeated indivisible project copies, and type-level allocation masses.

My lead anchor is Theorem 4.4, proved in this paper: Algorithm 1 computes a \(1/2\)-EF1 allocation in polynomial time for arbitrary heterogeneous budgets.

Call the mirror \(\mathrm{Budget\text{-}EF1}_{\infty}\). An instance has finitely many complete agent types \(b\in[\tau]\), where type \(b\) has budget \(B_b\) and population mass \(\mu_b\), with \(\sum_b\mu_b=1\). Since the paper assumes common item values, the budget is the only agent attribute; if agents had different valuations, those valuations would have to be included in the type.

There are finitely many repeated item classes \(g\in[r]\). Every copy of class \(g\) has size \(s_g\) and value \(v_g\), and \(q_g\) copies are available per unit population. A bundle is an integer vector \(k\in\mathbb Z_{\ge 0}^r\), with size and value

\[ s(k)=\sum_g s_g k_g, \qquad v(k)=\sum_g v_g k_g. \]

The decision variable is \(x_{b,k}\), the mass of type-\(b\) agents receiving the whole indivisible bundle \(k\). It must satisfy

\[ \sum_k x_{b,k}=\mu_b \]

for every \(b\), and

\[ \sum_{b,k} k_g x_{b,k}\le q_g \]

for every item class \(g\). The residual item supply is assigned to the charity.

The allocation is support-wise \(\alpha\)-EF1 if, for every occupied bundle \(k\), every other occupied bundle \(\ell\) or the charity bundle, every subbundle \(u\) of \(\ell\) satisfying \(s(u)\le B_b\), and some item copy \(e\) in \(u\),

\[ v(k)\ge \alpha\,v(u-e). \]

For Theorem 4.4, the requested solution is an \(x\) satisfying this condition with \(\alpha=1/2\). There is no welfare objective in the theorem itself: the computational task is to construct such an allocation. A natural optimization variant would maximize \(\alpha\).

This preserves the paper’s semantics. An individual agent still receives an integral bundle of indivisible items; EF1 still means removing one item, not removing an arbitrary fraction of a bundle. Only the number of interchangeable agents receiving each bundle is continuous.

The regime is plausible in the paper’s own contractor–project story: a very large pool of subcontractors has only a few standardized capacity classes, while the platform handles a repeated catalogue of project types. The number of agents is large compared with \(\tau\) and \(r\), and supplies scale proportionally with population. Fixed item supply would indeed make almost every agent empty and make charity comparisons degenerate, so supply scaling is essential.

There is also an exact finite bridge. If all masses and supply rates are rational, clearing denominators gives \(N\mu_b\) identical agents of type \(b\) and \(Nq_g\) copies of item class \(g\). A rational solution \(x\) becomes an allocation of whole bundles to integer numbers of agents. Conversely, any such repeated finite instance aggregates to \(x\). Thus this is an extension of a genuine high-multiplicity subclass of the paper, not merely a fractional relaxation.

I would expect the general mirror to be Class A in a finite-catalogue or bounded-configuration regime. The paper’s density ordering, virtual budgets, and feasible-configuration invariant are anonymous: they do not fundamentally depend on the names of agents. In the mass formulation, virtual-budget levels can be attached to budget types and bundle masses, while feasible configurations become capacity-compatible multisets of bundles. A configuration LP or a greedy mass process is therefore a credible route.

The important qualification is that Theorem 4.4 only proves polynomial time in the explicit numbers of agents and items. It does not prove polynomial time in \(\tau\), \(r\), and the binary encodings of huge multiplicities. The compressed problem may require a pricing or configuration oracle, and unrestricted item classes could introduce continuum-specific hardness. That is a worthwhile boundary question rather than a reason to reject the mirror.

A particularly strong special-case anchor is Theorem 5.1, also proved here: Algorithm 3 computes an exact EF1 allocation in polynomial time when all agents have the same budget.

Its mirror, \(\mathrm{Uniform\text{-}EF1}_{\infty}\), is the restriction of the preceding problem to one agent type, \(\mu_1=1\), with common budget \(B\). The instance has repeated indivisible item classes and per-capita supplies \(q_g\). The solution is a bundle-mass distribution \(x_k\) satisfying

\[ \sum_k x_k=1, \qquad \sum_k k_gx_k\le q_g, \]

such that every occupied agent bundle is EF1 toward every other occupied bundle and toward the charity, with the exact predicate

\[ v(k)\ge v(u-e) \]

for an appropriate item \(e\) in every budget-feasible comparison subbundle \(u\).

This is my strongest mirror. The paper itself identifies identical budgets as a natural special case, and the continuous regime has a clear interpretation: a large cohort of interchangeable contractors with the same capacity, handling many repeated projects. The density-greedy early-termination idea in Algorithm 3 has an obvious mass analogue: process item classes in non-increasing density order and continuously assign available copies to currently least-valued bundle masses until the budget or supply boundary is reached.

I would expect this special case to be Class A, at least when the item catalogue is fixed or admits efficient batching. The paper’s Lemma 4.7 and Theorem 5.1 proof are especially well suited to a support-wise mass formulation: they compare densities and capacities, not individual identities. The open issue is whether the greedy process can always be represented and implemented in time polynomial in \(r\) and the binary encoding length of the supplies, rather than in the total number of repeated item copies.

The third, narrower anchor is Theorem 4.9, proved here: if every item satisfies \(s_j\le B_i/\kappa\), Algorithm 1 computes a \((1-1/\kappa)\)-EF1 allocation in polynomial time.

The corresponding problem, \(\mathrm{Large\text{-}Budget\text{-}EF1}_{\infty}\), uses the same population and supply model but imposes

\[ s_g\le \frac{B_b}{\kappa} \]

for every item class \(g\) and every agent type \(b\). It asks for a mass allocation satisfying support-wise \((1-1/\kappa)\)-EF1. The asymptotic question is whether, as \(\kappa\to\infty\), one obtains an exact EF1 limit or a stronger limiting fairness notion under suitable value-density bounds.

This is useful because it supplies the natural nondegenerate scaling regime: many agents, many small project units, and per-agent capacity large relative to any individual item. It should be Class A if the mass version of Algorithm 1 can be batched. I would not claim that Theorem 4.9 automatically proves a continuous theorem; it supplies the structural reason to expect one.

I would not use Theorem 5.2 as an anchor: two agents are not a high-multiplicity population regime. Nor would I claim an NP-hardness mirror. The paper mentions the NP-completeness of knapsack in related work, but it contains no numbered in-paper hardness theorem for its own fair-allocation problem.

The weakest point is unavoidable: the mirror needs proportional scaling of the item supply and repeated item classes. With a fixed finite set of labelled goods and an atomless population, almost everyone receives nothing, so the model collapses. Repeated goods and bundle-mass variables therefore make this an extension rather than a literal population-only limit of every labelled-item instance.

But that extension is recognizable and faithful to the computational core. It preserves the budget constraint, integral bundles, charity, density ordering, feasible configurations, and the one-item EF1 predicate. The rational-clone bridge is explicit. The honest claim is therefore narrow: the paper supports a serious continuous high-multiplicity programme for repeated-project markets, with Theorem 4.4 as the general \(1/2\)-EF1 anchor and Theorem 5.1 as the strongest exact anchor.