The Price of Fairness for Indivisible Goods

Results proved. Exact computation of \(\mathrm{EF1}^{\infty}(I)\) is NP-hard. Its rational-threshold decision version is NP-complete. For the welfare ratio, I prove
\( \frac87\le \sup_I\frac{\mathrm{OPT}^{\infty}(I)}{\mathrm{EF1}^{\infty}(I)} \le\frac2{\sqrt3}. \)
The exact supremum remains unresolved here. The upper bound uses the discrete approximation guarantee supplied in the question.

1. Marginals and a necessary EF1 inequality.

Write \(v_t(g)=v_t(\{g\})\). Given a feasible population allocation, define
\( x_g=2\sum_{B:g\in B}y_{a,B}. \)
Thus \(x_g\in[0,1]\) is the conditional probability that a type-\(a\) bundle contains \(g\). The supply constraints imply that the corresponding probability for type \(b\) is \(1-x_g\).

By additivity and normalization, its welfare \(W\) satisfies
\( 2W=\sum_gv_a(g)x_g+\sum_gv_b(g)(1-x_g) =1+\sum_g\bigl(v_a(g)-v_b(g)\bigr)x_g. \)

Consequently,
\( \mathrm{OPT}^{\infty}(I)=\frac12\sum_g\max\{v_a(g),v_b(g)\}. \)
Indeed, the marginal expression gives the upper bound, and assigning each good entirely to a type valuing it most attains it.

Let \(M_b=\max_gv_b(g)\). Population-EF1 implies, for every supported type-\(b\) bundle \(B\) and type-\(a\) bundle \(C\),
\( v_b(B)\ge v_b(C)-M_b. \)
Average this inequality over the conditional distributions of both bundles. Their expected values under \(v_b\) are respectively \(1-\sum_gv_b(g)x_g\) and \(\sum_gv_b(g)x_g\). Hence every population-EF1 allocation satisfies
\[ \sum_gv_b(g)x_g\le\frac{1+M_b}{2}. \tag{1} \]

2. NP-hardness: construction from PARTITION.

Use the standard NP-complete problem PARTITION: given positive binary-encoded integers \(d_1,\ldots,d_n\), with \(D=\sum_i d_i\), decide whether some subset sums to \(D/2\).

Create goods \(A,P,h,g_1,\ldots,g_n\). Call \(h,g_1,\ldots,g_n\) the small goods. Define valuations by

| Good | Type \(a\) | Type \(b\) |
|---|---:|---:|
| \(A\) | \(19/30\) | \(1/2\) |
| \(P\) | \(0\) | \(1/6\) |
| \(h\) | \(11/60\) | \(1/6\) |
| \(g_i\) | \(11d_i/(60D)\) | \(d_i/(6D)\) |

The small goods have total value \(1/3\) for type \(b\), and type \(a\) values each of them at \(11/10\) times its type-\(b\) value. Therefore both valuations are nonnegative and normalized:
\( v_b(G)=\frac12+\frac16+\frac13=1, \qquad v_a(G)=\frac{19}{30}+\frac{11}{30}=1. \)
All numbers have polynomial encoding length. Give each good supply \(1/2\), as required.

I claim that
\[ \mathrm{EF1}^{\infty}(I)\ge\frac{139}{240} \quad\Longleftrightarrow\quad \text{the PARTITION instance is a yes-instance}. \tag{2} \]

3. Universal upper bound for the constructed instance.

For any population-EF1 allocation, put
\( z=x_A,\qquad r=x_P,\qquad s=\sum_{g\text{ small}}v_b(g)x_g. \)
Here \(M_b=1/2\). Inequality (1) gives
\[ \frac12z+\frac16r+s\le\frac34. \tag{3} \]

The welfare identity becomes
\( 2W=1+\frac{2}{15}z-\frac16r+\frac1{10}s. \)
Substituting the bound on \(s\) from (3),
\( 2W \le 1+\frac3{40}+\frac1{12}z-\frac{11}{60}r \le 1+\frac3{40}+\frac1{12} =\frac{139}{120}. \)
Thus \(W\le139/240\).

