Answer: polynomial-time solvable
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateUnder the responsiveness condition, when $N\le C$, the player-optimal stable regret of each player $p_i$ by following Algorithm \ref{alg:AETDA} satisfies \begin{align*} \overline{R}_i(T) \le O\bracket{ N\cdot \min\set{N, K}C \log T/\Delta_{\overline{m}}^2 } \,.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses over \(\tau\) worker types, per-capita employer capacities, responsive employer priorities over types, and unknown type–employer reward means, does there exist a policy with polynomial-size representation in \(K,\tau\), and input bit length \(L\) that achieves the proposed per-capita regret bound against the player-optimal stable mass matching? Each worker retains private reward history, so the policy must account for the evolving distribution of histories as mass is allocated across employers.
A society is given by its support: the list of \(\tau\) worker types with positive binary-rational masses \(w_i\), normalized by \(\sum_i w_i=1\). Here \(\tau\) is the support size, not the number of possible types. There are \(m=K\ge2\) employers with positive binary-rational per-capita capacities \(c_j\), with \(c=\sum_j c_j\ge1\), and known strict priority orders over types; all types are acceptable.
Each type–employer pair has an unknown rational mean \(\mu_{ij}\in(0,1]\), distinct across employers for each type. Accepted workers receive independent Bernoulli rewards with these means; rejected or abstaining workers receive zero. Let \(L\) bound the binary encoding length of the market data, including the hidden means; means and preference gaps are unavailable to the policy. The horizon \(T\ge2\) is known.
Each round, every worker proposes to one employer or abstains. Employers accept applicant mass in priority order up to capacity; a partially accepted type is thinned uniformly across its private histories. Workers retain their own observations and may report an employer label or an undecided status; accepted type masses and type–status masses are public. Population evolution uses the induced probability kernels, including reward outcomes, rather than replacing individual observations by their means.
A feasible mass matching \(x\) satisfies \(x_{ij}\ge0\), \(\sum_jx_{ij}\le w_i\), and \(\sum_ix_{ij}\le c_j\); unmatched mass has value zero. It is stable if no positive mass of a type prefers an employer to its present assignment while that employer has spare capacity or employs positive mass of a strictly lower-priority type. Equal-priority workers do not displace one another. Let \(x^*\) be the worker-optimal stable mass matching: for every type and preference prefix, its assigned mass in that prefix is at least that in any stable mass matching.
Write \(\rho_{i,k}\) for type \(i\)'s employer ranked \(k\)-th, set \(r_i=\max\{k:x^*_{i,\rho_{i,k}}>0\}\), and define \(\Delta=\min_{i,\,1\le k\le\min\{r_i,K-1\}}(\mu_{i,\rho_{i,k}}-\mu_{i,\rho_{i,k+1}})\). If \(a_{ij}(t)\) is accepted type–employer mass at round \(t\), type \(i\)'s per-capita stable regret is \(R_i(T)=w_i^{-1}\mathbb E\sum_{t=1}^T\sum_j\mu_{ij}(x^*_{ij}-a_{ij}(t))\).
A succinct policy consists of shared finite programs and private worker states of size \(\operatorname{poly}(K,\tau,L,\log T)\), specifying proposal and reporting kernels from private state and public observations. Its guarantee must hold uniformly over the hidden means. Polynomial synthesis means time \(\operatorname{poly}(m,\tau,L,\log T)\); execution per worker per round is polynomial in these parameters and the bit length of current observations.
Is constructing a succinct policy guaranteeing \(R_i(T)=O(\tau\min\{\tau,K\}\,c\log T/\Delta^2)\) for every type polynomial-time solvable, or NP-hard?
For finite workers, AETDA achieves per-worker player-optimal stable regret \(O(N\min\{N,K\}C\log T/\Delta_{\overline m}^2)\) under responsive priorities and \(N\le C\), without knowing the gap. [Kong–Li](https://arxiv.org/html/2401.01528v2).
A continuum model with individual reward histories admits nearly payoff-optimal matching policies when the payoff matrix is known and worker types are unknown; its objective is steady-state total payoff. [Johari–Kamble–Kanoria](https://www.columbia.edu/~yk2577/Matching-Learning-EC.pdf). No result settling the exact private-history stable-regret synthesis question above was located.
The problem is polynomial-time solvable. In fact, there is a succinct policy with \(\lvert R_i(T)\rvert\le 1\) for every type.
The decisive feature is the combination of exact public type–status masses and population evolution by probability kernels. Reporting individual reward outcomes through the permitted labels reveals every mean after one round. This construction applies to arbitrary positive masses and capacities, including markets whose stable assignments split types across employers.
I interpret the permitted reporting kernels literally: a worker may choose an employer label or undecided based on its private observations. The question imposes no additional requirement that a reported label certify the worker’s best employer.
Define the positive proposal probabilities
\[ p_j=\frac{c_j}{2c}. \]
Their sum is \(\sum_jp_j=1/2\). In round one, every worker, independently through its proposal kernel, proposes to employer \(j\) with probability \(p_j\) and abstains with probability \(1/2\).
The applicant mass at employer \(j\) is
\[ \sum_i w_i p_j=p_j=\frac{c_j}{2c}\le\frac{c_j}{2}<c_j, \]
where we used \(\sum_iw_i=1\) and \(c\ge1\). Consequently, every applicant is accepted, irrespective of employer priorities. Thus
\[ a_{ij}(1)=w_i p_j>0. \]
After receiving its private reward, a worker reports its proposed employer \(j\) if its reward was one, and reports undecided otherwise. Abstaining workers also report undecided.
Let \(s_{ij}\) be the resulting public mass of type \(i\) reporting label \(j\). The specified kernel evolution gives
\[ s_{ij}=w_i p_j\mu_{ij}. \]
Indeed, a type \(i\) worker proposes to \(j\) with probability \(p_j\), is accepted with probability one, and then reports \(j\) with conditional probability \(\mu_{ij}\).
This calculation preserves individual Bernoulli observations: successful and unsuccessful workers occupy different private histories. It derives the public mass by applying their reporting kernels; it does not replace an individual reward by its mean.
At the beginning of round two, every worker can therefore recover every mean exactly:
\[ \mu_{ij}=\frac{s_{ij}}{a_{ij}(1)}. \]
All denominators are positive. The first-round proposal and reporting rules require neither the hidden means nor the gaps.
We use the following established stable-allocation result: a bipartite allocation instance with vertex quotas, edge capacities, and strict preference lists admits a strongly polynomial algorithm computing a stable allocation that simultaneously lexicographically maximizes each proposing vertex’s allocation vector in its preference order. This is the job-optimal allocation described in Section 2 and computed by the algorithm in Section 3 of [Dean–Munshi, *Faster Algorithms for Stable Allocation Problems*](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
Here are the hypothesis checks and the identification with the question’s benchmark.
Use the types as jobs, with quotas \(w_i\), and employers as machines, with quotas \(c_j\). Give edge \(ij\) capacity
\[ u_{ij}=\min\{w_i,c_j\}. \]
These edge capacities impose no additional restriction on feasible mass matchings. Furthermore, a blocking pair in the question necessarily satisfies \(x_{ij}<u_{ij}\): if \(x_{ij}=w_i\), type \(i\) has no unmatched or worse-assigned mass; if \(x_{ij}=c_j\), employer \(j\) has neither spare capacity nor lower-priority assigned mass.
For completeness, the theorem’s formulation with fully assigned vertex quotas can represent unmatched mass and spare capacity explicitly. Add a dummy employer \(d\) of quota one and a dummy type \(0\) of quota \(c\). Every real vertex ranks the dummy vertex last; each dummy ranks all real vertices before the other dummy. Complete these to strict lists arbitrarily.
For any feasible original matching \(x\), write \(s=\sum_{ij}x_{ij}\) and extend it by
\[ y_{i d}=w_i-\sum_jx_{ij},\qquad y_{0j}=c_j-\sum_ix_{ij},\qquad y_{0d}=s. \]
These quantities are nonnegative and fill every augmented quota exactly. Conversely, the quota equations force precisely these dummy allocations in any augmented feasible allocation.
A real pair blocks the augmented allocation exactly when it blocks the original matching: dummy assignments represent unmatched workers and spare capacity. No pair involving a dummy can block, because at least one endpoint ranks the other endpoint last and has no strictly worse assignment. Thus restriction and extension preserve stability.
The recovered means give strict worker preference lists by the distinctness assumption; employer lists are already strict. The augmented instance has \(\tau+K+2\) vertices and \(\tau K+\tau+K+1\) edges.
Let \(z\) be the restriction of the job-optimal allocation returned by the algorithm.
The benchmark \(x^*\) specified in the question dominates every stable matching in every worker preference prefix. It therefore lexicographically dominates every stable allocation vector for each real type: at the first unequal coordinate, preceding coordinates agree, so the prefix inequality forces the coordinate of \(x^*\) to be larger.
Conversely, job optimality says that each allocation vector of \(z\) is lexicographically at least that of \(x^*\). These two statements force equality for every type. Hence \(z=x^*\).
Thus a worker can compute the exact benchmark from the round-one public observations in polynomial time.
At round two, every worker runs the same deterministic computation described above. A type \(i\) worker then selects a persistent employer label with probabilities
\[ q_{ij}=\frac{x^*_{ij}}{w_i}, \]
and selects persistent abstention with the remaining probability
\[ q_{i0}=1-\sum_jq_{ij}. \]
It follows that label in every remaining round. This selection kernel is independent of its first-round private history.
The resulting type–employer proposal mass is exactly \(w_iq_{ij}=x^*_{ij}\). Feasibility gives
\[ \sum_i x^*_{ij}\le c_j. \]
Therefore every proposal is accepted, and
\[ a_{ij}(t)=x^*_{ij}\qquad\text{for every }t\ge2. \]
Later private reward outcomes do not change these proposals.
The synthesized policy consists of fixed programs together with the public market data. Synthesis writes those programs and constants; the computation depending on hidden means occurs during execution, after the permitted public observations become available.
The first-round masses and recovered means have polynomial binary encoding length: they are products and quotients of the input rationals. Sorting the recovered means uses exact rational comparisons.
The stable-allocation algorithm also has polynomial bit complexity here. Its numerical updates use additions, subtractions, comparisons, and minima. After scaling quotas and edge capacities by a common denominator \(D\), these updates operate on integers. The bit length of \(D\), and of the bounded allocation and residual-capacity values, is polynomial in the input length.
Each worker needs polynomial storage for the recovered data and allocation computation, followed by its persistent label. Private reward counts, if retained, require only \(O(K\log T)\) additional bits. Proposal and reporting kernels are specified by rational probabilities of polynomial encoding length. No enumeration of microscopic workers or private histories is required.
Consequently, synthesis, private-state size, and execution satisfy the stated polynomial bounds.
All rounds after the first contribute zero regret. Hence
\[ R_i(T)= \frac{1}{w_i} \sum_j\mu_{ij}\bigl(x^*_{ij}-w_ip_j\bigr). \]
Both the benchmark per-capita payoff and the first-round per-capita payoff belong to \([0,1]\), because rewards lie in \([0,1]\) and each worker receives at most one reward per round. Therefore
\[ \lvert R_i(T)\rvert\le1. \]
To compare this with the requested bound, first observe that every stable matching fully matches every type. Otherwise, total assigned mass would be less than one, and hence less than total capacity \(c\). Some employer would have spare capacity, forming a blocking pair with any unmatched positive type mass, since all employers are acceptable.
Thus \(r_i\ge1\). Since \(K\ge2\) and each type’s means are distinct, the defining set for \(\Delta\) is nonempty and \(0<\Delta<1\). Using also \(T\ge2\), \(\tau\ge1\), and \(c\ge1\), we obtain
\[ \frac{\tau\min\{\tau,K\}\,c\log T}{\Delta^2}\ge\log2. \]
The constant regret bound therefore implies, uniformly over the hidden means,
\[ R_i(T)=O\!\left( \frac{\tau\min\{\tau,K\}\,c\log T}{\Delta^2} \right). \]
The proof uses exact public masses of reward-dependent reports. Under the stipulated kernel evolution, those masses reveal exact reward probabilities even though each worker observes only its own Bernoulli outcome.
If public masses were noisy or rounded, or reporting labels had additional prescribed semantics, this argument would require reconsideration. Those restrictions are absent from the assigned task.
⟨structured verdict parsed — rendered above⟩
The argument establishes polynomial-time synthesis under the observation model in USER_TASK, subject to one minor omission in specifying the augmented stable-allocation instance. No central step is false, and no additional mathematical argument is needed.
The decisive mean-recovery step is valid here: population masses evolve by the specified probability kernels, and reward-dependent status masses are public. The prover uses individual Bernoulli outcomes without substituting means for individual observations.
The probabilities \(p_j=c_j/(2c)\) are positive and sum to \(1/2\), so the proposal kernel is valid.
Under kernel evolution, employer \(j\)'s applicant mass is exactly
\[
\sum_i w_i p_j=p_j.
\]
Since \(c\ge1\), this mass satisfies \(p_j\le c_j/2<c_j\). Every applicant is therefore accepted, independently of priorities, and \(a_{ij}(1)=w_i p_j>0\).
This argument covers arbitrarily small positive masses and capacities. It requires no lower bound on their numerical magnitudes.
Reporting label \(j\) precisely after proposing to \(j\) and observing reward one is permitted by the stated reporting-kernel model. USER_TASK does not require labels to represent estimated preferences.
The resulting type–status mass is exactly
\[
s_{ij}=w_i p_j\mu_{ij}.
\]
This follows from composing the proposal, reward, and reporting kernels. Successful and unsuccessful workers still have distinct individual observations.
Consequently, dividing the public status mass by the positive public accepted mass recovers \(\mu_{ij}\) exactly. All type–employer means are recovered simultaneously before the second-round computation.
There is no sampling-error gap: exact kernel-induced population masses, rather than finite empirical frequencies, are stipulated by the task.
The cited result is applicable. Dean–Munshi define strict preferences, vertex quotas, edge capacities, and stability through an unsaturated edge with strictly worse positive allocations at both endpoints. Their job-optimal allocation maximizes each job's allocation vector lexicographically; Section 3 gives a polynomial algorithm returning that allocation. See [Dean–Munshi, Sections 2–3, particularly Lemma 5](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
The real-edge capacities \(u_{ij}=\min\{w_i,c_j\}\) introduce no additional feasibility restriction. The prover correctly checks that an original blocking pair cannot already saturate this capacity:
The dummy allocation formulas correctly fill all augmented quotas. The real-job totals become \(w_i\), the real-machine totals become \(c_j\), the dummy-job total becomes \(c\), and the dummy-machine total becomes one. Conversely, these quota equations determine the dummy allocations uniquely.
The stability correspondence is also correct, provided the dummy-edge capacities permit the displayed extension. Dummy allocations represent unmatched mass and unused capacity. A pair involving a dummy cannot block because a real endpoint ranks its dummy last, or both endpoints do so for the dummy–dummy pair.
Minor issue: The write-up does not explicitly specify capacities for the newly added dummy edges. These are part of the cited theorem's input, and the extension must respect them.
Minimum clarification needed: State the dummy-edge capacities and verify that the displayed extension satisfies them for every feasible original matching. This is a routine completion of the instance specification.
The identification is valid against the benchmark stipulated in USER_TASK.
Prefix dominance by \(x^*\) implies lexicographic dominance: at the first differing coordinate, all preceding coordinates agree, so the corresponding prefix inequality determines the direction of the difference.
Job optimality supplies the reverse lexicographic comparison between the computed stable allocation and the extension of \(x^*\). Hence every real type's allocation vector agrees with that of \(x^*\).
The argument uses the existence and prefix-optimality of \(x^*\) as supplied by the task; it does not mistakenly infer prefix dominance from lexicographic optimality alone.
The probabilities \(q_{ij}=x^*_{ij}/w_i\), together with the remaining abstention probability, are valid because \(w_i>0\) and the matching is feasible.
History-independent selection at round two assigns aggregate proposal mass \(x^*_{ij}\). Persistence preserves that mass in subsequent rounds, regardless of later rewards. Employer feasibility then guarantees acceptance of every proposal.
Thus \(a_{ij}(t)=x^*_{ij}\) for every \(t\ge2\). Split type assignments cause no difficulty.
The distinction between synthesis and execution is legitimate. Synthesis outputs programs using known market data; execution recovers hidden means from permitted observations.
The rational products and quotients used in recovery have polynomial encoding length. Exact sorting is therefore polynomial.
The stable-allocation computation uses polynomially many numerical operations. Its additions, subtractions, comparisons, and minima preserve a common rational denominator. Scaling by that denominator gives integers of polynomial bit length, so the stated arithmetic-operation bound yields polynomial bit complexity.
The allocation matrix, recovered means, temporary algorithm state, and persistent label all fit within polynomial private-state size. The construction specifies rational probability kernels directly, as permitted by the task.
Only the first round contributes regret. Both compared per-capita payoffs lie in \([0,1]\), so the claimed stronger bound \(\lvert R_i(T)\rvert\le1\) is correct.
The full-matching argument is valid: unmatched positive mass would imply total allocation below one and hence unused capacity somewhere, producing a blocking pair because every employer is acceptable.
Therefore each \(r_i\ge1\). With \(K\ge2\), the defining set for \(\Delta\) is nonempty. Strict preferences and means in \((0,1]\) give \(0<\Delta<1\).
The displayed comparison with \(\log2\) is correct using the natural logarithm. Another fixed logarithm base changes only the uniform constant. The constant regret bound consequently implies the requested bound for every type and every permitted hidden mean matrix.
Specify the capacities of all dummy edges and confirm that the extension formulas respect them. No other repair is required.
⟨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.