d4-journals-geb-2017-0044 (d4-journals-geb-2017-0044)

Given a rational distribution \(\mu\) with finite support in \(V=[0,\beta]\), positive maximum value, and supported masses at least \(\epsilon\), choose an allocation intensity \(a(r;\mu)\) and scaled transfer \(b(r;\mu)\) for every report \(r\in V\). In an \(N\)-agent approximation, a reporter receives the object with probability \(a(r;\mu)/N\) and pays \(b(r;\mu)/N\). Require \(\int a(v;\mu)\,d\mu(v)\le1\), \(\int b(v;\mu)\,d\mu(v)=0\), \(v a(v;\mu)-b(v;\mu)\ge v a(r;\mu)-b(r;\mu)\) for all \(v,r\in V\), and individual rationality for supported values. What is the maximum, over such rules, of the worst-case welfare ratio \(\inf_\mu \frac{\int v a(v;\mu)\,d\mu(v)}{\max\operatorname{supp}(\mu)}\)?

Fix binary rationals \(\beta>0\) and \(0<\epsilon\leq1\), and let \(V=[0,\beta]\). Let \(\mathcal D_{\beta,\epsilon}\) contain all finitely supported probability distributions on rational values in \(V\), with positive maximum supported value and every positive mass at least \(\epsilon\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each with its mass as a binary rational; \(\tau\) is the support size, not the number of possible types. There is \(m=1\) object. State society-processing running times in \(m,\tau,L\) and the other input parameters, where \(L\) is the total binary input length.
A rule \(M=(a,b)\) specifies finite values \(a(r;\mu)\geq0\) and \(b(r;\mu)\in\mathbb R\) for every \(\mu\in\mathcal D_{\beta,\epsilon}\) and every report \(r\in V\). Equal reports receive equal intensities and transfers; positive transfers are payments and negative transfers are subsidies.
For every \(\mu\), require \(\int a(v;\mu)\,d\mu(v)\leq1\), \(\int b(v;\mu)\,d\mu(v)=0\), and \(va(v;\mu)-b(v;\mu)\geq va(r;\mu)-b(r;\mu)\) for all \(v,r\in V\). Also require \(va(v;\mu)-b(v;\mu)\geq0\) for supported values, with outside option zero. A unilateral deviation holds \(\mu\) fixed.
The intensities represent allocation probability \(a/N\) and payment \(b/N\) in sufficiently large \(N\)-agent approximations with \(N\geq3\). The rule may depend on \(\mu\); no restriction to ranking rules is imposed.
Define \(R(\beta,\epsilon)=\sup_M\inf_{\mu\in\mathcal D_{\beta,\epsilon}}\frac{\int va(v;\mu)\,d\mu(v)}{\max\operatorname{supp}(\mu)}\), where the supremum ranges over the rules just defined.

Given binary rationals \(\beta>0\), \(0<\epsilon\leq1\), and \(q\in[0,1]\), is deciding whether \(R(\beta,\epsilon)\geq q\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? Here the global decision input consists of \((\beta,\epsilon,q)\), and polynomial time means polynomial in its binary length \(L\).

For finite \(n\geq3\), an explicit two-step rule optimizes worst-case welfare among symmetric, DSIC, budget-balanced ranking mechanisms and is ex-post individually rational; its formula yields computation polynomial in \(n\). Ranking probabilities are fixed by rank, weakly decreasing, and averaged across tied ranks. [Discrete ranking result](https://arxiv.org/html/1604.08379)
No result settling this exact distribution-based problem was located in the literature search.

The decision problem is in \(\mathrm P\). In fact, \(R(\beta,\epsilon)=1\) for every admissible \(\beta,\epsilon\). The explicitly stated convention that deviations hold \(\mu\) fixed permits a society-dependent threshold price with a uniform rebate.

Fix a society \(\mu\), and define
\[ h=\max\operatorname{supp}(\mu),\qquad p=\mu(\{h\}). \]
Thus \(h>0\) and \(p\geq\epsilon>0\). Let \(s\) be the largest supported value strictly below \(h\), setting \(s=0\) if the support is a singleton. Set \(t=(s+h)/2\). Then \(0<t<h\), and every supported value other than \(h\) is strictly below \(t\).

For every report \(r\in V\), define
\[ a(r;\mu)=\frac{\mathbf 1_{\{r\geq t\}}}{p}, \qquad b(r;\mu)=\frac{t\,\mathbf 1_{\{r\geq t\}}}{p}-t. \]
Applying this construction separately to every society defines a single rule \(M\) on the required domain. All its values are finite, and equal reports receive equal intensities and transfers.

To verify incentive compatibility, fix any true value \(v\in V\). Its utility from report \(r\) is
\[ va(r;\mu)-b(r;\mu) =t+\frac{v-t}{p}\mathbf 1_{\{r\geq t\}}. \]
If \(v<t\), reports below \(t\) maximize this expression, and truthful reporting is one such report. If \(v>t\), reports at least \(t\) maximize it, again including the truthful report. If \(v=t\), every report gives utility \(t\). These cases prove the required inequality for every pair \(v,r\in V\).

Truthful utility is therefore
\[ va(v;\mu)-b(v;\mu) =t+\max\left\{0,\frac{v-t}{p}\right\}\geq t>0. \]
In particular, individual rationality holds for every supported value.

Exactly the mass \(p\) at \(h\) lies above the threshold. Consequently,
\[ \int a(v;\mu)\,d\mu(v)=p\frac1p=1, \]
and
\[ \int b(v;\mu)\,d\mu(v) =p\left(\frac tp-t\right)+(1-p)(-t)=0. \]
Thus feasibility and budget balance hold. The welfare is
\[ \int va(v;\mu)\,d\mu(v)=p\,h\,\frac1p=h. \]
The constructed rule therefore achieves welfare ratio \(1\) in every society.

For the matching upper bound, consider any admissible rule and society. Since every supported value satisfies \(v\leq h\), nonnegative intensities and feasibility imply
\[ \int va(v;\mu)\,d\mu(v) \leq h\int a(v;\mu)\,d\mu(v) \leq h. \]
Every admissible welfare ratio is thus at most \(1\). Together with the construction, this proves \(R(\beta,\epsilon)=1\), with the supremum attained.

For society processing, let \(L\) denote its total binary input length, including the parameters. With \(m=1\), finding \(h,s,p\) requires \(O(\tau)\) rational comparisons. Computing \(t\) and the two allocation-transfer pairs then requires a constant number of rational operations. Using elementary integer arithmetic, a conservative bound is \(O(\tau L^2)\) bit operations, polynomial in the explicit support size \(\tau\) and input length \(L\). Evaluating the rule on a rational report of binary length \(\ell\) takes \(O((L+\ell)^2)\) bit operations after preprocessing. Moreover, \(a(r;\mu)\leq1/\epsilon\), so the stated allocation-probability interpretation holds whenever \(N\geq\max\{3,\lceil1/\epsilon\rceil\}\).

For the global decision input, every promised \(q\in[0,1]\) satisfies \(R(\beta,\epsilon)\geq q\). Hence the algorithm returns yes on every valid input; even including rational-input validation, its running time is polynomial in the global binary length.

The fixed-\(\mu\) convention is essential to the proof: it keeps \(h,p,t\) and the rebate unchanged during a deviation. The cited [finite-agent ranking result](https://arxiv.org/html/1604.08379) uses incentive constraints over changing report profiles, so its restrictions do not obstruct this construction.

⟨structured verdict parsed — rendered above⟩

The output resolves the assigned decision problem. The construction satisfies the stated constraints and attains welfare ratio \(1\) for every admissible society. No major or minor mathematical issues were found.

• Support and threshold definitions. Because the support is finite and has positive maximum, \(h\) exists and satisfies \(h>0\). Its mass satisfies \(p\geq\epsilon>0\). For a nonsingleton support, the largest supported value below \(h\) exists and satisfies \(0\leq s<h\). For a singleton, the specified choice \(s=0\) also satisfies this inequality. Thus \(0<t<h\), and the supported reports meeting \(r\geq t\) consist exactly of \(h\). This includes societies whose support contains zero.

• Definition of the rule. Since \(p>0\), both formulas are finite for every report, including irrational reports in \(V\). Intensities are nonnegative, and equal reports receive identical outcomes. Defining these formulas for each society specifies one rule on the entire required domain. Society dependence is explicitly permitted by the task.

• Incentive compatibility. Substitution correctly gives

$$ va(r;\mu)-b(r;\mu) =t+\frac{v-t}{p}\mathbf 1_{\{r\geq t\}}. $$
The sign of \(v-t\) determines which of the two report classes maximizes utility. Truthful reporting belongs to a maximizing class for \(v<t\) and \(v>t\), while every report maximizes utility at \(v=t\). This verifies the inequality for all true values and reports, including unsupported values and the threshold itself. Holding \(\mu\) fixed ensures that the quantities used in this calculation do not change during a deviation.

• Individual rationality. The stated truthful-utility formula follows from the same cases and is at least \(t>0\). It therefore establishes the required individual rationality for all supported values.

• Feasibility, budget balance, and welfare. Only the supported value \(h\) receives positive intensity. The allocation integral is consequently \(p/p=1\). The budget calculation simplifies to

$$ p\left(\frac{t}{p}-t\right)+(1-p)(-t) =t-pt-t+pt=0. $$
Welfare is \(ph/p=h\). These calculations remain valid when \(p=1\), including singleton societies.

• Upper bound and optimization. On the support, \(v\leq h\). Nonnegative intensities and feasibility therefore imply welfare at most \(h\). Division by \(h\) is valid because \(h>0\). The constructed rule attains this bound for every society, so the infimum for that rule equals \(1\), and the supremum over rules equals \(1\) and is attained.

• Computational claims. A scan of the explicit support identifies \(h,s,p\) using \(O(\tau)\) rational comparisons. Their bit lengths, and those of the constant number of subsequent arithmetic results, are \(O(L)\). Elementary arithmetic supports the conservative bound \(O(\tau L^2)\) with \(m=1\). The stated rational-report evaluation bound is also valid. Since \(a\leq1/\epsilon\), the given sufficient bound on \(N\) ensures \(a/N\leq1\). The global decision algorithm correctly returns yes for every promised input; input validation is polynomial in its binary length.

The cited finite-agent ranking result is not used as a theorem in this proof. The conclusion follows entirely from the explicit construction and the task’s fixed-society incentive constraints. No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