Moreover, equality forces
\[ z=1,\qquad r=0,\qquad s=\frac14. \tag{4} \]
The first two conclusions follow because the coefficient of \(z\) is strictly positive and that of \(r\) strictly negative. Equality in the preceding substitution then gives the value of \(s\).

4. Equality forces an actual partition.

Suppose a population-EF1 allocation attains \(139/240\). By (4), every supported type-\(a\) bundle contains \(A\) and excludes \(P\); every supported type-\(b\) bundle excludes \(A\) and contains \(P\).

For a supported type-\(a\) bundle \(C\), write
\( s(C)=\sum_{\substack{g\in C\\g\text{ small}}}v_b(g). \)
The good \(A\) has type-\(b\) value \(1/2\), while every small good has value at most \(1/6\). Therefore the minimum value remaining after deleting at most one good from \(C\) is exactly \(s(C)\).

Population-EF1 consequently requires
\( v_b(B)\ge s(C) \)
for every supported type-\(b\) bundle \(B\).

The conditional expected type-\(b\) value of a type-\(b\) bundle is, by (4),
\( 1-\left(\frac12z+\frac16r+s\right)=\frac14. \)
Averaging the preceding EF1 inequality over \(B\) shows that \(s(C)\le1/4\) for every supported \(C\). But the conditional average of \(s(C)\) is \(s=1/4\). Since every supported bundle has positive probability, every such bundle must satisfy \(s(C)=1/4\).

Choose one. The original goods \(g_i\) together have type-\(b\) value only \(1/6\), so its small-good subset must contain \(h\). Its remaining selected goods therefore satisfy
\( \sum_{i:g_i\in C}\frac{d_i}{6D} =\frac14-\frac16 =\frac1{12}. \)
Multiplying by \(6D\) yields
\( \sum_{i:g_i\in C}d_i=\frac D2. \)
Thus the original instance has a partition. This argument explicitly rules out attaining the threshold merely by mixing different subsets.

Conversely, suppose \(J\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in J}d_i=D/2\). Assign the bundle
\( C=\{A,h\}\cup\{g_i:i\in J\} \)
to all of type \(a\), and its complement \(B=G\setminus C\) to all of type \(b\).

The small goods in \(C\) have type-\(b\) value \(1/4\), so
\( v_b(B)=\frac14=v_b(C\setminus\{A\}). \)
Thus type \(b\)'s EF1 condition holds. Type \(a\) does not envy \(B\): its own bundle contains \(A\), worth \(19/30\), whereas all goods outside \(A\) together are worth only \(11/30\). Comparisons within either type are comparisons of a bundle with itself and automatically satisfy EF1.

Finally,
\( W =\frac12\left(\frac{19}{30}+\frac{11}{10}\cdot\frac14+\frac14\right) =\frac{139}{240}. \)
This proves (2), and therefore NP-hardness.

5. Polynomial-size certificates.

Consider the decision problem with an additional rational threshold \(K\), asking whether \(\mathrm{EF1}^{\infty}(I)\ge K\).

Let \(m=|G|\), and fix the set \(S\) of typed bundles appearing in any feasible population-EF1 allocation. Allow their weights to vary, subject to the original mass and supply equations, while keeping all other weights zero. This is a bounded linear-programming polytope with \(m+2\) equality constraints.

Every point of this polytope remains population-EF1: its positive support is a subset of the pairwise-compatible set \(S\). Maximizing welfare over this polytope therefore gives a vertex of at least the original welfare.

Such a vertex has at most \(m+2\) positive coordinates. To see this, if its positive columns were linearly dependent, a nonzero kernel direction supported on those coordinates could be added and subtracted by a sufficiently small amount, contradicting extremality.

These columns have entries in \(\{0,1\}\), and all right-hand sides equal \(1/2\). Select a nonsingular square subsystem determining the positive coordinates. Cramer's rule and the determinant bound for a matrix with entries in \(\{0,1\}\) show that their numerators and denominators have \(O(m\log(m+2))\) bits.

A certificate can thus list at most \(m+2\) bundles and their rational weights. In polynomial time one can verify:

the mass and supply equalities;
the welfare threshold;
every ordered EF1 comparison between listed typed bundles, by subtracting the largest singleton value from the compared bundle, or subtracting zero for an empty bundle.

Therefore the threshold problem belongs to NP and, by the reduction above, is NP-complete.

