Comparing Approximate Relaxations of Envy-Freeness

Partial results for continuous PMMS optimization

The general classification remains unresolved here. I prove that, for fixed \(\ell\), threshold feasibility belongs to \(\mathrm{NP}\), the finite optimum lies in a polynomial-size explicitly computable set, and unboundedness is polynomial-time decidable. I also solve the case \(\ell=1\) and give a strictly positive-valuation example showing why a direct convexity argument fails.

1. Conventions and a well-definedness issue

For complexity statements, assume that the masses \(\mu_t\), as well as the valuations and supplies, are rational and explicitly encoded in binary. Assume \(\ell\) is a fixed positive integer. If \(\ell=0\), every benchmark is zero and the objective is unbounded.

Write

\(\mathcal B=\{b\in\mathbb Z_{\geq 0}^{G}:\sum_g b_g=\ell\}\)

and

\(M_t(b,c)=\max_{0\leq u\leq b+c}\min\{v_t(u),v_t(b+c-u)\},\)

where the maximization is over integer vectors.

Under the stated hypotheses, a largest real feasible parameter need not exist: if every valuation is zero, every nonnegative parameter is feasible. Accordingly, the results below use the extended-value convention \(\lambda^\star=+\infty\) for an unbounded instance. Equivalently, an algorithm can report “unbounded.”

The quantifier over every positive-support pair includes comparing a pair with itself.

2. Polynomially many bundles and efficiently computable benchmarks

Let \(m=|G|\). The number of bundles is

\(B=|\mathcal B|=\binom{m+\ell-1}{\ell}.\)

Thus \(B\) is polynomial in the input size for fixed \(\ell\).

For any two bundles, their combined multiset contains exactly \(2\ell\) item copies. Temporarily distinguish copies of the same good. Every integer subbundle of the combined multiset is represented by a subset of these copies. Enumerating the at most \(2^{2\ell}\) subsets therefore computes \(M_t(b,c)\) exactly.

Consequently, all benchmarks can be computed in polynomial time for fixed \(\ell\). They are rational numbers of polynomial encoding length.

The computational obstacle is therefore the choice of support, rather than the computation of an individual benchmark.

3. A dichotomy: the optimum is at most one or is unbounded

Lemma 1. For every type and bundle,

\(M_t(b,b)=v_t(b).\)

Proof. The partition into two copies of \(b\) attains \(v_t(b)\). Conversely, the two parts of any partition have total value \(2v_t(b)\), so their smaller value is at most \(v_t(b)\). ∎

Proposition 2. If an allocation is feasible for any \(\lambda>1\), that same allocation is feasible for every nonnegative parameter.

Proof. For every supported pair \((t,b)\), its self-comparison gives

\(v_t(b)\geq\lambda M_t(b,b)=\lambda v_t(b).\)

Nonnegativity and \(\lambda>1\) imply \(v_t(b)=0\). Comparing this pair with any other supported pair \((s,c)\) now gives

\(0\geq\lambda M_t(b,c).\)

Since the benchmark is nonnegative, it must equal zero. All support inequalities consequently hold for every nonnegative parameter. ∎

There is always an allocation satisfying the mass and supply equations. Explicitly, set

\(x_{t,\ell e_g}=\mu_t q_g/\ell\)

and set all other coordinates to zero. Its type masses are correct because \(\sum_g q_g=\ell\), and its supply of good \(g\) is \(\sum_t\ell\mu_tq_g/\ell=q_g\). Every such allocation is feasible at \(\lambda=0\).

It follows that every bounded instance has optimum in \([0,1]\). Attainment is proved in Section 5.

Polynomial-time recognition of unboundedness

Let \(T_+=\{t:\mu_t>0\}\), and define the number of item copies in \(b\) that type \(t\) values positively by

\(p_t(b)=\sum_{\{g:v_t(g)>0\}}b_g.\)

Define

\(\mathcal R=\{b\in\mathcal B:p_t(b)\leq1\text{ for every }t\in T_+\}.\)

Proposition 3. The instance is unbounded if and only if the mass and supply equations have a nonnegative solution using only coordinates satisfying

\(t\in T_+,\qquad b\in\mathcal R,\qquad v_t(b)=0.\)

Thus unboundedness is decidable by a polynomial-size rational linear program for fixed \(\ell\).

Proof. A nonnegative additive valuation has two-way maximin benchmark zero on a multiset exactly when that multiset contains at most one positively valued item copy. With at most one such copy, one part of every partition has value zero. With at least two, placing one in each part gives a strictly positive minimum.

