Answer: polynomial-time solvable
Proposition 4.4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any set of valuations $v\in \bR_+^n$ (\ie, on an instance-by-instance basis) FairQuery achieves the optimal accuracy given budget $B$, among the set of all truthful, individually rational envy-free fixed purchase mechanisms.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a population scale \(N\), budget \(B\), and finite-support rational distribution \(\mu\) over verified-bit, linear-cost types \((b,v)\), choose a submeasure \(\xi\le\mu\) with \(\xi_{(b,v)}=r(v)\mu_{(b,v)}\) for a common selection rate \(r(v)\in[0,1]\). Maximize selected mass \(q=\|\xi\|\) subject to \(qv_q/(1-q)\le B\) and \(q\le 1-1/N\), where \(v_q\) is the cutoff in the marginal valuation distribution and partial selection at a tie is allowed. Return the threshold allocation and payment, with per-selected-person privacy level \(\epsilon=1/[N(1-q)]\) and payment \(v_q/[N(1-q)]\), and the estimate \(\hat{s}=\int b\,d\xi+(1-q)/2+\operatorname{Lap}(1-q)\) of the normalized statistic \(\int b\,d\mu\).
A society is a probability distribution \(\mu\) on types \((b,v)\), where \(b\in\{0,1\}\) is verified and \(v\in\mathbb{Q}_{\geq0}\) gives privacy cost \(c(v,\epsilon)=v\epsilon\); using valuations incurs no privacy cost. Its input is the list of its \(\tau\) positive-mass types with binary rational masses summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; the bit-domain size is \(m=2\).
Additional inputs are a binary-encoded integer population scale \(N\geq2\) and a binary rational budget \(B\geq0\). Let \(L\) be the total input bit length; masses need not be multiples of \(1/N\).
For \(q>0\), define \(v_q=\min\{t:\mu(v\leq t)\geq q\}\). A threshold allocation is \(\xi_{(b,v)}=r(v)\mu_{(b,v)}\), with \(r(v)=1\) below \(v_q\), \(r(v)=0\) above it, and a common fractional rate at \(v_q\) chosen so that \(\|\xi\|=q\), independently of \(b\).
Maximize \(q\) subject to \(0\leq q\leq1-1/N\) and \(qv_q/(1-q)\leq B\). At \(q=0\), set \(\xi=0\), \(v_0=0\), and expenditure to zero.
Return the optimal threshold allocation and its uniform per-selected-person privacy level \(\epsilon=1/[N(1-q)]\) and payment \(p=v_q/[N(1-q)]\); unselected mass receives zero privacy and payment. Total expenditure is \(Nqp\).
The associated normalized estimate has law \(\hat{s}=\int b\,d\xi+(1-q)/2+\operatorname{Lap}(1-q)\), estimating \(\int b\,d\mu\); \(\operatorname{Lap}\) denotes centered Laplace noise with the stated scale. Return its location and scale.
Is this exact continuous threshold-allocation problem solvable in polynomial time in \(m,\tau,L\), with \(N\) encoded in binary, or is it NP-hard?
For finite lists of agents, FairQuery is a polynomial-time, truthful, individually rational, budget-feasible algorithm attaining instancewise optimal accuracy among truthful, individually rational, envy-free mechanisms that purchase the same positive privacy level from every selected agent. [Ghosh and Roth](https://arxiv.org/pdf/1011.1375)
No result settling this exact finite-support mass formulation was located in the literature search.
Theorem. The stated continuous threshold-allocation problem is exactly solvable in polynomial time in \(m,\tau,L\), with \(N\) encoded in binary. All requested outputs are rational numbers with polynomial encoding length.
The proof below follows directly from the finite-support formulation. The [Ghosh–Roth paper](https://arxiv.org/pdf/1011.1375) supplies the finite-agent context; no extension of its mechanism-design theorem is needed here.
Proof: reduction to finitely many intervals. Write the distinct supported valuations in increasing order as \(a_1<\cdots<a_k\), where \(k\leq\tau\). Define their aggregate masses and cumulative masses by
\(w_j=\sum_{(b,v):\,v=a_j}\mu_{(b,v)},\qquad C_0=0,\qquad C_j=\sum_{i=1}^{j}w_i.\)
Every \(w_j\) is positive, and \(C_k=1\). Consequently, for every \(q\in(0,1]\),
\(v_q=a_j\quad\Longleftrightarrow\quad C_{j-1}<q\leq C_j.\)
Indeed, throughout this interval the cumulative mass below \(a_j\) is insufficient to reach \(q\), whereas the cumulative mass through \(a_j\) reaches \(q\). In particular, \(q=C_j\) belongs to the interval with threshold \(a_j\), not the next interval.
Set \(h=1-1/N\). Since \(N\geq2\), we have \(0<h<1\). On the interval with threshold \(a_j\), the budget condition is
\(\frac{q a_j}{1-q}\leq B.\)
The denominator is positive for \(q\leq h\), so this condition is equivalent to
\(q(a_j+B)\leq B.\)
Define
\(\beta_j=\begin{cases}1,&a_j=0,\\[2pt]\dfrac{B}{B+a_j},&a_j>0.\end{cases}\)
If \(a_j=0\), expenditure is zero, so the budget imposes no additional restriction. If \(a_j>0\), the denominator \(B+a_j\) is strictly positive, and the budget condition is exactly \(q\leq\beta_j\). This includes \(B=0\), in which case \(\beta_j=0\).
Thus the feasible masses in the \(j\)-th interval are precisely
\((C_{j-1},t_j]\quad\text{if }t_j>C_{j-1},\qquad t_j=\min\{C_j,h,\beta_j\},\)
and there are no feasible masses in that interval if \(t_j\leq C_{j-1}\).
Exact algorithm and optimality. Sort and aggregate the input as above. Compute every \(t_j\), retaining it only when \(t_j>C_{j-1}\). Return
\(q^\star=\max\bigl(\{0\}\cup\{t_j:1\leq j\leq k,\ t_j>C_{j-1}\}\bigr).\)
Each retained candidate is feasible: it lies in its stated valuation interval and satisfies both the population cap and the budget bound. Zero is feasible by the given convention.
Conversely, let \(q>0\) be any feasible mass. There is a unique \(j\) such that \(C_{j-1}<q\leq C_j\). Feasibility gives \(q\leq h\) and \(q\leq\beta_j\), hence \(q\leq t_j\). Since \(q>C_{j-1}\), this candidate was retained. Therefore \(q\leq q^\star\).
This proves that the returned mass is feasible and dominates every feasible mass. It also proves that a maximum exists despite the jumps in the threshold valuation.
For example, take masses \(1/2,1/2\) at valuations \(1,3\), with \(N=4\) and \(B=2\). The first interval contributes \(t_1=1/2\). The second has \(\beta_2=2/5< C_1\), so it contributes nothing. Thus \(q^\star=1/2\), with expenditure \(1<B\). This illustrates why an algorithm must allow an optimum at a cumulative-mass endpoint with unused budget.
Construction of every requested output. If \(q^\star=0\), return
\(\xi=0,\qquad \epsilon=\frac1N,\qquad p=0,\qquad \text{location}=\frac12,\qquad \text{scale}=1.\)
Here \(\epsilon\) is the requested formula; no mass is selected.
If \(q^\star>0\), find the unique index \(j^\star\) satisfying
\(C_{j^\star-1}<q^\star\leq C_{j^\star}.\)
Set
\(\alpha=\frac{q^\star-C_{j^\star-1}}{w_{j^\star}}.\)
The interval inequalities imply \(0<\alpha\leq1\). Define
\(r(v)=\begin{cases} 1,&v<a_{j^\star},\\ \alpha,&v=a_{j^\star},\\ 0,&v>a_{j^\star}, \end{cases} \qquad \xi_{(b,v)}=r(v)\mu_{(b,v)}.\)
This rate depends only on \(v\), so tied valuations receive the required common fractional rate independently of \(b\). Moreover,
\(\|\xi\|=C_{j^\star-1}+\alpha w_{j^\star}=q^\star.\)
The selected mass receives the uniform levels
\(\epsilon=\frac{1}{N(1-q^\star)},\qquad p=\frac{a_{j^\star}}{N(1-q^\star)}.\)
Unselected mass receives zero privacy and payment. Total expenditure is
\(Nq^\star p=\frac{q^\star a_{j^\star}}{1-q^\star}\leq B,\)
where the inequality follows from the established feasibility of \(q^\star\).
Finally, return the location and scale
\(\ell=\sum_{(b,v)}b\,\xi_{(b,v)}+\frac{1-q^\star}{2}, \qquad s=1-q^\star.\)
Then the specified estimate has exactly the law \(\ell+\operatorname{Lap}(s)\). Since \(q^\star\leq1-1/N\), its scale satisfies \(s\geq1/N>0\).
Bit complexity. All computations can use exact integer and rational arithmetic. The following bounds establish polynomial time in the binary input length, without expanding the population into \(N\) agents.
Write each input mass as \(n_i/d_i\), with positive denominator, and let
\(D=\prod_{i=1}^{\tau}d_i.\)
The binary length of \(D\) is \(O(L)\), because the sum of the input denominator lengths is at most \(L\). Each mass can therefore be written as \(A_i/D\). Positivity and normalization give \(0<A_i\leq D\) and \(\sum_i A_i=D\). Group masses and cumulative masses consequently have denominator \(D\) and numerators of \(O(L)\) bits.
If \(B=x/y\) and \(a_j=u/z>0\), then
\(\beta_j=\frac{xz}{xz+yu}.\)
Its numerator and denominator have \(O(L)\) bits. The cap \(h=(N-1)/N\) also has \(O(L)\) bits. Every candidate \(t_j\), and hence \(q^\star\), is one of these bounds or a cumulative mass. Write \(q^\star=Q/R\), with numerator and denominator of \(O(L)\) bits.
To check the allocation sizes explicitly, suppose \(q^\star>0\), and write
\(C_{j^\star-1}=M/D,\qquad w_{j^\star}=W/D.\)
Then
\(\alpha=\frac{QD-MR}{RW}.\)
For a type at the threshold, its allocated mass is
\(\xi_i=\frac{A_i(QD-MR)}{DRW}.\)
Every integer in this expression has \(O(L)\) bits. Allocations below and above the threshold likewise have \(O(L)\)-bit representations. All allocations admit the common denominator \(DRW\), so summing the selected bit-one mass does not cause uncontrolled denominator growth. The location, scale, privacy level, and payment also have \(O(L)\)-bit rational representations.
Sorting uses \(O(\tau\log\tau)\) rational comparisons. Aggregation, candidate generation, maximization, and output construction use polynomially many arithmetic operations on integers of polynomial bit length. Integer addition, multiplication, division, and exact comparison all have polynomial bit complexity. Therefore the complete algorithm runs in polynomial time in \(\tau,L\), and hence in \(m,\tau,L\) for the stipulated \(m=2\).
The use of binary-encoded \(N\) requires only arithmetic on its binary representation; there is no iteration proportional to \(N\). This completes the proof.
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated problem correctly. The interval algorithm finds an exact optimum, constructs every requested output, and runs in polynomial time in the binary input length. No major or minor gaps were found.
The proof addresses the finite-support mass formulation directly. It does not rely on extending the cited finite-agent mechanism-design result.
Each distinct supported valuation \(a_j\) has positive aggregate mass \(w_j\). Thus the cumulative masses are strictly increasing, with \(C_0=0\) and \(C_k=1\).
The characterization
\[
v_q=a_j\quad\Longleftrightarrow\quad C_{j-1}<q\leq C_j
\]
follows from the given quantile definition for every \(q\in(0,1]\). The strict lower endpoint and inclusive upper endpoint are essential and are handled correctly: at \(q=C_j\), the threshold remains \(a_j\).
Since \(N\geq2\), the cap \(h=1-1/N\) satisfies \(0<h<1\). Consequently, \(1-q>0\) for every permitted \(q\), so multiplying the budget inequality by \(1-q\) preserves its direction.
On an interval with threshold \(a_j\), the resulting condition is exactly
\[
q(a_j+B)\leq B.
\]
The cases defining \(\beta_j\) are exhaustive and correct:
No division by zero occurs.
Intersecting the quantile interval with the population cap and budget bound gives \((C_{j-1},t_j]\) when \(t_j>C_{j-1}\), where
\[
t_j=\min\{C_j,h,\beta_j\}.
\]
If \(t_j\leq C_{j-1}\), the intersection is empty. In particular, equality at the lower endpoint does not incorrectly create a candidate.
Every retained \(t_j\) belongs to its stated quantile interval and satisfies both bounds. The additional candidate zero is feasible by the task’s explicit convention.
Conversely, every positive feasible \(q\) belongs to exactly one quantile interval. In that interval it satisfies \(q\leq t_j\), and \(q>C_{j-1}\) ensures that \(t_j\) was retained. Therefore the returned \(q^\star\) dominates every feasible mass.
This establishes both attainment and optimality, including cases where a threshold jump prevents increasing the selected mass.
For the example, \(h=3/4\), \(\beta_1=2/3\), and \(\beta_2=2/5\). Hence \(t_1=1/2\), while the second interval contributes no candidate because \(2/5<1/2\).
At \(q^\star=1/2\), expenditure is \(1\), strictly below the budget \(2\).
For positive \(q^\star\), the unique threshold index exists, and \(w_{j^\star}>0\). Thus \(\alpha\) is well-defined. The interval inequalities give \(0<\alpha\leq1\).
The constructed rate depends only on valuation, so types sharing the threshold valuation receive the same fractional rate independently of their bits. Its total allocated mass is exactly
\[
C_{j^\star-1}+\alpha w_{j^\star}=q^\star.
\]
Allocated masses are nonnegative and do not exceed their input masses.
The returned \(\epsilon\) and \(p\) match the task’s formulas. Their denominators are positive. Substituting the payment into \(Nq^\star p\) gives the established budget expression.
The location correctly sums the selected bit-one mass and adds \((1-q^\star)/2\). The scale is exactly \(1-q^\star\), with the required positive lower bound \(1/N\).
For \(q^\star=0\), the returned allocation, privacy parameter, payment, location, and scale all match the stated conventions. Reporting \(\epsilon=1/N\) is consistent with the requested formula despite there being no selected mass.
The product \(D\) of all input mass denominators has \(O(L)\) bits because its logarithm is bounded by the sum of their input bit lengths. Rewriting masses over \(D\) is exact, and positivity and normalization bound aggregate numerators by \(D\).
The displayed formula for \(\beta_j\) is algebraically correct and has numerator and denominator of \(O(L)\) bits. The population cap has the same bound. Taking minima and maxima selects existing rational values, so \(q^\star\) also has an \(O(L)\)-bit representation.
The displayed formulas for \(\alpha\) and threshold allocations are correct. Their integer factors have \(O(L)\) bits. The common denominator \(DRW\) also represents allocations below and above the threshold, supporting the claimed bound for the selected bit-one sum and location. The remaining output formulas involve only a fixed number of arithmetic operations on such rationals.
Sorting and all subsequent steps require polynomially many exact arithmetic operations on integers of polynomial bit length. There is no iteration proportional to the numerical value of \(N\), and no assumption that masses are multiples of \(1/N\).
No repair or additional clarification is needed. The proof establishes polynomial-time exact solvability for the stipulated \(m=2\); it makes no unsupported claim about additional mechanism-design properties.
⟨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.