For completeness, the maximum is attained: the feasible EF1 set is a finite union of closed, bounded polytopes, one for each pairwise-compatible allowed support. Nonemptiness also follows from the supplied discrete EF1 guarantee.

6. A population lower bound of \(\boldsymbol{8/7}\).

Take three goods \(g_1,g_2,p\), and a rational parameter \(0<\varepsilon<1/6\). Set
\( (v_a(g_1),v_a(g_2),v_a(p)) =\left(\frac12,\frac12,0\right) \)
and
\( (v_b(g_1),v_b(g_2),v_b(p)) =\left(\frac13+\varepsilon,\frac13+\varepsilon,\frac13-2\varepsilon\right). \)
Both valuations are normalized. Write \(c=1/3+\varepsilon\) and \(d=1/3-2\varepsilon\).

I first show that every population-EF1 allocation satisfies
\[ x_{g_1}+x_{g_2}\le1. \tag{5} \]

If no supported type-\(a\) bundle contains both \(g_1\) and \(g_2\), (5) follows by averaging their number in a type-\(a\) bundle.

Otherwise, choose a supported type-\(a\) bundle containing both. Deleting at most one good leaves type-\(b\) value at least \(c\). Every supported type-\(b\) bundle must therefore have value at least \(c\). A bundle containing neither \(g_1\) nor \(g_2\) has value at most \(d<c\), so every type-\(b\) bundle contains at least one of them. Averaging and using the supply constraints gives
\( (1-x_{g_1})+(1-x_{g_2})\ge1, \)
which again proves (5).

The welfare identity now gives
\( 2W =1+\left(\frac12-c\right)(x_{g_1}+x_{g_2})-d x_p \le1+\frac12-c =\frac76-\varepsilon. \)
The partition assigning \(\{g_1\}\) to type \(a\) and \(\{g_2,p\}\) to type \(b\) is EF1 and attains this bound. Hence
\( \mathrm{EF1}^{\infty}(I)=\frac7{12}-\frac{\varepsilon}{2}. \)

The unconstrained optimum assigns both \(g_1,g_2\) to type \(a\) and \(p\) to type \(b\), giving
\( \mathrm{OPT}^{\infty}(I)=\frac23-\varepsilon. \)
Therefore
\( \frac{\mathrm{OPT}^{\infty}(I)}{\mathrm{EF1}^{\infty}(I)} =\frac{8-12\varepsilon}{7-6\varepsilon} \longrightarrow\frac87 \)
as positive rational \(\varepsilon\) tends to zero. This proves the claimed lower bound on the supremum.

7. Upper bound and remaining question.

Apply the discrete guarantee stated in the question to the same goods and valuations. Its hypotheses hold: there are two agents with nonnegative, normalized additive valuations.

The discrete unconstrained optimum is
\( \sum_g\max\{v_a(g),v_b(g)\}=2\mathrm{OPT}^{\infty}(I). \)
The guarantee supplies an EF1 partition \((A,B)\) satisfying
\( v_a(A)+v_b(B) \ge\frac{\sqrt3}{2}\cdot2\mathrm{OPT}^{\infty}(I). \)
Assigning \(A\) to all of type \(a\) and \(B\) to all of type \(b\) is population-EF1 and halves that discrete welfare. Consequently,
\( \mathrm{EF1}^{\infty}(I) \ge\frac{\sqrt3}{2}\mathrm{OPT}^{\infty}(I). \)

Thus exact computation is NP-hard, but the arguments here determine the price only within
\( \left[\frac87,\frac2{\sqrt3}\right]. \)

⟨structured verdict parsed — rendered above⟩

Adversarial review (gpt-6-astra / low, Bolzano verifier prompt)

The complexity result and both welfare-ratio bounds are correct. The output does not determine the exact supremum requested in USER_TASK, and explicitly acknowledges this limitation. The overall result is therefore partial, with no substantive mathematical error found in the arguments presented.

All mathematics below uses the final formatting instruction’s \( \) delimiters.

Marginal formulation and necessary EF1 inequality

The definition \(x_g=2\sum_{B:g\in B}y_{a,B}\) correctly gives the conditional inclusion probability for type \(a\), because its total mass is \(1/2\). The supply equation implies that type \(b\)’s conditional inclusion probability is \(1-x_g\).

