Hard-cap optimal-welfare certificate for the regional job-training design
Status: conventional derivation and executable certificate independently reviewed; exploration stage unchanged.
Generator: model/src/price_decomposition/cap_run.py. No Monte Carlo sampling.

Target and units
----------------
The target is the supremum, over one online rule that does not know the future
region sequence, of its minimum expected employment increment over all fixed
sequences with 2k A and 2k B applicants. Capacity is k on every realization.
Current region and score are observed before deciding. Because the eligibility
class includes all applicants, eligibility places no further restriction on
this unrestricted hard-cap optimum. Effects are the known conditional mean
increments; current outcomes are not observed. Applicants are independent.

All twenty scores in a region have probability 1/20. Effects, in units of 1/800,
are 47+14j in A and -222+36j in B, j=0,...,19. Thus the certificate uses exactly
the manuscript's regional distributions and does not discretize them further.

Lower certificate
-----------------
Let L[a,b,l] be a proposed lower continuation value when a A applicants and b B
applicants remain and l places remain. Put L[0,0,l]=L[a,b,0]=0. For a vector f,
define T_s f(l) = (1/20) sum_j max{f(l), r_sj+f(l-1)} for l>=1.
Compute L[a,b,l] as the minimum, over available next regions s, of T_s applied
to the corresponding next-count vector. This is the Bellman recursion for a
STRONGER adversary that observes realized capacity/history before selecting
the next region, but selects the region before seeing the next score.

For the actual certificate each expectation is rounded DOWN on a fixed grid.
The resulting L satisfies L[a,b,l] <= T_s L[next counts](l) for every possible
next region. Upon observing s and the score, the planner chooses whichever of
accept/reject attains the displayed maximum using L at the next counts. By
induction on a+b this rule has expected continuation welfare at least L[a,b,l]
against every such adversary, and hence against every fixed region sequence.
Therefore L[2k,2k,k] <= V_C for the original problem. The method does NOT assume
that an adaptive sequence adversary is equivalent to the original adversary.

Upper certificate
-----------------
Fix the particular sequence with all A before all B. Even a planner told this
whole sequence in advance has a standard online Bellman optimum obtained by
applying T_B 2k times and then T_A 2k times to the zero vector. Round each
expectation UP to obtain U. Every original rule has worst-sequence welfare
at most its welfare on this specific sequence, which is at most this known-
sequence optimum. Hence V_C <= U[k]. No claim that this block order is worst
among all orders is required.

Exact integer arithmetic and range
----------------------------------
The stored grid unit is 1/(800*10^12). Reward integers are multiples of Q=10^12.
For d=f[l]-f[l-1], the Bellman improvement is the mean positive part of r-d.
For an arithmetic reward grid of step t and top reward R, the number of
strictly positive terms is m=clip(ceil((R-d)/t),0,20), and their integer sum is
m(R-d)-t*m(m-1)/2. Integer division by 20, with or without adding 19, gives the
exact upward or downward rounding. All assertions are evaluated with int64.

The continuation vectors are nondecreasing in l and have increments at most
462Q: this property is preserved by T_s, by floor/ceil on the same integer
grid, and by the coordinatewise minimum. Values are at most 462*k*Q. For the
allowed k<=1000, this is 4.62e17, while intermediate tail sums are at most
20*462Q, far below the int64 maximum 9.22e18. Thus integer overflow cannot occur
on the stated domain. The code asserts the increment bounds at every update.
Floating decimal values are display only; rational numerator/denominator
strings in the output are the actual interval certificate.

Independent calculation
-----------------------
model/tests/price_decomposition/cap_exact.py uses Python Fraction and explicitly sums all
20 reward realizations, rather than using the arithmetic-tail shortcut. For
k=5, the unrounded lower and upper values agree exactly, certifying the exact
original optimum 1256374970631536438975171/655360000000000000000000.
For k=20,100,500 the directional intervals should be reported as intervals,
or rounded only to a precision shared by both endpoints. Their nonzero widths
are the gap between two comparison problems, not Monte Carlo uncertainty.

Reproduce
---------
python3 model/src/price_decomposition/cap_run.py
The C++ binary is built in a temporary directory. Results and input hashes are
saved in model/generated/price_decomposition/cap_bounds.json. Existing figures, tables,
simulation results, and manuscript sources are untouched.
