Answer: Polynomial-time solvable exactly. Both feedback models have zero minimax high-probability Nash regret and zero oracle calls required to produce the output.
Theorem 2 — class: algorithmic
Given rational type masses \(\mu\) over \(\tau\) symmetric compatibility types, \(K\) coalition labels, horizon \(H\), accuracy \(\varepsilon\), confidence \(\delta\), and a finite-rate semi-bandit or bandit oracle, choose per-type room distributions \(q^r\) from shared feedback to minimize normalized population Nash regret, and output \(\hat{q}\) with population Nash gap at most \(\varepsilon\); determine regret and sample complexity as functions of \(\tau\), \(K\), \(H\), \(\varepsilon\), \(\delta\), and the encoding length of \(\mu\).
A nonatomic society is given by its support: the list of \(\tau\geq1\) types with positive binary-rational masses \(\mu_r\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Let \(L\) be the input bit length.
There are \(K\geq1\) room labels, so the action count is \(m=K\), and \(H\geq1\) rounds; accuracy and confidence parameters satisfy \(\varepsilon,\delta\in(0,1)\). Unknown fixed distributions \(D_{rs}=D_{sr}\) on \([-1,1]\) have means \(a_{rs}=a_{sr}\); \(a_{rr}\) describes interactions between distinct individuals of type \(r\), not self-interaction.
An allocation consists of rational distributions \(q^r\in\Delta(\{1,\ldots,K\})\), with room masses \(x_{r\ell}=\mu_rq^r_\ell\) and individual payoff \(u_{r\ell}(q)=\sum_s a_{rs}x_{s\ell}\). Empty rooms are allowed. An infinitesimal individual may switch to any room label without changing these masses; an entire type is not a unilateral deviator.
Define the normalized population Nash gap \(G(q)=\max_r\bigl[\max_\ell u_{r\ell}(q)-\sum_\ell q^r_\ell u_{r\ell}(q)\bigr]\) and Nash regret \(R_H=\sum_{t=1}^H G(q_t)\).
The finite-rate oracle operates once per round: independently sample \(\ell_r\sim q^r\) for each type, and draw fresh independent samples \(X_{rs}=X_{sr}\sim D_{rs}\) for unordered type pairs, including diagonal pairs. Samples are binary rationals of at most \(B\) bits, where \(B\) is known.
Semi-bandit feedback reveals \(X_{rs}\) for each \(r,s\) with \(x_{s\ell_r}>0\); bandit feedback reveals only \(Y_r=\sum_s x_{s\ell_r}X_{rs}\) for each \(r\). All feedback and sampled labels are shared; subsequent allocations may depend on this history. One oracle call is one round, irrespective of the number of revealed components.
Is producing \(\widehat q\) with \(G(\widehat q)\leq\varepsilon\) with probability at least \(1-\delta\) polynomial-time solvable in this oracle model, or is it NP-hard? State computational dependence on \(m=K,\tau,L,B,\varepsilon^{-1},\log(1/\delta)\).
For each feedback model, what are the minimax high-probability regret over \(H\) rounds and the oracle-call complexity of obtaining such an output, as functions of the same parameters?
Discrete: for \(n\) agents, established high-probability upper bounds are \(O(\sqrt{n^3H\log(n^2H/\delta)})\) under semi-bandit feedback and \(O((n^{3/2}+1)\sqrt{n^3H\log(n^2H/\delta)})\) under bandit feedback ([finite-agent result](https://ojs.aaai.org/index.php/AAAI/article/download/33498/35653)).
Continuous: no result settling this precise population model with the specified finite-rate oracle was located.
Result
The problem is polynomial-time solvable exactly, without oracle calls. Under both feedback models, the minimax high-probability Nash regret is identically \(0\).
This holds throughout the stated parameter range: splitting every type equally among all labels produces a universal equilibrium.
Proof of the universal equilibrium
For every type \(r\) and label \(\ell\), set
\(q^{*,r}_\ell=1/K\).
These are rational distributions, including when \(K=1\). The resulting masses are
\(x^*_{s\ell}=\mu_s/K\).
Fix any admissible mean matrix \(A=(a_{rs})\). For every type \(r\) and every label \(\ell\),
\(u_{r\ell}(q^*)=\sum_{s=1}^{\tau}a_{rs}\mu_s/K=:c_r.\)
Thus all room labels give type \(r\) the same payoff. Consequently,
\(\max_\ell u_{r\ell}(q^*)-\sum_{\ell=1}^{K}q^{*,r}_\ell u_{r\ell}(q^*)=c_r-\sum_{\ell=1}^{K}c_r/K=0.\)
Taking the maximum over types proves \(G(q^*)=0\).
This calculation uses the stipulated nonatomic deviation rule: an individual’s switch does not change any room mass. It includes diagonal interactions exactly as defined. Indeed, symmetry of the mean matrix is unnecessary for this construction.
Computational and oracle-call complexity
The algorithm outputs \(\widehat q=q^*\). Its guarantee is deterministic:
\(\Pr\!\left(G(\widehat q)\leq\varepsilon\right)=1.\)
Under an explicit encoding listing all \(\tau K\) probabilities, each entry \(1/K\) requires \(O(\log(K+1))\) bits. Reading the input and writing the allocation therefore takes
\(O\!\left(L+\tau K\log(K+1)\right)\)
bit operations using ordinary binary fraction encoding. This is polynomial in \(m=K,\tau,L\). There is no additional dependence on \(B,\varepsilon^{-1}\), or \(\log(1/\delta)\).
The required oracle-call complexity is exactly \(0\), for both semi-bandit and bandit feedback.
Exact minimax regret
Use \(q_t=q^*\) in every round. For every admissible collection of distributions and every realization of the oracle feedback,
\(R_H=\sum_{t=1}^{H}G(q_t)=0.\)
For the matching lower bound, consider any allocation \(q\). For each type, \(\sum_\ell q^r_\ell u_{r\ell}(q)\) is a convex combination of its room payoffs, so it cannot exceed their maximum. Hence \(G(q)\geq0\), and therefore every algorithm has \(R_H\geq0\) on every trajectory.
These upper and lower bounds establish the exact minimax value:
| Feedback model | Minimax regret with probability at least \(1-\delta\) | Calls needed to produce \(\widehat q\) |
|---|---:|---:|
| Semi-bandit | \(0\) | \(0\) |
| Bandit | \(0\) | \(0\) |
If the online protocol requires one oracle invocation in each of its \(H\) rounds, that execution makes \(H\) calls. The allocation ignores their results, and producing the requested output requires none.
Why the discrete comparison does not obstruct this result
The [cited finite-agent paper](https://ojs.aaai.org/index.php/AAAI/article/download/33498/35653) studies partitions of individual agents. Here, type mass can be split equally, while unilateral individuals have zero mass. Also, the sampled labels determine feedback; the stated gap is evaluated at the population masses. These premises make the universal equilibrium above available for the entire specified model.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the stated population problem. The equilibrium calculation, computational bound, zero oracle-call complexity, and exact zero minimax regret are valid. No major or minor issues were found.
The proposed allocation assigns \(q^{*,r}_\ell=1/K\) for every supported type and every room label.
Because \(K\geq1\), these probabilities are nonnegative rational numbers and sum to \(1\) for each type. Thus they satisfy the required allocation domain, including the case \(K=1\). The corresponding room masses \(x^*_{s\ell}=\mu_s/K\) follow directly from the definition.
The task permits splitting each type among rooms. Consequently, this construction uses the intended allocation model.
Substituting the proposed masses into the stipulated payoff formula gives
\(u_{r\ell}(q^*)=\sum_{s=1}^{\tau}a_{rs}\mu_s/K=c_r\).
This expression is independent of the room label, for every type and every admissible mean matrix.
The next calculation is exact: the maximum room payoff is \(c_r\), and the probability-weighted average room payoff is also \(c_r\), since the probabilities sum to \(1\). Each type’s gap is therefore zero, and taking the maximum over the nonempty support gives \(G(q^*)=0\).
This argument remains valid for negative payoffs and diagonal terms. It correctly uses the specified nonatomic deviation rule: switching rooms does not change population masses. No symmetry assumption or unproved equilibrium-existence theorem is needed.
Under the stated explicit output representation, there are \(\tau K\) probabilities to write. Each rational \(1/K\) has a binary numerator-and-denominator representation of length \(O(\log(K+1))\). Accordingly, the claimed bound \(O(L+\tau K\log(K+1))\) is valid for reading the input and producing the allocation.
The allocation domain requires rational probabilities, so \(1/K\) is admissible even when it has no terminating binary expansion. The binary-rational restrictions on input masses and oracle samples do not impose a dyadic restriction on output probabilities.
The algorithm uses neither observations nor numerical approximation. Its absence of additional dependence on \(B\), \(\varepsilon^{-1}\), and \(\log(1/\delta)\) is justified. The result is polynomial in the parameters requested by the task, including \(m=K\).
Since \(G(q^*)=0\) for every admissible collection of distributions, the requested accuracy event holds deterministically for every allowed \(\varepsilon\) and \(\delta\).
Zero oracle calls suffice under either feedback model. The output correctly distinguishes this production cost from the \(H\) calls made when executing an online protocol that mandates one invocation per round.
Playing the same allocation every round gives \(R_H=0\) for every instance and every feedback realization. This establishes the claimed high-probability upper bound with probability \(1\).
The matching lower bound is correct: a convex combination of finitely many real payoffs cannot exceed their maximum. Therefore every type’s gap is nonnegative, hence \(G(q)\geq0\) and \(R_H\geq0\) for every algorithm and trajectory.
Together, these statements establish exact minimax regret zero for both feedback models, throughout the stated parameter range.
The description of the cited discrete work as studying partitions of individual agents is supported by the [finite-agent paper](https://ojs.aaai.org/index.php/AAAI/article/download/33498/35653). The output’s distinction between those partitions and the task’s divisible nonatomic allocations is valid. Its observation that sampled labels govern feedback while the gap is evaluated at population masses also matches the task.
Required clarification or repair: none.
⟨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.