Suppose first that an allocation is feasible at a parameter greater than one. Proposition 2 shows that every supported bundle has zero value to its recipient.

Fix any globally supported bundle \(c\) and any \(t\in T_+\). There is some supported pair \((t,b)\), because its total mass is positive. The benchmark \(M_t(b,c)\) is zero. Since \(b\) contains no item valued positively by \(t\), the preceding characterization implies \(p_t(c)\leq1\). Therefore every globally supported bundle belongs to \(\mathcal R\).

Conversely, suppose the stated linear system is feasible. For supported pairs \((t,b)\) and \((s,c)\), the bundle \(b\) has zero value to \(t\), while \(c\in\mathcal R\) contains at most one copy valued positively by \(t\). Hence \(M_t(b,c)=0\). Every support inequality holds at every parameter.

There are at most \(|T|B\) variables, and all eligibility tests and linear constraints have polynomial encoding length. Polynomial-time rational linear programming therefore applies. ∎

4. Exact support formulation and membership in NP

Fix a rational threshold \(\alpha\geq0\).

For a set \(H\subseteq\mathcal B\), define

\(A_t(H,\alpha)=\{b\in H:v_t(b)\geq\alpha M_t(b,c)\text{ for every }c\in H\}.\)

Consider the linear feasibility system with nonnegative variables only for \(b\in A_t(H,\alpha)\):

\(\sum_{b\in A_t(H,\alpha)}x_{t,b}=\mu_t\quad\text{for every }t,\)

\(\sum_t\sum_{b\in A_t(H,\alpha)}b_gx_{t,b}=q_g\quad\text{for every }g.\)

Proposition 4. Threshold \(\alpha\) is feasible if and only if this linear system is feasible for some \(H\subseteq\mathcal B\).

Proof. Given a PMMS-feasible allocation, take \(H\) to be its globally supported bundles. For every supported \((t,b)\) and every \(c\in H\), some type receives \(c\) with positive mass. The required comparison implies \(b\in A_t(H,\alpha)\).

Conversely, a solution of the displayed system uses only bundles from \(H\). Every supported \((t,b)\) is compatible, from type \(t\)'s perspective, with every bundle in \(H\). In particular, it is compatible with every actually supported bundle. ∎

The system need not force every member of \(H\) to appear: unused members merely impose extra restrictions, which do not invalidate the converse.

This gives a deterministic algorithm with running time

\(2^B\operatorname{poly}(L),\)

where \(L\) is the input length and \(\ell\) is fixed. In particular, threshold feasibility is polynomial-time solvable when both \(\ell\) and \(|G|\) are fixed, even if the number of types varies.

Proposition 5. For fixed \(\ell\), threshold feasibility belongs to \(\mathrm{NP}\). Every feasible threshold has a rational witnessing allocation with polynomial encoding length and at most \(|T|+|G|-1\) positive coordinates.

Proof. Start with any feasible allocation and restrict the mass and supply system to its support \(S\). The resulting polytope is nonempty and bounded: every coordinate lies between zero and its type mass. It therefore has an extreme point.

Its equality matrix has at most \(|T|+|G|-1\) independent rows. Indeed, summing the good rows gives \(\ell\) times the sum of the type rows, because every column represents a bundle of size \(\ell\). An extreme point consequently has at most this many positive coordinates.

The coefficients of the equality matrix are integers between zero and \(\ell\), and the right-hand side is rational with polynomial encoding length. The usual determinant bounds for basic solutions show that the extreme point has polynomial encoding length.

Its support is a subset of \(S\), so removing coordinates introduces no new pairwise comparisons. It remains feasible at \(\alpha\).

A verifier checks the mass equations, supply equations, nonnegativity, and every ordered pair in the supplied support. Section 2 shows that all these checks take polynomial time. ∎

5. The finite optimum belongs to a polynomial-size candidate set

Construct

\(\mathcal C=\{0,1\}\cup\{v_t(b)/M_t(b,c):t\in T,\ b,c\in\mathcal B,\ M_t(b,c)>0\},\)

and discard candidates outside \([0,1]\). There are at most \(2+|T|B^2\) candidates, each with polynomial encoding length.

Proposition 6. If the instance is bounded, its optimum is attained and belongs to \(\mathcal C\).

Proof. For any nonempty support \(S\) realizable by an allocation satisfying the mass and supply equations, define

\(L(S)=\min\{v_t(b)/M_t(b,c):(t,b),(s,c)\in S,\ M_t(b,c)>0\},\)