The welfare identity
\(2W=1+\sum_g(v_a(g)-v_b(g))x_g\)
follows directly from additivity and normalization.

The unconstrained optimum formula is correct. Assigning each good to a maximizing type defines a partition, and assigning each partition bundle to its entire type realizes the required marginal choices and all supply constraints. Ties cause no difficulty.

For every supported pair, EF1 implies \(v_b(B)\ge v_b(C)-M_b\): the value removed by any permitted deletion is at most \(M_b\). Averaging over the two conditional distributions is legitimate because the inequality holds for every supported pair. This gives \(1-\sum_gv_b(g)x_g\ge\sum_gv_b(g)x_g-M_b\), exactly yielding inequality (1).

Assessment: Correct.

Reduction construction

The construction requires a nonempty list of positive integers, so \(D>0\). This is a valid restriction of the stated standard PARTITION problem.

The normalization calculations are correct. The small goods have total type-\(b\) value \(1/3\), and their type-\(a\) values are exactly \(11/10\) times their type-\(b\) values. Every \(g_i\) has type-\(b\) value at most \(1/6\), since \(d_i\le D\). Thus \(M_b=1/2\).

The rational entries have polynomial encoding length: the binary length of \(D\) is polynomial in the input length, and all numerators and denominators are fixed multiples of \(d_i\) or \(D\). The number of goods is also polynomial.

Assessment: Correct polynomial-time construction.

Universal upper bound and equality conditions

The welfare coefficients are correct:
\(v_a(A)-v_b(A)=2/15\), \(v_a(P)-v_b(P)=-1/6\), and the small-good contribution is \(s/10\).

Substituting \(s\le3/4-z/2-r/6\) gives
\(2W\le43/40+z/12-11r/60\).
Using \(z\le1\) and \(r\ge0\) yields \(2W\le139/120\).

Equality requires both inequalities to be tight. The strictly positive coefficient of \(z\) and strictly negative coefficient of \(r\) force \(z=1\) and \(r=0\). Tightness of the substitution then forces \(s=1/4\).

Assessment: Correct, including the necessity of all equality conditions.

Threshold attainment implies a partition

Conditional inclusion probability one or zero forces inclusion or exclusion in every positive-probability bundle. Hence the support restrictions on \(A\) and \(P\) follow correctly.

In any supported type-\(a\) bundle, deleting \(A\) minimizes the remaining type-\(b\) value because \(A\) is worth \(1/2\), exceeding every small good’s value. The minimum remaining value is therefore exactly \(s(C)\).

Averaging the resulting inequality \(v_b(B)\ge s(C)\) over type-\(b\) bundles gives \(s(C)\le1/4\) for each supported \(C\). The conditional average of these quantities is \(1/4\). Since the support is finite and each supported bundle has positive weight, every supported \(C\) must attain \(s(C)=1/4\).

The original goods collectively contribute only \(1/6\), so such a bundle must contain \(h\). Its selected original goods then contribute \(1/12\), equivalent to a subset sum of \(D/2\).

This argument applies to arbitrary feasible mixtures and correctly excludes mixtures as a way to reach the threshold without an actual partition.

Assessment: Correct.

A partition implies threshold attainment

The proposed complementary bundles satisfy every mass and supply equation.

Type \(b\)’s cross-type EF1 comparison holds with equality after deleting \(A\). Type \(a\) does not envy the other bundle because its own value is at least \(19/30\), while any bundle excluding \(A\) has value at most \(11/30\). Within-type comparisons involve identical bundles and satisfy EF1 without deletion.

The welfare calculation checks:
\(19/30+(11/10)(1/4)+1/4=139/120\).
Multiplication by the population mass gives \(139/240\).

Together with the upper bound and the attainment argument supplied later, this proves the threshold equivalence. Exact computation is consequently NP-hard. The reduction establishes ordinary NP-hardness; it does not establish strong NP-hardness, which the output does not claim.

Assessment: Correct.

Polynomial certificates and existence of a maximum

Fixing a compatible allowed support gives a nonempty bounded polytope when starting from a feasible allocation. Allowing weights to vanish preserves EF1 because removing supported bundles cannot create a new comparison.

