Achieving Proportionality up to the Maximin Item with Indivisible Goods (d4-conf-aaai-2021-0629)

Given rational additive values \(v_t(j)\ge 0\) for five valuation types \(t\in T\), masses \(\mu_t=1/5\), and recurring indivisible good types \(j\in M\) with per-capita supplies \(\rho_j=1/5\), choose masses \(y_{t,B}\ge 0\) for integral bundles \(B\subseteq M\) satisfying \(\sum_B y_{t,B}=\mu_t\) and \(\sum_{t,B\ni j}y_{t,B}=\rho_j\). With \(y(B)=\sum_t y_{t,B}\) and \(\delta_t(y)=\max_{B:y(B)>0}\min_{j\in B}v_t(j)\), find a feasible allocation such that \(v_t(B)+\delta_t(y)\ge\sum_j\rho_jv_t(j)\) for every \(t,B\) with \(y_{t,B}>0\), taking the minimum of an empty bundle as \(0\).

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here \(T\) has \(\tau=5\), \(\mu_t=1/5\), and total society mass is \(1\).
There are \(m\) recurring indivisible good types \(M\), each with per-capita supply \(\rho_j=1/5\), and binary-rational additive values \(v_t(j)\geq0\); write \(v_t(B)=\sum_{j\in B}v_t(j)\). Each recipient receives an integral bundle \(B\subseteq M\), containing at most one copy of each good type; empty bundles are allowed.
An allocation consists of nonnegative rational masses \(y_{t,B}\), represented by their positive entries, satisfying \(\sum_{B\subseteq M}y_{t,B}=\mu_t\) and \(\sum_{t\in T}\sum_{B\ni j}y_{t,B}=\rho_j\). Let \(L\) be the total binary input length.
Define \(y(B)=\sum_{t\in T}y_{t,B}\), \(a_t(\varnothing)=0\), \(a_t(B)=\min_{j\in B}v_t(j)\) for nonempty \(B\), and \(\delta_t(y)=\max_{B:y(B)>0}a_t(B)\). This maximum includes bundles received by positive mass of the same type: excluding an individual recipient changes no mass.
Require \(v_t(B)+\delta_t(y)\geq\sum_{j\in M}\rho_jv_t(j)\) whenever \(y_{t,B}>0\).

Is finding an allocation satisfying these conditions polynomial-time solvable in \(m,\tau,L\), with \(\tau=5\), or is it NP-hard?

