Almost Envy-Free Allocation of Indivisible Goods: A Tale of Two Valuations (d4-conf-wine-2024-0029)

Given finitely many complete types \(T\) with masses \(\mu_t\ge0\), \(\sum_t\mu_t=1\), good classes \(G\) with per-capita supplies \(\sigma_g\), and restricted-additive values \(a_{t,g}\in\{0,w_g\}\), choose masses \(x_{t,\mathbf b}\ge0\) over integral configurations \(\mathbf b\in\mathbb Z_{\ge0}^{G}\) satisfying \(\sum_{\mathbf b}x_{t,\mathbf b}=\mu_t\) and \(\sum_{t,\mathbf b}b_gx_{t,\mathbf b}=\sigma_g\). Minimize \(\lambda\), where \(v_t(\mathbf b)=\sum_hb_ha_{t,h}\), subject to \(x_{t,\mathbf b}>0\) and \(x_{u,\mathbf b'}>0\) implying \(v_t(\mathbf b'-\mathbf e_g)\le\lambda v_t(\mathbf b)\) for every \(g\) with \(b'_g>0\); decide whether \(\lambda\le\sqrt{2}\), equivalently whether a \(\frac{\sqrt{2}}{2}\)-EFX allocation exists.

A society is given by its support: the list of \(\tau\) complete valuation types \(t\in T\) with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m=|G|\ge1\) good classes, with nonnegative binary-rational per-capita supplies \(\sigma_g\) and weights \(w_g\). Each type specifies \(a_{t,g}\in\{0,w_g\}\) for every class. Let \(L\) be the total input bit length.
Configurations are \(\mathbf b\in\mathbb Z_{\ge0}^{G}\), including the empty configuration, with \(v_t(\mathbf b)=\sum_g b_ga_{t,g}\). A complete allocation is a nonnegative real array \(x_{t,\mathbf b}\) satisfying \(\sum_{\mathbf b}x_{t,\mathbf b}=\mu_t\) and \(\sum_{t,\mathbf b}b_gx_{t,\mathbf b}=\sigma_g\) for every \(g\); its support need not be finite.
It is \(\frac{\sqrt2}{2}\)-EFX if, for every two occupied type–configuration pairs \((t,\mathbf b),(u,\mathbf b')\), including pairs with \(t=u\), and every \(g\) with \(b'_g>0\), one has \(v_t(\mathbf b'-\mathbf e_g)\le\sqrt2\,v_t(\mathbf b)\), where \(\mathbf e_g\) is the unit vector. Removal is required even when \(a_{t,g}=0\); equality is allowed.

Is deciding whether a complete \(\frac{\sqrt2}{2}\)-EFX allocation exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finite agents and individually listed goods with restricted-additive valuations, an algorithm guarantees a complete \(\frac{\sqrt2}{2}\)-EFX allocation; the theorem does not establish a polynomial running time ([Kaviani, Seddighin, and Shahrezaei](https://arxiv.org/html/2407.05139v2#S6)).
No result settling this exact mass-and-integral-configuration problem was located in the literature search.

Result

The decision problem is polynomial-time solvable. Every valid input admits a complete \(\frac{\sqrt{2}}{2}\)-EFX allocation.

The finite-agent existence theorem suffices: rational masses and supplies can be represented exactly by a finite population and finitely many individually labeled goods. This representation may be exponentially large, but it is used only to prove existence.

1. The finite theorem has the required EFX convention

The theorem of Kaviani, Seddighin, and Shahrezaei guarantees that every finite restricted-additive instance admits a complete allocation \((X_i)_{i\in A}\) satisfying, for distinct agents \(i,j\) and every item \(h\in X_j\),

\(\displaystyle V_i(X_j\setminus\{h\})\le \sqrt{2}\,V_i(X_i).\)

Their definition quantifies over all items in the compared bundle, without requiring positive value to the comparing agent. Their restricted-additive valuations are nonnegative. Thus the theorem uses exactly the removal convention required here. See [Definition 2.1 and the EFX definition in Section 2](https://arxiv.org/html/2407.05139v2#S2), and [Theorem 6.1 and its completeness step](https://arxiv.org/html/2407.05139v2#S6).

For \(i=j\), the same inequality follows directly from nonnegativity:

\(\displaystyle V_i(X_i\setminus\{h\})\le V_i(X_i)\le\sqrt{2}\,V_i(X_i).\)

We now verify all hypotheses and transfer the resulting allocation.

2. Clearing denominators gives a finite instance

Choose a positive integer \(Q\) divisible by every denominator appearing in the masses \(\mu_t\) and supplies \(\sigma_g\). Define

\(\displaystyle n_t=Q\mu_t,\qquad k_g=Q\sigma_g.\)

Each \(n_t\) is a positive integer, each \(k_g\) is a nonnegative integer, and

\(\displaystyle \sum_{t\in T}n_t=Q\sum_{t\in T}\mu_t=Q.\)

Construct a finite instance with:

• \(n_t\) distinct agents of type \(t\), for every \(t\in T\);
• \(k_g\) distinct labeled items of class \(g\), for every \(g\in G\).

Write \(t(i)\) for agent \(i\)'s type. Assign that agent additive valuation

\(\displaystyle V_i(S)=\sum_{h\in S}a_{t(i),\,g(h)},\)

where \(g(h)\) is item \(h\)'s class. Every item of class \(g\) has value either \(0\) or \(w_g\) to every agent. Consequently these valuations are nonnegative and restricted additive, as required by the finite theorem.

If there are no items, assigning the empty configuration to every type immediately satisfies the task. Otherwise, apply the theorem to obtain a complete \(\frac{\sqrt{2}}{2}\)-EFX allocation \((X_i)_{i\in A}\).

3. Aggregation preserves the masses and supplies

For each agent \(i\), define its integral configuration by

\(\displaystyle b(i)_g=\bigl|\{h\in X_i:g(h)=g\}\bigr|.\)

Thus \(V_i(X_i)=v_{t(i)}(\mathbf b(i))\).

Define the allocation array

\(\displaystyle x_{t,\mathbf b}=\frac{1}{Q}\bigl|\{i\in A:t(i)=t,\ \mathbf b(i)=\mathbf b\}\bigr|.\)

This is nonnegative and has finite support. For every type \(t\),

\(\displaystyle \sum_{\mathbf b}x_{t,\mathbf b}=\frac{n_t}{Q}=\mu_t.\)

For every class \(g\), completeness of the finite allocation gives

\(\displaystyle \sum_{t,\mathbf b}b_gx_{t,\mathbf b}=\frac{1}{Q}\sum_{i\in A}b(i)_g=\frac{k_g}{Q}=\sigma_g.\)

Hence \(x\) is complete and has exactly the prescribed type masses and supplies.

4. Aggregation preserves every required EFX comparison

Take any two occupied pairs \((t,\mathbf b)\) and \((u,\mathbf b')\), and any class \(g\) with \(b'_g>0\).

If the pairs are different, their positive masses ensure that there are distinct agents \(i,j\) satisfying

\(\displaystyle t(i)=t,\quad \mathbf b(i)=\mathbf b,\qquad t(j)=u,\quad \mathbf b(j)=\mathbf b'.\)

Choose a labeled item \(h\in X_j\) of class \(g\), which exists because \(b'_g>0\). By construction and finite-agent EFX,

\(\displaystyle v_t(\mathbf b'-\mathbf e_g)=V_i(X_j\setminus\{h\})\le\sqrt{2}\,V_i(X_i)=\sqrt{2}\,v_t(\mathbf b).\)

This applies also when \(t=u\): distinct agents of the same type remain subject to the finite theorem. It also applies when \(a_{t,g}=0\), because that theorem requires removal of every item.

If the two occupied pairs coincide, nonnegativity gives

\(\displaystyle v_t(\mathbf b-\mathbf e_g)=v_t(\mathbf b)-a_{t,g}\le v_t(\mathbf b)\le\sqrt{2}\,v_t(\mathbf b).\)

These cases exhaust all comparisons in the task. Therefore \(x\) is a complete \(\frac{\sqrt{2}}{2}\)-EFX allocation.

5. Decision complexity

On every input satisfying the stated hypotheses, the correct answer is YES. The decision algorithm therefore simply accepts valid inputs. If validity checking is included, checking the rational data, valuation restrictions, and mass normalization takes polynomial time in the input bit length \(L\).

The denominator-cleared instance can be very large, so this proof does not establish polynomial-time construction of an allocation. It completely settles the requested existence decision problem.

⟨structured verdict parsed — rendered above⟩

The prover’s argument is correct and resolves the requested decision problem. Every valid input admits a complete \(\frac{\sqrt{2}}{2}\)-EFX allocation, so accepting every valid input is a polynomial-time decision algorithm. No major or minor mathematical gaps were found.

1. The cited finite theorem applies

The external result is stated with the required valuation class and fairness convention:

• Definition 2.1 permits nonnegative additive valuations with each item’s value restricted to zero or its common item weight.
• Section 2 defines approximate EFX by the absence of a strict violation after removing any item in the compared bundle. There is no positive-value restriction on the removed item.
• Theorem 6.1 gives the \(\frac{\sqrt{2}}{2}\)-EFX guarantee; Section 6.4 allocates the entire remaining pool, establishing completeness.

These statements support the theorem invocation as written. [Definitions and EFX convention](https://arxiv.org/html/2407.05139v2#S2), [Theorem 6.1 and final allocation step](https://arxiv.org/html/2407.05139v2#S6).

The constant is translated correctly: the theorem’s guarantee requires
\[ V_i(X_j\setminus\{h\})\leq \sqrt{2}\,V_i(X_i). \]
Equality is permitted because violations are defined by a strict inequality.

Self-comparisons follow from nonnegativity, as the prover explicitly checks.

2. Clearing denominators is valid

There are finitely many rational masses and supplies, so a positive common denominator \(Q\) exists. Consequently,
\[ n_t=Q\mu_t,\qquad k_g=Q\sigma_g \]
are integers, with \(n_t>0\) and \(k_g\geq0\). The normalization gives exactly \(Q\) agents:
\[ \sum_{t\in T}n_t=Q. \]

The finite population therefore reproduces the listed support and its masses. It does not require introducing any unlisted valuation types.

The number of agents and goods may be enormous, but this does not invalidate an existence argument. The prover does not claim that constructing this instance takes polynomial time.

3. The constructed valuations satisfy the theorem’s hypotheses

Each labeled item of class \(g\) has value either zero or \(w_g\) to every agent. Thus the constructed valuations are additive, nonnegative, and restricted additive.

The weights need not be included in the denominator clearing: only agent counts and item counts must become integers. Rational item values are admissible.

Zero supplies, zero weights, and agents with identically zero valuations do not violate the stated valuation hypotheses. The separate no-items case is also correctly handled by empty configurations.

4. Aggregation preserves completeness exactly

Each finite bundle produces an integral nonnegative configuration. The definition
\[ x_{t,\mathbf b}=\frac{1}{Q}\bigl|\{i:t(i)=t,\ \mathbf b(i)=\mathbf b\}\bigr| \]
therefore gives a nonnegative array with finite support.

Every agent contributes to exactly one type–configuration entry, so
\[ \sum_{\mathbf b}x_{t,\mathbf b}=\frac{n_t}{Q}=\mu_t. \]

Every labeled item is allocated exactly once, so for every class,
\[ \sum_{t,\mathbf b}b_gx_{t,\mathbf b} =\frac{1}{Q}\sum_i b(i)_g =\frac{k_g}{Q} =\sigma_g. \]

These are precisely the required completeness equations. Finite support is allowed even though the task also permits infinite support.

5. Aggregation preserves all required EFX comparisons

For two different occupied type–configuration pairs, the corresponding sets of agents are nonempty and disjoint. Distinct representative agents \(i,j\) therefore exist, including when the pairs have the same type but different configurations.

If \(b'_g>0\), agent \(j\)’s bundle contains an item \(h\) of class \(g\). Additivity and the class valuation definition give
\[ v_t(\mathbf b'-\mathbf e_g)=V_i(X_j\setminus\{h\}). \]
Applying finite-agent EFX yields exactly the required inequality.

This argument remains valid when \(a_{t,g}=0\), because the cited removal convention includes such items.

For coincident pairs, the prover correctly uses
\[ v_t(\mathbf b-\mathbf e_g) =v_t(\mathbf b)-a_{t,g} \leq v_t(\mathbf b) \leq\sqrt{2}\,v_t(\mathbf b). \]
The condition \(b_g>0\) ensures that the removed configuration remains nonnegative. These cases exhaust the task’s comparisons.

6. The complexity conclusion follows

The existence proof covers every valid input. Hence the promised decision problem is solved by always answering YES.

If validity checking is included, the sign conditions, valuation restrictions, and rational mass normalization can be checked with exact arithmetic in polynomial time in \(L\). No allocation certificate or denominator-cleared construction must be generated.

The distinction between deciding existence and constructing an allocation is explicit and correct. No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