Answer: —
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateARSD is gsd-strategyproof while satisfying ex post efficiency and lsd-strategyproofness in each round.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite horizon, a shift set \(A\), per-capita capacities \(q_a\) with \(\sum_{a\in A}q_a=1\), and a finite support \(T\) of nurse types with rational masses \(\mu_\theta\), where each type specifies a strict ranking and a finite-state preference-transition rule, can one construct a finitely described history-dependent lottery over measurable assignments? Each realization must assign mass \(q_a\) to shift \(a\), each nurse must receive one indivisible shift, truthful reporting must sd-dominate unilateral misreports over the remaining horizon and in each period, and each realized assignment must be Pareto efficient.
A society is an atomless unit-mass population on \([0,1]\), given by its support: \(\tau\) types with positive binary-rational masses \(\mu_\theta\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
The input contains a horizon \(H\geq1\), a shift set \(A\) with \(m\geq2\), and positive binary-rational capacities \(q_a\) satisfying \(\sum_{a\in A}q_a=1\).
Each type specifies an initial state, a finite state set, a strict ranking of \(A\) in each state, and an explicit update \(g_\theta(s,a,z)\); \(z\) is a common shock drawn independently each period from an explicitly given finite rational distribution. Updates use true states and realized shifts, never reported rankings. Transition rules are common knowledge; current rankings are privately observed.
Each period, nurses report strict rankings after observing the public history of reports, shocks, and assignments. A policy uses these reports and histories, and each realization is a measurable map \(f_t:[0,1]\to A\) with \(\lambda(f_t^{-1}(a))=q_a\); every nurse receives one indivisible shift.
A finite description means finite formulas for jointly measurable assignment maps using rational constants, arithmetic, comparisons, Lebesgue integration, generalized inverses, and finitely many uniform random seeds. Individual reports and outcomes remain defined pointwise, including after a singleton deviation.
For nurse \(i\), let \(B_{i,\ell}(h_t)\) be her true top \(\ell\) shifts and \(p_{i,\ell}^{\sigma}(h_t)=\Pr_\sigma[f_t(i)\in B_{i,\ell}(h_t)\mid h_t]\). Define \(W_{i,\ell}^{\sigma}(h_t)=p_{i,\ell}^{\sigma}(h_t)\mathbb E_\sigma[W_{i,\ell}^{\sigma}(h_{t+1})\mid h_t]\), with terminal value \(W_{i,\ell}^{\sigma}(h_{H+1})=1\); the same rank cutoff is evaluated under the true ranking at each successor history.
Require, at every history and every cutoff, that truthful reporting weakly dominates every unilateral history-dependent reporting strategy in both \(p_{i,\ell}\) and \(W_{i,\ell}\), holding other nurses' reporting strategies fixed. Each realized assignment must be Pareto efficient for current reported rankings, hence for true rankings under truthful reporting; improvement means weak improvement almost everywhere and strict improvement on positive mass.
Is deciding whether an admissible instance admits such a finitely described policy in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,H,S,K,L\), where \(S\) is the total number of listed states, \(K\) the number of shock outcomes, and \(L\) the total binary input length.
For finite populations, adjusted random serial dictatorship is stated to guarantee global sd-strategyproofness, local sd-strategyproofness, and ex post efficiency, without a polynomial runtime guarantee ([Hosseini–Larson–Cohen](https://cs.uwaterloo.ca/~klarson/papers/HLC.AAAI2015.pdf)).
For a continuum with fixed strict preferences over complete allocation sequences and full-support preference distribution, incentive-compatible ordinally efficient rules are characterized as spot mechanisms ([Combe–Nora–Tercieux](https://onlinelibrary.wiley.com/doi/full/10.3982/TE5419)); this concerns a different preference domain and dominance criterion. No result settling the specified decision problem was located.
I do not settle whether the general existence problem is in $\mathrm P$ or is $\mathrm{NP}$-hard.
The following results are proved below.
The fourth result verifies a particular policy under a restricted class of opponents. It does not decide whether some policy satisfies the task’s full requirements.
Throughout, report profiles are measurable. A randomized reporting strategy means a behavioral strategy using private random seeds. The two-shift counterexample applies when “every reporting strategy” includes these strategies.
Fix a measurable report profile $r$. Use identity $i\in[0,1]$ as priority, with smaller identities processed first.
At a stage, let $b$ be the processed priority boundary, let $V\subseteq A$ be the nonempty set of available shifts, and let $R_a>0$ be the residual capacity of $a\in V$. Initially,
$$ b=0,\qquad V=A,\qquad R_a=q_a. $$
Write $\operatorname{best}_V(r_i)$ for the reported best shift in $V$. Define
$$ C_a(x)=\int_b^x \mathbf 1\{\operatorname{best}_V(r_j)=a\}\,dj, \qquad x\in[b,1]. $$
If $C_a(1)\geq R_a$, define
$$ T_a=\inf\{x\in[b,1]:C_a(x)\geq R_a\}. $$
Otherwise put $T_a=1$. Let
$$ c=\min_{a\in V}T_a. $$
Assign each nurse in $(b,c]$ her reported best shift in $V$. Include nurse $0$ in the first stage. Subtract $C_a(c)$ from every residual capacity, remove the exhausted shifts, and set $b=c$.
Thus an exhaustion boundary belongs to the preceding stage.
The invariant is
$$ \sum_{a\in V}R_a=1-b. $$
Each $C_a$ is continuous and nondecreasing, and
$$ \sum_{a\in V}C_a(x)=x-b. $$
For every $a\in V$,
$$ C_a(c)\leq R_a. $$
Indeed, if this inequality failed, continuity would give a hitting time strictly before $c$, contradicting its definition.
Positive residual capacities imply $c>b$ whenever $b<1$: every $C_a(b)$ is zero, and continuity gives a neighborhood of $b$ in which no capacity is exhausted.
If $c<1$, at least one shift reaches its capacity at $c$ and is removed. If $c=1$, then
$$ \sum_{a\in V}C_a(1)=1-b=\sum_{a\in V}R_a. $$
Together with the componentwise inequalities, this forces $C_a(1)=R_a$ for every remaining shift.
Consequently, there are at most $m$ stages, and each shift receives exactly its prescribed mass.
The construction uses comparisons, arithmetic, Lebesgue integration, and generalized inverses. Its bounded number of stages can be unrolled into finite formulas.
For a jointly measurable parameterized family of reports, the consumption functions are jointly measurable in the parameters and $x$. Their continuity in $x$ permits hitting-time conditions to be expressed through evaluations at rational positions. Hence the boundaries are measurable. Finite branching then gives jointly measurable assignment maps.
No random seed is needed.
Fix nurse $i$ and arbitrary reports by everyone else. Changing only $i$’s report changes each consumption integrand on at most a singleton. It therefore changes none of the integrals.
Inductively, all stage boundaries, residual capacities, and available menus remain unchanged. This includes the menu faced by $i$ at an exhaustion boundary.
Truthful reporting selects her true best member of that fixed menu. Thus, for every true cutoff $B_{i,\ell}$,
$$ \mathbf 1\{f^{\mathrm{truth}}(i)\in B_{i,\ell}\} \geq \mathbf 1\{f^{\mathrm{deviation}}(i)\in B_{i,\ell}\}. $$
This pointwise inequality also holds after averaging over a randomized report.
When $H=1$, the terminal condition gives $W_{i,\ell}=p_{i,\ell}$. Both required dominance inequalities follow.
Let $e_a$ be the priority boundary at which shift $a$ is exhausted.
Outside the finitely many stage boundaries, suppose a nurse receives $a$ and strictly prefers $d$ under her report. Shift $d$ must have been removed before her stage began. If that stage is $(b,c]$, then
$$ e_d\leq b<c\leq e_a. $$
Every strict reported improvement therefore replaces a shift by one with a strictly smaller exhaustion boundary.
Suppose a feasible assignment $g$ weakly improves nurses almost everywhere and strictly improves a positive-mass set. Strict rankings imply
$$ e_{g(i)}\leq e_{f(i)} $$
almost everywhere, with strict inequality on a positive-mass set. Since only finitely many exhaustion values occur,
$$ \int_0^1e_{g(i)}\,di < \int_0^1e_{f(i)}\,di. $$
Feasibility instead gives
$$ \int_0^1e_{g(i)}\,di = \sum_{a\in A}q_ae_a = \int_0^1e_{f(i)}\,di, $$
a contradiction.
This proves efficiency under precisely the task’s almost-everywhere and positive-mass definition.
The specified recursion is
$$ W_t=p_t\,\mathbb E[W_{t+1}\mid h_t]. $$
Its continuation expectation is unconditional on current cutoff success. Consequently, it generally differs from the probability of cutoff success in every remaining period.
For example, suppose two equally likely branches have current and next-period cutoff-success indicators
$$ (1,0)\quad\text{and}\quad(0,1). $$
The probability of success in both periods is zero. The specified recursion instead gives
$$ W_t=\frac12\left(\frac12\cdot0+\frac12\cdot1\right) =\frac14. $$
The next section realizes exactly this calculation in an admissible instance.
Let
$$ A=\{a,b\},\qquad (q_a,q_b)=\left(\frac14,\frac34\right),\qquad H=2. $$
There is one shock outcome, of probability $1$.
There are two types, each of mass $\frac12$. Realize type $X$ on $[0,\frac12)$ and type $Y$ on $[\frac12,1]$. Their five states have these rankings:
| Type | State | True ranking |
|---|---|---|
| $X$ | $x_0$, initial | $b\succ a$ |
| $X$ | $x_1$ | $a\succ b$ |
| $Y$ | $y_0$, initial | $b\succ a$ |
| $Y$ | $y_b$ | $a\succ b$ |
| $Y$ | $y_a$ | $b\succ a$ |
For type $X$, either shift moves $x_0$ to $x_1$, which is absorbing.
For type $Y$, shift $b$ in state $y_0$ leads to $y_b$, while shift $a$ leads to $y_a$. Both successor states are absorbing.
Thus
$$ m=2,\qquad \tau=2,\qquad H=2,\qquad S=5,\qquad K=1. $$
Repeat the policy from Section 2 in each period, using the same identity priority.
Everyone initially ranks $b$ first. Hence period one assigns $b$ through priority $\frac34$ and $a$ thereafter, apart from the already specified boundary convention.
In period two, every type-$X$ nurse has ranking $a\succ b$. The first quarter exhausts $a$, and everyone after priority $\frac14$ receives $b$.
Fix nurse
$$ i=\frac58. $$
Under truthfulness she receives $b$ in period one and enters $y_b$. Her first-period top-one probability is $1$. In period two she receives $b$, although her true top shift in $y_b$ is $a$. Therefore
$$ W_{i,1}^{\mathrm{truth}}(h_1)=1\cdot0=0. $$
Let this nurse use a fair private coin in period one:
Report truthfully in period two.
The singleton change leaves every aggregate consumption integral unchanged. At priority $\frac58$, both shifts are still available in period one. The two reports therefore obtain $b$ and $a$, respectively.
Her true initial top shift is $b$, so
$$ p_{i,1}^{\mathrm{deviation}}(h_1)=\frac12. $$
In the branch receiving $b$, she enters $y_b$ and fails the period-two top-one cutoff. In the branch receiving $a$, she enters $y_a$ and succeeds: her period-two assignment remains $b$, now her true top shift.
Thus
$$ \mathbb E_{\mathrm{deviation}} [W_{i,1}(h_2)\mid h_1] = \frac12\cdot0+\frac12\cdot1 = \frac12, $$
and
$$ W_{i,1}^{\mathrm{deviation}}(h_1)=\frac14>0. $$
The probability of receiving a top shift in both periods is nevertheless zero.
Every realized assignment remains feasible and Pareto efficient for the current reports. Immediate strategyproofness also remains valid. The failure is specifically in recursive dominance.
This proves failure of the repeated policy, not nonexistence of another qualifying policy.
Proven claim. Suppose $m=2$, use the repeated deterministic priority policy, and hold all other nurses’ strategies fixed at truthful reporting. For arbitrary $H$, transition rules, and common shocks, truthfulness dominates every pure history-dependent reporting strategy in both $p$ and $W$, along histories generated by these strategies.
This restricted statement does not cover arbitrary strategies by the other nurses.
Couple truthful and deviating executions using the same shocks.
A singleton report change leaves the current aggregate integrals unchanged and leaves every other nurse’s assignment unchanged. Since updates use each nurse’s own true state, assignment, and the common shock, every other nurse’s successor state remains unchanged.
Their subsequent truthful reports therefore remain unchanged. Induction shows that the deviating nurse’s menu process depends on the aggregate truthful population and the shocks, but not on her reports or assignments.
The repeated policy also ignores past reports when determining the current assignment.
There are only two cutoffs.
For $\ell=2$, every assignment succeeds. Hence
$$ p_{i,2}=W_{i,2}=1 $$
under every strategy.
Consider $\ell=1$. At a fixed history, a pure strategy selects one report.
If it reports truthfully now, the current assignment agrees with truthfulness, and the induction hypothesis applies to every successor history.
If it reverses the ranking and the menu contains both shifts, it obtains the true worse shift. Consequently,
$$ p_{i,1}^{\mathrm{deviation}}=0, \qquad W_{i,1}^{\mathrm{deviation}}=0. $$
If the menu is a singleton, both reports obtain the same shift. When that shift is not the true top shift, both recursive values are zero. When it is the true top shift, both current probabilities equal $1$. Their own successor states and aggregate successor states coincide under each shock; applying the induction hypothesis and averaging proves the desired inequality.
The terminal value starts the induction. Immediate dominance follows from Section 2.
The counterexample in Section 4 shows that this pure-strategy result cannot be extended merely by mixing pure strategies: the recursion is nonlinear in the reporting strategy.
Here the shock distribution has exactly one outcome. Fix all other nurses at truthful reporting, and allow the specified nurse arbitrary randomized history-dependent reports.
The test below checks dominance at every history obtained by allowing that nurse to deviate while everyone else always reports truthfully.
Realize the support types on consecutive intervals of the prescribed masses.
First compute the entirely truthful trajectory. Fix an identity $i$, and let
$$ V_t(i)\subseteq A $$
be its menu at period $t$ in that trajectory.
The singleton-invariance argument from Section 5 works for arbitrary $m$. Thus these menus remain unchanged under every deviation by $i$.
Every shift in $V_t(i)$ is attainable: the nurse can report it first. No shift outside $V_t(i)$ is attainable.
Fix the nurse’s type and suppress it from the notation. Write the deterministic update as $g(s,a)$ and the true top-$\ell$ set as $B_\ell(s)$.
Past reports can be ignored for this restricted analysis. The future aggregate trajectory is fixed, and the nurse’s future state depends only on her current state and subsequent assignments.
Define $E_{t,\ell}(s)$ to mean:
Some randomized reporting strategy from state $s$ at period $t$ has strictly positive recursive value for cutoff $\ell$.
The terminal condition is
$$ E_{H+1,\ell}(s)=1. $$
Define the currently successful actions by
$$ G_{t,\ell}(s)=V_t(i)\cap B_\ell(s). $$
Then the exact recursion is
$$ E_{t,\ell}(s) = \mathbf 1\{G_{t,\ell}(s)\neq\varnothing\} \land \bigvee_{a\in V_t(i)} E_{t+1,\ell}(g(s,a)). $$
Proof. If $G_{t,\ell}(s)$ is empty, every report has current cutoff probability zero.
If every attainable successor has $E_{t+1,\ell}=0$, every continuation strategy has value zero, so the continuation expectation is zero.
Conversely, suppose $G_{t,\ell}(s)$ is nonempty and some attainable action $a^\ast$ has a positive-value continuation.
If $a^\ast$ is currently successful, choose it deterministically and use that continuation.
If $a^\ast$ is currently unsuccessful, choose any $a^0\in G_{t,\ell}(s)$ and randomize equally between $a^0$ and $a^\ast$. The current success probability is $\frac12$. Conditional on $a^\ast$, use its positive-value continuation; conditional on $a^0$, use any continuation. The unconditional continuation expectation is strictly positive, so their product is strictly positive.
This proves both directions. The witness uses only finitely many fair coins.
Let $T_{t,\ell}(s)$ denote the truthful recursive value in this fixed menu environment. Since the mechanism, shocks, and truthful reports are deterministic,
$$ T_{t,\ell}(s)\in\{0,1\}. $$
Put
$$ a_t(s)=\operatorname{best}_{V_t(i)}(s). $$
Then
$$ T_{H+1,\ell}(s)=1 $$
and
$$ T_{t,\ell}(s) = \mathbf 1\{a_t(s)\in B_\ell(s)\} \,T_{t+1,\ell}(g(s,a_t(s))). $$
Every recursive value under every strategy lies in $[0,1]$, by induction from the terminal value. Therefore truthfulness dominates all deviations at a given state precisely when
$$ T_{t,\ell}(s)=1 \quad\text{or}\quad E_{t,\ell}(s)=0. $$
Indeed, truthful value $1$ dominates every possible value. Truthful value $0$ dominates exactly when no deviation has positive value.
For the specified identity and its initial state $s^0$, compute
$$ R_1=\{s^0\}, $$
$$ R_{t+1} = \{g(s,a):s\in R_t,\ a\in V_t(i)\}. $$
These are exactly the states reachable through the nurse’s reports. Each listed action can be selected by ranking it first, and every realized assignment belongs to the current menu.
The test checks the preceding dominance condition for every
$$ t,\qquad s\in R_t,\qquad \ell\in\{1,\ldots,m\}. $$
Thus it covers all histories in the stated restricted class, including histories following earlier deviations.
Initially the truthful state profile is constant on $\tau$ intervals.
Each period’s priority construction has at most $m-1$ internal exhaustion boundaries. Refining the existing partition at these boundaries makes the successor state profile constant on each resulting open interval. Therefore, after $t$ periods, there are at most
$$ \tau+(m-1)t $$
such intervals.
Take the union of the initial type boundaries and every exhaustion boundary over the horizon. Its complementary intervals, together with the boundary points themselves, give
$$ O(\tau+mH) $$
identity classes.
Within each open interval, initial type and the entire menu sequence agree. Boundary points are handled separately using the preceding-stage convention. Hence one finite-state calculation per class suffices.
For $H=1$, existence always has answer “yes” on the promised admissible domain. Reading the input takes $O(L)$ bit operations.
The static policy has a finite description using $O(m^2)$ integral and generalized-inverse expressions. This is a symbolic description, not a polynomial-time numerical integration claim for arbitrary measurable reports.
For the canonical interval realization, truthful one-period evaluation takes $O(m^2\tau)$ rational operations. A conservative bit bound is
$$ O\!\left(L^3+m^2\tau L^2\right). $$
For the restricted verification problem of Section 6, computing the truthful trajectory takes
$$ O\!\left(Hm^2(\tau+mH)\right) $$
rational operations.
All its boundaries have a common denominator obtained from the input masses and capacities. Scanning an interval consumes a selected shift at rate $1$, so computing an exhaustion point introduces no new denominator. These rational quantities therefore have $O(L)$-bit representations.
The Boolean calculations over identity classes, states, actions, periods, and cutoffs take at most
$$ O\!\left(Hm^2S(\tau+mH)\right) $$
elementary operations. Including rational arithmetic and bookkeeping, a conservative total bit bound is
$$ O\!\left( L^3+ Hm^2(S+1)(\tau+mH)L^2 \right). $$
This bound assumes $K=1$. It is polynomial in the displayed parameters; if $H$ is binary encoded, it need not be polynomial in $L$ alone.
The general existence problem remains open here. In particular, the verification test neither handles arbitrary history-dependent strategies of the other nurses nor searches over alternative policies. No hardness reduction or general existence theorem has been proved.
⟨structured verdict parsed — rendered above⟩
The output establishes meaningful partial results, but it does not resolve the requested complexity classification. I found no false central step in its auxiliary arguments. Two minor clarifications concern measurable reporting strategies and the types assigned to boundary identities.
The assigned task asks for either a polynomial-time decision procedure for policy existence or an $\mathrm{NP}$-hardness result. Neither is supplied.
The prover correctly distinguishes its restricted verification algorithm from an existence algorithm. Likewise, failure of the repeated priority policy does not establish that the counterexample instance admits no qualifying policy.
Minimum additional work required: supply a classification argument covering the full existence question, including arbitrary opponent strategies and the permitted shock distributions. The current results cannot support that conclusion by themselves.
The consumption functions are continuous and nondecreasing because their integrands are bounded and measurable. Each processed identity selects exactly one available shift, giving
$$
\sum_{a\in V}C_a(x)=x-b.
$$
The argument that $C_a(c)\leq R_a$ is valid: exceeding a residual capacity at $c$ would force an earlier hitting time. Positive residual capacities and finitely many available shifts imply $c>b$ while $b<1$.
Updating residual capacities preserves
$$
\sum_{a\in V}R_a=1-b.
$$
Every nonterminal stage removes at least one shift. At $c=1$, the componentwise consumption inequalities and equality of their sums force every remaining residual capacity to be consumed exactly. Thus the construction terminates within $m$ stages and assigns each shift its required mass.
The conventions for identity $0$ and exhaustion boundaries give pointwise assignments without changing any capacity calculation.
The construction uses permitted operations and has a bounded number of stages. For a jointly measurable parameterized report family, parameter-dependent integration gives jointly measurable consumption functions. Continuity in the priority coordinate permits measurable hitting-time definitions through rational test positions. Finite branching then preserves measurability.
However, the prover explicitly assumes that report profiles are measurable, whereas the task does not explicitly delimit admissible reporting strategies this way. Its joint-measurability argument also assumes a jointly measurable parameterized family of reports.
This is a natural interpretation of the continuum model and therefore a minor clarification under the task’s stated verification standard.
Minimum clarification: state that admissible reporting strategies generate measurable profiles and the jointly measurable families needed for the policy’s measurability requirement.
Changing one identity’s report changes each consumption integrand only on a singleton. Consequently, every integral, exhaustion boundary, residual capacity, and available menu remains unchanged.
The boundary convention matters here and is explicitly handled: the deviating identity remains assigned through the same stage. Truthfulness selects its true best available shift, which weakly dominates every other available choice for every true rank cutoff.
Averaging this pointwise comparison covers randomized reports. With $H=1$, the terminal condition makes $W_{i,\ell}=p_{i,\ell}$, so both required dominance comparisons follow.
This establishes the claimed one-period existence result under the measurable-report interpretation.
Away from finitely many boundaries, an identity assigned $a$ could prefer $d$ only if $d$ had already been removed. For its stage $(b,c]$, this gives
$$
e_d\leq b<c\leq e_a.
$$
Thus every strict improvement strictly decreases the exhaustion-boundary value attached to that identity’s assignment. A weak improvement almost everywhere with strict improvement on positive mass would strictly decrease the integral of this value.
Feasibility fixes that integral at
$$
\sum_{a\in A}q_ae_a
$$
for both assignments, giving the claimed contradiction. Ignoring finitely many boundary identities is legitimate for the task’s almost-everywhere and positive-mass efficiency definition.
The prover correctly observes that the continuation expectation in the specified recursion is not conditioned on current cutoff success.
In the concrete instance, period one exhausts $b$ at priority $\frac34$. Therefore identity $\frac58$ has both shifts available and truthfully receives $b$. In period two, the initial quarter of type-$X$ identities exhausts $a$, so identity $\frac58$ receives $b$ regardless of its singleton deviation.
Under truthfulness, that identity enters $y_b$, where $a$ is its top shift, and its recursive top-one value is zero.
Under the fair-coin deviation, its current top-one probability is $\frac12$. Receiving $b$ leads to continuation value zero; receiving $a$ leads to state $y_a$, where its subsequent assignment $b$ is top-ranked. Hence
$$
W_{i,1}^{\mathrm{deviation}}
=
\frac12\left(\frac12\cdot0+\frac12\cdot1\right)
=
\frac14.
$$
The deviation strictly improves $W$ while reducing $p$. This refutes recursive dominance for the repeated policy. It does not refute policy existence, and the prover does not claim otherwise.
With truthful opponents, singleton deviations leave all other assignments and successor states unchanged under a coupling using the same shocks. Their future truthful reports therefore remain unchanged. This justifies menu invariance across the coupled executions.
For the top-one cutoff, a pure reversal with both shifts available gives current success probability zero and therefore recursive value zero. With a singleton menu, both reports obtain the same assignment and have the same successor states under each shock. If the current assignment succeeds, backward induction applies to the continuations; otherwise both recursive values vanish.
The top-two cutoff always succeeds. These cases exhaust the possibilities.
There is no inconsistency with the randomized counterexample: the recursion is nonlinear in the reporting strategy. The restriction to truthful opponents is essential to the written argument and is acknowledged.
For $K=1$ and truthful opponents, singleton invariance makes the aggregate trajectory and the identity’s menu sequence independent of its deviations. Every menu action is attainable by reporting it first.
The positivity recursion correctly requires both:
These actions need not coincide. The fair-coin construction establishes sufficiency when they differ. Necessity follows because either a zero current success probability or a zero continuation expectation forces the product to vanish.
Truthful recursive values are binary in this deterministic environment. Since every strategy’s value lies in $[0,1]$, the dominance condition
$$
T_{t,\ell}(s)=1
\quad\text{or}\quad
E_{t,\ell}(s)=0
$$
is exact.
The reachable-state recursion also correctly enumerates states obtainable through previous reports. Ignoring past reports is justified here because the repeated policy ignores them and truthful opponents’ states are unaffected by singleton deviations.
Each period introduces at most $m-1$ internal exhaustion boundaries. Refining the existing intervals at these points keeps the truthful successor state constant on each resulting open interval. Consequently, the stated bounds
$$
\tau+(m-1)t
\quad\text{and}\quad
O(\tau+mH)
$$
are valid.
Treating boundary identities separately correctly preserves pointwise verification. However, “consecutive intervals” does not specify which type owns each original type boundary. The preceding-stage convention specifies allocation-stage membership, not initial type membership.
Minimum clarification: give an endpoint convention for the canonical type realization and use it when initializing the calculations for boundary identities. This is a minor omission.
For $H=1$, the promised-domain existence answer is always affirmative, so the stated input-reading bound is appropriate. The prover correctly distinguishes a finite symbolic policy description from numerical integration of arbitrary measurable reports.
On the canonical interval realization, the bounds for truthful evaluation and trajectory computation allow scanning the current interval partition across stages and shifts.
The common-denominator claim is valid: initial endpoints, capacities, residual capacities, and new exhaustion points are obtained through additions and subtractions. Scanning an interval consumes capacity at rate one, so no additional division creates a new denominator. Their rational representations therefore have $O(L)$ bits.
The Boolean recursions fit within the stated conservative bound
$$
O\!\left(
L^3+
Hm^2(S+1)(\tau+mH)L^2
\right).
$$
The restrictions $K=1$ and polynomial dependence on the numerical value of $H$ are explicitly stated. The prover correctly warns that this need not be polynomial in $L$ when $H$ is binary encoded.
The appropriate adjudication is partial: the auxiliary results are sound in substance, but the assigned existence classification remains unresolved. The missing classification is a scope failure, not a demonstrated error in the established constructions.
⟨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.