A linear objective attains its maximum at a vertex of this polytope. The kernel-direction argument correctly establishes that the positive columns at a vertex are linearly independent, so there are at most \(m+2\) positive coordinates.

The rational-size argument is also valid. For \(k\le m+2\) positive coordinates, independent columns admit a nonsingular \(k\)-row square subsystem. Its coefficient entries are zero or one and its right-hand side is uniformly \(1/2\). The determinant bound \( |\det A|\le k^{k/2}\), together with Cramer’s rule, gives polynomial bit length as claimed. Rank deficiencies in the full equation system do not invalidate this reasoning.

Bundle descriptions, rational arithmetic, and the quadratically many ordered support comparisons all have polynomial size. For nonnegative additive valuations, deleting a maximum-valued good gives the smallest possible remaining value; the empty-bundle convention is correct.

The finite-union argument correctly proves attainment: there are finitely many typed bundles and hence finitely many compatible allowed supports, each defining a closed bounded polytope. The supplied discrete guarantee ensures nonemptiness.

Minor issue: The explicit certificate-verification checklist omits checking that weights are nonnegative. This is part of feasibility and is an immediate polynomial-time check, but should be stated. It does not undermine NP membership.

Assessment: NP-completeness is established, subject only to that routine clarification.

Population lower bound

The parameter restriction gives \(0<d<c<1/2\), so all valuations are nonnegative and both signs used in the welfare bound are correct.

The proof of inequality (5) exhausts both possibilities. If no supported type-\(a\) bundle contains both distinguished goods, its conditional expected count is at most one. Otherwise, deleting any one good from the selected bundle leaves type-\(b\) value at least \(c\). Every supported type-\(b\) bundle must then contain a distinguished good because a bundle containing neither has value at most \(d<c\). The supply equations give the claimed bound.

The welfare bound follows because \(1/2-c>0\), \(d>0\), and \(x_p\ge0\).

The claimed attaining allocation is EF1: type \(a\) values both bundles at \(1/2\), and type \(b\)’s comparison against the singleton bundle is satisfied by deleting that singleton. Its welfare is \(7/12-\varepsilon/2\).

The unconstrained optimum is \(2/3-\varepsilon\), since each distinguished good is valued more by type \(a\) and \(p\) more by type \(b\). The ratio and its limit are correct. Positive rational parameters approaching zero suffice to establish a supremum lower bound; no claim of attainment at zero is needed.

Assessment: Correct.

Upper bound from the supplied discrete guarantee

The invoked guarantee is stated quantitatively, and its hypotheses match the instance: two agents with normalized nonnegative additive valuations.

The discrete optimum equals twice the population unconstrained optimum. Replicating an EF1 partition across the two populations preserves cross-type EF1, makes within-type comparisons trivial, and satisfies every supply constraint. Its welfare is half the discrete welfare.

Consequently, \(\mathrm{EF1}^{\infty}(I)\ge(\sqrt3/2)\mathrm{OPT}^{\infty}(I)\), giving the claimed ratio bound. The denominator is positive: normalization gives \(\mathrm{OPT}^{\infty}(I)\ge1/2\), and this guarantee supplies a positive EF1 welfare.

Assessment: Correct, using the discrete guarantee expressly supplied in USER_TASK.

Unresolved portion and required feedback

The bounds \(8/7\) and \(2/\sqrt3\) differ. Neither the reduction nor the ratio arguments determine the exact supremum.

Major incompleteness relative to USER_TASK: The exact welfare-ratio target remains unresolved. This is accurately disclosed by the prover, rather than concealed by an unsupported claim.

To complete the assignment, the prover must establish the exact supremum with matching upper and lower bounds. This requires additional mathematics, not clarification of the present proof. The only expositional repair needed for the established complexity result is to include nonnegativity in the certificate checks.

⟨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.

The Price of Fairness for Indivisible Goods (d4-conf-ijcai-2019-1021)

The anchor (named result in the paper)

The continuous mirror question, as graded

Packaged proof task (what the prover saw — nothing else)

Definitions

Target

Nearest known results

Prover output (gpt-6-astra / medium, Bolzano prover prompt)

Adversarial review (gpt-6-astra / low, Bolzano verifier prompt)