For discrete agents, PROPm requires \(v_i(X_i)+\max_{k\ne i}a_i(X_k)\geq v_i(M)/n\). Every five-agent additive instance admits such an allocation ([Baklanov et al., 2021](https://arxiv.org/abs/2009.09508)); later work computes one in polynomial time for arbitrary numbers of agents and goods ([Baklanov et al., IJCAI 2021](https://www.ijcai.org/proceedings/2021/0004.pdf)).
No result treating exactly the mass-allocation formulation above was identified in the literature search.

Polynomial-time solvability

The stated problem is polynomial-time solvable. A discrete PROPm partition produces a feasible mass allocation with exactly five positive entries. The crucial hypotheses are that every type mass and every good supply equal \(1/5\).

1. The discrete theorem used

The algorithm of Baklanov, Garimidi, Gkatzelis, and Schoepflin computes a PROPm allocation for nonnegative additive valuations in polynomial time. Applied to five agents with valuations \(v_t\), it returns a partition \(X_1,\ldots,X_5\) of \(M\) satisfying

\(v_t(X_t)+d_t(X)\geq v_t(M)/5,\qquad d_t(X)=\max_{k\ne t}a_t(X_k).\)

Here empty bundles contribute zero. This is the discrete guarantee stated in the question; its algorithm and running-time analysis appear in [the IJCAI 2021 paper, Sections 5–7](https://www.ijcai.org/proceedings/2021/0004.pdf).

The hypotheses hold: there are five agents, one for each supported type; the goods are the elements of \(M\); and every valuation is nonnegative and additive.

If \(M=\varnothing\), simply set \(y_{t,\varnothing}=1/5\) for every type. All required inequalities then read \(0\geq0\). Henceforth assume \(M\ne\varnothing\). If normalization is needed, an identically zero valuation can first be replaced by the auxiliary valuation assigning value one to every good. The resulting allocation remains valid for the original zero valuation, whose fairness condition is automatic.

2. Constructing and verifying the mass allocation

For the discrete partition, define

\(y_{t,X_t}=1/5\)

for every \(t\), and set all other entries to zero. Thus every recipient of type \(t\) receives the integral bundle \(X_t\).

Type masses. Each type has exactly one positive entry, so

\(\sum_{B\subseteq M}y_{t,B}=1/5=\mu_t.\)

Good supplies. Because the bundles form a partition, each good \(j\) belongs to exactly one \(X_t\). Consequently,

\(\sum_{t\in T}\sum_{B\ni j}y_{t,B}=1/5=\rho_j.\)

This verifies the supply equalities, including their requirement of allocating the entire supply.

Fairness. Every bundle \(X_k\) has positive aggregate mass: indeed, \(y(X_k)\geq y_{k,X_k}=1/5\). Conversely, every bundle with positive aggregate mass equals some \(X_k\). Therefore,

\(\delta_t(y)=\max_{1\leq k\leq5}a_t(X_k)\geq\max_{k\ne t}a_t(X_k)=d_t(X).\)

This calculation remains valid when several agents receive the empty bundle: repeated occurrences do not change a maximum, and \(a_t(\varnothing)=0\).

The only positive entry for type \(t\) is on \(X_t\). Its required inequality follows from

\(v_t(X_t)+\delta_t(y)\geq v_t(X_t)+d_t(X)\geq v_t(M)/5=\sum_{j\in M}\rho_jv_t(j).\)

Thus every constraint in the mass formulation holds. Including the recipient’s own type in the definition of \(\delta_t(y)\) only enlarges the correction term used by the discrete guarantee.

3. Binary complexity and output size

The discrete algorithm performs polynomially many sorting, valuation-sum, comparison, and graph operations. Its numerical operations involve subset-value sums and division by agent counts or normalization totals. These admit exact polynomial-time arithmetic on the present binary-rational input.

To make the bit bound explicit, write \(v_t(j)=p_{tj}/q_{tj}\), with integer numerator and positive integer denominator. For each type let

\(D_t=\prod_{j\in M}q_{tj},\qquad w_t(j)=D_tv_t(j).\)

All \(w_t(j)\) are nonnegative integers. The bit length of \(D_t\) is at most the sum of the denominator bit lengths, hence at most \(L\); each \(w_t(j)\), and each subset sum of these integers, has \(O(L+\log m)\) bits. Positive scaling of an agent’s valuation preserves its PROPm inequalities.

Any normalization on a remaining set \(S\) can be represented directly as

\(w_t(j)\big/\sum_{\ell\in S}w_t(\ell),\)

whenever the denominator is positive. Comparisons of normalized subset values are performed by cross-multiplying these polynomial-length integers. Agent counts never exceed five. Therefore the arithmetic implementation has polynomial bit complexity in \(m\) and \(L\).

The mass-allocation output consists of five entries. Each bundle can be represented by an \(m\)-bit incidence vector, and every positive mass is the fixed rational \(1/5\). No enumeration of all subsets of \(M\) is needed.

4. Scope of the conclusion

This settles the specified equal-mass, equal-supply problem with \(\tau=5\). The construction does not require a general algorithm for arbitrary mass-allocation instances: it suffices that a discrete partition lifts to a valid allocation under these particular masses and supplies.

⟨structured verdict parsed — rendered above⟩

The output resolves the specified problem correctly: it establishes polynomial-time solvability for the five supported types with equal masses and equal supplies. No major or minor mathematical issue was identified.

• The discrete theorem is applicable.

The prover states the needed guarantee precisely: a partition \(X_1,\ldots,X_5\) satisfying
\[ v_t(X_t)+\max_{k\ne t}a_t(X_k)\geq v_t(M)/5 \]
for every type \(t\), computable in polynomial time.

The cited paper establishes polynomial-time computation of PROPm allocations for nonnegative additive valuations: Section 6 provides correctness and Section 7 analyzes the running time. Its normalization and large-item assumptions are presentation reductions, rather than restrictions on the overall result. Thus the prover invokes the general result correctly. [Baklanov et al., IJCAI 2021](https://www.ijcai.org/proceedings/2021/0004.pdf)

All required hypotheses match the input: five agents correspond to the five supported types, the discrete items correspond to the good types, and the valuations are nonnegative and additive. No assumption about the number of possible unsupported types is used.

• The preliminary edge cases are handled correctly.

For \(M=\varnothing\), the five entries \(y_{t,\varnothing}=1/5\) satisfy the type constraints. There are no good constraints, and every fairness inequality is \(0\geq0\).

For a type whose valuation is identically zero, the proposed auxiliary valuation is legitimate when \(M\ne\varnothing\). The original type’s fairness inequality remains automatic for any returned allocation. Other types retain their original valuations and their discrete guarantees. This preprocessing therefore does not invalidate the application.

• The construction satisfies all allocation constraints.

Assigning \(y_{t,X_t}=1/5\), with every other entry zero, gives exactly one positive entry for each type. Hence each type receives its required total mass.

Since the discrete allocation is a partition of \(M\), every good belongs to exactly one assigned bundle. Its allocated mass is consequently exactly \(1/5\), as required by the supply equality.

Every assigned bundle is a subset of \(M\), so recipients receive integral bundles with at most one copy of each good type. All reported masses are nonnegative rationals.

Even if several types receive the empty bundle, their entries remain distinct because entries are indexed by the pair \((t,B)\). Thus the claim of exactly five positive entries is correct.

• The comparison of correction terms is exact.

Each \(X_k\) has positive aggregate mass, and every bundle of positive aggregate mass is some \(X_k\). Consequently,
\[ \delta_t(y)=\max_{1\leq k\leq5}a_t(X_k)\geq d_t(X). \]

Repeated empty bundles do not affect this equality. The convention \(a_t(\varnothing)=0\) also ensures that every term is defined.

The prover correctly includes the bundle assigned to type \(t\) in the continuous maximum. This agrees with the task’s explicit definition and introduces no exclusion-of-an-individual ambiguity.

• The required fairness inequalities follow for every positive entry.

The only positive entry for type \(t\) is on \(X_t\). The displayed chain
\[ v_t(X_t)+\delta_t(y)\geq v_t(X_t)+d_t(X) \geq v_t(M)/5 =\sum_{j\in M}\rho_jv_t(j) \]
is valid. The final equality uses precisely the stipulated equal supplies. Thus the proof checks the required quantifier over all positive entries, without imposing an unnecessary condition on zero entries.

• The binary-complexity and output-size claims are justified.

The denominator product \(D_t\) has bit length bounded by the sum of the input denominator lengths. The scaled integers \(w_t(j)\) and their subset sums therefore have polynomial bit length, with the stated \(O(L+\log m)\) bound valid.

Positive scaling preserves the discrete inequalities, including their minimum and maximum terms. The normalization representation uses subset sums of these integers; exact comparisons by cross-multiplication retain polynomial bit complexity. Combined with the cited algorithm’s polynomial operation count, this establishes polynomial running time on binary-rational inputs.

Five bundle incidence vectors and five fixed masses \(1/5\) constitute a polynomial-size output. No enumeration of all subsets is required.

The conclusion is appropriately restricted to the stipulated equal-mass, equal-supply instance. No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