Approximation Algorithm for Computing Budget-Feasible EF1 Allocations (aamas23-00027)

Given rational type masses \(\mu_b\) with \(\sum_b\mu_b=1\), budgets \(B_b\), item classes \(g\in[r]\) with sizes \(s_g\), values \(v_g\), and per-capita copy supplies \(q_g\), find masses \(x_{b,k}\ge0\) over integral bundles \(k\in\mathbb Z_{\ge0}^r\) satisfying \(\sum_kx_{b,k}=\mu_b\) and \(\sum_{b,k}k_gx_{b,k}\le q_g\), such that every positive-mass type-bundle pair satisfies budget-aware \(1/2\)-EF1 against every occupied bundle and every admissible subbundle of the residual charity stock: for each comparison subbundle \(u\) with \(s(u)\le B_b\), some item copy \(e\in u\) obeys \(v(k)\ge\frac12v(u-e)\).

A society is given by its support: the list of \(\tau\ge1\) types with positive masses \(\mu_b\), each a binary rational, with \(\sum_b\mu_b=1\). Here \(\tau\) is the support size, not the number of possible types; type \(b\) has budget \(B_b>0\).
There are \(m=r\ge1\) item classes, with sizes \(s_g>0\), common additive values \(v_g\ge0\), and per-capita supplies \(q_g\ge0\). All numerical inputs are binary rationals; \(L\) is their total encoding length.
For an integral bundle \(k\in\mathbb Z_{\ge0}^{m}\), write \(s(k)=\sum_gs_gk_g\) and \(v(k)=\sum_gv_gk_g\). An allocation consists of finitely supported rational masses \(x_{b,k}\ge0\), with \(x_{b,k}>0\) only when \(s(k)\le B_b\), satisfying \(\sum_kx_{b,k}=\mu_b\) and \(\sum_{b,k}k_gx_{b,k}\le q_g\).
The charity receives the residual stock \(c_g=q_g-\sum_{b,k}k_gx_{b,k}\). Its admissible subbundles are integral vectors \(u\in\mathbb Z_{\ge0}^{m}\) with \(u\le c\) componentwise.
The allocation is budget-aware \(\tfrac12\)-EF1 if, for every \(x_{b,k}>0\) and every nonzero integral \(u\) with \(s(u)\le B_b\) that satisfies either \(u\le h\) for some occupied bundle \(h\), or \(u\le c\), there is a class \(g\) with \(u_g>0\) such that \(v(k)\ge\tfrac12\bigl(v(u)-v_g\bigr)\). Empty comparison bundles impose no condition; the charity has no fairness obligations.
Find such an allocation, or determine that none exists.

Can this continuous allocation problem, retaining the \(\tfrac12\)-EF1 guarantee, be solved in time polynomial in \(m,\tau,L\), or is it NP-hard?

For explicitly listed finite agents and item copies with identical additive valuations and heterogeneous budgets, a budget-feasible \(\tfrac12\)-EF1 allocation can be computed in polynomial time, including comparisons with charity ([Gan, Li and Wu](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p170.pdf)).
No result settling exactly the support-encoded continuous model above was located.

Result

The problem is polynomial-time solvable. Every instance admits a budget-aware \(\tfrac12\)-EF1 allocation with exactly one occupied bundle per type.

The construction uses the integer inventory \(n_g=\lfloor q_g\rfloor\). Every type independently chooses a density-greedy bundle from this same inventory. Because the type masses sum to one, these choices respect aggregate supply.

If every \(q_g<1\), the empty allocation already satisfies the stated charity rule. The proof below handles arbitrary supplies and heterogeneous budgets.

1. A universal greedy lemma

Fix an integer inventory \(n\in\mathbb Z_{\ge0}^{m}\) and a budget \(B>0\). Order the classes by nonincreasing density:

\(\rho_1\ge\rho_2\ge\cdots\ge\rho_m,\qquad \rho_g=v_g/s_g.\)

Ties may be broken arbitrarily. Starting with remaining budget \(R_0=B\), construct \(k\) by

\(k_g=\min\{n_g,\lfloor R_{g-1}/s_g\rfloor\},\qquad R_g=R_{g-1}-s_gk_g,\quad g=1,\ldots,m.\)

Thus \(k\le n\) and \(s(k)\le B\).

