Answer: \(\mathrm P\): feasible exactly when \(B\le q\,\mathbb E_{\mu\sim\Pi}[Q_q(\mu)]\).
THEOREM 1 — class: algorithmic
Given a finite value set \(T\subseteq[L,U]\), a rational supply share \(q\in(0,1)\), and a finite rational prior \(\Pi\) over societies \(\mu\in\Delta(T)\), allocate mass \(q\) efficiently to the highest reported values, splitting mass at the cutoff as needed. Find coefficients for a common per-capita rebate \(\rho(\mu)\), a finite linear combination of quantile values of \(\mu\), that maximizes \(\mathbb{E}_{\mu\sim\Pi}[\rho(\mu)]\), subject to dominant-strategy truthfulness for each infinitesimal bidder and the pointwise non-deficit constraint \(\rho(\mu)\le q\theta_q(\mu)\), where \(\theta_q(\mu)\) is the allocation cutoff.
Let \(T\subseteq[\ell,u]\cap\mathbb Q\) be nonempty, with \(0\le\ell<u<\infty\), and write \(m=|T|\). There is unit total mass of nonatomic, unit-demand bidders with quasilinear utilities; values and reports belong to \(T\).
A society \(\mu\in\Delta(T)\) is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational. Support size means the number of listed types, not the number of possible types.
Input consists of rational supply \(q\in(0,1)\), an explicitly listed prior \(\Pi\) on \(h\) rational societies with positive rational probabilities summing to one, and a rational threshold \(B\). Let \(\tau\) denote the maximum input society support size and \(L\) the total input bit length; state running times in \(m,\tau,h,L\).
For \(0\le s<1\), define the descending quantile \(Q_s(\mu)=\max\{t\in T:\mu(\{x\in T:x\ge t\})>s\}\), and let \(\theta_q(\mu)=Q_q(\mu)\).
Allocate all mass above \(\theta_q(\mu)\), none below it, and the fraction \((q-\mu(\{x>\theta_q(\mu)\}))/\mu(\{\theta_q(\mu)\})\) of each bidder at the cutoff. Charge \(\theta_q(\mu)\) per allocated unit.
A common per-capita rebate has the form \(\rho(\mu)=c_0+\sum_{j=1}^{k}c_jQ_{s_j}(\mu)\), where any finite \(k\ge0\), rational levels \(s_j\in[0,1)\), and signed rational coefficients are chosen by the designer and fixed across societies. No individual-rationality or rebate-nonnegativity constraint is imposed.
Require dominant-strategy truthfulness against every unilateral report by a measure-zero bidder, which leaves the aggregate society unchanged, and require \(\rho(\mu)\le q\theta_q(\mu)\) for every \(\mu\in\Delta(T)\), including societies outside the prior support.
Is deciding whether such a mechanism attains \(\mathbb E_{\mu\sim\Pi}[\rho(\mu)]\ge B\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite bidders, optimal expected redistribution among anonymous affine functions of the other bidders' ordered bids has an explicit polynomial-time solution given the expected order statistics, subject to efficiency, truthfulness, and non-deficit. [Guo–Conitzer](https://www.cs.cmu.edu/~conitzer/oelAIJ10.pdf)
No result settling this precise continuum problem was located in the literature search.
The decision problem is in \(\mathrm P\). Its answer is yes exactly when
\(B\le q\,\mathbb E_{\mu\sim\Pi}[Q_q(\mu)]\).
The permitted choice \(s_1=q\) allows the rebate \(\rho(\mu)=qQ_q(\mu)\), which redistributes the entire revenue in every society. This construction works for arbitrary support sizes, so it settles the stated problem without an additional restriction or interpretation.
Fix any society \(\mu\in\Delta(T)\), and write \(\theta=Q_q(\mu)\), \(A=\mu(\{x>\theta\})\), and \(M=\mu(\{\theta\})\).
The defining maximum exists: at the minimum element of \(T\), the upper-tail mass is \(1>q\). By definition, \(A+M>q\).
Also \(A\le q\). Indeed, if \(A>q\), there is a smallest positive-mass type \(a>\theta\). Its upper-tail mass equals \(A>q\), contradicting maximality of \(\theta\). Consequently \(M>0\), and the cutoff allocation fraction satisfies
\(\alpha=(q-A)/M\in[0,1)\).
In particular, equality \(A=q\) is allowed and gives \(\alpha=0\). The total allocated mass is \(A+\alpha M=q\), so total revenue is \(q\theta\).
Now fix a measure-zero bidder with true value \(v\in T\). By hypothesis, every unilateral report leaves \(\mu\), hence \(\theta\), \(\alpha\), and \(\rho(\mu)\), unchanged. Reporting \(r\in T\) gives allocation
\(x(r)=1\) if \(r>\theta\), \(x(r)=\alpha\) if \(r=\theta\), and \(x(r)=0\) if \(r<\theta\).
The bidder’s quasilinear utility is
\(u(v,r)=(v-\theta)x(r)+\rho(\mu)\).
There are three cases:
Thus truthful reporting is weakly optimal against every unilateral report. This proof applies to every common rebate depending only on the unchanged aggregate society.
Choose the rational parameters
\(k=1\), \(c_0=0\), \(c_1=q\), and \(s_1=q\).
They are admissible because \(q\in(0,1)\). The resulting rebate is
\(\rho^*(\mu)=qQ_q(\mu)=q\theta_q(\mu)\).
Section 2 proves dominant-strategy truthfulness. Moreover, the non-deficit constraint holds with equality for every society, including societies outside the prior support. Since total bidder mass is one, total redistribution equals the per-capita rebate.
Conversely, every feasible rebate satisfies \(\rho(\mu)\le qQ_q(\mu)\) pointwise. Taking expectations therefore gives
\(\mathbb E_{\Pi}[\rho(\mu)]\le q\mathbb E_{\Pi}[Q_q(\mu)]\).
The rebate \(\rho^*\) attains this bound. Hence the maximum is attained and equals \(q\mathbb E_{\Pi}[Q_q(\mu)]\), proving the decision criterion in Section 1.
Write the listed prior as \(\Pi=\{(\pi_i,\mu_i):1\le i\le h\}\). For each society, sort its positive-mass support in descending order:
\(t_{i,1}>\cdots>t_{i,\tau_i}\), with corresponding masses \(w_{i,j}>0\).
Compute cumulative masses \(C_{i,j}=\sum_{a=1}^{j}w_{i,a}\). Let \(j_i\) be the first index with \(C_{i,j_i}>q\); such an index exists because \(C_{i,\tau_i}=1\). Then
\(Q_q(\mu_i)=t_{i,j_i}\).
To verify this identity, the upper-tail mass at \(t_{i,j_i}\) exceeds \(q\), whereas every type strictly above it has upper-tail mass at most \(C_{i,j_i-1}\le q\). This also accounts for unlisted types in \(T\).
Compute the rational number
\(R=q\sum_{i=1}^{h}\pi_i t_{i,j_i}\)
and return yes exactly when \(R\ge B\).
There are \(O(h\tau\log(\tau+1))\) rational comparisons and arithmetic operations. With fractions reduced after arithmetic, intermediate bit lengths are \(O(L)\): cumulative-mass denominators divide products of input mass denominators, and the expectation denominator divides the product of the prior-probability denominators and distinct selected-type denominators. Multiplication by \(q\) adds only its input bit length.
Using elementary integer arithmetic, a conservative bit-time bound is
\(O\!\left(L+h\tau\log(\tau+1)L^3\right)\).
There is no additional dependence on \(m\); only listed support types need processing.
The [Guo–Conitzer paper](https://www.cs.cmu.edu/~conitzer/oelAIJ10.pdf) studies finite-bidder rebates expressed using other bidders’ ordered bids. Here the stipulated invariance of the aggregate under every unilateral report makes the aggregate revenue itself an admissible, report-independent rebate. The proof above directly verifies the consequences of that continuum assumption.
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the stated problem correctly. The construction is admissible, its truthfulness proof covers every unilateral report, and its global feasibility and optimality arguments are valid. The exact algorithm has polynomial bit complexity. No major or minor issues were found.
The proof uses the intended finite-type interpretation of \(T\), consistent with the task’s parameter \(m=|T|\) and requested running times. It handles all societies in \(\Delta(T)\), rather than restricting feasibility to the prior support.
The decisive modeling assumptions are explicit in the task: a unilateral report by a measure-zero bidder leaves the aggregate society unchanged, and the designer may choose the rational quantile level \(s_1=q\). The prover uses these assumptions directly, without introducing an additional restriction.
For every society, the minimum type has upper-tail mass \(1>q\), so the set defining \(Q_q(\mu)\) is nonempty. Its maximum exists because \(T\) is finite.
With the prover’s notation, the definition gives \(A+M>q\). The argument establishing \(A\le q\) is correct: if \(A>q\), the smallest positive-mass type above \(\theta\) exists, and its upper-tail mass is precisely \(A\). It would therefore be a larger admissible type in the defining maximum, a contradiction.
These inequalities establish \(M>0\) and
\[
0\le \alpha=\frac{q-A}{M}<1.
\]
Thus the allocation fraction is well-defined. The calculation \(A+\alpha M=q\) is exact, and charging \(\theta\) per allocated unit yields total revenue \(q\theta\).
The boundary case \(A=q\) is explicitly handled: the cutoff receives allocation fraction zero. The strict upper-tail inequality in the quantile definition is respected throughout.
The utility expression
\[
u(v,r)=(v-\theta)x(r)+\rho(\mu)
\]
correctly includes both the allocation payment and the common rebate.
Under the task’s stipulated invariance, every unilateral report leaves \(\theta\), \(\alpha\), and \(\rho(\mu)\) unchanged. The report affects only the bidder’s allocation through the stated three-way rule.
Each case is valid:
The proof applies to every aggregate society and every report in \(T\). Consequently, it establishes the required dominant-strategy condition, including indifference at the cutoff.
The proposed parameters \(k=1\), \(c_0=0\), \(c_1=q\), and \(s_1=q\) satisfy every stated restriction: the level lies in \([0,1)\), and the level and coefficients are rational.
The resulting rebate satisfies
\[
\rho^*(\mu)=qQ_q(\mu)=q\theta_q(\mu)
\]
for every society. Because total bidder mass is one, total redistribution equals this per-capita rebate. Non-deficit therefore holds with equality globally, including outside the prior support.
The converse is also valid. Every feasible rebate is bounded pointwise by \(qQ_q(\mu)\); taking the finite prior expectation preserves that inequality. The proposed rebate attains the upper bound, so the claimed optimum is attained, rather than merely approached.
Thus the decision criterion
\[
B\le q\,\mathbb E_{\mu\sim\Pi}[Q_q(\mu)]
\]
follows exactly.
Sorting each listed support in descending order and choosing the first cumulative mass strictly exceeding \(q\) computes the required quantile.
At the selected type, the upper-tail mass exceeds \(q\). Every larger type, including an unlisted type, has upper-tail mass at most the preceding cumulative mass, which is at most \(q\). This verifies maximality over all of \(T\).
Equality of a cumulative mass with \(q\) is treated correctly by continuing to the first strict exceedance. A selected index always exists because the final cumulative mass is \(1>q\). Singleton societies are covered as well.
The subsequent rational comparison \(R\ge B\) implements the proved decision criterion exactly.
The stated operation count \(O(h\tau\log(\tau+1))\) covers sorting, cumulative sums, and expectation computation.
The intermediate bit-length claim is sound. Reduced cumulative denominators divide products of input mass denominators. The expectation denominator divides the stated product of prior denominators and distinct selected-type denominators. Those products have bit lengths bounded by the total input encoding length. Numerators also have \(O(L)\) bit lengths, using the bounds on cumulative masses and the positive weighted expectation.
Reduction of fractions and exact comparisons are polynomial-time integer operations. The conservative bound
\[
O\!\left(L+h\tau\log(\tau+1)L^3\right)
\]
is sufficient. The absence of additional dependence on \(m\) is justified because only listed support types require processing.
The contextual description of finite-bidder rebates using other bidders’ ordered bids agrees with the [Guo–Conitzer paper](https://www.cs.cmu.edu/~conitzer/oelAIJ10.pdf). No theorem from that paper is invoked to establish the continuum result, so the proof has no unverified external theorem application.
No repair or additional 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.