with value \(+\infty\) when the set is empty.

An allocation with exactly this support is feasible at parameter \(\lambda\geq0\) precisely when \(\lambda\leq L(S)\). This follows by dividing each support inequality having positive benchmark by that benchmark; zero benchmarks impose no restriction.

There are finitely many supports and at least one realizable support. In a bounded instance, all realizable supports have finite \(L(S)\), and each such value is an attained minimum of the displayed ratios. Choose a realizable support maximizing \(L(S)\). Any allocation realizing it attains that value.

Proposition 2 places the resulting optimum in \([0,1]\), so it belongs to \(\mathcal C\). ∎

Thus exact optimization reduces to polynomially many threshold tests. More precisely, after testing unboundedness, sorting \(\mathcal C\), and using monotonicity of feasibility, binary search needs only logarithmically many queries to an \(\mathrm{NP}\) oracle.

This is an upper bound, not a polynomial-time algorithm without an oracle.

6. Complete solution for bundle size one

Proposition 7. For \(\ell=1\), every allocation satisfying the mass and supply equations is feasible at parameter one. The extended optimum is either \(1\) or \(+\infty\), and it is computable in polynomial time.

Proof. Every bundle is a singleton \(e_g\). The combined multiset of two singleton bundles has benchmark

\(M_t(e_g,e_h)=\min\{v_t(g),v_t(h)\}.\)

Indeed, separating the two item copies attains this value, while placing both in one part gives minimum zero. Consequently,

\(v_t(g)\geq M_t(e_g,e_h)\)

for every ordered pair. Therefore every allocation is feasible at one.

By Proposition 2, either the optimum is one or the instance is unbounded. In this case every bundle automatically belongs to \(\mathcal R\). Proposition 3 therefore reduces unboundedness to the transportation feasibility system

\(\sum_gx_{t,g}=\mu_t,\qquad\sum_tx_{t,g}=q_g,\qquad x_{t,g}\geq0,\)

with \(x_{t,g}=0\) whenever \(v_t(g)>0\). This is a polynomial-size rational linear program. ∎

7. Feasibility is nonconvex even with strictly positive valuations

The following example rules out directly treating the original feasible allocation set as a polytope.

Take \(\ell=2\), goods \(a,b\), and types \(t,s\), with

\(\mu_t=\tfrac14,\qquad\mu_s=\tfrac34,\qquad q_a=\tfrac34,\qquad q_b=\tfrac54.\)

Let

\(v_t(a)=10,\quad v_t(b)=1,\qquad v_s(a)=v_s(b)=1.\)

Write \(aa,ab,bb\) for the three bundles. Consider these two allocations; unlisted coordinates are zero.

| Coordinate | Allocation \(X\) | Allocation \(Y\) |
|---|---:|---:|
| \(x_{t,bb}\) | \(\tfrac14\) | \(0\) |
| \(x_{t,ab}\) | \(0\) | \(\tfrac14\) |
| \(x_{s,ab}\) | \(\tfrac34\) | \(0\) |
| \(x_{s,aa}\) | \(0\) | \(\tfrac14\) |
| \(x_{s,bb}\) | \(0\) | \(\tfrac12\) |

Both have the specified masses and supplies.

Every bundle has value two to type \(s\), and every combined multiset has benchmark two. Thus its inequalities hold at every parameter at most one.

In \(X\), type \(t\) receives \(bb\), of value two. Its self-benchmark is two. Against \(ab\), the item values are \(10,1,1,1\). Any partition has a part without the value-ten item, of value at most three; separating that item from the other three attains three. Hence

\(M_t(bb,ab)=3.\)

Allocation \(X\) is therefore feasible at \(\lambda=\tfrac23\).

In \(Y\), type \(t\) receives \(ab\), of value eleven. Against \(aa\), the item values are \(10,10,10,1\). The possible subset values are \(0,1,10,11,20,21,30,31\), so the best smaller part has value eleven. Against \(bb\), the benchmark is three, as above. Its self-benchmark is eleven. Thus \(Y\) is feasible even at parameter one.

However, the midpoint of \(X\) and \(Y\) supports both \((t,bb)\) and \((s,aa)\). Their combined item values to \(t\) are \(10,10,1,1\), whose benchmark is eleven: the partition into two value-eleven parts attains half the total value. Their required inequality at parameter \(\tfrac23\) would be

\(2\geq\tfrac23\cdot11,\)

which is false.