Lemma. For every nonzero integral \(u\le n\) with \(s(u)\le B\), there is a class \(g\) with \(u_g>0\) such that

\(v(u)-v_g\le 2v(k).\)

Proof. First consider any class \(g\) for which \(k_g<n_g\). At its processing step, the budget bound determined its chosen count, so

\(k_g=\lfloor R_{g-1}/s_g\rfloor,\qquad 0\le R_g<s_g.\)

Let \(p^{(g)}\) be the selected prefix: its coordinates are \(k_j\) for \(j\le g\), and zero otherwise. Then

\(s(p^{(g)})=B-R_g>B-s_g.\)

Every class in this prefix has density at least \(\rho_g\). Since values are nonnegative and \(p^{(g)}\le k\), it follows that

\(v(k)\ge v(p^{(g)})\ge \rho_gs(p^{(g)})\ge \rho_g(B-s_g).\qquad (1)\)

The last inequality remains valid when \(\rho_g=0\).

Now fix the comparison bundle \(u\). Define its overlap with \(k\) and its remaining part by

\(a_j=\min\{u_j,k_j\},\qquad d_j=u_j-a_j.\)

These vectors satisfy

\(u=a+d,\qquad a\le k,\qquad d\le n-k,\qquad s(d)\le s(u)\le B.\)

There are two cases.

• If \(d=0\), then \(u\le k\). For any class \(g\) with \(u_g>0\), nonnegative values give \(v(u)-v_g\le v(u)\le v(k)\le 2v(k)\).

• If \(d\ne0\), choose a class \(g\) of maximum density among those with \(d_g>0\). Because \(d\le n-k\), we have \(k_g<n_g\), so (1) applies. Write \(e_g\) for the vector containing one item of class \(g\). Every item in \(d-e_g\) has density at most \(\rho_g\); therefore

\(v(d-e_g)\le \rho_gs(d-e_g)\le \rho_g(B-s_g)\le v(k).\)

Also, \(a\le k\) implies \(v(a)\le v(k)\). Consequently,

\(v(u)-v_g=v(a)+v(d-e_g)\le 2v(k).\)

The chosen class satisfies \(u_g\ge d_g>0\), as required.

This proves the lemma. \(\square\)

2. Construction of the allocation

Set

\(n_g=\lfloor q_g\rfloor\quad\text{for every class }g.\)

Sort classes by density once. For each type \(b\), run the greedy construction from Section 1 with inventory \(n\) and budget \(B_b\), obtaining \(k^{(b)}\).

Define the allocation by

\(x_{b,k^{(b)}}=\mu_b,\)

with all other masses zero.

These masses are rational and give every type its required total mass. The greedy construction guarantees \(s(k^{(b)})\le B_b\).

For each class \(g\), its aggregate consumption satisfies

\(\sum_b\mu_bk^{(b)}_g\le \sum_b\mu_bn_g=n_g\le q_g,\)

where the equality uses \(\sum_b\mu_b=1\). Hence the allocation respects supply, and its charity residual \(c\) is nonnegative.

3. Verification of all fairness comparisons

Fix any type \(b\), whose occupied bundle is \(k^{(b)}\), and any nonzero integral comparison bundle \(u\) with \(s(u)\le B_b\).

