d4-journals-jair-2011-0023 (d4-journals-jair-2011-0023)

Given a rational supply ratio \(0<\rho<1\), a rational nonincreasing piecewise-constant slot-quality schedule \(\gamma:[0,\rho]\to\mathbb{R}_{\ge0}\) with its terminal drop to zero, and at most \(\tau\) scalar value types, characterize and compute the optimal limiting redistribution law. At each resolution \(N\), there are \(N\) unit-demand agents and \(p_N/N\to\rho\) slots whose qualities approximate \(\gamma\); choose anonymous Groves rebates \(r_i^N=f_N(\mathbf v_{-i})\) that are individually rational and feasible for every profile. Maximize \(\liminf_{N\to\infty}\inf_{\mathbf v:S_N>0}\sum_i r_i^N/S_N\), over profiles using at most \(\tau\) value types, and give exact finite strategyproof lifts of the limiting law.

A society is given by its support: \(\mu=\sum_{a=1}^{\tau}w_a\delta_{v_a}\), listing distinct nonnegative rational values and positive binary-rational masses with \(\sum_a w_a=1\). Here \(\tau\) is the support size, not the number of possible types; \(T\ge1\) is the input bound on support size.
Supply is a rational \(0<\rho<1\). The public quality schedule has \(m\) constant intervals with rational endpoints and positive rational heights, is nonincreasing and right-continuous on \([0,\rho)\), and drops to zero at \(\rho\).
At resolution \(N\), set \(p_N=\lfloor\rho N\rfloor\), \(\gamma_j^N=\gamma((j-1)/N)\) for \(1\le j\le p_N\), and \(\gamma_{p_N+1}^N=0\); consider resolutions with \(N>p_N+1\) and \(p_N>1\). Each unit-demand agent has value \(\gamma_j^Nv_i\) for slot \(j\), with \(v_i\in\mathbb R_{\ge0}\).
Allocate efficiently by decreasing value, breaking ties by a fixed order independent of reports. For sorted values, the Clarke surplus is \(S_N(\mathbf v)=\sum_{j=1}^{p_N}j(\gamma_j^N-\gamma_{j+1}^N)v_{j+1}\).
A permitted mechanism charges each agent its Clarke pivotal payment minus \(r_i^N=f_N(\mathbf v_{-i})\), where \(f_N\) is deterministic and symmetric. Require \(r_i^N\ge0\) and \(\sum_i r_i^N\le S_N(\mathbf v)\) on every nonnegative real profile, including profiles with more than \(T\) types and profiles with zero surplus; rebates need not be linear.
Define \(E(\rho,\gamma,T)=\sup_{(f_N)}\liminf_{N\to\infty}\inf_{\mathbf v:\,|\operatorname{supp}(\mathbf v)|\le T,\ S_N(\mathbf v)>0}\frac{\sum_i f_N(\mathbf v_{-i})}{S_N(\mathbf v)}\), with the supremum over permitted mechanism sequences.
For a rational society, let \(\mathbf v^N(\mu)\) contain exactly \(Nw_a\) copies of each \(v_a\), along resolutions where these counts are integers. A limiting redistribution law assigns a per-agent rebate \(R(\mu,v_a)=\lim_N f_N(\mathbf v^N(\mu)\setminus\{v_a\})\); exact finite lifts are permitted mechanisms realizing these limits and attaining \(E\) in the preceding worst-case criterion.
Is deciding \(E(\rho,\gamma,T)\ge q\), for rational \(q\in[0,1]\), in P or NP-hard? Can the optimal value, an optimal limiting law, and exact finite strategyproof lifts be computed in polynomial time?
State running times in \(m,\tau,T,L\), where \(L\) is the total binary input length, and additionally in \(N\) and the finite profile's bit length when evaluating lifts.
For finite scalar-value slot assignment with \(n>p+1\), an LP of size polynomial in \(n\) computes a linear mechanism that is worst-case optimal among all feasible, individually rational, deterministic anonymous Groves mechanisms. [Gujar–Narahari](https://arxiv.org/pdf/1401.3884)
No result addressing exactly this support-bounded mass-limit optimization and its finite lifts was identified in the literature search.

Polynomial-time solution

The decision problem is in P. The optimal value, an optimal limiting redistribution law, and permitted exact finite lifts can all be computed in polynomial time.

The support restriction matters only in distinguishing $T=1$ from $T\ge2$. The finite lifts constructed below are feasible on every nonnegative real profile, including profiles with arbitrarily many support values and profiles with zero surplus.

1. The optimal value

Merge adjacent quality intervals of equal height. Write the remaining drop locations and height decreases as
$$ 0<\alpha_1<\cdots<\alpha_s=\rho, \qquad \delta_r>0. $$
The final drop to zero is included, and $s\le m$. Define
$$ A_r=\sum_{h<r}\alpha_h\delta_h, \qquad B_r=A_r+\alpha_r\delta_r, \qquad b=B_s. $$
For each drop beyond one half, define
$$ \Phi_r= \frac{1-\alpha_r}{\alpha_r} + \frac{2\alpha_r-1}{\alpha_r(1-\alpha_r)} \frac{A_r}{B_r}. $$
An empty minimum below is interpreted as $1$. Put
$$ e_*=\min\left\{1,\ \min_{\alpha_r>1/2}\Phi_r\right\}. $$

Theorem.
$$ \boxed{ E(\rho,\gamma,T)= \begin{cases} 1,&T=1,\\ e_*,&T\ge2. \end{cases} } $$

All quantities in this formula are rational. In particular, it gives an exact polynomial-time threshold algorithm, without approximating a limit of finite LPs.

The proof also supplies an optimal limiting law and exact finite lifts.

2. Finite reduction and universal feasibility

Fix a permitted resolution $N$, and abbreviate $p=p_N$. Define
$$ a_j=j(\gamma_j^N-\gamma_{j+1}^N), \qquad b_k^N=\sum_{\substack{1\le j\le p\\j<k}}a_j \quad(0\le k\le N). $$
Thus $b_k^N$ is the surplus of the binary profile with $k$ ones and $N-k$ zeros.

Consider the LP
$$ \begin{aligned} \text{maximize }&e,\\ \text{subject to }& 0\le e\le1,\qquad x_k\ge0\quad(0\le k\le N-1),\\ &e b_k^N \le kx_{k-1}+(N-k)x_k \le b_k^N \quad(0\le k\le N), \end{aligned} $$
where $x_{-1}=x_N=0$. Denote its optimum by $e_N$.

Upper bound for arbitrary anonymous rebates

For any permitted rebate function, set
$$ x_k=f_N(\underbrace{1,\ldots,1}_{k}, \underbrace{0,\ldots,0}_{N-1-k}). $$
Individual nonnegativity gives $x_k\ge0$. On the full binary profile with $k$ ones, total rebates are
$$ kx_{k-1}+(N-k)x_k. $$
Universal feasibility gives the LP upper constraints. If the mechanism guarantees a fraction $e$ on profiles with at most $T\ge2$ values, binary profiles give the lower constraints. At zero surplus, those lower constraints are automatic.

Consequently, no such mechanism has finite guarantee exceeding $e_N$.

Construction from feasible coefficients

Conversely, suppose $x_0,\ldots,x_{N-1}$ satisfy the LP constraints for some $e$. The constraint at $k=0$ implies $x_0=0$.

For a decreasing deletion profile
$$ y_1\ge\cdots\ge y_{N-1}\ge0, $$
define
$$ f_N(y)=\sum_{k=1}^{N-1}(x_k-x_{k-1})y_k. $$
With $y_N=0$, summation by parts gives
$$ f_N(y)=\sum_{k=1}^{N-1}x_k(y_k-y_{k+1})\ge0. $$

For a decreasing full profile, put $v_{N+1}=0$ and
$$ z_k=kx_{k-1}+(N-k)x_k. $$
Then
$$ S_N(v)=\sum_{k=1}^{N}(v_k-v_{k+1})b_k^N, $$
and
$$ \sum_i f_N(v_{-i}) = \sum_{k=1}^{N}(v_k-v_{k+1})z_k. $$
To verify the second identity, decompose the decreasing profile as
$$ v=\sum_{k=1}^{N}(v_k-v_{k+1}) (\underbrace{1,\ldots,1}_{k},0,\ldots,0). $$
On the cone of decreasing full profiles, each deletion rebate is linear in the ordered values; on each displayed binary vector, its aggregate is $z_k$.

Multiplication of the LP inequalities by the nonnegative differences $v_k-v_{k+1}$ therefore proves
$$ eS_N(v)\le\sum_i f_N(v_{-i})\le S_N(v) $$
on every nonnegative real profile.

The rebate is deterministic, symmetric, and independent of the recipient’s report. Adding it to the Clarke utility preserves dominant-strategy truthfulness.

The LP optimum exists: the zero solution is feasible, and each variable satisfies
$$ 0\le x_k\le\frac{b_k^N}{N-k}. $$
It follows that, for $T\ge2$,
$$ E(\rho,\gamma,T)=\liminf_{N\to\infty}e_N. $$

We will prove the stronger conclusion
$$ e_N\longrightarrow e_*. $$

3. Upper bound at a quality drop

Fix a drop $\alpha=\alpha_r>1/2$, and abbreviate $A=A_r$, $B=B_r$.

For all sufficiently large $N$, its finite drop index is
$$ d= \begin{cases} \lceil\alpha N\rceil,&r<s,\\ \lfloor\rho N\rfloor,&r=s. \end{cases} $$
Distinct drops eventually have distinct indices. Therefore
$$ \frac{b_d^N}{N}\longrightarrow A, \qquad \frac{b_{d+1}^N}{N}\longrightarrow B. $$
For every fixed number of ranks after $d$, the binary surplus equals $b_{d+1}^N$ for all sufficiently large $N$.

Take any subsequence along which $e_N\to e$, and choose optimal LP coefficients on it. The upper constraint at $d$ gives
$$ x_d\le\frac{b_d^N}{N-d}, \qquad \limsup x_d\le\frac{A}{1-\alpha}. $$

Write $\beta=b_{d+1}^N$. Within the constant-surplus segment after the drop, combine
$$ kx_{k-1}+(N-k)x_k\le\beta $$
with
$$ (k+1)x_k+(N-k-1)x_{k+1}\ge e_N\beta. $$
Eliminating $x_k$ yields
$$ x_{k-1} \le \frac{\beta}{k} -\frac{(N-k)e_N\beta}{k(k+1)} +\frac{(N-k)(N-k-1)}{k(k+1)}x_{k+1}. $$

Let
$$ r=\frac{1-\alpha}{\alpha}<1. $$
Starting at $k=d+2$, iterate this inequality $H$ times, with $H$ fixed. The constant terms converge to
$$ \frac{B}{\alpha}(1-re), $$
and the successive coefficients converge to $r^2$.

The terminal variable is bounded by the next upper constraint:
$$ x_\ell\le\frac{\beta}{\ell+1}. $$
For each fixed $H$, its limiting upper bound can be taken to be a constant $M$ independent of $H$, because $\ell/N\to\alpha$ and $\beta/N\to B$. Hence
$$ \limsup x_{d+1} \le \frac{B}{\alpha}(1-re) \sum_{h=0}^{H-1}r^{2h} +r^{2H}M. $$
Letting $H\to\infty$ gives
$$ \limsup x_{d+1} \le \frac{B\bigl(\alpha-(1-\alpha)e\bigr)}{2\alpha-1}. $$

Finally, the lower constraint at the jump gives
$$ e_Nb_{d+1}^N \le(d+1)x_d+(N-d-1)x_{d+1}. $$
After division by $N$ and passage to the limit,
$$ eB \le \frac{\alpha A}{1-\alpha} + \frac{(1-\alpha)B\bigl(\alpha-(1-\alpha)e\bigr)} {2\alpha-1}. $$
Since the denominators are positive, rearrangement gives
$$ e\le \frac{1-\alpha}{\alpha} + \frac{2\alpha-1}{\alpha(1-\alpha)}\frac{A}{B} =\Phi_r. $$

This applies to every subsequential limit and every drop beyond one half. Together with $e_N\le1$, it proves
$$ \limsup_{N\to\infty}e_N\le e_*. $$

4. Construction of exact finite lifts for $T\ge2$

We now construct universally feasible mechanisms whose guarantees tend to $e_*$. They need not be finite-optimal at every individual resolution; they satisfy precisely the definition of exact finite lifts in the question.

Throughout this construction, write $e=e_*$. Set
$$ h=\lfloor\sqrt N\rfloor, \qquad \varepsilon_N=\frac{1}{\lceil N^{1/4}\rceil}. $$
Both are computable by integer arithmetic.

For sufficiently large $N$, the discrete drops have the indices specified above and are separated by more than the widths used below. To define the mechanism at every permitted resolution, use the zero rebate if these conditions fail. More explicitly, require the reserved integer intervals
$$ [d_r-h-1,\ d_r+2h+2] $$
to be disjoint and contained in $[0,N-1]$. For fixed input data, these requirements hold eventually, because the drop locations are distinct and belong to $(0,1)$.

Initialize
$$ x_k=\frac{b_k^N}{N} \qquad(0\le k\le N-1). $$
Modify these coefficients near each drop as follows. For that drop write
$$ A_N=\frac{b_d^N}{N}, \qquad B_N=\frac{b_{d+1}^N}{N}. $$

Drops below one half

If $\alpha<1/2$, retain $x_d=A_N$ and set, successively,
$$ x_k= \frac{NB_N-kx_{k-1}}{N-k} \qquad(d+1\le k\le d+h). $$
All other coefficients near this drop retain their initialized values.

A drop at one half

If $\alpha=1/2$, retain $x_d=A_N$ and put
$$ x_{d+\ell} = B_N+(-1)^\ell(A_N-B_N) \left(1-\frac{\ell}{h}\right) \qquad(1\le\ell\le h). $$

Drops beyond one half

If $\alpha>1/2$, put
$$ r=\frac{1-\alpha}{\alpha}, \qquad a_N=\min\{1,\max\{e,r\}+\varepsilon_N\}, \qquad K=d+2h+1. $$
Set $x_K=B_N$. For $k=K,K-1,\ldots,d+2$, define
$$ q_k= \begin{cases} NB_N,&k-d\text{ is even},\\ a_NNB_N,&k-d\text{ is odd}, \end{cases} $$
and
$$ x_{k-1}=\frac{q_k-(N-k)x_k}{k}. $$
This determines $x_{d+1}$.

Next set
$$ x_d= \min\left\{ \frac{b_d^N}{N-d}, \ \max\left\{ 0,\ \frac{e\,b_{d+1}^N-(N-d-1)x_{d+1}}{d+1} \right\} \right\}. $$
Finally, for $k=d,d-1,\ldots,d-h+1$, define
$$ x_{k-1}=\frac{b_d^N-(N-k)x_k}{k}. $$

Exact feasibility correction

Compute
$$ z_k=kx_{k-1}+(N-k)x_k, \qquad x_{-1}=x_N=0. $$
Check, using exact rational arithmetic, that every $x_k$ is nonnegative and that
$$ b_k^N=0\quad\Longrightarrow\quad z_k=0. $$
If either check fails, use the zero rebate.

Otherwise define
$$ \lambda_N= \max\left\{1,\ \max_{b_k^N>0}\frac{z_k}{b_k^N}\right\}, \qquad \widehat x_k=\frac{x_k}{\lambda_N}. $$
The finite rebate is
$$ \boxed{ f_N(y)= \sum_{k=1}^{N-1} (\widehat x_k-\widehat x_{k-1})y_k, } $$
where the deletion profile is sorted decreasingly.

By Section 2, the exact checks and scaling make this mechanism permitted on every nonnegative real profile. Its guarantee is at least
$$ \eta_N= \min_{b_k^N>0}\frac{z_k}{\lambda_Nb_k^N}. $$

We next prove that the fallback cases occur only finitely often and that
$$ \lambda_N\to1, \qquad \liminf\eta_N\ge e. $$

5. Verification of the construction

All estimates in this section concern fixed input data as $N\to\infty$. There are finitely many drops, so estimates established for each drop can be combined uniformly across them.

Drops below one half

The forward recurrence satisfies
$$ x_k-B_N = -\frac{k}{N-k}(x_{k-1}-B_N). $$
Over the modified interval, all ratios are eventually bounded by some fixed $c<1$, because $k/N\to\alpha<1/2$ uniformly there.

Initially,
$$ x_d-B_N=A_N-B_N, \qquad |A_N-B_N|\le B_N. $$
It follows that all modified coefficients are nonnegative and
$$ |x_{d+h}-B_N|\le B_Nc^h. $$

The budget equations are exactly
$$ z_k=NB_N \qquad(d+1\le k\le d+h). $$
At the transition back to initialized coefficients,
$$ z_{d+h+1}-NB_N = (d+h+1)(x_{d+h}-B_N), $$
so the relative budget error is at most $c^h$.

A drop at one half

Let
$$ D_N=A_N-B_N, \qquad \theta_\ell=1-\frac{\ell}{h}. $$
Because $|D_N|\le B_N$ and $0\le\theta_\ell\le1$, all modified coefficients are nonnegative.

For $k=d+\ell$, with $t=k/N$,
$$ \frac{z_k}{N} = B_N+ (-1)^{\ell-1}D_N \bigl(t\theta_{\ell-1}-(1-t)\theta_\ell\bigr). $$
Moreover,
$$ t\theta_{\ell-1}-(1-t)\theta_\ell = (2t-1)\theta_\ell+\frac{t}{h}. $$
Here
$$ \left|t-\frac12\right|=O(h/N). $$
Therefore, uniformly through the modified interval,
$$ \left|\frac{z_k}{NB_N}-1\right| = O\left(\frac{h}{N}+\frac1h\right) =o(1). $$
At its end, $x_{d+h}=B_N$, so the next budget equation is exact.

Nonnegativity after a drop beyond one half

Fix such a drop and write $r=(1-\alpha)/\alpha$. Normalize the post-drop coefficients by $B_N$.

The exact backward map at rank $k$ is
$$ u\longmapsto \frac{\sigma-(1-k/N)u}{k/N}, \qquad \sigma\in\{1,a_N\}. $$
Compare it with the constant-coefficient map
$$ T_\sigma(u)=\frac{\sigma-(1-\alpha)u}{\alpha}. $$

Define
$$ H_N=\frac{\alpha-(1-\alpha)a_N}{2\alpha-1}, \qquad L_N=\frac{\alpha a_N-(1-\alpha)}{2\alpha-1}. $$
Since $r\le a_N\le1$,
$$ 0\le L_N\le1\le H_N\le\frac1\alpha. $$
Direct substitution gives
$$ T_1(L_N)=H_N, \qquad T_{a_N}(H_N)=L_N, \qquad T_1(1)=1. $$
Consequently, the constant-coefficient backward sequence, initialized at $1$, has its high coefficients in $[1,H_N]$ and its low coefficients in $[L_N,1]$.

The exact ranks satisfy
$$ k/N=\alpha+O(h/N) $$
throughout this interval. The exact maps have contraction factors $(N-k)/k$ bounded by a fixed $c<1$. Their differences from the constant-coefficient maps, on the displayed bounded intervals, are $O(h/N)$. Thus the error after any number of backward steps is bounded by
$$ C\frac{h}{N}\sum_{j\ge0}c^j = O(h/N). $$

If $e<1$, then eventually $a_N<1$ and
$$ a_N-r\ge\varepsilon_N, \qquad L_N\ge\frac{\alpha\varepsilon_N}{2\alpha-1}. $$
Since
$$ h/N=O(N^{-1/2}), \qquad \varepsilon_N\asymp N^{-1/4}, $$
the exact coefficients are nonnegative for all sufficiently large $N$.

If $e=1$, then $a_N=1$, and the exact backward recurrence preserves $x_k=B_N$ identically. Nonnegativity is immediate.

Let
$$ a=\max\{e,r\}, \qquad V= \frac{B\bigl(\alpha-(1-\alpha)a\bigr)}{2\alpha-1}. $$
The constant-coefficient sequence approaches its high fixed coefficient geometrically. There are $2h$ steps between $K$ and $d+1$, while the exact-map error is $o(1)$. Therefore
$$ x_{d+1}\longrightarrow V. $$

The jump and the coefficients before it

The definition of $x_d$ gives
$$ x_d\longrightarrow U= \min\left\{ \frac{A}{1-\alpha}, \ \max\left\{0,\frac{eB-(1-\alpha)V}{\alpha}\right\} \right\}. $$

The outer minimum is redundant in this limit. Indeed:

• If $e\le r$, then $a=r$, $V=B/\alpha$, and the inner maximum is zero.
• If $e>r$, then $a=e$, and direct rearrangement gives

$$ \frac{eB-(1-\alpha)V}{\alpha} \le\frac{A}{1-\alpha} \quad\Longleftrightarrow\quad e\le\Phi_r. $$
This holds by the definition of $e$.

Thus
$$ \boxed{ U=\max\left\{0,\frac{eB-(1-\alpha)V}{\alpha}\right\}. } $$
Because $a\ge r$,
$$ V\le\frac{B}{\alpha}. $$
The normalized jump budget therefore converges to
$$ \alpha U+(1-\alpha)V = \max\{eB,(1-\alpha)V\} \in[eB,B]. $$

For the pre-drop recurrence, the cap on $x_d$ ensures
$$ 0\le x_{d-1} = \frac{b_d^N-(N-d)x_d}{d} \le\frac{b_d^N}{d}. $$
More generally, if
$$ 0\le x_k\le\frac{b_d^N}{k+1} $$
and $N-k\le k+1$, then
$$ 0\le \frac{b_d^N-(N-k)x_k}{k} \le\frac{b_d^N}{k}. $$
Every rank in this pre-drop interval is eventually beyond one half. Induction proves nonnegativity throughout it.

Relative to $A_N$, the recurrence is
$$ x_{k-1}-A_N = -\frac{N-k}{k}(x_k-A_N). $$
Its factors are uniformly bounded by a constant below one. If $A_N>0$, the initial cap bounds $|x_d-A_N|$ by a constant multiple of $A_N$. Hence the relative budget error at the transition to initialized coefficients is $O(c^h)$. If $A_N=0$, the entire pre-drop interval is exactly zero.

The pre-drop budget equations are otherwise exact, and the post-drop equations have ratios exactly $1$ or $a_N$.

Global conclusion

Outside the modified intervals and their transitions, the coefficients are constant on each constant-surplus segment, so
$$ z_k=b_k^N. $$
Before the first positive-surplus rank, the construction leaves all relevant coefficients zero; this remains true if the first drop is beyond one half, because its pre-drop cap is zero. Thus every zero-surplus constraint holds exactly.

The preceding arguments prove eventual nonnegativity and show, uniformly over positive-surplus ranks,
$$ \frac{z_k}{b_k^N}\le1+o(1), \qquad \frac{z_k}{b_k^N}\ge e-o(1). $$
Therefore the fallback checks eventually pass,
$$ \lambda_N\to1, \qquad \liminf\eta_N\ge e. $$

The mechanisms are feasible on all profiles, so Section 2 gives $e_N\ge\eta_N$. Combined with Section 3,
$$ e_N\longrightarrow e_*. $$
This proves the claimed optimal value for $T\ge2$.

6. An optimal limiting redistribution law

Sort the society’s distinct values as
$$ v_1>\cdots>v_\tau\ge0, \qquad C_a=\sum_{j=1}^{a}w_j, \qquad C_0=0. $$

For every drop $\alpha_r>1/2$, compute
$$ r_r=\frac{1-\alpha_r}{\alpha_r}, \qquad a_r=\max\{e_*,r_r\}, $$
$$ V_r= \frac{B_r\bigl(\alpha_r-(1-\alpha_r)a_r\bigr)} {2\alpha_r-1}, $$
$$ U_r= \max\left\{0, \frac{e_*B_r-(1-\alpha_r)V_r}{\alpha_r} \right\}, \qquad W_r=\frac{A_r-(1-\alpha_r)U_r}{\alpha_r}. $$
Section 5 proves
$$ 0\le U_r\le\frac{A_r}{1-\alpha_r}, \qquad W_r\ge0. $$

For $a<\tau$ and recipient type $v_h$, define
$$ X_{a,h}= \begin{cases} W_r, &C_a=\alpha_r>1/2\text{ and }h\le a,\\ U_r, &C_a=\alpha_r>1/2\text{ and }h>a,\\ \displaystyle\sum_{\alpha_r<C_a}\alpha_r\delta_r, &\text{otherwise}. \end{cases} $$
The optimal law is
$$ \boxed{ R(\mu,v_h) = v_\tau b+ \sum_{a=1}^{\tau-1}(v_a-v_{a+1})X_{a,h}. } $$
All its coefficients are nonnegative.

Verification of the individual limits

Along resolutions with integral society counts, deleting an agent of type $v_h$ leaves
$$ K_a=NC_a-\mathbf1_{\{h\le a\}} $$
agents among the first $a$ value types. The finite rebate has the exact expansion
$$ f_N(v^N(\mu)\setminus\{v_h\}) = v_\tau\widehat x_{N-1} + \sum_{a=1}^{\tau-1} (v_a-v_{a+1})\widehat x_{K_a}. $$

If $C_a$ differs from every drop location, its distance from the drops is fixed and positive. Since the modified intervals have width $O(\sqrt N)$, $K_a$ eventually lies outside them. Consequently,
$$ \widehat x_{K_a} \longrightarrow \sum_{\alpha_r<C_a}\alpha_r\delta_r. $$

If $C_a=\alpha_r$, integrality implies $\alpha_rN$ is an integer. Thus the discrete drop index is exactly $d=\alpha_rN$, including at the final drop.

For $\alpha_r\le1/2$, the construction has
$$ x_d=x_{d-1}=A_{r,N}\longrightarrow A_r. $$
For $\alpha_r>1/2$, Section 5 gives
$$ x_d\longrightarrow U_r, \qquad x_{d-1} = \frac{b_d^N-(N-d)x_d}{d} \longrightarrow W_r. $$
Deletion selects $d-1$ precisely when $h\le a$, and otherwise selects $d$.

Finally,
$$ \widehat x_{N-1}\longrightarrow b, $$
because that coefficient is eventually outside every modified interval and $\lambda_N\to1$.

These facts establish the displayed law for every rational society and every supported value. The finite mechanisms realizing it attain $E$ in the specified worst-case criterion.

For constant quality, this law simplifies even when $\rho>1/2$: there is only one drop, its $A_r$ is zero, and both boundary coefficients $U_r,W_r$ are zero.

7. The case $T=1$

Define the rebate
$$ f_N^{\mathrm{BC}}(y) = \frac1N\sum_{j=1}^{p}a_jy_{j+1}. $$
It is nonnegative and symmetric. For a decreasing full profile, deletion-rank counting gives
$$ \sum_i f_N^{\mathrm{BC}}(v_{-i}) = \frac1N\sum_{j=1}^{p}a_j \bigl((N-j-1)v_{j+1}+(j+1)v_{j+2}\bigr). $$
Since $v_{j+2}\le v_{j+1}$, this is at most $S_N(v)$. Thus the mechanism is universally feasible.

On a constant profile $v_i=c>0$, every order statistic used in the deletion rebate equals $c$, because $p+1\le N-1$. Total rebates consequently equal surplus exactly. Therefore
$$ E(\rho,\gamma,1)=1. $$

Define the right-continuous decreasing quantile by
$$ Q_\mu(t)=v_a \qquad(C_{a-1}\le t<C_a). $$
The limiting law realized by these finite mechanisms is
$$ \boxed{ R_{\mathrm{BC}}(\mu,v_h) = \sum_{r=1}^{s}\alpha_r\delta_rQ_\mu(\alpha_r). } $$

Indeed, a discrete drop contributes
$$ \frac{d_r\delta_r}{N}y_{d_r+1}. $$
Its coefficient converges to $\alpha_r\delta_r$. Away from a cumulative-mass boundary, the selected value converges to the quantile value. At $\alpha_r=C_a$, integrality makes $d_r=NC_a$, and rank $d_r+1$ after any deletion lies in the lower-valued block for all sufficiently large $N$. This proves the stated right-continuous convention and the individual limits.

8. Algorithms and running times

Let $L$ be the total binary input length, and let $H_{\mathrm{prof}}$ be the bit length of a finite reported profile.

Optimal value and threshold decision

Extract the positive drops, accumulate $A_r,B_r$, and evaluate the formula for $E$ using exact rational arithmetic.

This requires $O(m)$ rational arithmetic operations and polynomially many bit operations in $m$ and $L$. The dependence on $T$ consists only of testing whether $T=1$.

Thus deciding
$$ E(\rho,\gamma,T)\ge q $$
is in P.

Optimal limiting law

After sorting the $\tau$ supported values, merge the cumulative masses with the drop locations. This identifies strict inequalities and exact boundary equalities using rational comparisons.

The work is
$$ O(\tau\log\tau+m+\tau) $$
rational comparisons and arithmetic operations. All $\tau$ recipient rebates can be computed together: use the default coefficients $U_r$ at boundary coincidences, then accumulate the corrections $(v_a-v_{a+1})(W_r-U_r)$ for recipient indices $h\le a$.

The bit complexity is
$$ \operatorname{poly}(m,\tau,T,L), $$
with no substantive dependence on $T$ beyond its comparison with $1$.

Exact finite lifts

The construction uses integer roots, rational recurrences, exact sign checks, and rational scaling. With disjoint reserved intervals, the total number of modified coefficients is $O(N)$; otherwise the algorithm immediately uses the zero mechanism.

Coefficient construction uses $O(N+m)$ rational operations. Every recurrence has depth at most $O(N)$ and multiplies or divides by integers of $O(\log N)$ bits. Hence all intermediate rational numbers have bit length polynomial in $N$ and $L$, and construction takes
$$ \operatorname{poly}(N,m,L) $$
bit operations.

To evaluate the lift, sort the finite profile in $O(N\log N)$ comparisons. If
$$ c_k=\widehat x_k-\widehat x_{k-1}, $$
the rebate of the agent at deletion rank $i$ is
$$ \sum_{k<i}c_kv_k+ \sum_{k\ge i}^{N-1}c_kv_{k+1}. $$
Prefix and suffix sums evaluate all rebates in $O(N)$ additional rational operations. The Clarke payments can likewise be evaluated from suffix sums of the quality-drop terms.

The complete finite mechanism can therefore be evaluated in
$$ \operatorname{poly}(N,m,L,H_{\mathrm{prof}}) $$
bit operations.

The fallback rule defines valid mechanisms even at early resolutions with one-slot interior components, coincident discrete drops, or insufficient separation. Since only finitely many resolutions fall back for any fixed schedule, this does not affect the law or optimal asymptotic guarantee.

⟨structured verdict parsed — rendered above⟩

The output resolves the assigned task. The finite LP reduction, asymptotic upper bound, constructive lower bound, individual rebate limits, and polynomial-time claims are consistent and correct. I found no major or minor issues requiring repair.

• Quality drops and discretization.

Merging adjacent intervals of equal height gives positive drops at
$$ 0<\alpha_1<\cdots<\alpha_s=\rho. $$
Including the final drop to zero is necessary and is handled correctly.

For an interior drop, the index is $\lceil\alpha_rN\rceil$: this is where the sampling points defining consecutive qualities first straddle the drop. The final drop instead occurs at $p_N=\lfloor\rho N\rfloor$, because the last sampled quality is followed by the stipulated zero quality.

Once the distinct drops have distinct indices, the limits
$$ \frac{b_{d_r}^N}{N}\longrightarrow A_r, \qquad \frac{b_{d_r+1}^N}{N}\longrightarrow B_r $$
follow from the definitions. The distinction between the cumulative surplus before and after the drop is maintained throughout the proof.

• The finite LP gives a valid upper bound for arbitrary permitted rebates.

On a binary profile with $k$ ones, each recipient sees one of the two deletion profiles used to define $x_{k-1}$ and $x_k$. Thus the aggregate rebate is exactly
$$ kx_{k-1}+(N-k)x_k. $$
Nonnegative rebates give $x_k\ge0$, and universal feasibility gives the upper LP constraints.

For $T\ge2$, every binary profile belongs to the support-bounded test class. The positive-surplus binary profiles therefore give the lower constraints for any claimed guarantee. At zero surplus, the lower constraint is automatic, while the upper constraint remains necessary.

Consequently, this upper bound applies to nonlinear rebate functions as well as linear ones. There is no unsupported restriction of the mechanism class.

• The LP coefficients yield universally feasible mechanisms.

The constraint at $k=0$ gives $x_0=0$. The summation-by-parts identity
$$ f_N(y)=\sum_{k=1}^{N-1}x_k(y_k-y_{k+1}) $$
establishes individual nonnegativity, even when some differences $x_k-x_{k-1}$ are negative.

Both full-profile decomposition identities are correct. In particular, deleting a fixed rank preserves linearity in the ordered coordinates on the cone of decreasing profiles. Evaluating the aggregate on the displayed binary vectors therefore gives the stated coefficients $z_k$.

Multiplying the LP inequalities by $v_k-v_{k+1}\ge0$ proves the guarantee and budget constraint on every nonnegative real profile. This includes profiles with more than $T$ values and profiles with zero surplus.

Symmetry, determinism, and independence from the recipient’s report are satisfied. The rebate adds a term independent of that report to the recipient’s Clarke utility, so dominant-strategy truthfulness is preserved.

The LP feasible region is nonempty, closed, and bounded by the stated coordinate bounds. Its optimum exists. Together, the upper bound and construction justify
$$ E(\rho,\gamma,T)=\liminf_{N\to\infty}e_N \qquad(T\ge2). $$

• The upper bound at drops beyond one half is valid.

The elimination of $x_k$ from consecutive upper and lower constraints has the correct signs and coefficients:
$$ x_{k-1} \le \frac{\beta}{k} -\frac{(N-k)e_N\beta}{k(k+1)} +\frac{(N-k)(N-k-1)}{k(k+1)}x_{k+1}. $$

Starting at $k=d+2$ bounds $x_{d+1}$, as required. For each fixed number of iterations, all ranks remain in the same constant-surplus segment for sufficiently large $N$.

The limiting iteration coefficient is
$$ \left(\frac{1-\alpha}{\alpha}\right)^2<1. $$
The terminal-variable bound follows from the next upper constraint. Its limiting bound can be chosen independently of the fixed iteration count, permitting the subsequent limit in that count.

The resulting estimate for $\limsup x_{d+1}$ and the jump constraint give the displayed inequality for $e$. Rearrangement produces exactly $\Phi_r$; all divided denominators are positive because $\alpha>1/2$.

Thus every subsequential limit satisfies every applicable drop bound, establishing
$$ \limsup_{N\to\infty}e_N\le e_*. $$

• The finite construction and feasibility correction are sound.

The reserved intervals eventually become disjoint and lie inside the allowed index range: their widths are $O(\sqrt N)$, whereas the fixed drop separations and distances from the endpoints correspond to distances proportional to $N$.

At every resolution, the fallback mechanism is permitted. When the exact checks pass, nonnegative coefficients give nonnegative rebates and nonnegative aggregate coefficients. The zero-surplus check enforces the corresponding budget constraints exactly.

Scaling by $\lambda_N$ then enforces every positive-surplus upper constraint. Hence finite feasibility does not depend on the asymptotic estimates being accurate at a particular resolution.

The construction need not be finite-optimal at each resolution. This matches the task’s definition of an exact finite lift: exact feasibility, realization of the individual limits, and attainment of the asymptotic worst-case value.

• The three local asymptotic analyses check out.

For drops below one half, the forward recurrence has the stated error multiplier
$$ -\frac{k}{N-k}. $$
Its magnitude is uniformly below one on the modified interval for sufficiently large $N$. Starting from $A_N\in[0,B_N]$ establishes nonnegativity and geometric decay. The transition budget error has the claimed vanishing relative bound.

At one half, the alternating tapered coefficients are nonnegative. The identity involving $\theta_\ell$ is correct, and the uniform error bound
$$ O\left(\frac{h}{N}+\frac1h\right) $$
tends to zero. The endpoint coefficient equals $B_N$, so the following budget equation is exact.

Beyond one half, the backward-map identities for $H_N$ and $L_N$ are correct. The parity of the construction makes $x_{d+1}$ a high coefficient. The exact maps are contractions with a fixed factor below one, and their perturbations from the constant-coefficient maps are uniformly $O(h/N)$.

When $e<1$, the lower-coefficient margin supplied by $\varepsilon_N$ dominates this perturbation. When $e=1$, the recurrence preserves $B_N$ exactly. These arguments establish eventual post-drop nonnegativity and the claimed limit $V$.

The cap defining $x_d$ establishes nonnegativity of the first preceding coefficient. The subsequent induction uses the correct rank-dependent bounds. The pre-drop contraction proves that the transition error vanishes; the case $A_N=0$ is explicitly handled.

• The jump budget and global lower bound are justified.

The limiting cap is redundant for the reasons given: the case $e\le r$ makes the inner maximum zero, and the case $e>r$ uses precisely the inequality $e\le\Phi_r$.

The limiting jump budget is therefore
$$ \max\{eB,(1-\alpha)V\}, $$
which lies in $[eB,B]$ by the stated bounds.

There are finitely many drops, so the local uniform estimates combine into uniform estimates over all positive-surplus ranks. Zero-surplus ranks retain exactly zero aggregate rebates. Thus the fallback checks eventually pass,
$$ \lambda_N\longrightarrow1, \qquad \liminf\eta_N\ge e_*. $$
Combined with the upper bound, this proves $e_N\to e_*$ and settles the claimed value for $T\ge2$.

• The limiting redistribution law uses the correct boundary ranks.

Deleting a recipient of type $v_h$ leaves
$$ K_a=NC_a-\mathbf1_{\{h\le a\}} $$
agents above each value gap. The exact finite rebate expansion using these ranks is correct.

Away from drop locations, the selected ranks eventually lie outside every modification interval. At a boundary $C_a=\alpha_r$, integrality makes the drop index exactly $NC_a$, including at the final drop. Deletion therefore selects $d-1$ for $h\le a$ and $d$ otherwise.

These ranks produce precisely the stated coefficients $W_r$ and $U_r$ beyond one half, and $A_r$ at or below one half. The baseline coefficient converges to $b$. Scaling does not alter these limits because $\lambda_N\to1$.

The resulting law exists for every rational society and every supported recipient type, and is realized by the constructed mechanism sequence.

• The case $T=1$ is proved separately and correctly.

The deletion-rank counting formula has the correct multiplicities. Monotonicity of the ordered values proves universal feasibility of the proposed rebate.

On a positive constant profile, all needed deletion order statistics exist because $N>p+1$, and total rebates equal surplus. This proves $E=1$.

The limiting quantile convention is also correct. At a cumulative-mass boundary, rank $d_r+1$ after either kind of deletion eventually belongs to the lower-valued block. Thus the displayed limiting law is independent of recipient type and has the claimed boundary convention.

• The computational claims meet the requested scope.

The optimal-value formula uses $O(m)$ rational operations and has polynomial bit complexity in the binary input length. Dependence on $T$ is limited to distinguishing $T=1$ from $T\ge2$.

Sorting the society, merging cumulative masses with drop locations, and accumulating the recipient corrections support the claimed polynomial computation of all limiting rebates.

For finite lifts, the recurrence depths and integer factors give polynomial intermediate bit lengths in $N$ and $L$. Exact checks and scaling remain polynomial. For binary-encoded rational finite reports, sorting and prefix/suffix evaluation give the claimed polynomial dependence on $N$, $m$, $L$, and the finite profile’s bit length.

No polynomial bound on the resolution needed for asymptotic convergence is claimed or needed. The cited finite-mechanism result is not used as an unverified premise; the output supplies its own reduction and construction.

No additional clarification is needed to make the argument verifiable.

⟨structured verdict parsed — rendered above⟩