Answer: —
Theorem 1 — class: algorithmic
Given rational type masses \(\mu_t\), moving costs \(r_t\), a rational prior \((\pi_0,\pi_1)\), and rational \(A,B>0\), let \(f(z)=A/(B+z)\). Choose distributions \(\kappa_0,\kappa_1\) over feasible mass vectors \(x\), where \(0\le x_t\le\mu_t\) and \(z=\sum_t x_t\). Maximize \(\sum_{\theta\in\{0,1\}}\pi_\theta\int(\theta zf(z)-\sum_t r_tx_t)\,d\kappa_\theta(x)\), subject for every type \(t\) to \(\sum_\theta\pi_\theta\int x_t(\theta f(z)-r_t)\,d\kappa_\theta(x)\ge0\) and \(\sum_\theta\pi_\theta\int(\mu_t-x_t)(\theta f(z)-r_t)\,d\kappa_\theta(x)\le0\). Determine an optimal pair of signaling distributions and its computational complexity in \(\tau\) and the input bit length.
A society is given by its support: the list of \(\tau\ge1\) types with positive mass, each mass \(\mu_t\) a binary rational; \(\tau\) counts supported types, not possible types. Total mass \(M=\sum_t\mu_t\) need not equal one. There are \(m=2\) locations, and all agents initially occupy the first.
Type \(t\) has rational moving cost \(r_t\ge0\). Staying yields zero; moving yields \(\theta f(z)-r_t\), where \(\theta\in\{0,1\}\), \(z\) is total moving mass, and \(f(z)=A/(B+z)\) for rational \(A,B>0\). Agents are nonatomic, so unilateral deviations do not change \(z\).
The principal observes the state, whose common rational prior satisfies \(\pi_0,\pi_1\ge0\) and \(\pi_0+\pi_1=1\), and commits to private move/stay recommendations. Indifferent agents follow their recommendations.
A mechanism consists of Borel probability distributions \(\kappa_0,\kappa_1\) on \(X=\prod_{t=1}^{\tau}[0,\mu_t]\); \(x_t\) is the mass of type \(t\) recommended to move, and \(z=\sum_t x_t\). Within each type, recommendations are exchangeable; each agent observes only her own recommendation.
For every type \(t\), obedience requires \(\sum_{\theta=0}^{1}\pi_\theta\int_X x_t(\theta f(z)-r_t)\,d\kappa_\theta(x)\ge0\) and \(\sum_{\theta=0}^{1}\pi_\theta\int_X(\mu_t-x_t)(\theta f(z)-r_t)\,d\kappa_\theta(x)\le0\).
Maximize expected welfare \(W(\kappa)=\sum_{\theta=0}^{1}\pi_\theta\int_X(\theta zf(z)-\sum_t r_tx_t)\,d\kappa_\theta(x)\). For a binary-rational threshold \(q\), the exact decision problem asks whether an obedient mechanism with \(W(\kappa)\ge q\) exists. Let \(L\) be the total input bit length, including \(q\).
Is this exact continuous private-signaling decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For explicitly listed finite agents, optimal private signaling is computable in polynomial time using a linear program with \(O(N^2)\) variables and an efficient sampling procedure. [Yang, Iyer and Frazier](https://arxiv.org/pdf/1909.12723)
For nonatomic routing with polynomial latencies and fixed nonparticipant flow, optimal private signaling admits a finitely supported solution and a polynomial optimization formulation; that result concerns different payoffs. [Zhu and Savla](https://arxiv.org/pdf/2005.03000)
No result settling the exact continuous problem specified here was located.
The exact complexity classification remains unresolved. I prove three additional structural and algorithmic results:
All these statements use supported masses as given; no normalization of total mass is assumed.
Write $p=\pi_1$.
If $p=0$, welfare is nonpositive. Recommending universal staying is obedient and achieves zero. Thus the answer is yes exactly when $q\leq 0$.
Assume henceforth that $p>0$. Replace $\kappa_0$ by $\delta_0$. For type $t$, this increases its move-obedience expression by
$$
(1-p)r_t\int x_t\,d\kappa_0,
$$
decreases its stay-obedience expression by the same quantity, and increases welfare by the sum of these quantities. All are nonnegative. Consequently, this replacement preserves obedience and weakly increases welfare.
For a state-$1$ distribution, define
$$
h=\mathbb E[f(z)],
\qquad
u_t=\mathbb E[x_t(f(z)-r_t)].
$$
With $\kappa_0=\delta_0$, the obedience conditions become
$$
u_t\geq 0,
\qquad
u_t-\mu_t\left(h-\frac{r_t}{p}\right)\geq 0.
$$
Indeed, the original stay-obedience expression is
$$
p\mu_t h-pu_t-\mu_t r_t.
$$
Welfare becomes
$$
W=p\sum_t u_t.
$$
Define
$$
H(x)=\left(f(z),x_1(f(z)-r_1),\ldots,x_\tau(f(z)-r_\tau)\right),
\qquad
C=\operatorname{conv}(H(X)).
$$
The set $H(X)$ is compact because $X$ is compact and $B+z\geq B>0$. Its convex hull is compact: by Carathéodory’s theorem, it is the image of a compact set of convex combinations involving at most $\tau+2$ points.
The attainable moment vectors are exactly $C$. Finite convex combinations are realized by finitely supported Borel distributions. Conversely, an expectation outside $C$ would, by strict separation, have some linear functional larger than its maximum on $H(X)$, which is impossible.
Thus the exact problem is
$$
(h,u)\in C,
\qquad
u_t\geq 0,
\qquad
u_t-\mu_t\left(h-\frac{r_t}{p}\right)\geq 0,
\qquad
p\sum_tu_t\geq q.
$$
The following lemma supplies both a feasible mechanism and a tool used later.
Lemma. Given positive rational $A',B'$ and supported masses and costs, a rational profile $y$ satisfying
$$
y_t\left(\frac{A'}{B'+\sum_s y_s}-r_t\right)\geq 0,
\qquad
(\mu_t-y_t)\left(\frac{A'}{B'+\sum_s y_s}-r_t\right)\leq 0
$$
can be computed in polynomial time.
Proof. A maximizer on $X$ of
$$
A'\log\left(B'+\sum_t y_t\right)-\sum_t r_t y_t
$$
exists. Its coordinate derivatives are
$$
\frac{A'}{B'+\sum_s y_s}-r_t.
$$
The necessary one-sided derivative conditions imply that this expression is nonpositive at a zero coordinate, zero at an interior coordinate, and nonnegative at a full coordinate. These are precisely the asserted inequalities.
To compute such a profile without evaluating logarithms, sort costs so that
$$
r_1\leq r_2\leq\cdots\leq r_\tau,
$$
and put $T_j=\sum_{i\leq j}\mu_i$, with $T_0=0$.
At a fixed total mass $z\in[T_{j-1},T_j]$, minimum moving cost is attained by filling the first $j-1$ types and partially filling type $j$. This follows by transferring mass from a higher-cost occupied coordinate to a lower-cost unfilled coordinate. Its cost is
$$
K(z)=\sum_{i<j}r_i\mu_i+r_j(z-T_{j-1}).
$$
The maximum potential at total mass $z$ is therefore
$$
A'\log(B'+z)-K(z).
$$
This function is strictly concave: the logarithmic term is strictly concave, and $K$ is convex because its successive slopes are the sorted costs.
On the interior of the $j$th segment, its derivative is
$$
\frac{A'}{B'+z}-r_j.
$$
An interior maximizer, when $r_j>0$, is consequently
$$
z=\frac{A'}{r_j}-B'.
$$
At an interior prefix $T_j$, the maximizer condition is
$$
r_j\leq \frac{A'}{B'+T_j}\leq r_{j+1}.
$$
The two endpoint conditions are respectively
$$
\frac{A'}{B'}\leq r_1,
\qquad
\frac{A'}{B'+T_\tau}\geq r_\tau.
$$
Scanning these rational conditions and the rational interior candidates finds the unique maximizing total. The corresponding greedy profile satisfies the coordinate conditions above.
Sorting and all subsequent rational arithmetic have polynomial bit complexity. $\square$
Applying the lemma with $A'=A$ and $B'=B$ gives an obedient mechanism consisting of this state-$1$ profile and universal staying in state $0$. Hence the feasible moment set is nonempty. Being a closed subset of compact $C$, it is compact, and optimal welfare is attained.
Theorem. If $p=1$, every obedient mechanism has the same total moving mass almost surely and the same welfare. The exact decision problem is polynomial-time solvable.
Proof. Let $y$ be the profile constructed by the equilibrium lemma, and write
$$
z_*=\sum_t y_t,
\qquad
f_*=f(z_*).
$$
Its coordinate conditions imply, for every $x\in X$,
$$
\sum_t(x_t-y_t)(f_*-r_t)\leq 0.
$$
To check this coordinatewise:
Now let $x$ be distributed according to any obedient state-$1$ mechanism. Because $p=1$, obedience gives
$$
\mathbb E[x_t(f(z)-r_t)]\geq0,
\qquad
\mathbb E[(\mu_t-x_t)(f(z)-r_t)]\leq0.
$$
For each $t$,
$$
\begin{aligned}
\mathbb E[(x_t-y_t)(f(z)-r_t)]
={}&
\left(1-\frac{y_t}{\mu_t}\right)
\mathbb E[x_t(f(z)-r_t)]\\
&-\frac{y_t}{\mu_t}
\mathbb E[(\mu_t-x_t)(f(z)-r_t)]
\geq0.
\end{aligned}
$$
Summing, and subtracting the preceding equilibrium inequality in expectation, yields
$$
\mathbb E[(z-z_*)(f(z)-f_*)]\geq0.
$$
But $f$ is strictly decreasing, so
$$
(z-z_*)(f(z)-f_*)\leq0,
$$
with equality exactly when $z=z_*$. The integrand must therefore vanish almost surely:
$$
z=z_*\quad\text{almost surely}.
$$
Thus $f(z)=f_*$ almost surely. If $r_t<f_*$, stay obedience becomes
$$
(f_*-r_t)(\mu_t-\mathbb E[x_t])\leq0,
$$
forcing $\mathbb E[x_t]=\mu_t$, and hence $x_t=\mu_t$ almost surely. If $r_t>f_*$, move obedience forces $x_t=0$ almost surely. Types with $r_t=f_*$ contribute zero welfare regardless of their allocation.
Every obedient mechanism consequently has welfare
$$
W_*=\sum_{t:r_t<f_*}\mu_t(f_*-r_t).
$$
The equilibrium lemma computes rational $z_*$, so $f_*$ and $W_*$ are rational with polynomial encoding length. Comparing $W_*$ with $q$ decides the instance exactly in polynomial time. $\square$
The rigidity argument uses nonatomicity: each obedience expression evaluates deviations at the same total $z$.
Let $E\subseteq X$ be the union of all edges of the box. Equivalently, $E$ consists of profiles having at most one coordinate strictly between zero and its supported mass.
Proposition.
$$
C=\operatorname{conv}(H(E)).
$$
Proof. Fix a profile $x$ and its total $z$. On
$$
Q_z=\left\{y\in X:\sum_t y_t=z\right\},
$$
the map $H$ is affine, because $f(z)$ is constant.
Suppose $x$ has two partial coordinates $i,j$. Set
$$
a=\min\{\mu_i-x_i,x_j\}>0,
\qquad
b=\min\{x_i,\mu_j-x_j\}>0.
$$
The profiles
$$
x^+=x+a(e_i-e_j),
\qquad
x^-=x-b(e_i-e_j)
$$
belong to $Q_z$, and each has fewer partial coordinates than $x$. Moreover,
$$
x=\frac{b}{a+b}x^++\frac{a}{a+b}x^-.
$$
Repeating this decomposition terminates after finitely many steps, expressing $x$ as a convex combination of profiles in $E\cap Q_z$. Affineness of $H$ on $Q_z$ gives the same convex combination for $H(x)$. The reverse inclusion follows from $E\subseteq X$. $\square$
Index an edge by a partially variable type $j$ and a subset
$$
S\subseteq\{1,\ldots,\tau\}\setminus\{j\}.
$$
Types in $S$ move fully, types outside $S\cup\{j\}$ stay, and type $j$ has moving mass $y\in[0,\mu_j]$.
Put
$$
c_S=\sum_{t\in S}\mu_t,
\qquad
K=B+c_S,
\qquad
s=\frac{A}{K+y}.
$$
Then
$$
a=\frac{A}{K+\mu_j}\leq s\leq \frac{A}{K}=b.
$$
Since $\mu_j>0$, we have $0<a<b$.
Along this edge,
$$
H_0=s,
$$
and for $t\in S$,
$$
H_t=\mu_t(s-r_t).
$$
For the partial type,
$$
\begin{aligned}
H_j
&=\left(\frac{A}{s}-K\right)(s-r_j)\\
&=A+Kr_j-Ks-\frac{Ar_j}{s}.
\end{aligned}
$$
Therefore, an arbitrary distribution along the edge affects its moments only through
$$
\bar s=\mathbb E[s],
\qquad
v=\mathbb E[1/s].
$$
Their exact feasible set is
$$
a\leq\bar s\leq b,
\qquad
\frac1{\bar s}\leq v\leq\frac{a+b-\bar s}{ab}.
$$
For necessity, the lower bound is Jensen’s inequality for the convex function $s\mapsto1/s$. The upper bound follows from its secant inequality on $[a,b]$:
$$
\frac1s\leq\frac{a+b-s}{ab}.
$$
For sufficiency, fix $\bar s$. The point mass at $\bar s$ realizes the lower bound. The distribution on $\{a,b\}$ with probability
$$
\frac{b-\bar s}{b-a}
$$
at $a$ has mean $\bar s$ and realizes the upper bound. Mixing these two distributions realizes every intermediate $v$ while preserving the mean. Thus the description is exact.
For every edge $e=(S,j)$, introduce variables
$$
\lambda_e,\qquad h_e,\qquad v_e.
$$
Here $\lambda_e$ is its mixture weight, while $h_e$ and $v_e$ are its weighted reciprocal moments. With the edge-specific constants $K_e,a_e,b_e$ defined above, impose
$$
\lambda_e\geq0,\qquad h_e\geq0,\qquad v_e\geq0,
$$
$$
a_e\lambda_e\leq h_e\leq b_e\lambda_e,
$$
$$
h_ev_e\geq\lambda_e^2,
\qquad
v_e\leq
\frac{(a_e+b_e)\lambda_e-h_e}{a_eb_e}.
$$
The nonlinear inequality is a rotated second-order cone constraint; explicitly, it is equivalent to
$$
\left\|(2\lambda_e,h_e-v_e)\right\|_2\leq h_e+v_e.
$$
If $\lambda_e>0$, dividing by $\lambda_e$ gives exactly the preceding one-edge moment description. If $\lambda_e=0$, the linear bounds force $h_e=v_e=0$.
Require
$$
\sum_e\lambda_e=1,
\qquad
h=\sum_e h_e.
$$
The contribution of edge $e=(S,j)$ to coordinate $u_t$ is
$$
u_{t,e}=
\begin{cases}
\mu_t(h_e-r_t\lambda_e),&t\in S,\\
(A+K_er_t)\lambda_e-K_eh_e-Ar_tv_e,&t=j,\\
0,&t\notin S\cup\{j\}.
\end{cases}
$$
Set
$$
u_t=\sum_e u_{t,e}.
$$
The proposition and the exact one-edge convexification prove that the projection of this conic system is precisely $C$. Adding the linear obedience inequalities and welfare threshold therefore gives an exact second-order cone feasibility formulation of the original decision problem.
There are
$$
\tau 2^{\tau-1}
$$
edges. Each block has rational coefficients of polynomial encoding length, but the number of blocks is exponential in $\tau$. This formulation consequently does not establish a polynomial-time exact algorithm.
Proposition. Every attainable moment vector is realizable by at most $\tau+1$ profiles in $E$.
Proof. The box-edge set $E$ is path connected. Any edge point can be joined to a vertex along its edge; any two vertices can be joined by successively changing coordinates along box edges. Since $H$ is continuous, $H(E)$ is path connected.
We use the following elementary refinement of Carathéodory’s theorem: if $S\subseteq\mathbb R^d$ is path connected, every point of $\operatorname{conv}(S)$ is a convex combination of at most $d$ points of $S$.
To prove the refinement, start with a Carathéodory representation. If it already uses at most $d$ points, there is nothing to prove. Otherwise it uses $d+1$ affinely independent points $a_0,\ldots,a_d$, all with positive weights. Move $a_0$ continuously along a path in $S$ ending at $a_1$, keeping the other points fixed.
Initially the target lies in the interior of the resulting simplex. Continue until the first time that affine independence or positivity of all barycentric coordinates fails. Such a time exists because the final simplex has coincident vertices. Taking limits of the barycentric coordinates shows that the target still belongs to the simplex at this first failure time.
If the vertices remain affinely independent, a barycentric coordinate is zero, leaving at most $d$ points. If they become dependent, their affine hull has dimension at most $d-1$, and ordinary Carathéodory in that affine hull again gives at most $d$ points.
Apply this refinement with $d=\tau+1$ and $S=H(E)$. $\square$
In particular, an optimum exists with at most $\tau+1$ state-$1$ profiles, each having at most one partially moving type. This is a support-size statement, not a bound on the encoding length of optimal real atom locations.
I now prove the following result, which applies jointly to variable $\tau$ and heterogeneous costs.
Theorem. For rational $0<\varepsilon\leq1$, one can compute a rational number $\widehat W$ satisfying
$$
|\widehat W-W_*|\leq\varepsilon
$$
in time polynomial in $\tau$, $L$, and the encoding length of $\varepsilon$. In particular, the dependence on required precision is polynomial in $\log(1/\varepsilon)$.
The cases $p=0$ and $p=1$ were already solved exactly. Assume throughout this section that
$$
0<p<1.
$$
For a zero-cost type, reduced stay obedience gives
$$
\mathbb E[(\mu_t-x_t)f(z)]\leq0.
$$
The integrand is nonnegative and $f(z)>0$. Hence
$$
x_t=\mu_t\quad\text{almost surely}.
$$
Let
$$
Z_0=\sum_{t:r_t=0}\mu_t,
\qquad
B'=B+Z_0,
\qquad
F=\frac{A}{B'}.
$$
For every remaining type, $f(z)\leq F$. If $r_t\geq F$, then
$$
x_t(f(z)-r_t)\leq0.
$$
Moreover, it is strictly negative whenever $x_t>0$, because then $z>Z_0$ and $f(z)<F\leq r_t$. Move obedience therefore forces
$$
x_t=0\quad\text{almost surely}.
$$
Their stay constraints hold automatically, since $ph\leq pF\leq r_t$.
The remaining $k$ active types consequently satisfy
$$
0<r_t<F.
$$
Relabel them by $t=1,\ldots,k$. Their payoff function is
$$
f'(z)=\frac{A}{B'+z},
$$
where $z$ now denotes only active moving mass.
Their moments are
$$
h=\mathbb E[f'(z)],
\qquad
u_t=\mathbb E[x_t(f'(z)-r_t)].
$$
Their constraints remain
$$
u_t\geq0,
\qquad
u_t-\mu_t\left(h-\frac{r_t}{p}\right)\geq0.
$$
Welfare, including the forced zero-cost movers, is
$$
w(h,u)=p\left(Z_0h+\sum_{t=1}^k u_t\right).
$$
If $k=0$, the state-$1$ profile is fixed and
$$
W_*=pZ_0F,
$$
which is rational. We may therefore assume $k\geq1$.
Let $C'$ denote the compact attainable moment set for these active types and the function $f'$.
Define the active stay margins by
$$
b_t(h,u)=u_t-\mu_t\left(h-\frac{r_t}{p}\right).
$$
Lemma. In polynomial time, one can construct a rational finitely supported mechanism and a positive rational $\eta$, both of polynomial encoding length, such that
$$
u_t\geq\eta,
\qquad
b_t(h,u)\geq\eta
$$
for every active type.
Proof. Put
$$
s=\frac{1+p}{2},
$$
so that $p<s<1$. Apply the equilibrium lemma to the payoff
$$
s f'(z)-r_t.
$$
It gives a rational profile $y$. Write
$$
h_y=f'\left(\sum_t y_t\right).
$$
Its coordinate conditions imply:
In every case, the move utility at $y$ is nonnegative. Its stay margin is strictly positive:
If $y_t=0$, then
$$
b_t(y)=\mu_t\left(\frac{r_t}{p}-h_y\right)
\geq
\mu_t\left(\frac{s}{p}-1\right)h_y>0.
$$
If $0<y_t<\mu_t$, then
$$
b_t(y)
=
y_t(1-s)h_y+
\mu_t\left(\frac{s}{p}-1\right)h_y>0.
$$
If $y_t=\mu_t$, then
$$
b_t(y)=\mu_t r_t\left(\frac1p-1\right)>0,
$$
using $r_t>0$.
Let
$$
d=\min_t b_t(y)>0.
$$
For each type $t$, choose the positive rational
$$
e_t=
\min\left\{
\frac{\mu_t}{2},
\frac{A/r_t-B'}{2}
\right\}.
$$
The second entry is positive because $r_t<F$. The profile moving only mass $e_t$ of type $t$ satisfies
$$
f'(e_t)>r_t.
$$
Let $\nu$ be the uniform distribution on these $k$ profiles. Then every move utility under $\nu$ is positive:
$$
u_t(\nu)=\frac{e_t(f'(e_t)-r_t)}{k}>0.
$$
For any active profile,
$$
|u_t|\leq\mu_t(F+r_t),
$$
and
$$
|b_t|\leq
\mu_t\left(2F+r_t+\frac{r_t}{p}\right).
$$
Choose the rational bound
$$
G=
\max\left\{
1,\,
\max_t\mu_t\left(2F+r_t+\frac{r_t}{p}\right)
\right\}.
$$
In particular, $b_t(\nu)\geq-G$.
Now set
$$
\delta=\frac{d}{2(d+G)}
$$
and use the distribution
$$
(1-\delta)\delta_y+\delta\nu.
$$
Its stay margins satisfy
$$
b_t\geq(1-\delta)d-\delta G=\frac d2.
$$
Its move utilities satisfy
$$
u_t\geq
\frac{\delta}{k}e_t(f'(e_t)-r_t).
$$
Thus one may take
$$
\eta=
\min\left\{
\frac d2,\,
\frac{\delta}{k}
\min_t e_t(f'(e_t)-r_t)
\right\}>0.
$$
Every quantity used here is obtained by polynomially many rational operations from polynomial-length inputs. The profiles, probabilities, and $\eta$ therefore have polynomial encoding length. $\square$
Lemma. Given rational coefficients $d_0,d_1,\ldots,d_k$ and rational $\xi>0$, one can compute a rational profile $x$ such that
$$
d\cdot H'(x)\geq
\max_{v\in C'}d\cdot v-\xi
$$
in time polynomial in the input lengths and $\log(1/\xi)$.
Here $H'$ is the active moment map.
Proof. Linear optimization over $C'$ equals optimization over $H'(X')$. At fixed total active mass $z$, the expression to maximize is
$$
d_0 f'(z)+\sum_t d_t x_t(f'(z)-r_t).
$$
The allocation part is a continuous knapsack problem with coefficients
$$
a_t(z)=d_t\left(\frac{A}{B'+z}-r_t\right).
$$
An optimal allocation fills types in nonincreasing coefficient order, with at most one partial type. The exchange argument is the same as in the equilibrium lemma.
A pair of coefficients crosses only when
$$
A(d_i-d_j)=(d_ir_i-d_jr_j)(B'+z).
$$
Unless the pair is identical throughout, there is at most one crossing, and its location is rational. These crossings partition the total-mass interval into $O(k^2)$ intervals having fixed coefficient order. At a crossing endpoint, the chosen order remains valid because the crossing coefficients tie.
For each ordering, adding its prefix mass sums yields at most $k+1$ further pieces. Thus there are $O(k^3)$ pieces altogether.
On each piece, the greedy coordinates are constant except for one coordinate affine in $z$. Substitution gives
$$
\ell(z)=\alpha z+\beta+\frac{\gamma}{B'+z},
$$
with polynomial-length rational coefficients. Its derivative is
$$
\ell'(z)=\alpha-\frac{\gamma}{(B'+z)^2}.
$$
A maximum occurs at an endpoint or an interior stationary point. If $\alpha\neq0$ and $\gamma/\alpha>0$, the sole possible stationary point in the domain is
$$
z=\sqrt{\frac{\gamma}{\alpha}}-B'.
$$
Otherwise there is no isolated stationary point. The case $\alpha=\gamma=0$ is constant.
Membership of a stationary point in a rational interval is decided by comparing $\gamma/\alpha$ with the squares of its positive shifted endpoints. Its square root can be approximated by rational bisection.
Finally, the derivative bounds
$$
\left|\frac{\partial f'}{\partial x_j}\right|
\leq\frac{A}{(B')^2},
$$
and
$$
\left|\frac{\partial H'_t}{\partial x_j}\right|
\leq F+r_t+\frac{\mu_tA}{(B')^2}
$$
give an explicitly computable rational Lipschitz bound of polynomial encoding length. Consequently, every candidate can be replaced by a feasible rational profile whose objective value differs by at most $\xi/2$, using polynomially many bits. Clamping approximated stationary totals to their rational piece intervals preserves feasibility.
Evaluate the resulting polynomially many rational profiles exactly and select the largest value. This gives the asserted additive guarantee. $\square$
Collect the $n=2k$ active obedience margins into
$$
g(v)=
\left(u_1,\ldots,u_k,b_1,\ldots,b_k\right),
\qquad v=(h,u).
$$
Then
$$
W_*=\max\{w(v):v\in C',\ g(v)\geq0\}.
$$
For $c\in\mathbb R_{\geq0}^n$, define
$$
D(c)=\max_{v\in C'}\bigl(w(v)+c\cdot g(v)\bigr).
$$
Weak duality gives
$$
D(c)\geq W_*.
$$
There is an attained dual optimum with equality. Here is a direct separation proof.
Consider the downward closed convex set
$$
K=
\left\{
(b,a):
\text{there exists }v\in C'
\text{ with }b\leq g(v),\ a\leq w(v)
\right\}.
$$
It is closed: for a convergent sequence in $K$, compactness of $C'$ supplies a convergent subsequence of witnessing moments, and the inequalities pass to the limit.
The point $(0,W_*)$ belongs to the boundary of $K$. It belongs to $K$ by attainment of the primal optimum, while $(0,W_*+\rho)$ is outside $K$ for every $\rho>0$.
A supporting hyperplane at $(0,W_*)$ has a nonzero normal $(c,\beta)$ satisfying
$$
c\cdot b+\beta a\leq\beta W_*
\quad\text{for all }(b,a)\in K.
$$
Downward closure forces $c\geq0$ and $\beta\geq0$. The strictly feasible moment $v_0$ from the preceding lemma has $g_i(v_0)\geq\eta>0$. If $\beta=0$, the supporting inequality would imply
$$
c\cdot g(v_0)\leq0,
$$
contradicting $c\neq0$ and strict positivity. Therefore $\beta>0$. Dividing by $\beta$ gives a nonnegative dual vector with
$$
D(c)\leq W_*.
$$
Together with weak duality, this proves equality and attainment.
Moreover,
$$
D(c)\geq w(v_0)+\eta\sum_i c_i.
$$
Here $w(v_0)\geq0$. Also every profile has welfare at most $pA$, because moving costs are nonnegative and
$$
zf(z)=\frac{Az}{B+z}\leq A.
$$
Hence an optimal dual vector satisfies
$$
\sum_i c_i\leq\frac{pA}{\eta}.
$$
Define
$$
R=\frac{pA+1}{\eta}.
$$
It follows that
$$
W_*=\min_{c\in[0,R]^n}D(c).
$$
The rational number $R$ has polynomial encoding length.
The bound $G$ constructed above bounds every component of $g(v)$ in absolute value. Therefore, on the box $[0,R]^n$,
$$
0\leq D(c)\leq pA+nRG.
$$
Set
$$
T=pA+nRG+1
$$
and consider the convex body
$$
\mathcal E=
\left\{
(c,t):
c\in[0,R]^n,\ D(c)\leq t\leq T
\right\}.
$$
Its minimum $t$-coordinate is exactly $W_*$.
This body has explicitly known rational inner and outer balls. In particular, let
$$
a_0=(R/2,\ldots,R/2,T-1/2),
\qquad
\rho=\min\{R/4,1/4\}.
$$
The ball of radius $\rho$ around $a_0$ stays inside the coordinate box and has
$$
T-\frac34\leq t\leq T-\frac14.
$$
Since $D(c)\leq T-1$ throughout the box, this ball is contained in $\mathcal E$. An outer ball centered at $a_0$ with radius
$$
R_{\mathrm{out}}=nR+T+1
$$
contains $\mathcal E$. Both radii have polynomial encoding length.
A polynomial-time weak separation oracle is available:
$$ L(c,v):=w(v)+c\cdot g(v)\geq D(c)-\xi. $$
$$
t'\geq w(v)+c'\cdot g(v)
$$
is valid throughout $\mathcal E$ and strictly separates the query point.
Thus the oracle supplies either an exact rational separating hyperplane or a certificate of distance at most $\xi$ from $\mathcal E$.
The weak separation-to-optimization theorem gives polynomial-time additive optimization of a rational linear functional over a bounded full-dimensional convex body when rational inner and outer balls and a polynomial-time weak separation oracle are provided. These are exactly the hypotheses verified above. See [Grötschel–Lovász–Schrijver, Theorem 3.1](https://ir.cwi.nl/pub/10046/10046D.pdf).
Applying that theorem to the $t$-coordinate gives a rational approximation to its minimum, and hence to $W_*$, with the stated running time. This proves the additive-approximation theorem.
As a consequence, the promise version distinguishing
$$
W_*\geq q+\varepsilon
\quad\text{from}\quad
W_*\leq q-\varepsilon
$$
is polynomial-time solvable.
The approximation theorem supplies no polynomial lower bound on a nonzero gap $|W_*-q|$. It also does not distinguish $W_*=q$ from a sufficiently close value below $q$.
Likewise, the exact conic formulation has exponentially many blocks. The improved support bound limits the number of profiles needed, but does not provide polynomial-length rational descriptions of optimal atom locations.
Therefore, the general exact decision problem for variable $\tau$, heterogeneous costs, and $0<p<1$ is still not classified here. Neither a jointly polynomial-time exact algorithm nor an $\mathrm{NP}$-hardness reduction has been proved.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial partial results, but it does not resolve the general exact decision problem in USER_TASK. I found no false central step in the structural arguments or the approximation argument. The latter has a minor omission in matching its oracle and output guarantees to the cited theorem.
The appropriate overall status is partial. The missing exact complexity classification is an acknowledged limitation, not a refutation of the results proved.
Correct.
For $p=0$, every welfare contribution is $-r_tx_t\leq0$. Universal staying satisfies both obedience inequalities and gives welfare zero. Thus the stated threshold criterion is correct, including zero-cost types.
For $p>0$, replacing $\kappa_0$ by $\delta_0$ changes the move expression, stay expression, and welfare with exactly the signs stated. The replacement therefore preserves feasibility and weakly increases welfare. This suffices for both the optimization problem and the existence question at a threshold.
The reduced stay expression is correctly computed as
$$
p\mu_th-pu_t-\mu_tr_t.
$$
Dividing its required nonpositivity by $p>0$ gives the stated constraint. The welfare identity
$$
W=p\sum_tu_t
$$
is also correct.
The identification of attainable moments with $C$ is rigorous. The moment map is continuous on compact $X$, its convex hull is compact by the stated finite-dimensional Carathéodory bound, and strict separation excludes expectations outside that convex hull. Finite combinations are admissible Borel distributions.
Correct.
The one-sided derivative signs agree with maximization over the box: the derivative is nonpositive at a zero coordinate, nonnegative at a full coordinate, and zero at an interior coordinate.
The exchange argument correctly identifies minimum moving cost at each fixed total. Sorted nonnegative costs make $K$ convex, so the resulting scalar potential is strictly concave. The interior stationary candidates, prefix conditions, and endpoint conditions have the correct signs.
The treatment covers tied costs and zero costs. Supported masses are positive, so the prefix intervals have positive length. All candidate totals and conditions involve rational arithmetic with polynomial encoding length; logarithms need not be evaluated.
Applying the lemma gives a feasible reduced mechanism for every $p>0$. Together with compactness and closed obedience constraints, this establishes attainment of optimal welfare.
Correct.
The deterministic equilibrium inequality is valid coordinatewise. The identity combining move and stay obedience is also correct; division by $\mu_t$ is legitimate because masses are positive.
After summation and subtraction, the resulting expectation inequality is exactly
$$
\mathbb E[(z-z_*)(f(z)-f_*)]\geq0.
$$
Its integrand is nonpositive because $f$ is strictly decreasing, and equality occurs only at $z=z_*$. Hence the almost-sure conclusion follows.
Once $f(z)=f_*$ almost surely, obedience forces full movement for types with $r_t<f_*$ and zero movement for types with $r_t>f_*$. Types at equality contribute zero welfare. The stated welfare formula and polynomial-time rational threshold comparison are valid.
This settles the pure-prior subcase, not the general problem.
Correct.
Both perturbed profiles remain in the same fixed-total slice, and the coefficients in the convex combination are correct. Each descendant has fewer partial coordinates, so the decomposition terminates.
At a fixed total, every coordinate of $H$ is affine in the profile. Consequently, the decomposition transfers to moment vectors and proves
$$
C=\operatorname{conv}(H(E)).
$$
The argument also covers $\tau=1$, when the entire box already has at most one partial coordinate.
Correct.
The reciprocal parametrization has the stated positive endpoints, with $a<b$ because $\mu_j>0$. Expanding the partial type’s utility gives exactly
$$
A+Kr_j-Ks-\frac{Ar_j}{s}.
$$
The lower reciprocal-moment bound follows from convexity, and the upper bound is the correct secant bound. The endpoint distribution has the required mean. Mixing it with the point mass realizes every intermediate reciprocal moment.
Zero moving cost causes no failure: the reciprocal moment remains a legitimate auxiliary variable even when its coefficient in utility vanishes.
Correct.
The displayed norm inequality is equivalent to $h_ev_e\geq\lambda_e^2$ under the imposed nonnegativity conditions.
For positive mixture weight, the constraints recover the single-edge moment region. At zero weight, the linear inequalities force both weighted moments to vanish. Thus no extraneous moments enter through zero-weight blocks.
The expressions for every edge contribution to $u_t$ are correct. Combining the blocks therefore gives exactly $C$, and adding obedience and the welfare threshold gives an exact feasibility formulation.
The block count
$$
\tau2^{\tau-1}
$$
is correct. Its exponential dependence on supported types prevents this formulation from establishing the requested polynomial-time bound.
Correct.
The edge set is path connected, including in the one-type case, and continuity preserves path connectedness of its image.
The supplied refinement of Carathéodory’s theorem is sound. Before the first failure, positive barycentric coordinates lie in a compact probability simplex. Their limiting representation at the failure time is justified by taking a convergent subsequence if necessary. Either a coefficient vanishes or affine dependence permits the stated dimension reduction.
Applying the refinement in ambient dimension $\tau+1$ gives the claimed support bound. The output correctly distinguishes support cardinality from encoding length of the real atom locations.
Correct.
For zero-cost types, the nonnegative stay-obedience integrand forces full state-$1$ movement almost surely.
After those types are fixed, $f(z)\leq F$. For a type with $r_t\geq F$, positive movement makes its move-utility integrand strictly negative. Move obedience therefore forces zero movement, including the boundary case $r_t=F$.
Their stay constraints hold automatically. The active payoff, active obedience constraints, and welfare contribution $pZ_0h$ are correctly retained. The case with no active types is handled explicitly.
Correct.
The scaled-payoff equilibrium gives nonnegative move utilities and strictly positive stay margins. All three coordinate cases have the correct calculations; positivity uses both $p<s<1$ and positive active costs.
The proposed single-type profiles have positive mass and strictly positive move utility. Their uniform mixture therefore makes every active move utility positive.
The bounds defining $G$ are valid. The mixture weight satisfies the stated stay-margin calculation, and the resulting $\eta$ is positive. The construction uses polynomially many rational operations of controlled encoding length.
This establishes strict feasibility in obedience margins; it does not assert that $C'$ itself has interior.
Correct.
At a fixed total, the objective is a continuous knapsack problem with the stated coefficients. Pairwise crossings satisfy the displayed rational equation, and nonidentical pairs have at most one crossing. Persistent ties do not invalidate the greedy allocation.
The crossing intervals and prefix subdivisions give the claimed polynomial number of pieces. On each piece, substitution produces the stated scalar function. Its derivative and possible stationary point are correct.
Endpoints and stationary candidates cover all maxima, including monotone and constant cases. The derivative bounds provide sufficient control for rational approximation, and clamping preserves feasibility. Polynomial encoding length of the interval endpoints and Lipschitz bound supports the asserted precision complexity.
Correct.
The sign of the multiplier term is appropriate for constraints $g(v)\geq0$, and weak duality follows.
The downward closed set $K$ is convex and closed. The primal optimum produces the stated boundary point, so a supporting hyperplane exists. Downward closure forces nonnegative normal components; strict feasibility excludes a zero objective component. The resulting dual equality and attainment follow.
The bounds $w(v_0)\geq0$ and $W_*\leq pA$ are valid, including the forced zero-cost movers. Hence the multiplier bound and restriction to the rational box are justified.
Sound in substance, with a minor expositional gap.
The uniform bounds on $D$, the inner ball, and the outer ball are correct. In particular, the inner ball remains above the uniformly bounded epigraph boundary.
Each support-generated inequality is valid throughout the epigraph and strictly separates whenever violated. In the acceptance branch, the stated vertical displacement gives the claimed distance bound and respects the upper cap.
The cited [Grötschel–Lovász–Schrijver theorem](https://ir.cwi.nl/pub/10046/10046D.pdf) does provide polynomial equivalence between weak separation and weak optimization for convex bodies supplied with inner and outer balls. Its definitions include normalization of separating normals and separate distance and objective tolerances.
The write-up does not explicitly match those formal output requirements. This is minor: its cuts are exact rational cuts, and the final objective is a unit coordinate functional. No new mathematical argument is needed, but the theorem application should state the normalization and explain how its output guarantees yield the claimed two-sided numerical error.
Unresolved, as the prover explicitly acknowledges.
Neither the approximation theorem nor the support bound supplies an exact threshold procedure. The conic formulation has exponentially many blocks. No hardness reduction is given.
These observations explain why the presented methods do not settle the target; they do not establish any impossibility of a polynomial-time exact algorithm.
USER_TASK, provide either a polynomial-time algorithm for arbitrary rational inputs, including threshold equality, or an appropriate hardness reduction. The established subcase and approximation results do not satisfy that requirement.No counterexample to the proved structural claims was found. The direction is promising, but its exact-complexity conclusion remains open within this output.
⟨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.