Answer: Pointwise \(R_T=o(T)\) is polynomial-time achievable. Static selection is \(\mathrm{NP}\)-hard with a constant gap; uniformly polynomial-horizon learning would imply \(\mathrm{NP}=\mathrm{RP}\). An \(\varepsilon\)-accurate implementation in time \(f(\tau,\alpha)\operatorname{poly}(m,L,T,1/\varepsilon,W,\sigma)\) exists.
Theorem 4 — class: algorithmic
Given rational type masses \(\mu_a\), a coalition-size bound \(\alpha\), a per-capita coalition-count bound \(\kappa\), and unknown symmetric type-pair utilities \(w_{ab}\), does there exist a learner with expected regret \(o(T)\) against the minimum achievable maximum pairwise envy? In each round it chooses masses \(x_q\) over nonempty integer group compositions \(q\in\mathbb{Z}_{\ge 0}^{\tau}\) with \(\sum_a q_a\le\alpha\), subject to \(\sum_q q_a x_q=\mu_a\) and \(\sum_q x_q\le\kappa\), then receives one independent sub-Gaussian report for each type pair that co-occurs in positive mass (including \((a,a)\) when a group contains at least two type-\(a\) members). For a type-\(a\) person in composition \(q\), own utility is \(\sum_c(q_c-\mathbf{1}[c=a])w_{ac}\); replacing a type-\(b\) member of composition \(r\) gives utility \(\sum_c(r_c-\mathbf{1}[c=b])w_{ac}\). The envy objective is the maximum positive difference between these utilities over types and positive-mass compositions. Can the learner achieve this regret with an \(f(\tau,\alpha)\operatorname{poly}(L,T,1/\varepsilon)\)-time \(\varepsilon\)-accurate implementation, where \(L\) is the input bit length?
A society is given by its support: \(\tau\) types with positive binary-rational masses \(\mu_a\), normalized by \(\sum_a\mu_a=1\); \(\tau\) is the support size, not the number of possible types. Here \(m=\tau\), since there is no separate underlying ground set.
Let \(\alpha\ge2\) be an integer and \(\kappa\) a binary rational with \(1/\alpha\le\kappa<1\). Write \(Q=\{q\in\mathbb Z_{\ge0}^{\tau}:1\le\sum_aq_a\le\alpha\}\). A feasible action is a nonnegative mass vector \(x\) satisfying \(\sum_{q\in Q}q_ax_q=\mu_a\) for every \(a\) and \(\sum_{q\in Q}x_q\le\kappa\); denote its feasible set by \(X\).
Utilities \(w_{ab}=w_{ba}\in\mathbb R\) are fixed and unknown, with a known rational bound \(W>0\) satisfying \(|w_{ab}|\le W\). The value \(w_{aa}\) describes two distinct people of type \(a\), not self-utility; self-utility is zero.
Define \(u_a(q)=\sum_c(q_c-\mathbf1[c=a])w_{ac}\) and \(v_{a,b}(r)=\sum_c(r_c-\mathbf1[c=b])w_{ac}\). Set \(E(x,w)=\max\{0,\max_{x_qx_r>0,\ q_a>0,\ r_b>0}(v_{a,b}(r)-u_a(q))\}\); comparisons concern distinct group instances, allowing \(q=r\). Assume \(E(\cdot,w)\) is nonconstant on \(X\).
At round \(t\), a learner chooses a rational feasible \(x^t\) using only previous feedback. It receives one report \(w_{ab}+\eta^t_{ab}\) for each unordered pair occurring in a positive-mass composition, including \((a,a)\) precisely when some such composition has \(q_a\ge2\). Noises are independent, mean-zero, and identically distributed across rounds for each pair, with known sub-Gaussian proxy \(\sigma^2\).
Let \(E^\star(w)=\inf_{x\in X}E(x,w)\) and \(R_T=\mathbb E[\sum_{t=1}^T(E(x^t,w)-E^\star(w))]\). An \(\varepsilon\)-accurate implementation permits additive regret overhead at most \(\varepsilon T\), while preserving feasibility exactly; obtaining \(o(T)\) requires a vanishing accuracy schedule.
Use binary computation with reports accessible to requested absolute precision; charge their encoding and precision costs. Let \(L\) count the supplied rational input and processed report bits, and state running times in \(m,\tau,\alpha,L,T,1/\varepsilon,W,\sigma\).
Is achieving expected regret \(R_T=o(T)\) in this model polynomial-time solvable, or is it NP-hard?
Can such a learner have an \(\varepsilon\)-accurate implementation taking total time \(f(\tau,\alpha)\operatorname{poly}(m,L,T,1/\varepsilon,W,\sigma)\)?
For finite societies, an oracle-based learner has a reported expected envy-regret bound of order \(O(T^{2/3}(\log T)^{1/3})\); its analysis assumes an efficient exact partition-selection oracle, rather than establishing polynomial-time implementation ([source](https://journals.sagepub.com/doi/10.3233/FAIA251405)). No result settling this exact mass-and-feedback model was located.
The answer depends on the quantifiers in “\(R_T=o(T)\).” The following statements hold for the model in the question.
Thus, for the substantive interpretation suggested by the cited regret rate, there is computational hardness. For the literal asymptotic requirement alone, there is a polynomial-time learner. Both assertions are proved below.
Actions are encoded as explicit sparse lists of compositions and positive rational masses. Report encoding and requested precision are charged throughout.
Write \(|q|=\sum_a q_a\), and let
\(N=|Q|=\binom{\tau+\alpha}{\alpha}-1,\qquad r=\tau+1.\)
Introduce a slack variable \(s=\kappa-\sum_q x_q\). Feasibility is equivalent to
\(\sum_{q\in Q}(q,1)x_q+(0,1)s=(\mu,\kappa),\qquad x_q\ge 0,\quad s\ge 0.\)
Let \(A\) denote this integer matrix, with \(N+1\) columns and \(r\) rows. It has rank \(r\): the columns corresponding to \(e_1,\ldots,e_\tau\), together with the slack column, are linearly independent.
The feasible set is nonempty. Indeed, assigning mass \(\mu_a/\alpha\) to composition \(\alpha e_a\) gives total group mass \(1/\alpha\le\kappa\).
For any feasible augmented vector \(y=(x,s)\), suppose its positive columns are linearly dependent. There is then a nonzero vector \(h\), supported on those columns, with \(Ah=0\).
Every column of \(A\) has last coordinate \(1\), so \(\sum_i h_i=0\). Consequently, \(h\) has both positive and negative entries. Set
\(\theta=\min_{h_i>0}y_i/h_i.\)
Then \(y-\theta h\) is feasible, nonnegative, and has strictly smaller support. Repeating this operation yields a feasible vector whose positive columns are independent. Extend these columns to a basis of \(A\), assigning zero to the additional basic variables.
This produces a basic feasible action \(x'\) satisfying
\(\operatorname{supp}(x')\subseteq\operatorname{supp}(x).\)
Removing supported compositions removes envy comparisons. Therefore,
\(E(x',w)\le E(x,w).\)
Enumerate every nonsingular set of \(r\) columns of \(A\), solve its system against \((\mu,\kappa)\), and retain the nonnegative solutions. Let \(\mathcal A\) be the resulting finite family of actions. The preceding argument proves
\(E^\star(w)=\min_{x\in\mathcal A}E(x,w).\)
In particular, the infimum is attained by a rational action supported on at most \(\tau+1\) compositions. This conclusion does not require continuity of \(E\).
Let \(L_0\) denote the supplied rational input length. Clear the denominators of \((\mu,\kappa)\) using a common denominator of bit length at most \(L_0\). A basis matrix has dimension \(r\) and entries of absolute value at most \(\alpha\). Cramer’s rule and the determinant bound \(r!\alpha^r\) show that its solution coordinates have bit length
\(O\!\left(L_0+r\log r+r\log\alpha\right).\)
Thus each basis can be processed using polynomially many bit operations. There are at most
\(M=\binom{N+1}{r}\le (N+1)^r\)
bases. Compositions can be indexed and recovered using binomial counts, without first materializing all of \(Q\).
For rational utilities, a certificate for \(E^\star\le h\) consists of one such sparse rational action. Its feasibility and every relevant envy comparison can be checked in polynomial time.
We reduce from the \(\mathrm{NP}\)-complete clique problem. Its classical hardness is established in [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Start with a graph \(G_0\) and target clique size \(k_0\), with \(2\le k_0\le |V(G_0)|\). To make all supplied masses and \(\kappa\) dyadic, let \(\alpha\) be the least power of two at least \(k_0+1\), and put \(k=\alpha-1\). Add \(k-k_0\) new vertices adjacent to every other vertex, obtaining \(G\).
Then \(G\) has a \(k\)-clique exactly when \(G_0\) has a \(k_0\)-clique: a \(k\)-clique contains at least \(k_0\) original vertices, and an original \(k_0\)-clique extends using the new vertices.
Let \(n=|V(G)|\). This padding is polynomial in the original input size.
The types are the \(n\) graph vertices and three additional types \(p,s,z\). Thus
\(m=\tau=n+3,\qquad \alpha=k+1,\qquad \kappa=1/\alpha,\qquad W=2.\)
Choose a dyadic rational \(\lambda\) satisfying
\(0<\lambda<\frac{1}{2\alpha(n+2)}.\)
Set
\(\mu_a=\lambda\quad(a\in V(G)),\qquad \mu_s=\mu_z=\lambda,\qquad \mu_p=1-(n+2)\lambda.\)
All masses are positive, normalized, and have polynomial encoding length.
Define symmetric utilities as follows:
These specify all unordered pairs. The value \(w_{zz}=2\) concerns two distinct people of type \(z\); the subtraction in \(u_z\) still excludes self-utility.
We prove
\(G\text{ has a }k\text{-clique}\ \Longleftrightarrow\ E^\star(w)=0,\)
and otherwise \(E^\star(w)\ge 1\).
For any feasible action,
\(1=\sum_q |q|x_q\le\alpha\sum_q x_q\le\alpha\kappa=1.\)
Equality throughout implies \(\sum_q x_q=1/\alpha\), and every positive-mass composition has size \(\alpha\).
Moreover, every feasible action contains a positive-mass pure \(p\) composition \(\alpha e_p\). Otherwise every supported composition would contain at most \(k\) copies of \(p\), giving
\(\mu_p\le k\sum_q x_q=k/\alpha.\)
But the chosen masses satisfy \(\mu_p>k/\alpha\).
Suppose \(E(x,w)<1\).
For any supported composition \(q\) containing types \(a,b\), the allowed comparison with another instance of the same composition gives
\(v_{a,b}(q)-u_a(q)=w_{aa}-w_{ab}.\)
If a composition contained \(z\) and another type \(b\), this difference for \(a=z\) would be at least \(1\). Thus every composition containing \(z\) is pure. Since \(\mu_z>0\), composition \(\alpha e_z\) has positive mass.
Now take any supported composition \(q\) containing \(s\). Comparing an \(s\)-person with a \(z\)-person in the pure \(z\) composition gives prospective utility \(k\). Hence
\(k-u_s(q)<1.\)
The utility \(u_s(q)\) is an integer at most \(k\), so \(u_s(q)=k\). Every one of the \(k\) other occupants must therefore have utility \(1\) for \(s\).
There can be no additional \(s\), no \(p\), and no \(z\): the first two have utility \(0\) for \(s\), and mixed \(z\) compositions were excluded. Thus \(q\) contains one \(s\) and \(k\) graph vertices, initially possibly with repetitions.
For any graph type \(a\) occurring in \(q\), comparison with the positive-mass pure \(p\) composition gives
\(k-u_a(q)<1.\)
Again \(u_a(q)\) is an integer at most \(k\), so it equals \(k\). Every other occupant must have utility \(1\) for \(a\). Because \(w_{aa}=0\), graph vertices cannot repeat. Because nonedges have utility \(0\), all graph vertices in \(q\) are mutually adjacent.
Consequently, \(q\) contains a \(k\)-clique.
Conversely, let \(C\) be a \(k\)-clique. Use the following compositions and masses:
The last mass is positive, since
\(\mu_p-k(n-k)\lambda=1-[n+2+k(n-k)]\lambda>0,\)
using \(n+2+k(n-k)\le\alpha(n+2)\).
Each graph type, \(s\), and \(z\) receives exactly its prescribed mass. The remaining \(p\)-mass is assigned to pure \(p\) groups. Since every composition has size \(\alpha\), the total group mass is exactly \(1/\alpha\). Feasibility is exact.
Every graph person, \(s\)-person, and \(p\)-person has utility \(k\). Every \(z\)-person has utility \(2k\). All entries in a non-\(z\) row are at most \(1\), and all entries in the \(z\)-row are at most \(2\). Thus prospective utilities are respectively at most \(k\) and \(2k\). No comparison has positive envy.
Therefore \(E(x,w)=0\).
The pure-type action \(x_{\alpha e_a}=\mu_a/\alpha\) has envy exactly \(k\). Graph people have own utility \(0\) and prospective utility \(k\) in pure \(p\) groups; \(s\)-people similarly see utility \(k\) in pure \(z\) groups. The row bounds above exclude larger envy.
For a second action, choose any graph vertex \(a_0\). Assign:
The remaining \(p\)-mass is positive because its numerator is
\(1-[n+2+kn-1]\lambda>0.\)
Graph people have utility \(k\); \(s\)-people have utility \(1\); \(p\)-people have utility \(k\) or \(k-1\); and \(z\)-people have utility \(2k\). Their maximum envies are respectively \(0,k-1,1,0\). Since \(k\ge2\), this action has envy exactly \(k-1\).
Hence \(E\) is nonconstant, independently of whether a clique exists.
The reduction proves the promised gap. Section 1 supplies polynomial-size certificates, so deciding whether \(E^\star=0\) is \(\mathrm{NP}\)-complete for rational utility input.
In particular, producing an action with
\(E(x,w)\le E^\star(w)+\varepsilon\)
for a fixed \(\varepsilon<1\) is \(\mathrm{NP}\)-hard: on a yes-instance its output has envy below \(1\), which certifies and explicitly exhibits a clique.
Consider a learner with polynomial total bit cost and the following uniform convergence guarantee: for the constructed instances of encoding length at most \(S\), a computable polynomial horizon \(H(S)\) satisfies
\(R_{H(S)}/H(S)\le 1/4.\)
Simulate the learner on a clique instance. Use identically zero noise, which satisfies the noise assumption with, for example, known proxy \(\sigma^2=1\). Every requested report is a known integer utility.
On a yes-instance, \(E^\star=0\). Choose a round \(J\) uniformly from \(\{1,\ldots,H(S)\}\). Then
\(\mathbb E[E(x^J,w)]\le1/4.\)
By Markov’s inequality,
\(\Pr(E(x^J,w)\ge1)\le1/4.\)
Accept precisely when \(E(x^J,w)<1\). This test takes polynomial time on the explicit output. By the reduction, no no-instance can be accepted, while a yes-instance is accepted with probability at least \(3/4\). Thus clique belongs to \(\mathrm{RP}\), implying \(\mathrm{NP}=\mathrm{RP}\).
Requested precision costs must be included in this polynomial bit budget; allowing exponentially expensive report requests would not yield a polynomial-time simulation.
For example, a guarantee
\(R_T\le P(m,\alpha,L_0,W,\sigma)\,T^{2/3}(\log T)^{1/3}\)
with polynomial \(P\), together with polynomial computational and observation costs, satisfies the polynomial-horizon condition. An implementation overhead of \(\varepsilon T\) does not avoid the conclusion: take a fixed sufficiently small \(\varepsilon\), and choose the horizon so that the remaining average-regret bound is also sufficiently small.
This establishes hardness for the intended uniform interpretation of efficient sublinear regret.
Let \(d=\tau(\tau+1)/2\), and define
\(\rho=\frac{\min_a\mu_a}{2\alpha(d+1)}.\)
For each \(a<b\), assign mass \(\rho\) to
\(q^{ab}=(\alpha-1)e_a+e_b.\)
Define residual type masses
\(r_a=\mu_a-\rho\sum_{i<j}q^{ij}_a,\)
and assign mass \(r_a/\alpha\) to \(\alpha e_a\).
Since \(\rho\alpha d<\min_a\mu_a/2\), every residual is positive. Every composition has size \(\alpha\), so this action is exactly feasible with total group mass \(1/\alpha\).
Every off-diagonal pair occurs in its designated composition. Every diagonal pair occurs in a pure composition, since \(\alpha\ge2\). Thus each play provides one report for every unordered pair, irrespective of how small the positive masses are.
The action has at most \(\tau+\binom{\tau}{2}\) compositions and polynomial encoding length.
For every relevant comparison, both \(q-e_a\) and \(r-e_b\) are nonnegative vectors with coordinate sums at most \(\alpha-1\). Therefore the comparison, as a linear function of utilities, has coefficient norm at most \(2(\alpha-1)\).
Taking maxima preserves this bound:
\(|E(x,w)-E(x,\widetilde w)|\le2(\alpha-1)\|w-\widetilde w\|_\infty.\)
Also,
\(0\le E(x,w)\le B,\qquad B=2(\alpha-1)W.\)
For a given horizon \(T\), play the exploration action for
\(n=\min\{T,\lceil T^{2/3}\rceil\}\)
rounds. Access each report to absolute error at most \(\delta\), average the accessed reports for each pair, and project each average onto \([-W,W]\). Denote the resulting rational symmetric matrix by \(\widehat w\).
The true unrounded sample mean for each pair has centered sub-Gaussian proxy \(\sigma^2/n\). Applying the exponential-moment bound to both signs of all \(d\) errors gives
\(\mathbb E\|\widehat w-w\|_\infty\le \sigma\sqrt{\frac{2\log(2d)}{n}}+\delta.\)
Projection cannot increase error because every true utility lies in \([-W,W]\).
For the remaining rounds, choose exactly a minimizer
\(\widehat x\in\arg\min_{x\in\mathcal A}E(x,\widehat w).\)
If \(x^\star\in\mathcal A\) minimizes true envy, the Lipschitz bound and estimated optimality imply
\(E(\widehat x,w)-E^\star(w)\le4(\alpha-1)\|\widehat w-w\|_\infty.\)
Consequently,
\(R_T\le Bn+4(\alpha-1)(T-n)\left(\sigma\sqrt{\frac{2\log(2d)}{n}}+\delta\right).\)
Choosing \(\delta\le\varepsilon/[4(\alpha-1)]\) yields
\(R_T=O\!\left((\alpha-1)\bigl(W+\sigma\sqrt{\log(2d)}\bigr)T^{2/3}\right)+\varepsilon T.\)
Selection on the rational estimates is exact. The numerical term is at most \(\varepsilon T\).
To obtain sublinear regret, use a vanishing accuracy schedule, for example
\(\delta_T\le\frac{\min\{\varepsilon,T^{-1/3}\}}{4(\alpha-1)}.\)
The resulting bound is \(o(T)\). An unknown horizon can be handled by doubling epochs; fresh exploration in each epoch preserves the same order of regret.
Enumerate the basic feasible actions from Section 1 once, and compare their envy values using exact rational arithmetic. Feasibility is never approximated.
For instance, a valid parameter factor is
\(f(\tau,\alpha)=\left[\binom{\tau+\alpha}{\alpha}\right]^{\tau+1}\operatorname{poly}(\tau,\log\alpha).\)
The total bit time is
\(f(\tau,\alpha)\operatorname{poly}(m,L,T,1/\varepsilon,W,\sigma).\)
Requested fractional precision requires only
\(O\!\left(\log(2+\alpha/\varepsilon)+\log(2+T)\right)\)
bits per accessed report. Unbounded report integer parts and all processed report bits are charged through \(L\). No exact comparison of unknown real utilities is used.
This proves the requested parameterized implementation exists.
For completeness, here is an explicit learner establishing the literal asymptotic claim.
At each round:
At exploration round \(j^2\), access reports with absolute error at most \(1/j\), implemented using dyadic precision. Estimate utilities using these exploration reports only, and project the averages onto \([-W,W]\).
After at most \(M\) rounds, every basis has been processed. The retained family then contains a true optimal action. Before this time, regret is at most \(BM\).
By round \(t\), the number of previous scheduled observations per pair is \(\lfloor\sqrt{t-1}\rfloor\). Averaged numerical error is bounded by
\(\frac{1}{n}\sum_{j=1}^n\frac1j\le\frac{1+\log n}{n}.\)
The statistical error bound and the Lipschitz argument therefore give, after enumeration is complete, expected exploitation regret per round of order
\(O\!\left((\alpha-1)\left[\sigma\sqrt{\log(2d)}\,t^{-1/4}+(\log t)t^{-1/2}\right]\right).\)
There are at most \(\sqrt T+1\) exploration rounds. Summing yields
\(R_T\le BM+O\!\left(B\sqrt T+(\alpha-1)\sigma\sqrt{\log(2d)}\,T^{3/4}+(\alpha-1)\sqrt T\log(2+T)\right).\)
For every fixed society, \(M\) is finite, so this is \(o(T)\).
Meanwhile, only one basis is processed per round, and at most \(T\) retained actions are evaluated in any round. Total computation is bounded by
\(T^2\operatorname{poly}(m,\tau,\alpha,L,W,\sigma).\)
Thus the literal pointwise requirement has a polynomial-time solution. Its potentially exponential transient \(BM\) explains why it does not contradict the uniform hardness result.
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance. It establishes a polynomial-time learner for the literal, pointwise requirement \(R_T=o(T)\), a constant-gap hardness result for static selection, and a conditional obstruction to learning with a uniformly polynomial convergence horizon. The parameterized implementation also follows. I found one minor precision-accounting clarification and no blocking mathematical issue.
The augmented feasibility system correctly includes the group-mass slack. Its matrix has rank \(\tau+1\), as witnessed by the singleton columns and the slack column.
The support-reduction argument is valid: a dependence vector has entries of both signs because every column has last coordinate \(1\). The specified displacement preserves feasibility and nonnegativity while eliminating a positive coordinate. Repetition terminates with independent positive columns.
Crucially, removing compositions can only remove envy comparisons. Thus the argument correctly establishes
\[
E^\star(w)=\min_{x\in\mathcal A}E(x,w).
\]
No continuity assumption is needed.
The determinant bound and rational-coordinate bit-length estimate are valid. The resulting certificates have polynomial length, and feasibility and all relevant comparisons can be checked from the sparse representation. Zero basic coordinates and duplicate actions do not affect the argument.
The invoked source problem is the standard NP-complete CLIQUE decision problem, attributed to [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9). The restriction \(2\le k_0\le |V(G_0)|\) removes only trivial cases.
Padding by universal vertices preserves the stated equivalence. The least-power-of-two choice makes \(\alpha\) polynomially bounded in the original instance size and makes \(\kappa=1/\alpha\) dyadic.
The masses are positive and normalized. A dyadic \(\lambda\) satisfying the strict upper bound can have polynomial encoding length. The utility table specifies every unordered pair, is symmetric, and respects \(W=2\).
Equality in the displayed mass inequalities forces every positive composition to have size \(\alpha\).
The claimed mandatory pure \(p\) composition also follows. The bound on \(\lambda\) gives \(\mu_p>k/\alpha\), contradicting the maximum possible \(p\)-mass if every supported composition contained at most \(k\) copies of \(p\).
The identity
\[
v_{a,b}(q)-u_a(q)=w_{aa}-w_{ab}
\]
is correct. Its use is legitimate because the task expressly permits comparisons between distinct instances of the same composition.
For a mixed composition containing \(z\), the difference is at least \(1\). Consequently, envy below \(1\) forces all \(z\)-groups to be pure.
Comparing an \(s\)-person against a pure \(z\)-group forces their integer utility to equal \(k\). The utility table then forces exactly one \(s\) and \(k\) graph occupants.
Comparing each graph occupant against a pure \(p\)-group similarly forces utility \(k\). Repeated vertices and nonadjacent vertices would each prevent that equality. The supported \(s\)-composition therefore contains a \(k\)-clique.
This proves the full gap implication: if there is no clique, every feasible action has envy at least \(1\).
Every prescribed type mass is correct. The remaining pure \(p\)-mass is strictly positive under the displayed bound on \(\lambda\). Since all compositions have size \(\alpha\), the total group mass is exactly \(\kappa\).
The claimed utilities are correct: graph, \(s\), and \(p\) occupants obtain \(k\), while \(z\) occupants obtain \(2k\). The row bounds control every prospective utility, including comparisons within the same composition. Thus the action has zero envy.
The pure-type action has envy exactly \(k\).
For the second action, the remaining \(p\)-mass numerator is correctly computed and positive. The stated occupant utilities are correct. The maximum envies are respectively \(0,k-1,1,0\), with pure \(z\) and pure \(p\) groups supplying the required comparisons.
Because \(k\ge2\), the second action has envy exactly \(k-1\). The promise therefore holds on both yes-instances and no-instances.
The static NP-hardness claim, its constant additive gap, and the polynomial certificate claim all follow.
Zero noise satisfies the model. On a yes-instance, the uniformly sampled round has expected envy at most \(1/4\). Markov’s inequality gives acceptance probability at least \(3/4\). On a no-instance, the gap makes acceptance impossible.
The acceptance test is polynomial on the explicit rational action. With the stipulated polynomial horizon and polynomial computation and observation costs, this gives an RP algorithm for CLIQUE and hence \(\mathrm{NP}=\mathrm{RP}\).
The write-up correctly treats this as a conditional consequence. Bare pointwise sublinear regret does not supply a polynomial convergence horizon.
Each residual mass is strictly positive. The action has full-size compositions and total group mass \(1/\alpha\), so feasibility is exact even when \(\kappa>1/\alpha\).
Every off-diagonal pair occurs in its designated composition, and every diagonal pair occurs in a positive pure composition. This correctly uses the model’s rule that observation depends on positive support rather than on the magnitude of the composition mass.
The coefficient norm bound \(2(\alpha-1)\) is correct, as are the Lipschitz inequality and the uniform envy bound \(B=2(\alpha-1)W\).
The expected maximum estimation-error bound correctly uses \(n\) independent observations per pair and both signs of the \(d\) errors. Independence between different pairs is unnecessary for this particular maximum bound. Rounding contributes at most \(\delta\), and projection cannot increase error.
Exact minimization over \(\mathcal A\) then gives the stated factor \(4(\alpha-1)\). With \(n=\lceil T^{2/3}\rceil\), capped at \(T\), the displayed regret bound and numerical overhead follow. The vanishing precision schedule gives sublinear regret for each fixed instance.
The doubling-epoch assertion is a routine extension; no additional mathematical obstacle is apparent.
Exhaustive basis enumeration has a parameter-dependent number of iterations. Each iteration uses exact rational arithmetic of polynomial bit cost. The resulting feasibility guarantee is exact, and all processed report bits are explicitly charged through \(L\).
Minor issue — Section 4, accuracy choices and “Requested fractional precision requires only…”: The displayed conditions specify upper bounds on \(\delta\) and \(\delta_T\), whereas the precision-cost bound presumes that the algorithm chooses a dyadic accuracy at the stated scale. Arbitrarily smaller permitted accuracies could require arbitrarily more fractional bits.
Minimum clarification: State that the chosen dyadic accuracies are within a constant factor of the displayed thresholds. This is an implementation specification, not a missing mathematical argument, and does not undermine the existence claim.
Processing one basis per round limits the retained family to at most \(T\) actions. Thus the potentially exponential total family size does not enter the computational bound for a run of \(T\) rounds.
After enumeration finishes, the retained family contains a true optimum. Before completion, \(BM\) bounds accumulated regret. Square-numbered exploration supplies the stated number of observations, and the harmonic rounding-error bound is correct.
The resulting exploitation terms sum to the displayed \(T^{3/4}\) and \(\sqrt T\log(2+T)\) orders. Since \(M\) is fixed for each society, the regret is \(o(T)\). The computational bound is polynomial in the stated variables and processed bit length.
This establishes the literal target. It does not establish uniformly polynomial convergence, and the write-up correctly explains that distinction.
The appropriate continuous-status classification is polynomial for the task’s literal pointwise requirement. The differing convergence quantifiers do not constitute a split by input encoding or representation.
⟨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.