Hence the feasible set at a fixed threshold can be nonconvex even when all item valuations are strictly positive. Nonconvexity alone does not establish hardness.

8. Remaining classification question

For fixed \(\ell\geq2\) and an unrestricted number of goods and types, the unresolved step is deciding whether one can select a globally compatible bundle support in polynomial time.

The support formulation isolates that step exactly. It does not justify an arbitrary-graph hardness reduction: any reduction must realize the required incompatibilities through additive PMMS benchmarks and must exclude fractional allocations that circumvent the intended discrete choices.

⟨structured verdict parsed — rendered above⟩

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

The output is correct as a collection of partial results, but it does not settle the requested complexity classification for fixed \(\ell\geq2\). I find no mathematical error in the stated partial results. The unresolved support-selection problem is explicitly acknowledged.

The appropriate status is partial: the proof establishes genuine upper bounds and special cases, without establishing either polynomial-time solvability or hardness for the general target.

1. Scope and conventions

The complexity results explicitly assume that \(\mu\) is rational and encoded in binary. This is a necessary clarification of the computational input model: the task specifies rational valuations and supplies but only states \(\mu\in\Delta(T)\). Accordingly, the complexity claims are verified under the prover’s declared rational-input convention.

The extended-value convention is also justified. When every valuation is zero, every nonnegative parameter is feasible, so the “largest feasible” real parameter in the task does not exist. Reporting unboundedness resolves this definitional issue transparently.

Including self-comparisons agrees with the task’s unrestricted quantifier over positive-support pairs. Several subsequent conclusions depend on this interpretation, and the prover states it explicitly.

For \(\ell=0\), nonnegative supplies summing to zero are all zero, the only bundle is the zero bundle, and every benchmark is zero. The stated unboundedness conclusion is correct.

2. Bundle enumeration and benchmark computation

For fixed positive integer \(\ell\), the formula
\[ |\mathcal B|=\binom{|G|+\ell-1}{\ell} \]
correctly counts nonnegative integer bundles of total size \(\ell\), and is polynomial in the explicitly encoded input size.

The benchmark calculation is valid. A combined bundle contains \(2\ell\) copies, and every integer subbundle can be represented by a subset of distinguished copies. Repeated representations do not affect the maximum. Enumerating at most \(2^{2\ell}\) subsets therefore computes each benchmark exactly.

Each value involves sums of a fixed number of rational item values, followed by comparisons. Polynomial encoding length and polynomial total computation time follow as claimed.

The statement that support choice is the remaining obstacle is supported by the later exact support formulation; benchmark computation itself presents no unresolved complexity issue here.

3. Boundedness dichotomy

Lemma 1 is correct. Splitting \(2b\) into two copies of \(b\) attains \(v_t(b)\). Every partition has total value \(2v_t(b)\), so its smaller part cannot exceed \(v_t(b)\).

Proposition 2 is correct. At a parameter \(\lambda>1\), self-comparison forces every recipient’s supported bundle to have value zero. Comparing that coordinate against every other supported coordinate then forces every relevant benchmark to be zero. The same allocation consequently works at every nonnegative parameter.

The baseline allocation
\[ x_{t,\ell e_g}=\mu_tq_g/\ell \]
has the claimed type masses and supplies. Nonnegativity of valuations makes it feasible at zero. Thus there is no missing feasibility assumption behind the boundedness dichotomy.

Proposition 3 is correct. The characterization of a zero benchmark is exact for nonnegative additive valuations: a multiset admits a partition with both parts strictly positive precisely when it contains at least two positively valued item copies.

Both directions of the unboundedness criterion are verified:

Necessity uses positive type mass to obtain a supported bundle for each \(t\in T_+\). Its zero recipient value, together with its zero benchmark against every globally supported bundle, implies the stated restriction on that bundle.
Sufficiency uses \(v_t(b)=0\) and \(p_t(c)\leq1\) to make every relevant benchmark zero.

Types outside \(T_+\) cannot have positive allocation coordinates, so their exclusion is appropriate.

The resulting linear program has polynomially many variables, constraints, and rational coefficient bits. The invocation of polynomial-time rational linear feasibility has its required hypotheses satisfied.

4. Exact support formulation

Proposition 4 is correct.

For necessity, taking \(H\) to be the actual global bundle support ensures that every \(c\in H\) has a positive-support recipient. The original pairwise requirement therefore gives every inequality defining \(A_t(H,\alpha)\).

For sufficiency, every actual supported bundle lies in \(H\), so eligibility against all of \(H\) implies eligibility against the actual support. The formulation need not force every member of \(H\) to occur, exactly as the prover explains.

