Answer: \(\mathrm{NP}\)-hard
— class:
Given \(m\) ordered indivisible items, a finite library \(T\) of complete additive utility types, rational society distribution \(\mu\), privacy atom \(\delta=1/N\), \(\varepsilon\), and \(\beta\), what is the minimum \(c\) for an \(\varepsilon\)-DP randomized mass allocation \(x\) over whole connected intervals satisfying \(\sum_I x_{t,I}=\mu_t\), \(\sum_{t,I \text{ containing } j} x_{t,I}=\delta\), \(\mathrm{PROP}_c\) for every supported type-bundle pair, and adjacency \(\mu'=\mu+\delta(e_{t'}-e_t)\) when types differ on one item?
Let [0m\(\mathcal T\subseteq\{0,1\}^d\) be a finite type catalogue; type \(t\) values an integral bundle \(b\in\mathbb Z_{\ge0}^d\) by \(u_t(b)=t\cdot b\). An admissible society is \(\mu\in\eta\mathbb Z_{\ge0}^{\mathcal T}\) with \(\sum_t\mu_t=1\), where \(\eta=1/N\) and \(N\rho\in\mathbb Z_{\ge0}^d\).
A kernel \(q\) has \(q_{t,b}\ge0\), \(\sum_bq_{t,b}=1\), and supply balance \(\sum_t\mu_t\sum_bq_{t,b}b=\rho\). It is \(\mathrm{EF}_c\) if, whenever \(\mu_tq_{t,b}>0\) and \(\mu_{t'}q_{t',b'}>0\), some \(x\in\mathbb Z_{\ge0}^d\) satisfies \(x\le b'\), \(\|x\|_1\le c\), and \(u_t(b)\ge u_t(b'-x)\).
A randomized mechanism \(\mathcal M\) is \(\varepsilon\)-DP if for every mass-step neighbors \(\mu' =\mu+\eta(e_{t'}-e_t)\) and every output event \(E\), \(\Pr[\mathcal M(\mu)\in E]\le e^\varepsilon\Pr[\mathcal M(\mu')\in E]\).
Is deciding whether such a mechanism exists, with a \(\mathrm{EF}_c\), supply-balanced kernel output with probability at least \(1-\beta\) for every admissible \(\mu\), in \(\mathrm P\) or \(\mathrm{NP}\)-hard?
For finite lists of agents with binary additive utilities and agent-level adjacency, a pure \(\varepsilon\)-DP mechanism cannot guarantee \(\mathrm{EF}_c\) at high probability for \(c=\Theta\!\left(\sqrt{\frac mn\min\{\log n,\frac mn\}}\right)\).
That lower bound concerns discrete agent lists, not the distribution-over-types problem above.
Under the standard explicit-input interpretation—where \(d\), \(\mathcal T\), \(N\), \(N\rho\), \(c\), \(\varepsilon\), and \(\beta\) are encoded as part of the instance—the decision problem is \(\mathrm{NP}\)-hard.
The reduction below fixes \(N=2\), \(c=0\), and \(\varepsilon=1\), uses \(\rho=(1/2,\ldots,1/2)\), and has an inverse-polynomial positive failure probability. It does not establish membership in \(\mathrm{NP}\), nor hardness when \(c\geq1\) and \(\beta\) are fixed positive constants.
For binary \(t\), the condition for bundles \(b,b'\) is equivalent to
\(t\cdot b+c\geq t\cdot b'\).
Indeed, necessity follows from \(t\cdot x\leq\lVert x\rVert_1\leq c\). Conversely, if \(k=\max\{0,t\cdot b'-t\cdot b\}\leq c\), then \(t\cdot b'\) counts the units of \(b'\) in coordinates valued by \(t\). We may therefore choose \(x\leq b'\), supported on these coordinates, with \(\lVert x\rVert_1=k\). Then \(t\cdot(b'-x)\leq t\cdot b\).
In particular, \(\mathrm{EF}_0\) simply requires \(t\cdot b\geq t\cdot b'\).
Let \(X\) be the finite set of admissible societies, and let \(S_\mu\) denote the set of kernels that are supply-balanced and \(\mathrm{EF}_c\) for \(\mu\).
For \(\mu,\nu\in X\), let
\(\delta(\mu,\nu)=\frac12\lVert N\mu-N\nu\rVert_1\).
This is the distance in the mass-step adjacency graph. Repeated application of differential privacy gives group privacy:
\(\Pr[\mathcal M(\mu)\in E]\leq e^{\varepsilon\delta(\mu,\nu)}\Pr[\mathcal M(\nu)\in E]\).
Fix \(\mu_0\in X\). Since \(\Pr[\mathcal M(\nu)\notin S_\nu]\leq\beta\), group privacy and the union bound give
\(\Pr[\mathcal M(\mu_0)\in\bigcap_{\nu\in X}S_\nu]\geq1-\beta\sum_{\nu\in X}e^{\varepsilon\delta(\mu_0,\nu)}\).
Consequently, if
\(\beta\sum_{\nu\in X}e^{\varepsilon\delta(\mu_0,\nu)}<1\),
then \(\bigcap_{\nu\in X}S_\nu\neq\varnothing\): some single kernel works for every society.
For \(\beta=0\), this yields the exact equivalence:
The reverse implication uses the input-independent mechanism that always outputs that kernel.
Let
\(R=\{z\in\{0,1\}^4:z_1+z_2+z_3+z_4=2\}\).
The constraint problem \(\operatorname{SAT}(\{R\})\) is \(\mathrm{NP}\)-complete by Schaefer’s dichotomy theorem. Its hypotheses can be checked directly:
These exclude all tractable cases in the dichotomy. See [Schaefer, “The Complexity of Satisfiability Problems”](https://doi.org/10.1145/800133.804350).
Consider an \(R\)-SAT instance with variables \(z_1,\ldots,z_n\).
For every Boolean variable \(z_i\), introduce two goods coordinates \(g_i^1,g_i^0\). Thus \(d=2n\). Set
\(N=2\), \(\rho_j=1/2\) for every coordinate, \(c=0\), and \(\varepsilon=1\).
Hence \(N\rho\) is the all-ones integral vector.
For each \(i\), introduce the type \(p_i\) that values exactly \(g_i^1\) and \(g_i^0\). Its target value at \(\rho\) is
\(p_i\cdot\rho=1\).
The equation \(p_i\cdot b=1\), together with \(b\in\mathbb Z_{\geq0}^{2n}\), forces exactly one of \(b_{g_i^1},b_{g_i^0}\) to equal \(1\).
For a constraint \(R(z_a,z_b,z_c,z_d)\) on four distinct variables, introduce the type that values \(g_a^1,g_b^1,g_c^1,g_d^1\). Its target value is \(2\).
Repeated variables can also be handled:
Thus every constructed type has Hamming weight \(2\) or \(4\). Duplicate types can be removed without changing feasibility.
Let \(s=|\mathcal T|\). With \(N=2\), the number of admissible societies is
\(K=\binom{s+1}{2}\).
Set
\(\beta=\frac1{16K}>0\).
The construction has polynomial size.
Suppose the \(R\)-SAT instance has a satisfying assignment \(a\).
Define \(b^a\in\{0,1\}^{2n}\) by
\(b^a_{g_i^1}=a_i\) and \(b^a_{g_i^0}=1-a_i\).
Every weight-\(2\) type evaluates \(b^a\) to \(1\), and every constraint type evaluates it to \(2\). Because exact-\(2\)-in-\(4\) constraints are preserved by complementing every variable, \(\mathbf1-b^a\) has exactly the same value for every constructed type.
For every \(t\in\mathcal T\), define
\(q_{t,b^a}=q_{t,\mathbf1-b^a}=1/2\).
Then every marginal has expectation
\(\frac12b^a+\frac12(\mathbf1-b^a)=\rho\).
Therefore, for every society \(\mu\),
\(\sum_t\mu_t\sum_bq_{t,b}b=\sum_t\mu_t\rho=\rho\).
Every supported bundle has the same value for every type, so the kernel is \(\mathrm{EF}_0\). The input-independent mechanism that always outputs \(q\) is \(0\)-DP and succeeds with probability \(1\).
Suppose a mechanism satisfying the constructed instance exists.
For \(N=2\), every pair of societies has distance at most \(2\). Hence
\(\beta\sum_{\nu\in X}e^{\delta(\mu_0,\nu)}\leq\frac1{16K}Ke^2=\frac{e^2}{16}<1\).
By Section 2, there exists a kernel \(q\) successful for every admissible society.
Fix a type \(r\). In the pure society \(\mu=e_r\), supply balance gives
\(\sum_bq_{r,b}b=\rho\).
Because this society is \(\mathrm{EF}_0\), all bundles in the support of \(q_r\) have the same \(r\)-value. Its expectation is \(r\cdot\rho\), so
\(r\cdot b=r\cdot\rho\)
for every \(b\) with \(q_{r,b}>0\).
Now take any type \(s\) and the society assigning mass \(1/2\) to \(r\) and \(1/2\) to \(s\). For \(b\in\operatorname{supp}(q_r)\) and \(b'\in\operatorname{supp}(q_s)\), \(\mathrm{EF}_0\) gives
\(r\cdot b'\leq r\cdot b=r\cdot\rho\).
On the other hand, supply balance in the pure society \(e_s\) gives \(\mathbb E_{q_s}[b']=\rho\), and hence
\(\mathbb E_{q_s}[r\cdot b']=r\cdot\rho\).
A random variable bounded above by its expectation must equal that expectation almost surely. Therefore every supported \(b'\) satisfies
\(r\cdot b'=r\cdot\rho\).
Since \(r\) was arbitrary, every bundle in the support of every marginal satisfies all constructed equations.
Choose any supported bundle \(b'\). The Booleanity equations imply
\(b'_{g_i^1}+b'_{g_i^0}=1\)
for every \(i\). Thus these coordinates encode a Boolean assignment. The constraint equations say that exactly two variables in every \(R\)-constraint are true. Hence the original \(R\)-SAT instance is satisfiable.
This proves soundness and completes the polynomial reduction.
Therefore the general variable-parameter decision problem is \(\mathrm{NP}\)-hard, even with \(N=2\), \(c=0\), fixed finite \(\varepsilon\), binary supplies, and \(\beta\) inverse-polynomial.
This does not yet resolve two important restrictions:
The cited discrete lower bound is logically separate: it concerns labelled finite-agent allocations and agent-level adjacency, and is an information-theoretic impossibility rather than a computational reduction. See [Manurangsi and Suksompong, “Differentially Private Fair Division”](https://ojs.aaai.org/index.php/AAAI/article/download/25721/25493).
⟨structured verdict parsed — rendered above⟩
The prover’s central \(\mathrm{NP}\)-hardness reduction is sound. The fairness equivalence, differential-privacy intersection argument, completeness construction, and soundness extraction all check out.
The write-up has several minor rigor gaps: the repeated-variable preprocessing does not fully specify the resulting reduction, one quantified soundness step implicitly assumes two distinct types, and the invoked closure characterizations behind Schaefer’s theorem are not stated. These are expositional repairs and do not require new mathematical ideas.
The equivalence
\[ t\cdot b+c\geq t\cdot b' \]
with the original \(\mathrm{EF}_c\) condition is correct for binary \(t\).
For necessity, any admissible \(x\) satisfies
\[ t\cdot x\leq \lVert x\rVert_1\leq c. \]
For sufficiency, the proposed quantity
\[ k=\max\{0,t\cdot b'-t\cdot b\} \]
is an integer and does not exceed \(t\cdot b'\). Thus \(k\) units can indeed be removed from coordinates with \(t_j=1\), respecting \(x\leq b'\). The specialization to \(c=0\) is valid.
The histogram distance
\[ \delta(\mu,\nu)=\frac12\lVert N\mu-N\nu\rVert_1 \]
is the graph distance under one-unit mass transfers. Iterating pure differential privacy along a shortest path gives the stated group-privacy inequality.
Applying it to \(S_\nu^c\) gives
\[ \Pr[\mathcal M(\mu_0)\notin S_\nu] \leq e^{\varepsilon\delta(\mu_0,\nu)}\beta. \]
The finite union bound therefore yields the claimed lower bound on the probability of \(\bigcap_\nu S_\nu\). If that probability is positive, the intersection is nonempty. The equivalence asserted for \(\beta=0\) is also correct.
This step implicitly assumes that each success set \(S_\nu\) is a measurable output event. That is already implicit in the problem’s probabilistic success requirement, so it does not create a separate defect.
The relation \(R\) is correctly shown to be outside all six tractable classes of Schaefer’s dichotomy:
Consequently, \(\operatorname{SAT}(\{R\})\) is \(\mathrm{NP}\)-complete by [Schaefer’s dichotomy theorem](https://doi.org/10.1145/800133.804350).
The write-up does not explicitly state the closure characterizations connecting these counterexamples to the six syntactic classes. Under the verification standard requested, that is a minor omission: the prover should state that Horn, dual-Horn, bijunctive, and affine Boolean relations are respectively closed under coordinatewise conjunction, disjunction, majority, and ternary XOR.
The construction uses \(d=2n\), at most polynomially many explicitly represented types, \(N=2\), rational supply \(\rho_j=1/2\), and fixed \(c=0\), \(\varepsilon=1\).
For \(s=|\mathcal T|\), the number of admissible societies is correctly calculated as
\[ K=\binom{s+1}{2}. \]
The rational number \(\beta=1/(16K)\) has polynomial encoding length. Thus the reduction has polynomial size under the stated explicit-input interpretation.
The claimed logical equivalences are correct:
\[ R(x,x,y,z)\iff (x+y=1)\land(x+z=1), \]
and
\[ R(x,x,y,y)\iff x+y=1. \]
The multiplicity patterns \(R(x,x,x,y)\) and \(R(x,x,x,x)\) are indeed unsatisfiable.
There is nevertheless a minor specification gap. The reduction only explicitly defines the type for constraints on four distinct variables. It should explicitly say that an equation such as \(x+y=1\) is replaced by the weight-\(2\) type valuing \(g_x^1\) and \(g_y^1\). It also refers to a “fixed no-instance” without exhibiting one or establishing that the chosen target instance is a no-instance. As written, the many-one reduction is not completely defined on source instances containing the unsatisfiable repetition patterns.
Given a satisfying Boolean assignment \(a\), the bundles \(b^a\) and \(\mathbf 1-b^a\) satisfy:
Complementing all variables preserves these values. Consequently, every constructed type gives the two supported bundles equal utility.
The kernel placing probability \(1/2\) on each bundle has marginal expectation \(\rho\) for every type. It is therefore supply-balanced for every society and satisfies \(\mathrm{EF}_0\). The constant mechanism is \(0\)-DP. Completeness is correct.
With \(N=2\), the maximum histogram distance is \(2\). Therefore
\[ \beta\sum_{\nu\in X}e^{\delta(\mu_0,\nu)} \leq \frac{e^2}{16}<1. \]
The common-kernel lemma is consequently applicable.
For a pure society \(e_r\), supply balance gives
\[ \mathbb E_{q_r}[b]=\rho. \]
The two directed \(\mathrm{EF}_0\) comparisons between any two supported bundles imply that their \(r\)-values are equal. Their common value must therefore be \(r\cdot\rho\).
For distinct types \(r\) and \(s\), the society \(\frac12e_r+\frac12e_s\) is admissible. Its fairness condition yields
\[ r\cdot b'\leq r\cdot\rho \]
for every \(b'\in\operatorname{supp}(q_s)\). Pure-society balance for \(s\) gives
\[ \mathbb E_{q_s}[r\cdot b']=r\cdot\rho. \]
Since the random variable is integrable and bounded above by its expectation, equality holds almost surely. Because every support point has positive probability, equality holds at every support point.
The text says “take any type \(s\)” without separating the case \(s=r\). If \(s=r\), the purported half-\(r\), half-\(s\) society is just the pure society, but the required equality was already established in the preceding paragraph. This is a minor quantifier clarification, not a substantive gap.
It follows that every supported bundle satisfies every constructed type equation. The Booleanity equations force each coordinate pair to be either \((1,0)\) or \((0,1)\), and the constraint equations then give a satisfying exact-\(2\)-in-\(4\) assignment. Soundness is correct.
The final conclusion accurately limits the result to the variable-parameter problem, with \(c=0\) and inverse-polynomial \(\beta\). It does not claim hardness for fixed positive \(c\) or constant positive \(\beta\), nor membership in \(\mathrm{NP}\).
The ancillary round-robin observation is consistent with the standard \(\mathrm{EF}_1\) property of round-robin allocations for nonnegative additive utilities. It is not used in the hardness proof.
⟨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.