Answer: —
Theorem 3.9 — class: algorithmic
Given total population mass \(N\), data categories \(j\in[h]\), known finite-support conditional cost laws \(F_j\), privacy parameter \(\epsilon\), a fixed privacy-unit mass \(\delta\), and the paper’s common Bayesian belief \(G\), design a randomized contract and estimator that work for every hidden category-mass vector \(\theta\) with \(\sum_j\theta_j=N\). Require BIC and EIIR for each privacy unit, \(\epsilon\)-differential privacy when one unit changes data category and its cost is redrawn from the corresponding \(F_j\), perfect-data-privacy compensation under \(G\), and \(\Pr[|\hat\theta_1-\theta_1|\ge K]\le 1/3\); minimize expected total payment for the prescribed accuracy \(K\).
A society is an atomless population of total mass \(N\), represented by its support: the \(\tau\) types \((j,v)\) with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. The support and masses are private and accessible only through participation.
There are \(m=h\ge2\) categories. Public conditional cost laws \(F_j\) have finite support of nonnegative rational costs and rational probabilities; a hidden category vector satisfies \(\theta_j\ge0\) and \(\sum_j\theta_j=N\), and type \((j,v)\) has mass \(\theta_j\Pr_{F_j}[v]\).
Public rational parameters satisfy \(N>0\), \(0<\delta\le N\), \(\epsilon>0\), \(0<K<N/2\), and \(B\ge0\). Masses are divisible and need not be multiples of \(\delta\). A privacy unit is a block of mass \(\delta\); costs and payments are densities per unit mass.
A randomized indirect contract offers category-dependent expected payments before requesting information. Participants accept or reject; categories are verifiable only with consent, and costs need not be reported. Acceptance at indifference is prescribed by the contract. Transfers may be signed, with finite absolute expectation, and total payment is their mass integral.
The common belief \(G\) is supplied explicitly as a finite rational prior over labelled finite-support population profiles. Write \(x=1\) wherever the mechanism's transcript changes its posterior about a participant's category from its prior under \(G\), including inference from rejection; utility density is \(p-\epsilon vx\). Perfect-data-privacy compensation requires conditional expected payment density at least \(\epsilon v\) wherever \(x=1\).
Require the prescribed acceptance strategy to be a Bayesian equilibrium and EIIR for every type, with expectations over contract randomness and the conditional cost beliefs. These requirements apply to every hidden category-mass vector, including profiles outside the support of \(G\).
Privacy adjacency transfers one tagged block of mass \(\delta\) from category \(j\) to category \(k\), replacing its conditional cost composition \(F_j\) by \(F_k\). Require \(\epsilon\)-differential privacy of the joint estimate and full labelled payment output under this adjacency; probabilities average over all contract randomness.
Require \(\Pr[|\hat\theta_1-\theta_1|\ge K]\le1/3\) for every hidden \(\theta\). Define the payment objective as the supremum over such \(\theta\) of expected total payment.
Is deciding whether a contract and estimator satisfying these requirements have payment objective at most \(B\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\) and the encoded parameters, where \(L\) includes the laws, prior, and rational inputs.
For finite populations, a posted-contract construction is claimed to satisfy BIC, EIIR, perfect-data-privacy compensation, differential privacy, and \(O(\epsilon^{-1})\) accuracy; this is a feasibility result, not an exact payment-minimization algorithm ([source](https://arxiv.org/pdf/1204.4031)).
The published version retains these definitions and construction ([source](https://www.cs.tau.ac.il/~fiat/cgt12/EC_2012/docs/p568.pdf)); the search identified no result settling the mass decision problem specified here.
I do not resolve the full $\mathrm{P}$ versus $\mathrm{NP}$-hardness question.
I prove an exact privacy–accuracy characterization for a substantial subclass: all costs are zero and $K\le\delta/2$. The characterization holds for arbitrarily long adjacency paths and arbitrary finite priors. I also repair the rejection-compensation problem in the previous construction and give valid upper and lower payment certificates for positive costs.
Throughout, population-level absolute integrability means that, for each admissible profile,
$$
\mathbb E\!\left[\int_I |p_i|\,d\mu(i)\right]<\infty,
$$
where $(I,\mu)$ is the labelled population space, of mass $N$.
Assume:
The dyadic assumption ensures that the profiles used in the necessity proof satisfy the mass restriction even if “binary rational” means dyadic rational.
Define
$$
n=\left\lfloor\frac N\delta\right\rfloor+1,
\qquad
c=\left\lfloor\frac{n-1}{2}\right\rfloor,
$$
and, for $a>1$, define
$$
S_n(a)=\sum_{j=0}^{n-1}a^{-|j-c|}.
$$
Theorem. Under these assumptions, a contract satisfying all the requirements exists if and only if
$$
\boxed{S_n(e^\epsilon)\le\frac32.}
$$
Whenever one exists, payment objective $0$ is achievable. Consequently, because the task assumes $B\ge0$, this inequality exactly characterizes feasibility for this subclass.
The proof requires a finite-path estimator construction, which is established next.
For each integer $n\ge2$, there is a unique $a_n>1$ satisfying
$$
S_n(a_n)=\frac32.
$$
Indeed, $S_n$ is continuous and strictly decreasing, its limit at $1$ is $n$, and its limit at infinity is $1$.
The central row has the largest geometric sum. More explicitly,
$$
S_{2s}(a)
=
1+2\sum_{k=1}^{s-1}a^{-k}+a^{-s},
$$
and
$$
S_{2s+1}(a)
=
1+2\sum_{k=1}^{s}a^{-k}.
$$
To verify maximality, write
$$
T_i(a)=\sum_{j=0}^{n-1}a^{-|i-j|}.
$$
Then
$$
T_{i+1}(a)-T_i(a)
=
a^{-(i+1)}-a^{-(n-1-i)}.
$$
Thus the sums increase towards the middle and decrease afterwards.
These formulas also show that $a_n$ increases with $n$, that $a_2=2$, and that $a_n<5$: at $a=5$, every finite sum is strictly smaller than
$$
1+2\sum_{k=1}^{\infty}5^{-k}=\frac32.
$$
Finite-path lemma. There is an $n$-by-$n$ stochastic matrix $Q$ such that
$$
Q_{ii}=\frac23
$$
and, for every adjacent pair of rows and every column,
$$
Q_{ij}\le a_n Q_{i+1,j},
\qquad
Q_{i+1,j}\le a_n Q_{ij}.
$$
Here rows represent inputs $0,\ldots,n-1$, and columns represent outputs with the same indices.
Set
$$
u=\frac23,\qquad a=a_n,\qquad b=a^{-1},
$$
and begin with
$$
H_{ij}=u b^{|i-j|}.
$$
Because the central geometric sum is $1/u$ and is maximal, every row sum of $H$ is at most $1$. Define its deficit by
$$
r_i=1-\sum_{j=0}^{n-1}H_{ij}\ge0.
$$
If $n=2s+1$, add the entire deficit in each row to column $s$:
$$
Q_{ij}=H_{ij}+r_i\mathbf 1_{\{j=s\}}.
$$
If $n=2s$, add left-half deficits to column $s$ and right-half deficits to column $s-1$:
$$
Q_{ij}
=
H_{ij}
+
\begin{cases}
r_i\mathbf 1_{\{j=s\}},&i<s,\\
r_i\mathbf 1_{\{j=s-1\}},&i\ge s.
\end{cases}
$$
Every row now sums to $1$. In the odd case, the central deficit is zero. In the even case, both central deficits are zero. No diagonal entry therefore receives a positive deficit, so every diagonal entry equals $u$.
It remains to prove the adjacent-row inequalities for the modified columns. All unmodified columns already satisfy them, because their adjacent ratios are $a$ or $a^{-1}$.
Let $n=2s+1$. Write the modified central-column entry as
$$
q_i=Q_{i,s}=1-\sum_{j\ne s}H_{ij}.
$$
For $0\le i<n-1$, direct subtraction gives
$$
a q_{i+1}-q_i
=
(a-1)\left[
1-(a+1)\sum_{\substack{j\ge i+1\\j\ne s}}H_{ij}
\right],
$$
and
$$
a q_i-q_{i+1}
=
(a-1)\left[
1-(a+1)\sum_{\substack{j\le i\\j\ne s}}H_{i+1,j}
\right].
$$
Thus it suffices to bound both sums by $1/(a+1)$.
The threshold equation gives
$$
u\sum_{k=1}^{s}b^k=\frac16.
$$
For $i\ge s$, the first sum is at most this quantity.
For $i<s$, put $\ell=s-i$. The first sum is
$$
R_i
=
\frac{u}{a-1}(1-b^{s+\ell})-u b^\ell.
$$
It increases with $\ell$, so its largest value on this side occurs at $i=0$. Comparing with the value at $i=s$ gives
$$
R_0-R_s
=
u b^s\left[
\frac{1-b^s}{a-1}-1
\right]
\le0,
$$
because $a\ge2$. Hence the first sum is always at most $1/6$. Reflection gives the same bound for the second sum.
Finally, $a<5$ implies
$$
\frac16\le\frac1{a+1}.
$$
Both required inequalities follow.
Let $n=2s$. When $s=1$, there are no deficits, and the claim follows directly from $H$.
Suppose $s\ge2$. Consider column $s$. Its entries differ from $H$ only on the left side. For $i\le s-1$, write
$$
q_i=Q_{i,s}=1-\sum_{j\ne s}H_{ij}.
$$
For $i\ge s-1$, the column equals $H$: row $s-1$ has zero deficit, and subsequent rows send their deficits to the other central column.
We therefore only need to check adjacent pairs with $0\le i\le s-2$. The same subtraction identities reduce the proof to bounding
$$
R_i=\sum_{\substack{j\ge i+1\\j\ne s}}H_{ij},
\qquad
L_i=\sum_{j\le i}H_{i+1,j}.
$$
The threshold equation is
$$
u\frac{a+1}{a-1}(1-b^s)=1.
$$
Consequently,
$$
L_i
=
\frac{u}{a-1}(1-b^{i+1})
\le
\frac{u}{a-1}(1-b^{s-1})
\le
\frac1{a+1}.
$$
For $R_i$, putting $\ell=s-i$ gives
$$
R_i
=
\frac{u}{a-1}(1-b^{s-1+\ell})-u b^\ell.
$$
This increases with $\ell$, so $R_i\le R_0$. Using the threshold equation,
$$
R_0
=
\frac{1-b^{2s-1}-(a-1)b^s}
{(a+1)(1-b^s)}
\le
\frac1{a+1}.
$$
The last inequality is equivalent to
$$
b^{2s-1}+(a-2)b^s\ge0,
$$
which holds because $a\ge2$.
This proves the inequalities for column $s$. Reflection proves them for column $s-1$, completing the finite-path lemma.
Let
$$
q=\left\lfloor\frac N\delta\right\rfloor,
$$
so $n=q+1$. Partition a fixed labelled population into $q$ tagged blocks of mass $\delta$ and a possible remainder.
For $i=0,\ldots,q$, let $D_i$ place the first $i$ blocks in category $1$ and all remaining mass in category $2$. These are admissible dyadic profiles, and consecutive profiles are adjacent. Their category-$1$ masses are $i\delta$.
Let $P_i$ be the estimate distribution under the prescribed equilibrium at $D_i$, and define
$$
A_i=\{y:|y-i\delta|<K\}.
$$
Because $2K\le\delta$, the events $A_i$ are pairwise disjoint. This includes equality: the success intervals are open.
Accuracy gives $P_i(A_i)\ge2/3$. Iterating differential privacy along the path gives
$$
P_c(A_i)
\ge
e^{-\epsilon|i-c|}P_i(A_i)
\ge
\frac23 e^{-\epsilon|i-c|}.
$$
Summing disjoint-event probabilities yields
$$
1
\ge
\sum_{i=0}^{n-1}P_c(A_i)
\ge
\frac23 S_n(e^\epsilon).
$$
Hence the displayed condition is necessary. This argument uses only the estimate marginal, so it applies to every contract satisfying the stronger joint-output privacy requirement.
Offer payment density $0$ for both acceptance and rejection, and prescribe acceptance at indifference. Since every cost is zero, every action has utility zero. Acceptance is therefore a Bayesian equilibrium, EIIR holds, and perfect-data-privacy compensation holds regardless of posterior conventions.
Under the prescribed equilibrium, all participants consent, allowing the mechanism to compute
$$
t=\theta_1.
$$
Write uniquely
$$
t=r+i\delta,
\qquad
0\le r<\delta,
\qquad
i=\left\lfloor\frac t\delta\right\rfloor.
$$
Define
$$
\ell(r)=\left\lfloor\frac{N-r}{\delta}\right\rfloor+1.
$$
The possible scalar query values with this residue form the finite path
$$
r,\ r+\delta,\ \ldots,\ r+(\ell(r)-1)\delta.
$$
If $\ell(r)=1$, release $t$. Otherwise use row $i$ of the finite-path matrix for $\ell(r)$, releasing $r+j\delta$ when column $j$ is selected.
An adjacency changes $t$ by $0$ or by $\delta$. In the latter case, the two inputs have the same residue, use the same matrix, and occupy adjacent rows. Also,
$$
\ell(r)\le n,
\qquad
a_{\ell(r)}\le a_n\le e^\epsilon.
$$
The matrix inequalities therefore prove $\epsilon$-differential privacy.
The true value is released with probability $2/3$ when $\ell(r)\ge2$, and with probability $1$ otherwise. Thus
$$
\Pr[|\hat\theta_1-\theta_1|\ge K]\le\frac13.
$$
All labelled payments are identically zero, so the joint estimate-and-payment output has the same privacy guarantee.
To complete the contract off equilibrium, release $0$ if the consenting mass is less than $N$; otherwise run the estimator on the consenting population. All transfers remain zero. These histories do not affect the equilibrium proof because every participant’s cost and utility are zero.
This establishes the theorem.
For illustration, the first thresholds are:
| $n$ | $a_n$ |
|---|---|
| $2$ | $2$ |
| $3$ | $4$ |
| $4$ | $2+\sqrt6$ |
| $5$ | $2+2\sqrt2$ |
Thus the exact privacy threshold in this subclass is $\epsilon\ge\log a_n$.
Let
$$
V=\max_j\max\operatorname{supp}(F_j),
\qquad
P=\epsilon V.
$$
Offer every category the following deterministic payment densities:
Prescribe acceptance at indifference. Verify categories only after consent.
For every completed transcript, every binary indicator $x$, and every admissible cost $v\le V$, acceptance utility satisfies
$$
2P-\epsilon vx\ge2P-\epsilon v\ge P.
$$
Rejection utility satisfies
$$
P-\epsilon vx\le P.
$$
These bounds concern the respective completed transcripts; their indicators need not agree.
Acceptance therefore weakly dominates rejection under every hidden profile and every conditional cost belief. Moreover, accepting utility is nonnegative, and either action pays at least
$$
P\ge\epsilon v.
$$
Thus EIIR and perfect-data-privacy compensation hold.
This construction avoids the verifier’s objection: it never computes a rejection transfer from a posterior indicator at an earlier transcript stage. Its incentive and compensation proofs hold for every binary assignment of the completed-transcript indicators.
Under the prescribed equilibrium, the labelled payment field is constant at $2P$, and total payment is
$$
2N\epsilon V.
$$
A simple estimator gives a rationally checkable feasibility certificate. Suppose $\epsilon\ge2$. Draw an integer $Z$ with
$$
\Pr[Z=z]=\frac23\,5^{-|z|},
\qquad z\in\mathbb Z,
$$
and release
$$
\hat\theta_1=\theta_1+\delta Z.
$$
The distribution is normalized because
$$
\frac23\left(1+2\sum_{z=1}^{\infty}5^{-z}\right)=1.
$$
Adjacent query values differ by $0$ or $\delta$. Their output supports coincide, and corresponding probability ratios are at most $5$. Since
$$
e^2>1+2+2+\frac43>5,
$$
this proves $\epsilon$-differential privacy. Constant equilibrium payments preserve joint-output privacy.
For every $K>0$, the event $Z=0$ guarantees success. Therefore failure probability is at most $1/3$.
After rejection, use the same completion rule as above: release $0$ if consenting mass is below $N$; otherwise apply this estimator to the consenting category-$1$ mass.
We obtain the valid certificate
$$
\boxed{\epsilon\ge2,\qquad B\ge2N\epsilon V
\quad\Longrightarrow\quad\text{feasible}.}
$$
It applies to arbitrary finite conditional cost laws and arbitrary supplied priors.
Fix an admissible profile. EIIR, conditional on a participant’s type, gives
$$
\mathbb E[p_i]\ge\epsilon v_i\Pr[x_i=1].
$$
Population-level absolute integrability permits Fubini’s theorem. Hence
$$
\mathbb E\!\left[\int_I p_i\,d\mu(i)\right]
\ge
\epsilon\int_I v_i\Pr[x_i=1]\,d\mu(i)
\ge0.
$$
Signed transfers therefore cannot make the payment objective negative.
A positive lower bound survives from the two-profile example, with a complete proof as follows.
Assume two categories, both costs constantly $c>0$, and prior probability $1/2$ on each of:
Let $P_0,P_1$ be the full-transcript laws, and put
$$
M=\frac{P_0+P_1}{2},
\qquad
h_r=\frac{dP_r}{dM}.
$$
Almost surely under $M$, $h_0+h_1=2$, and Bayes’ rule gives posterior probability $h_0/2$ for $D_0$.
Define
$$
U=\{h_0=h_1=1\}.
$$
On $U$, every label’s posterior category distribution equals its prior. Outside $U$, every label’s posterior changes. The restricted measures agree:
$$
P_0(\,\cdot\cap U)=P_1(\,\cdot\cap U).
$$
Write their common mass as $a$.
The success events
$$
A_0=\{|\hat\theta_1|<K\},
\qquad
A_1=\{|\hat\theta_1-N|<K\}
$$
are disjoint because $K<N/2$. Their contributions on $U$ sum to at most $a$, while their contributions outside $U$ sum to at most $2(1-a)$. Accuracy therefore implies
$$
\frac43
\le P_0(A_0)+P_1(A_1)
\le2-a.
$$
Thus $a\le2/3$, and under either profile every participant has posterior-change probability at least $1/3$. Integrating EIIR gives
$$
\boxed{\sup_\theta\mathbb E[\text{total payment}]
\ge\frac{\epsilon cN}{3}.}
$$
This proof uses only prior-supported profiles and requires no off-prior posterior convention.
Let
$$
s=\sum_{j=1}^{m}|\operatorname{supp}(F_j)|.
$$
This is the public number of possible types, whereas the private realized support size is $\tau\le s$.
Scanning the laws and checking the rational certificate in Section 4 takes a conservative
$$
O(sL^2)
$$
bit operations with schoolbook rational arithmetic. Since the laws are explicitly encoded, this is polynomial in the public input length.
For execution, let $L_{\mathrm{pop}}$ denote the encoding length of the support and masses exposed through participation. Summing the category-$1$ masses takes a conservative
$$
O\!\left(\tau(L_{\mathrm{pop}}+L)^2\right)
$$
bit operations.
The noise distribution in Section 4 is exactly samplable with an expected constant number of fair coin flips. For example, take independent geometric variables
$$
\Pr[G=k]=\frac45\,5^{-k},
\qquad k\ge0,
$$
and set $Z=G_1-G_2$. For $z\ge0$,
$$
\Pr[Z=z]
=
\sum_{k=0}^{\infty}
\left(\frac45\right)^2 5^{-(k+z)}5^{-k}
=
\frac23\,5^{-z};
$$
negative values follow by symmetry.
No execution bound solely in $m,\tau,L$ follows from the task: private mass precision is unbounded by these quantities.
For the exact zero-cost characterization, the explicit finite-path construction uses $O(n^2)$ probability entries, where
$$
n=\left\lfloor N/\delta\right\rfloor+1.
$$
This can be exponential in the binary public encoding. Furthermore, the exact threshold comparison involves $e^\epsilon$ and an algebraic threshold $a_n$. I have proved the mathematical characterization, not a polynomial bit-complexity algorithm for its exact evaluation.
The finite-population feasibility theorem in the supplied [preprint](https://arxiv.org/pdf/1204.4031) and [published version](https://www.cs.tau.ac.il/~fiat/cgt12/EC_2012/docs/p568.pdf) does not provide the missing characterization of minimum payments in this mass model.
The remaining central problem is to characterize arbitrary randomized contracts with positive costs. Optimizing the repaired construction would not suffice: a hardness reduction must exclude cheaper contracts, and a polynomial-time algorithm must cover them.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial partial results. The zero-cost characterization and the positive-cost feasibility certificate are correct as written. The payment lower bounds are correct under the stated population-level absolute-integrability condition, whose relationship to the task’s wording needs clarification. The requested $\mathrm{P}$ versus $\mathrm{NP}$-hardness classification remains unresolved, as the prover explicitly acknowledges.
The prover does not claim to solve the full task. Its exact characterization assumes zero costs, dyadic $N,\delta$, and $K\le\delta/2$. The positive-cost construction supplies a sufficient feasibility condition, while the two-profile argument supplies a lower bound.
These results engage the assigned problem, but neither an exact decision algorithm nor a hardness reduction is supplied. Thus the appropriate overall status is partial, rather than proved or refuted.
Since $0<\delta\le N$, the integer
$$
n=\left\lfloor N/\delta\right\rfloor+1
$$
satisfies $n\ge2$.
For each such $n$, the claimed continuity, strict decrease, and limiting values of $S_n(a)$ establish existence and uniqueness of $a_n>1$ with $S_n(a_n)=3/2$.
The row-sum difference
$$
T_{i+1}(a)-T_i(a)
=
a^{-(i+1)}-a^{-(n-1-i)}
$$
is correct. Its signs establish the central-row maximum, including the two equal central rows when $n$ is even.
The even and odd geometric-sum formulas are correct. They also justify that the thresholds increase with $n$, that $a_2=2$, and that $a_n<5$. Consequently, the later uses of $a_n\ge2$ and $a_n<5$ are justified.
The initial matrix $H$ has nonnegative entries and row sums at most $1$. The deficits are therefore nonnegative, and allocating them as prescribed makes $Q$ stochastic.
In the odd case, the sole modified diagonal location has zero deficit. In the even case, both central rows have zero deficit, and all other deficits are placed off the diagonal. Thus every diagonal entry remains $2/3$.
The adjacent-row inequalities for unmodified entries follow immediately from the geometric form of $H$.
For modified entries, both subtraction identities are correct. They reduce the two privacy inequalities to the stated bounds on the corresponding one-sided sums.
$$
u\sum_{k=1}^{s}b^k=\frac16.
$$
The expression for $R_i$, its increase with $\ell$, and the displayed comparison $R_0-R_s\le0$ are correct. Reflection supplies the other one-sided bound. Since $a<5$, the required comparison $1/6\le1/(a+1)$ holds.
$$
u\frac{a+1}{a-1}(1-b^s)=1
$$
is correct. It justifies the bound on $L_i$. The expression for $R_0$ is also correct, and its final inequality is equivalent to
$$
b^{2s-1}+(a-2)b^s\ge0,
$$
as asserted. The boundary between modified and unmodified rows is covered because row $s-1$ has zero deficit. Reflection covers the other modified column.
No false computation or missing substantive lemma was found in this construction.
The tagged-block profiles have total mass $N$, obey the zero-cost laws, and have dyadic type masses under the stated assumptions. Consecutive profiles are adjacent.
The success events are pairwise disjoint when $2K\le\delta$. At equality, their being open correctly prevents overlap.
Accuracy supplies $P_i(A_i)\ge2/3$. Differential privacy of the joint output implies privacy of its estimate marginal, and iteration along the path gives the displayed lower bound on $P_c(A_i)$.
Summing those disjoint-event probabilities proves
$$
S_n(e^\epsilon)\le\frac32.
$$
The argument does not require the constructed profiles to lie in the supplied prior’s support, because the task requires accuracy and privacy for every admissible profile.
With zero costs and zero transfers, every action has zero utility. Prescribed acceptance at indifference therefore gives a Bayesian equilibrium, EIIR, and compensation for every possible posterior-change indicator.
For each actual query value $t$, the residue decomposition is unique. Its index lies in the finite path defined by $\ell(r)$, and $\ell(r)\le n$.
Adjacency changes $t$ by $0$ or $\pm\delta$. A nonzero change preserves the residue and moves between adjacent rows of the same matrix. Monotonicity of the thresholds therefore justifies
$$
a_{\ell(r)}\le a_n\le e^\epsilon.
$$
The singleton-path case causes no privacy problem: it has no distinct scalar neighbor in that residue class.
The diagonal probability establishes the required success probability. Constant zero labelled payments preserve joint-output privacy.
The off-equilibrium completion rule does not invalidate the incentive argument: utilities remain zero regardless of the estimator’s behavior. No off-prior posterior convention is needed to verify this construction’s utility or compensation inequalities.
The four listed numerical thresholds are correct. This establishes the stated subclass characterization, but not its polynomial-time evaluation.
The finite public supports ensure that $V$ is finite. Every admissible cost satisfies $v\le V$, including on profiles outside the prior.
With $P=\epsilon V$, the acceptance and rejection utility bounds hold for their respective transcript indicators:
$$
2P-\epsilon vx_{\mathrm{accept}}\ge P,
\qquad
P-\epsilon vx_{\mathrm{reject}}\le P.
$$
Thus acceptance weakly dominates rejection without requiring those indicators to agree. Prescribed acceptance at indifference handles ties, including $V=0$.
Accepting utility is nonnegative, and either action receives at least $\epsilon v$. These pointwise bounds establish the required incentive, EIIR, and compensation properties independently of conditional beliefs.
Under prescribed participation, every labelled payment is the same deterministic density $2P$, giving total payment $2N\epsilon V$.
The proposed noise law is normalized. When adjacent query values differ by $\delta$, their output supports coincide and their atom probabilities have ratios bounded by $5$ in both directions. These atomwise bounds extend to arbitrary measurable output events. The displayed estimate $e^2>5$ justifies privacy for $\epsilon\ge2$.
Since $Z=0$ has probability $2/3$, accuracy holds for every $K>0$. The constant payment field preserves joint-output privacy.
Hence the boxed implication is a valid sufficient feasibility certificate. It does not characterize minimum payment.
The pointwise EIIR inequality is valid under the task’s profilewise requirement:
$$
\mathbb E[p_i]\ge\epsilon v_i\Pr[x_i=1].
$$
The subsequent interchange of expectation and population integration is valid under the prover’s explicitly stated condition
$$
\mathbb E\!\left[\int_I|p_i|\,d\mu(i)\right]<\infty.
$$
However, finite absolute expectation for each individual transfer does not by itself imply this population-level condition. Nor does absolute integrability of the total signed payment imply it.
Minimum clarification: State explicitly that the task’s phrase “finite absolute expectation” is being interpreted as this population-level condition. Otherwise, qualify both integrated lower bounds as requiring that additional hypothesis.
Under the natural population-level interpretation, this is a minor clarification. Under a weaker interpretation, the universal signed-payment lower bounds have not been established. The explicit feasibility constructions are unaffected because their payments are bounded.
The dominating measure $M$ exists, and the Radon–Nikodym derivatives satisfy $h_0+h_1=2$ almost surely under $M$. Bayes’ rule gives the stated posterior on the two prior-supported profiles.
Because these profiles assign opposite categories to every label, equality of each label’s posterior category distribution with its prior is equivalent to $h_0=h_1=1$. The restricted measures on $U$ therefore agree.
The success events are disjoint because $K<N/2$. Their combined contribution on $U$ is at most $a$, and their combined contribution outside $U$ is at most $2(1-a)$. Thus accuracy implies $a\le2/3$.
Under either profile, every label consequently has posterior-change probability at least $1/3$. With population-level absolute integrability, EIIR gives the claimed bound
$$
\sup_\theta\mathbb E[\text{total payment}]
\ge\frac{\epsilon cN}{3}.
$$
This proof requires no adjacency relationship between the two profiles and no off-prior posterior convention. It establishes a lower bound, not the exact optimum.
Distinguishing the public possible-type count $s$ from the private realized support size $\tau$ is correct. The rational certificate can be checked using polynomial-time arithmetic, and the conservative bound $O(sL^2)$ is consistent with explicitly encoded rational inputs.
Summing participating masses requires their actual bit lengths. The stated dependence on $L_{\mathrm{pop}}$ is therefore appropriate; the task does not bound private mass precision by $m,\tau,L$.
The convolution calculation for $G_1-G_2$ is correct. The constant expected fair-coin sampling claim is also valid: the fixed rational continuation probability can be sampled with constant expected coin use, and the geometric variables have finite constant expectations.
The explicit finite-path matrix has $O(n^2)$ entries. Since $n$ can be exponential in the public binary encoding, this construction supplies no polynomial execution bound in that encoding.
The prover correctly distinguishes its mathematical threshold characterization from an exact bit-complexity algorithm for comparing $S_n(e^\epsilon)$ with $3/2$.
The cited finite-population feasibility statement appears as Theorem 3.9 in both the [preprint](https://arxiv.org/pdf/1204.4031) and [published version](https://www.cs.tau.ac.il/~fiat/cgt12/EC_2012/docs/p568.pdf). The prover does not use it as a theorem establishing optimal payments or classifying the specified mass problem. Its independent constructions therefore do not depend on an unverified transfer of that theorem to the atomless model.
The actionable feedback is to clarify the integrability interpretation and retain the explicit partial-status qualification. Resolving the original assignment still requires an exact polynomial-time decision procedure or a valid hardness result covering the full contract class; the present certificates do not supply either.
⟨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.