Answer: \(\mathrm{R3SAT}\)-hard to approximate within \(O((\log(2+\tau))^{\epsilon_0})\) for some constant \(\epsilon_0>0\), even when \(s=B\).
Theorem 11 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateApproximating (GENERAL,ITEM)-pricing within O (logε n), for some ε > 0, is R3SAT-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(\tau\) types with rational masses \(\mu_t\) summing to \(1\), valuation schedules \(v_t(j)\) for integral bundle sizes \(j\in\{0,\ldots,B\}\), and rational per-capita supply \(s\), choose a common item price \(p\ge0\) and mass shares \(q_{t,j}\ge0\). Require \(\sum_j q_{t,j}=1\), \(\sum_t\mu_t\sum_j j q_{t,j}\le s\), \(q_{t,j}>0\Rightarrow v_t(j)-pj\ge0\), and \(v_t(j)-pj\ge v_t(k)-pk\) whenever \(q_{t,j}>0\) and \(q_{u,k}>0\). Maximize \(p\sum_t\mu_t\sum_j j q_{t,j}\). What is the complexity, in \(B,\tau\), and input bit length \(L\), of finding an optimum; in particular, is approximation within \(O((\log\tau)^\epsilon)\) R3SAT-hard for some \(\epsilon>0\)?
A society is given by its support: the list of the \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). The parameter \(\tau\) is the support size, not the number of possible types.
Input also includes an integer maximum bundle size \(B\ge1\), explicitly tabulated binary-rational valuations \(v_t(j)\ge0\) for \(j\in\{0,\ldots,B\}\), with \(v_t(0)=0\), and positive binary-rational per-capita supply \(s\). Valuations need not be monotone. Write \(m:=B\) and let \(L\) be the total input bit length; running times are measured in \(B,\tau,L\).
Choose a common real item price \(p\ge0\) and real conditional mass shares \(q_{t,j}\ge0\), satisfying \(\sum_{j=0}^{B}q_{t,j}=1\) and \(\sum_t\mu_t\sum_{j=0}^{B}j q_{t,j}\le s\). Each individual receives an integral bundle; shares split a type's population between bundle sizes.
Require individual rationality \(q_{t,j}>0\Rightarrow v_t(j)-pj\ge0\) and pair envy-freeness \(q_{t,j}>0\land q_{u,k}>0\Rightarrow v_t(j)-pj\ge v_t(k)-pk\), for all types and sizes, including \(t=u\) and size \(0\). Ties may be resolved by the seller. Revenue is \(R(p,q)=p\sum_t\mu_t\sum_{j=0}^{B}j q_{t,j}\); let \(\mathrm{OPT}\) be its maximum over feasible outcomes.
Here R3SAT-hardness means that a polynomial-time approximation would contradict the following random-formula hypothesis: for every fixed \(\delta>0\) and sufficiently large constant \(\Delta\), no randomized polynomial-time algorithm labels at least half of random formulas on \(N\) variables with \(\Delta N\) clauses as typical, while labeling every formula with at least \((1-\delta)\Delta N\) simultaneously satisfiable clauses as exceptional with exponentially small error. Random formulas independently sample each literal uniformly. [Hardness convention](https://www.cs.cornell.edu/~pbriest/papers/uniformBudgets.pdf).
Is approximating \(\mathrm{OPT}\) within \(O((\log(2+\tau))^\epsilon)\) R3SAT-hard for some \(\epsilon>0\), or can algorithms polynomial in \(B,\tau,L\) attain this ratio for every fixed \(\epsilon>0\)?
For finite societies with \(n\) buyers, general valuations and common item pricing, approximation within \(O((\log n)^\epsilon)\) is R3SAT-hard for some \(\epsilon>0\), even with unlimited supply. [Discrete hardness](https://ojs.aaai.org/index.php/AAAI/article/download/11438/11297).
The discrete problem admits a polynomial-time \(O(\log n)\)-approximation. [Discrete algorithm](https://ricerca.univaq.it/retrieve/e2188bfa-63a3-f28d-e053-d805fe0ac2bb/envyfree-944-revised.pdf). No published result settling the approximation question for exactly the mass-allocation model above was found.
1. Result
There exists a constant \(\epsilon_0>0\) such that approximating the stated mass-allocation problem within \(O((\log(2+\tau))^{\epsilon_0})\) is R3SAT-hard. This holds already when \(s=B\), so supply never binds.
The key fact is that, with nonbinding supply, population splitting cannot improve optimal revenue over deterministic allocation to each type.
2. Removing population splitting
Lemma. Suppose \(s\ge B\). Every feasible outcome \((p,q)\) can be replaced, at the same price, by a feasible outcome assigning one bundle size to each type and earning at least as much revenue.
Proof. For each type \(t\), define its nonempty allocation support and largest assigned size by
\(\displaystyle A_t=\{j:q_{t,j}>0\},\qquad x_t=\max A_t.\)
Assign size \(x_t\) to the entire population of type \(t\).
Individual rationality follows because \(x_t\in A_t\). For every pair of types \(t,u\), the original pair envy-freeness constraint applied to \(x_t\in A_t\) and \(x_u\in A_u\) gives
\(\displaystyle v_t(x_t)-px_t\ge v_t(x_u)-px_u.\)
Thus the new outcome is pair envy-free. Its expected quantity satisfies
\(\displaystyle \sum_t\mu_t x_t\le B\sum_t\mu_t=B\le s,\)
so it also satisfies supply. Finally, since \(p\ge0\) and every size in \(A_t\) is at most \(x_t\),
\(\displaystyle p\sum_t\mu_t x_t\ge p\sum_t\mu_t\sum_{j=0}^{B}j q_{t,j}.\)
This proves the lemma. In particular, the argument applies at ties without requiring any perturbation. ∎
3. An exact reduction with dyadic masses and distinct support types
Consider a discrete instance with \(n\) buyers, valuations \(v_i(0),\ldots,v_i(B)\), and nonbinding supply. Write \(\operatorname{OPT}_{D}\) for its maximum pair envy-free revenue.
Let
\(\displaystyle Q=2^{\lceil\log_2 n\rceil}.\)
Add \(Q-n\) dummy buyers whose valuation is zero at every size. Group the resulting buyers by their complete valuation vectors. For each distinct vector \(t\), let \(c_t\) be its multiplicity and define
\(\displaystyle \mu_t=\frac{c_t}{Q}.\)
The mass instance uses these distinct vectors as its support, the same maximum bundle size \(B\), and supply \(s=B\). Consequently:
I claim that this reduction satisfies
\(\displaystyle \operatorname{OPT}_{M}=\frac{\operatorname{OPT}_{D}}{Q}.\)
From discrete outcomes to mass outcomes. Start with any feasible discrete outcome. Give every dummy buyer size \(0\). This preserves pair envy-freeness: an original buyer weakly prefers its allocation to size \(0\) by individual rationality, while a dummy buyer values another buyer’s size \(j\) at utility \(-pj\le0\).
Within each valuation group, define \(q_{t,j}\) as the fraction of its augmented buyers assigned size \(j\). Every positive share therefore corresponds to an actual assigned bundle. The discrete pair envy-freeness inequalities imply all required mass inequalities, including comparisons between two sizes assigned within the same type. For an identical size compared with itself, the inequality is equality.
Supply is automatic because \(s=B\). The resulting mass revenue is exactly the original discrete revenue divided by \(Q\). Hence
\(\displaystyle \operatorname{OPT}_{M}\ge\frac{\operatorname{OPT}_{D}}{Q}.\)
From mass outcomes to discrete outcomes. Take any feasible mass outcome with revenue \(R\). Apply the lemma, obtaining sizes \(x_t\) and revenue \(R'\ge R\).
If \(p>0\), individual rationality forces any identically zero valuation type to receive size \(0\), since \(-px_t\ge0\). Assign each original buyer the size chosen for its valuation type. These assignments are individually rational and pair envy-free by the lemma. Dummy buyers contribute zero, so the discrete revenue is
\(\displaystyle p\sum_{i=1}^{n}x_{t(i)} =p\sum_t c_t x_t =Q R' \ge Q R.\)
If \(p=0\), then \(R=0\), and assigning every original buyer size \(0\) supplies the required discrete outcome.
Thus every feasible mass revenue yields a discrete revenue at least \(Q\) times larger, proving the reverse inequality and the claimed equality.
Both transformations take polynomial time. They also show that any approximation factor for the mass instance transfers unchanged to the discrete instance.
4. Checking the published hardness theorem’s encoding
The invoked discrete result is Theorem 11 of [*On Social Envy-Freeness in Multi-Unit Markets*](https://cdn.aaai.org/ojs/11438/11438-13-14966-1-2-20201228.pdf): for some \(\epsilon_0>0\), approximation within \(O((\log n)^{\epsilon_0})\) is R3SAT-hard for general valuations and common item pricing under pair envy-freeness, even with unlimited supply.
Its hard instances meet the present explicit-table requirement. The construction starts from \(M\) sets over a universe \(U\), uses \(\kappa=O(\log M)\) classes, and creates at most \(M2^\kappa\) buyers. Its nonzero valuations are integers, and every positively valued size is at most \(2^\kappa|U|\). Thus the entire valuation table through
\(\displaystyle B=2^\kappa|U|\)
has polynomial size. Larger sizes have zero valuation: at positive prices, individual rationality excludes them, and at price zero they earn no revenue. Restricting to this \(B\) therefore preserves the optimum.
The hardness convention agrees with the question’s randomized, exponentially small error convention; see Hypothesis 1 and Definition 3 in [Briest’s paper](https://www.cs.cornell.edu/~pbriest/papers/uniformBudgets.pdf).
5. Transferring the approximation barrier
Suppose an algorithm polynomial in \(B,\tau,L\) always produces revenue at least
\(\displaystyle \frac{\operatorname{OPT}_{M}}{C(\log(2+\tau))^{\epsilon_0}}\)
for some constant \(C\).
Apply it to the mass instance constructed above, then convert its output to a discrete outcome. The resulting discrete revenue is at least
\(\displaystyle \frac{Q\operatorname{OPT}_{M}}{C(\log(2+\tau))^{\epsilon_0}} = \frac{\operatorname{OPT}_{D}}{C(\log(2+\tau))^{\epsilon_0}}. \)
Because \(\tau\le n+1\),
\(\displaystyle \log(2+\tau)\le\log(n+3)=O(\log n).\)
The resulting algorithm would therefore be a polynomial-time \(O((\log n)^{\epsilon_0})\)-approximation for the discrete hard instances, contradicting the stated random-formula hypothesis.
This settles the requested alternative: the hardness transfers to support size despite allowing population splitting.
⟨structured verdict parsed — rendered above⟩
The claimed hardness transfer is correct. The population-splitting lemma and both directions of the reduction preserve the required feasibility conditions and revenue comparison. The cited theorem also supplies hard instances compatible with the explicit valuation-table encoding. I found no major or minor issues.
Each allocation support \(A_t\) is nonempty because its nonnegative shares sum to \(1\). It is finite, so \(x_t=\max A_t\) exists and belongs to \(A_t\).
Individual rationality therefore holds for the selected size. For every ordered pair \(t,u\), the original envy constraint applies to the two selected positive-share sizes. This proves the required envy inequality after replacement. When \(t=u\), the replacement assigns only one size, and the remaining self-comparison is equality.
The supply calculation is correct: each \(x_t\le B\), and the masses sum to \(1\), so total per-capita quantity is at most \(B\le s\).
Finally, the maximum supported size is at least the original conditional expected size. Multiplication by the nonnegative price preserves the inequality. This includes \(p=0\) and requires no strict preferences or tie perturbations.
Finding: The lemma is fully proved under its stated hypothesis \(s\ge B\).
For \(n\ge1\), the chosen power of two satisfies \(n\le Q<2n\). Adding \(Q-n\) zero-valuation buyers therefore increases the buyer count only polynomially.
Grouping complete valuation vectors produces positive integer multiplicities summing to \(Q\). Consequently, the masses \(c_t/Q\) are positive dyadic rationals summing to \(1\), with the claimed bit-length bound. There are at most \(n\) original distinct vectors and one additional dummy vector, giving \(\tau\le n+1\). If the zero vector already occurs, it is correctly merged.
Setting \(s=B\) satisfies the positive-supply requirement and makes supply nonbinding.
Finding: The constructed input satisfies the task’s support and encoding requirements.
Assigning dummy buyers size \(0\) preserves individual rationality. Original buyers weakly prefer their allocation to size \(0\) by their existing individual rationality. Dummy buyers weakly prefer size \(0\) to every other assigned size because \(p\ge0\).
Every positive grouped share has an actual buyer witnessing that assigned size. Comparisons between different assigned sizes in the same valuation group follow from the discrete pair constraints between their corresponding buyers. Comparisons of a size with itself are equality.
The revenue normalization by \(Q\) is exact.
Finding: The inequality \(\operatorname{OPT}_M\ge\operatorname{OPT}_D/Q\) is justified.
The lemma provides deterministic sizes with mass revenue \(R'\ge R\). At positive price, individual rationality forces every zero-valuation type to receive size \(0\). Thus deleting dummy buyers removes no revenue, even when their valuation group contains original buyers.
Assigning each original buyer its type’s selected size preserves individual rationality and every pair envy inequality. The identity
\(p\sum_i x_{t(i)}=p\sum_t c_t x_t=QR'\)
is valid because dummy contributions vanish.
At \(p=0\), the original mass revenue is zero. Assigning all original buyers size \(0\) is feasible and supplies the required revenue comparison.
Finding: The reverse optimum inequality and the exact equality \(\operatorname{OPT}_M=\operatorname{OPT}_D/Q\) are established.
The cited Theorem 11 concerns general valuations, common item pricing, and classical pair envy-freeness. Its proof explicitly establishes hardness with unlimited supply and chooses logarithmically many separability classes. The paper’s definitions include nonnegative valuations, zero valuation at size \(0\), nonnegative prices, and individual rationality. These match the reduction’s source problem. [Published theorem and definitions](https://cdn.aaai.org/ojs/11438/11438-13-14966-1-2-20201228.pdf).
The construction confirms the stated buyer-count bound, integer valuations, and upper bound \(2^\kappa|U|\) on positively valued sizes. Since \(\kappa=O(\log M)\), explicit tabulation has polynomial size and polynomial bit length. Excluding larger sizes preserves positive-price outcomes by individual rationality; zero-price outcomes have zero revenue.
Briest’s Hypothesis 1 uses independently uniform literal sampling and the randomized exceptional-formula guarantee with exponentially small error. Definition 3 specifies the corresponding hardness convention. The prover’s identification with the task’s hypothesis is justified. [Hypothesis 1 and Definition 3](https://www.cs.cornell.edu/~pbriest/papers/uniformBudgets.pdf).
Finding: The cited theorem is applicable with the required encoding and hardness convention.
The outcome conversion preserves the approximation factor because the optima differ by exactly \(Q\). The inequality \(\tau\le n+1\) gives the required logarithmic comparison for \(n\ge2\); the isolated case \(n=1\) has no effect on asymptotic hardness.
Polynomial running time in \(B,\tau,L\) remains polynomial on the explicitly tabulated hard instances. Zero optimum and zero returned revenue introduce no invalid division in the argument.
Finding: The output resolves the requested alternative: the stated support-size approximation barrier transfers, already with nonbinding supply. No repair or additional mathematical clarification is needed.
⟨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.