Answer: Such a decentralized Thompson-sampling policy exists under the stated exact public-matrix model. It satisfies the stronger regret upper bound $R_p(T)\le O(m^2+L+\log(\tau+1)+\log(1/\Delta))$ with the required polynomial per-employer, per-round computation.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet ρ = λN−1(1 −λ). Following Algorithm 1, the stable regret of each player pi satisfies Ri(T) ≤ 2N 5K2 log T ρN 4 4 + 6 log T ρ(∆−2ε)2 + C ρε6 + 6 + 6N 4 ρN 4 · ∆i,max (3) =O N 5K2 log2 T ρN 4∆2 · ∆i,max , (4) for any ε such that ∆−2ε > 0, where C is a universal constant. Due to the space limit, we provide the proof sketch as well as the full proof in the Appendix.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite employer and worker type sets \(P,A\), rational employer masses \((\alpha_p)_{p\in P}\) summing to \(1\), per-capita worker supplies \((\beta_a)_{a\in A}\) with total supply at least \(1\), known worker-type priorities over employer types, and fixed but policy-unknown Bernoulli reward means \((\mu_{p,a})\) with positive minimum gap \(\Delta\), consider atomless employers who learn from their own feedback and face priority-based acceptance at each round. Is there a decentralized Thompson-sampling policy, with per-employer computation polynomial in \(|P|,|A|,L,1/\Delta\), whose expected regret for every employer type \(p\)—measured against its minimum per-capita payoff over stable mass assignments, multiplied by \(T\)—is \(O(\operatorname{poly}(|P|,|A|,L,1/\Delta)\log^2 T)\), uniformly in the absolute population size?
A society is given by its support: the list of its \(\tau\) positive-mass types, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here the two sides have finite supports \(P,A\), \(\tau=|P|+|A|\), \(m=|A|\ge2\), and public input bit length \(L\).
Employer masses satisfy \(\alpha_p>0\) and \(\sum_p\alpha_p=1\); worker supplies satisfy \(\beta_a>0\) and \(\sum_a\beta_a\ge1\). Each worker type has a public strict priority order \(\succ_a\) over employer types. Everyone finds every opposite-side type acceptable, and employers are indifferent between workers of the same type.
The fixed means \(\mu_{p,a}\in[0,1]\) induce strict employer preferences, with \(\Delta=\min_{p,a\ne b}|\mu_{p,a}-\mu_{p,b}|>0\). Neither the means nor \(\Delta\) are supplied to the policy.
Each round, every employer requests one worker type. Each worker type accepts requesting mass up to its supply, in descending employer-type priority; a partially accepted employer type is rationed uniformly across its requesting members. Private randomization is interpreted through exact population laws, including the distribution of individual histories.
An accepted employer receives an independent Bernoulli reward with its pair's mean and observes that reward; rejection gives zero payoff and no reward observation. The accepted mass matrix is public after each round. Employers retain individual histories; rewards and posterior statistics cannot be pooled or communicated.
A decentralized Thompson-sampling policy uses only public input, past accepted mass matrices, its own history, and private randomness. Each employer maintains independent \(\operatorname{Beta}(1+s_a,1+f_a)\) posteriors from its own accepted successes and failures, and selects the largest fresh posterior sample in a nonempty history-dependent eligible set; randomized retention of its previous request is allowed.
A stable mass assignment is \(x\ge0\) with \(\sum_a x_{p,a}=\alpha_p\) and \(\sum_p x_{p,a}\le\beta_a\), having no \(p,a,b\) with \(x_{p,b}>0\), \(\mu_{p,a}>\mu_{p,b}\), and either \(\sum_qx_{q,a}<\beta_a\) or \(x_{q,a}>0\) for some \(p\succ_a q\).
Let \(v_p^-\) be the minimum of \(\alpha_p^{-1}\sum_a\mu_{p,a}x_{p,a}\) over stable mass assignments. Define \(R_p(T)=Tv_p^- -\mathbb E[\sum_{t=1}^T Y_p(t)]\), where \(Y_p(t)\) is the payoff of a representative employer sampled from type \(p\).
Count arithmetic on reward counters and posterior sampling as unit-cost operations; all structural rational data retain their binary encoding.
Does a decentralized Thompson-sampling policy exist with per-employer, per-round computation polynomial in \(m,\tau,L,1/\Delta\) and \(R_p(T)=O(\operatorname{poly}(m,\tau,L,1/\Delta)\log^2 T)\) for every \(p\) and \(T\ge2\), with constants independent of absolute population scale, or is this guarantee impossible?
For finite one-to-one markets, conflict-avoiding Thompson sampling achieves player-pessimal stable regret of order \(\log^2 T\), with exponential dependence on the number of employers ([Kong–Yin–Li](https://arxiv.org/pdf/2204.12048)).
No result settling this specified atomless, individual-feedback policy question was located in the literature search.
I interpret the regret requirement as the conventional upper bound on $R_p(T)$.
The exact public mass matrices make it possible to learn every employer type’s strict preference order using small cohorts that run ordinary two-arm Thompson sampling. No employer shares rewards or posterior parameters. After learning the orders, employers independently implement a stable mass assignment.
The resulting policy satisfies the stronger bound
$$
R_p(T)\le C\left(m^2+L+\log(\tau+1)+\log(1/\Delta)\right)
$$
for an absolute constant $C$, every employer type $p$, and every $T\ge2$. Its per-employer, per-round computation is polynomial in the parameters requested in the question.
The construction uses the stated permission to compute from public accepted mass matrices. Their exactness is essential.
Consider an employer whose posteriors for worker types $a$ and $b$ are both initially $\operatorname{Beta}(1,1)$. Suppose it uses eligible set $\{a,b\}$ for two rounds, and its first-round request is accepted.
In the first round it chooses each type with probability $1/2$.
If it first chooses $a$, its second-round probability of choosing $a$ is $2/3$ after a success and $1/3$ after a failure. Indeed, for an independent uniform sample $U$ and any random variable $Z$ supported on $[0,1]$,
$$
\Pr(Z>U)=\mathbb E[Z].
$$
The relevant posterior means are those of $\operatorname{Beta}(2,1)$ and $\operatorname{Beta}(1,2)$.
If it first chooses $b$, its second-round probability of choosing $a$ is $1/3$ after a success and $2/3$ after a failure. Therefore its unconditional second-round probability of requesting $a$ is
$$
\begin{aligned}
Q_{p,a}
&=\frac12\left(\frac23\mu_{p,a}+\frac13(1-\mu_{p,a})\right)\\
&\quad+\frac12\left(\frac13\mu_{p,b}+\frac23(1-\mu_{p,b})\right)\\
&=\frac12+\frac{\mu_{p,a}-\mu_{p,b}}6.
\end{aligned}
$$
This identity includes boundary means. It requires acceptance in the first round; second-round acceptance does not affect the request probability.
Under the exact-population interpretation, a cohort of type-$p$ employers with mass $h_p$ consequently requests mass
$$
h_p\left(\frac12+\frac{\mu_{p,a}-\mu_{p,b}}6\right)
$$
at type $a$ in the second round.
Fix a public numbering of the worker types. Let
$$
N=\binom m2,\qquad
\beta_{\min}=\min_a\beta_a,\qquad
\eta=\frac12\min\{1,\beta_{\min}\},\qquad
q=\frac{\eta}{N}.
$$
All these quantities are positive encoded rationals.
For every unordered pair $E\subseteq A$ of size two, choose publicly a filler type
$$
f(E)\in A\setminus E.
$$
At initialization, every employer independently chooses a permanent private label:
Thus each pair cohort within employer type $p$ has mass
$$
h_p=\alpha_pq.
$$
The total mass of all pair cohorts, across all employer types, is $\eta$.
Process the $N$ pairs in a fixed public order, using two rounds per pair. During the two rounds for $E=\{a,b\}$:
Outside its own two-round probe, a pair cohort always requests its filler type.
Before cohort $E=\{a,b\}$ starts its probe, its members have requested only $f(E)$, which is outside $E$. Their posteriors for $a$ and $b$ are therefore still independent $\operatorname{Beta}(1,1)$ distributions.
During this probe, no main-label employer requests $a$ or $b$. Consequently, the total requesting mass at either tested type is at most $\eta$. Since
$$
\eta\le\frac{\beta_{\min}}2<\beta_a,\beta_b,
$$
every request at either tested type is accepted in both rounds. This conclusion is independent of worker priorities.
Choose $a$ as the publicly designated first member of $E$. The type-$p$ background mass requesting $a$ is the known rational
$$
B_{p,E,a}
=\alpha_pq\,\bigl|\{E'\ne E:f(E')=a\}\bigr|.
$$
Let $X^E_{p,a}$ be the public accepted mass at $(p,a)$ in the second round of this probe. The identity from Section 1 and full acceptance give
$$
X^E_{p,a}
=B_{p,E,a}+\frac{h_p}{2}
+\frac{h_p}{6}(\mu_{p,a}-\mu_{p,b}).
$$
Hence comparison with the known rational threshold
$$
B_{p,E,a}+\frac{h_p}{2}
$$
reveals whether $\mu_{p,a}>\mu_{p,b}$.
Every employer type is probed simultaneously. After $2N$ rounds, the public matrices contain a signal for every employer-type preference comparison.
Write the worker types as $1,2$, and define
$$
B=\beta_1+\beta_2,\qquad
\gamma=\frac{\beta_1}{B},\qquad
q=\min\{\gamma,1-\gamma\}.
$$
Here $B\ge1$ and $q>0$.
Every employer independently chooses one of three private cohorts, with probabilities
$$
\gamma-\frac q2,\qquad
1-\gamma-\frac q2,\qquad
q.
$$
The first cohort requests type $1$ in both probe rounds; the second requests type $2$; the third uses eligible set $\{1,2\}$ in both rounds.
In the first round, the total request masses are
$$
r_1=\gamma,\qquad r_2=1-\gamma.
$$
Because $B\ge1$,
$$
\gamma\le\beta_1,\qquad 1-\gamma\le\beta_2.
$$
Thus every first-round request is accepted.
Put $h_p=\alpha_pq$. Section 1 gives the type-$p$ second-round request mass
$$
r_{p,1}
=\alpha_p\gamma+\frac{h_p}{6}(\mu_{p,1}-\mu_{p,2}).
$$
Second-round rationing may occur. The following observation handles it.
Let $x_{p,a}$ be any round’s accepted matrix, let $r_{p,a}$ be its request matrix, and define
$$
c_a=\sum_p x_{p,a},\qquad s_a=\beta_a-c_a.
$$
If $s_a>0$, every request at type $a$ was accepted, so
$$
x_{p,a}=r_{p,a}\quad\text{for every }p.
$$
Thus:
If both slacks vanish, total accepted mass is $B$. Total requesting mass is $1$, so $B\le1$. Since $B\ge1$, all requests were accepted and $r_{p,1}=x_{p,1}$.
Therefore the accepted matrix determines every type’s request masses. Applied to the second probe round, it determines the sign of
$$
r_{p,1}-\alpha_p\gamma
=\frac{h_p}{6}(\mu_{p,1}-\mu_{p,2}).
$$
The next section gives a reconstruction procedure that avoids exact zero tests and arbitrarily delicate slack comparisons.
Let $n=|P|$. Public matrix entries are exact observations, but the policy only needs finitely many binary digits of them. At precision level $k$, use dyadic approximations with error at most
$$
\varepsilon=2^{-k}.
$$
All computations thereafter are on encoded rationals.
For $m\ge3$, approximating $X^E_{p,a}$ to this accuracy approximates its comparison signal with error at most $\varepsilon$.
For $m=2$, the following bound suffices.
Suppose
$$
|z_{p,a}-x_{p,a}|\le\varepsilon
$$
for every $p,a$. Compute
$$
\widetilde s_a=\beta_a-\sum_pz_{p,a},
$$
and choose $j\in\{1,2\}$ maximizing $\widetilde s_j$, with a fixed tie rule. Define
$$
\widetilde r_{p,1}=
\begin{cases}
z_{p,1},&j=1,\\
\alpha_p-z_{p,2},&j=2.
\end{cases}
$$
Then
$$
|\widetilde r_{p,1}-r_{p,1}|
\le(2n+1)\varepsilon.
$$
Proof. Each approximate slack has error at most $n\varepsilon$.
If $s_j>0$, all requests at the selected worker type were accepted. The selected reconstruction formula is then correct up to $\varepsilon$.
Suppose $s_j=0$. If the other slack also vanishes, Section 3 shows that all requests were accepted, giving the same bound.
Otherwise, writing the other worker type as $i$, the choice of $j$ implies
$$
s_i\le2n\varepsilon.
$$
The total rejected mass is
$$
d=1-c_1-c_2=1-B+s_i\le s_i\le2n\varepsilon.
$$
For each employer type, its rejected mass is at most $d$. Either candidate $x_{p,1}$ or $\alpha_p-x_{p,2}$ differs from $r_{p,1}$ by at most that rejected mass. Adding the approximation error gives the stated bound. $\square$
Use the common error bound
$$
E_k=(2n+1)2^{-k}.
$$
A comparison is certified positive when its approximate signal exceeds $E_k$, and certified negative when it is less than $-E_k$. These certifications cannot be wrong.
After the $2N$ probe rounds, employers increase $k$ by one each round until every comparison is certified. While waiting, they use a fixed singleton eligible set. This stopping rule does not use $\Delta$.
In both constructions, every true comparison signal has magnitude at least
$$
\frac{\alpha_{\min}q\Delta}{6},
\qquad
\alpha_{\min}=\min_p\alpha_p.
$$
Consequently all comparisons are certified by precision
$$
K=\left\lceil
\log_2\frac{24(2n+1)}{\alpha_{\min}q\Delta}
\right\rceil.
$$
This is an analysis bound; the policy does not compute it.
A positive rational whose encoding is part of an input of length $L$ is at least $2^{-L}$, and its value is at most $2^L$. Hence
$$
\alpha_{\min}\ge2^{-L},\qquad \beta_{\min}\ge2^{-L}.
$$
For $m\ge3$,
$$
q\ge\frac{2^{-(L+1)}}N.
$$
For $m=2$,
$$
q=\frac{\min\{\beta_1,\beta_2\}}{\beta_1+\beta_2}
\ge2^{-(2L+1)}.
$$
Thus, uniformly over both cases,
$$
\alpha_{\min}q\ge\frac{2^{-(3L+1)}}N.
$$
It follows that
$$
K=O\!\left(L+\log(m+1)+\log(n+1)+\log(1/\Delta)\right).
$$
All structural probabilities and thresholds have polynomial encoding length. At each precision level, the policy reads polynomially many public entries to $k$ bits and performs rational computations of polynomial bit complexity. In particular, it requires neither an inverse-supply number of rounds nor exact comparisons between nearly equal public slacks.
Once the comparisons are certified, every employer can recover every employer type’s true strict worker ordering.
We use the following known algorithmic theorem: a bipartite stable-allocation instance with rational vertex quotas, rational edge capacities, and strict incident-edge preferences admits a stable allocation computable in polynomial time in graph size and binary input length. Baïou–Balinski established a strongly polynomial algorithm; Dean–Munshi provide a faster algorithm. [Baïou–Balinski](https://pubsonline.informs.org/doi/10.1287/moor.27.3.485.310), [Dean–Munshi](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf)
Here standard stable-allocation stability excludes an unsaturated edge whose two endpoints could increase allocation on that edge by using unused quota or reducing allocation on a less preferred incident edge.
Apply the theorem to the complete bipartite graph on $P,A$, with quotas $\alpha_p,\beta_a$, edge capacities
$$
u_{p,a}=\min\{\alpha_p,\beta_a\},
$$
and the learned employer orders and public worker priorities. Every hypothesis is satisfied, and the resulting instance has polynomial encoding length.
Let $x$ be the resulting allocation.
First, every employer quota is filled. Otherwise total employer allocation would be less than $1$. Since total worker quota is at least $1$, some worker quota would also be unfilled. The edge between an unfilled employer $p$ and unfilled worker $a$ satisfies
$$
x_{p,a}<\alpha_p,\qquad x_{p,a}<\beta_a,
$$
so it is unsaturated and blocks through unused quota at both endpoints. This contradicts stability.
Second, $x$ is stable in the task’s precise sense. A blocking triple $p,a,b$ would give
$$
x_{p,b}>0,\qquad \mu_{p,a}>\mu_{p,b}.
$$
In particular $x_{p,a}<\alpha_p$. The worker-side condition—unused supply or positive allocation to a lower-priority employer—also implies $x_{p,a}<\beta_a$. Hence edge $(p,a)$ is unsaturated, and both endpoints could improve as required by standard stable-allocation blocking. Again this contradicts stability.
Each employer runs the same deterministic implementation of the algorithm, so they obtain the same rational matrix $x$.
The preceding argument establishes existence of a stable mass assignment.
Within the feasible set, stability is equivalent to requiring, for every triple with $\mu_{p,a}>\mu_{p,b}$,
$$
x_{p,b}=0
\quad\text{or}\quad
\left(
\sum_qx_{q,a}=\beta_a
\ \text{and}\
x_{q,a}=0\text{ for every }q\text{ with }p\succ_a q
\right).
$$
These are finite combinations of closed conditions. Stable assignments therefore form a closed, bounded, nonempty set.
Since $\alpha_p>0$, the benchmark objective is continuous and takes values in $[0,1]$. Its minimum is attained, so every $v_p^-$ is well defined.
After computing $x$, each type-$p$ employer independently chooses a permanent worker type $a$ with probability
$$
\frac{x_{p,a}}{\alpha_p}.
$$
It subsequently uses singleton eligible set $\{a\}$.
Under exact population laws, the requesting mass matrix is then exactly $x$ in every round. Its feasibility guarantees that every request is accepted.
Throughout the entire policy:
During informative probes, the eligible sets are fixed by the public schedule and private cohort label. The request’s dependence on private rewards is precisely ordinary Thompson sampling. No reward records or posterior parameters are sent or collected, and no public inference is used to update another employer’s posterior.
Thus the construction satisfies the stated feedback and policy restrictions.
There are $2N$ probe rounds, at most $K$ decoding rounds, and at most one additional round for computing and initializing the stable assignment. Write
$$
H=2N+K+1.
$$
Before permanent assignment, payoffs are nonnegative and $v_p^-\le1$. Thus these rounds contribute at most $H$ to the regret upper bound.
After permanent assignment, the representative type-$p$ employer’s expected per-round payoff is
$$
v_p(x)=\frac1{\alpha_p}\sum_a\mu_{p,a}x_{p,a}.
$$
Because $x$ is stable,
$$
v_p(x)\ge v_p^-.
$$
Every subsequent round therefore contributes a nonpositive amount to regret. For every horizon,
$$
R_p(T)\le\min\{T,H\}.
$$
Using the bound on $K$,
$$
R_p(T)
=O\!\left(m^2+L+\log(\tau+1)+\log(1/\Delta)\right)
$$
as an upper bound. Since $T\ge2$, this implies the requested
$$
R_p(T)=O\!\left(\operatorname{poly}(m,\tau,L,1/\Delta)\log^2T\right).
$$
The largest precision used is $K$, all structural calculations have polynomial bit complexity, and the stable-allocation computation is polynomial. Posterior sampling and reward-counter operations have the stipulated unit costs. Permanent-assignment rounds require only a singleton posterior sample and a local update.
All bounds depend on support parameters and encoded masses, with constants independent of absolute population scale.
⟨structured verdict parsed — rendered above⟩
The construction is sound under the natural interpretation that exact public matrix observations permit access to finite-precision approximations in polynomial time. The probe identities, acceptance arguments, reconstruction bound, stability argument, and regret calculation all check out.
There is one minor computational-model clarification: exactness of an observed real number does not itself specify the cost of reading its binary digits. The write-up should explicitly identify the observation-access convention it uses. No new mathematical argument appears necessary under the intended finite-digit interpretation.
The calculation is correct.
After choosing $a$ initially, its second-round selection probability is $2/3$ following a success and $1/3$ following a failure. After choosing $b$ initially, those probabilities are reversed. Averaging gives exactly
$$
Q_{p,a}=\frac12+\frac{\mu_{p,a}-\mu_{p,b}}6.
$$
The required hypotheses are correctly identified: both tested posteriors initially have distribution $\operatorname{Beta}(1,1)$, samples are independent, and every first-round probe request is accepted.
Boundary means cause no difficulty. Posterior samples have continuous distributions, so sample ties have probability zero. The conversion from an individual selection probability to exact cohort request mass is authorized by the task’s exact-population interpretation.
The cohort probabilities are valid:
$$
Nq=\eta,\qquad 0<\eta\le\frac12.
$$
Each pair cohort requests only its filler before its own probe. Because the filler lies outside the tested pair, both tested posteriors remain fresh.
During a probe, main-label employers request outside the tested pair. All requests at either tested type therefore come from pair cohorts, whose total mass is $\eta$. Since
$$
\eta\le\frac{\beta_{\min}}2<\beta_a,\beta_b,
$$
every tested request is accepted, regardless of worker priorities.
The background mass formula correctly counts all other pair cohorts whose singleton filler is $a$. Consequently,
$$
X^E_{p,a}-B_{p,E,a}-\frac{h_p}{2}
=\frac{h_p}{6}(\mu_{p,a}-\mu_{p,b}).
$$
Every factor multiplying the mean difference is positive. Thus the public signal correctly determines the comparison, simultaneously for all employer types.
All three cohort probabilities are nonnegative and sum to one. The initial request masses are correctly calculated as $\gamma$ and $1-\gamma$. The inequalities ensuring first-round acceptance follow from $B\ge1$.
The second-round request formula is also correct:
$$
r_{p,1}
=\alpha_p\gamma+\frac{\alpha_pq}{6}(\mu_{p,1}-\mu_{p,2}).
$$
The exact reconstruction argument covers every case:
This reasoning also covers supplies totaling exactly one and the case of a single employer type.
The reconstruction lemma is correct. Each approximate slack has error at most $n\varepsilon$. If the selected worker type has zero true slack while the other has positive slack, maximality of its approximate slack gives
$$
s_i\le2n\varepsilon.
$$
The total rejected mass satisfies
$$
d=1-B+s_i\le s_i.
$$
Each employer type’s rejected mass is bounded by $d$. The resulting error bound
$$
|\widetilde r_{p,1}-r_{p,1}|
\le(2n+1)\varepsilon
$$
is therefore justified.
Certification using $E_k$ cannot produce an incorrect sign. The stated precision bound gives
$$
E_K\le\frac{\alpha_{\min}q\Delta}{24},
$$
whereas every true signal has magnitude at least $\alpha_{\min}q\Delta/6$. Hence every comparison is certified by that precision.
The stopping rule does not require knowing $\Delta$.
Minor issue: observation-access convention. The statement that the policy “reads polynomially many public entries to $k$ bits” assumes a computational interface for exact real observations. The task specifies exact public matrices, but does not explicitly define this interface or its cost.
Minimum clarification: State that a public matrix entry admits a deterministic dyadic approximation with error at most $2^{-k}$ at cost polynomial in $k$ and the relevant input dimensions. This is a natural interpretation of the stipulated exact observations; arbitrary alternative representations would require a separate access-cost analysis.
The rational size bounds are valid for the ordinary binary encoding assumed in the task. In particular,
$$
\alpha_{\min}\ge2^{-L},\qquad \beta_{\min}\ge2^{-L}.
$$
Both case-specific bounds for $q$, and the weaker uniform bound for $\alpha_{\min}q$, are correct. They yield
$$
K=O\!\left(L+\log(m+1)+\log(n+1)+\log(1/\Delta)\right).
$$
The structural probabilities and thresholds have polynomial encoding length. There are polynomially many stored probe entries and comparisons. Subject to the observation-access clarification above, the decoding computations have polynomial bit complexity.
There is no hidden inverse-supply or inverse-employer-mass number of rounds.
The cited algorithmic result applies. The [Dean–Munshi paper](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf) permits nonintegral quotas and edge capacities, requires strict preferences, and describes polynomial algorithms for bipartite stable allocation. Its dummy-vertex convention represents unused quotas and gives the unused-quota blocking interpretation used by the prover.
The constructed instance satisfies the required hypotheses:
The employer-quota argument is correct: an unfilled employer and an unfilled worker would have an unsaturated connecting edge that blocks through unused quota.
The conversion to the task’s stability definition also checks out. A proposed blocking triple implies $x_{p,a}<\alpha_p$. Either worker-side blocking condition implies $x_{p,a}<\beta_a$. Thus the edge is unsaturated and blocks in the cited allocation model.
The compactness argument for the benchmark is valid: stability is expressed by finitely many unions and intersections of closed conditions, within a bounded feasible set. Existence has already been established, and the continuous benchmark objective attains its minimum.
The write-up respects the stated individual-feedback restrictions:
Inference from aggregate actions is permitted by the stated public-matrix access. The proof does not require a separate reward-sharing channel.
Independent permanent choices with probabilities $x_{p,a}/\alpha_p$ produce request matrix $x$ under exact population laws. Feasibility then guarantees acceptance of every request.
The regret argument is correct as a one-sided upper bound, which the prover explicitly states at the outset.
Before assignment, nonnegative payoffs and $v_p^-\le1$ bound each round’s regret contribution by one. After assignment,
$$
v_p(x)\ge v_p^-,
$$
so subsequent expected contributions are nonpositive. Therefore,
$$
R_p(T)\le\min\{T,H\}.
$$
The bound on $H$ yields the claimed horizon-independent upper bound, and hence the requested logarithmic regret upper bound for every $T\ge2$.
The argument does not establish an absolute-value bound on regret; none is required under the stated conventional interpretation. Its constants depend on encoded support data rather than absolute population scale.
⟨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.