If \(u\le h\) for an occupied bundle \(h\), then \(h=k^{(b')}\le n\) for some type \(b'\). Thus \(u\le n\).

If instead \(u\le c\), then \(c\le q\). Since \(u\) is integral, each coordinate satisfies

\(u_g\le\lfloor q_g\rfloor=n_g.\)

Thus, in either permitted comparison, \(u\le n\). Applying the universal greedy lemma with budget \(B_b\) gives a class \(g\) with \(u_g>0\) for which

\(v(k^{(b)})\ge\tfrac12\bigl(v(u)-v_g\bigr).\)

This is precisely the required budget-aware \(\tfrac12\)-EF1 condition. It covers every occupied bundle and every admissible charity subbundle.

4. Polynomial running time and output size

The algorithm performs one density sort and then one pass through the classes for each type: \(O(m\log m+\tau m)\) arithmetic operations.

These operations have polynomial bit complexity. To see this explicitly, let \(D\) be the product of the denominators occurring in the sizes and budgets, and set

\(S_g=Ds_g,\qquad C_b=DB_b.\)

These are positive integers with \(O(L)\)-bit encodings. The greedy pass can maintain an integer remainder \(T\), initially \(C_b\), and compute

\(k^{(b)}_g=\min\{n_g,\lfloor T/S_g\rfloor\},\qquad T\leftarrow T-S_gk^{(b)}_g.\)

Throughout the pass, \(0\le T\le C_b\). Each chosen count also satisfies \(k^{(b)}_g\le\lfloor B_b/s_g\rfloor\), so it has \(O(L)\) bits. Density comparisons use exact rational cross multiplication, likewise with polynomial bit complexity.

The output contains \(\tau\) type–bundle pairs, with their original masses \(\mu_b\), and has polynomial encoding length. No item copies or replicated agents need to be enumerated.

Therefore the stated search problem is solvable in time polynomial in \(m,\tau,L\); under its hypotheses, the “none exists” outcome never occurs.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The construction satisfies the exact support-encoded model, and the argument establishes polynomial running time. No mathematical gaps or false statements were found.

• Greedy feasibility. Each remaining budget stays nonnegative because the chosen count is at most \(\lfloor R_{g-1}/s_g\rfloor\). The inventory bound is enforced by the minimum with \(n_g\). Thus \(k\le n\) and \(s(k)\le B\), including when some inventory coordinates are zero.

• The prefix bound. Whenever \(k_g<n_g\), the inventory cap did not determine the count. Hence \(k_g=\lfloor R_{g-1}/s_g\rfloor\), giving \(0\le R_g<s_g\) and \(s(p^{(g)})=B-R_g>B-s_g\). Every selected prefix item has density at least \(\rho_g\). Nonnegative values justify \(v(k)\ge v(p^{(g)})\), and nonnegative density justifies the final weak inequality in (1). The case \(\rho_g=0\) is covered.

• The overlap decomposition. The definitions give nonnegative integral vectors \(a,d\) with \(u=a+d\), \(a\le k\), and \(d\le n-k\). In particular, when \(u_j>k_j\), the bound follows from \(d_j=u_j-k_j\le n_j-k_j\); otherwise \(d_j=0\). Nonnegative sizes imply \(s(d)\le s(u)\le B\).

• Both cases of the universal lemma.

• If \(d=0\), then \(u\le k\), and nonnegative values give the asserted inequality for any class present in \(u\).
• If \(d\ne0\), the maximum-density class \(g\) exists. Since \(d_g>0\), the vector \(d-e_g\) is nonnegative and \(k_g<n_g\), so (1) applies. All remaining items in \(d-e_g\) have density at most \(\rho_g\), and \(s(d-e_g)\le B-s_g\). Consequently the displayed bound on \(v(d-e_g)\) is valid. Adding \(v(a)\le v(k)\) proves the lemma, with \(u_g>0\) as required.

This checks the central argument without requiring any external theorem.

• Allocation constraints. Assigning mass \(\mu_b\) to \(k^{(b)}\) gives a finitely supported rational allocation with the correct mass for every type and a budget-feasible occupied bundle. The supply calculation is correct: every type’s coordinate is bounded by the same \(n_g\), and the masses sum to one. Thus aggregate consumption is at most \(n_g\le q_g\).

• All required fairness comparisons. Every occupied bundle lies below \(n\). Every integral charity subbundle also lies below \(n\), because \(u_g\le c_g\le q_g\) implies \(u_g\le\lfloor q_g\rfloor\). The lemma therefore applies to every permitted comparison using the comparing type’s own budget. Its conclusion supplies exactly the class required by the task. Empty comparisons impose no condition.

The preliminary statement about an “empty allocation” is consistent with the later construction: when every \(q_g<1\), all types receive the zero bundle with their prescribed masses. No nonzero integral charity subbundle then exists.

• Polynomial bit complexity and output size. The product of the size and budget denominators has bit length bounded by their total encoding length. The scaled sizes and budgets consequently have \(O(L)\)-bit encodings. The integer remainder stays between zero and the scaled budget; counts, inventory floors, and intermediate products also have polynomial bit length. Exact density comparisons use rational cross multiplication on polynomial-length integers. The stated sort and greedy passes therefore take polynomial bit time. Writing one bundle vector and its original mass per type also requires polynomial output length.

The proof resolves existence and computation for every allowed instance. No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