There are \(2^B\) choices of \(H\), each yielding a polynomial-size linear feasibility problem. The running-time statement is correct, with the rational threshold’s encoding length understood as part of the threshold-instance input length.

When both \(\ell\) and \(|G|\) are fixed, \(B\) is constant. The resulting polynomial-time special case follows.

5. NP membership and certificate size

Proposition 5 is correct.

Restricting to the support of an existing feasible allocation gives a nonempty bounded polytope: every variable is nonnegative and bounded above by its type mass. Thus an extreme point exists.

The asserted row dependence is valid. In every column, the sum of the good-row coefficients is \(\ell\), and the sum of the type-row coefficients is one. Hence the matrix rank is at most
\[ |T|+|G|-1. \]

The standard extreme-point support bound applies to this equality-constrained nonnegative polytope. Consequently, an extreme point has at most that many positive coordinates.

The determinant-bound assertion is routine and applicable: the matrix dimension is polynomial, its integer entries are bounded by fixed \(\ell\), and the rational right-hand side has polynomial encoding length. These conditions give polynomial bit length for basic solutions. No substantive missing lemma is needed here.

Finally, replacing the original allocation by this extreme point only removes supported coordinates. It introduces no new comparisons, so threshold feasibility is preserved.

Verification of the rational allocation and all ordered supported pairs takes polynomial time. The NP-membership conclusion is established.

6. Candidate set and attainment

Proposition 6 is correct.

For an exactly realizable support \(S\), every positive benchmark imposes its corresponding ratio bound, while zero benchmarks impose no restriction. Therefore feasibility for that support is precisely
\[ 0\leq\lambda\leq L(S). \]

There are finitely many possible supports. In a bounded instance, none of the realizable supports can have \(L(S)=+\infty\). Maximizing their finite endpoints therefore produces an attained optimum.

Each finite endpoint is one of the explicitly listed ratios. Proposition 2 ensures that the maximizing endpoint lies in \([0,1]\), so discarding candidates outside this interval is legitimate.

The candidate count and rational encoding bounds are correct. Threshold feasibility is monotone, so binary search uses logarithmically many NP-oracle queries after sorting the polynomial-size candidate set.

This establishes an oracle upper bound, not an ordinary polynomial-time algorithm. The prover correctly maintains that distinction.

7. The case \(\ell=1\)

Proposition 7 is correct.

For two singleton bundles, separating the copies gives the smaller singleton value; putting both copies in one part gives zero. Thus
\[ M_t(e_g,e_h)=\min\{v_t(g),v_t(h)\}, \]
including when \(g=h\).

Every recipient’s singleton value is at least this benchmark, so every allocation satisfying the linear constraints is feasible at one.

Combined with Proposition 2, this gives optimum one or unboundedness. Every singleton automatically satisfies the defining restriction for \(\mathcal R\), and the stated transportation feasibility system correctly tests unboundedness.

The claimed polynomial-time solution for this special case is established.

8. Nonconvexity example

The numerical example checks out.

Both allocations give type masses \(1/4\) and \(3/4\), and supplies \(q_a=3/4\) and \(q_b=5/4\).

For type \(s\), every bundle has value two and every combined multiset has benchmark two.

For type \(t\):

In \(X\), the supported bundle \(bb\) has value two, its self-benchmark is two, and its benchmark against \(ab\) is three. Thus \(X\) is feasible at \(2/3\).
In \(Y\), the supported bundle \(ab\) has value eleven. Its benchmarks against \(aa\), \(bb\), and itself are respectively eleven, three, and eleven. Thus \(Y\) is feasible at one, and hence at \(2/3\).
The midpoint supports both \((t,bb)\) and \((s,aa)\). Their benchmark from type \(t\)’s perspective is eleven, while the recipient value is two. The required inequality fails because \(2<22/3\).

The example therefore proves nonconvexity at a fixed threshold with strictly positive valuations. The prover correctly avoids inferring hardness from nonconvexity.

9. What remains necessary

There are no identified false steps or substantive gaps in the partial results. Nevertheless, the target remains unresolved for fixed \(\ell\geq2\) with unrestricted numbers of goods and types.

To complete the assigned task, the prover must supply either:

a polynomial-time algorithm that resolves the support-selection step; or
a hardness reduction that respects additive PMMS benchmarks and continuous allocation masses.

That is missing substantive mathematics, rather than a clarification of an existing proof. The current write-up accurately labels itself partial and does not claim otherwise.