Answer: —
Theorem 4.10 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateTop Responsive hedonic games with informa- tive representation are efficiently PAC stabilizable.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Fix constant \(B\), a finite type set \(T\), and rational masses \(\mu_t>0\) with \(\sum_{t\in T}\mu_t=1\). Let \(\mathcal G_B=\{g\in\mathbb Z_{\ge0}^{T}:1\le\sum_t g_t\le B\}\). A type-\(t\) agent has unknown utility \(u_t(g)\) for any team profile \(g\) with \(g_t>0\). Define \(x_t(g)\) as the unique maximizer of \(u_t(x)\) over \(x\le g\) with \(x_t\ge1\); require the paper’s top-responsiveness comparison clauses on profiles, and require sampled utilities to reveal comparisons between choice profiles as in its informative-representation condition. Given samples \((h,(u_t(h))_{t:h_t>0})\) from an unknown distribution \(D\) over \(\mathcal G_B\), with team members sampled uniformly from their type populations, find an algorithm with sample and computation complexity polynomial in \(|T|\), \(1/\epsilon\), \(\log(1/\delta)\), and the input bit length that outputs rational frequencies \(q_g\ge0\) satisfying \(\sum_{g\in\mathcal G_B}g_tq_g=\mu_t\) for every \(t\), and, with probability at least \(1-\delta\) over the samples, satisfies \(\mathbb E_{h\sim D}[\prod_{t:h_t>0}p_t(h;q)^{h_t}]<\epsilon\), where \(p_t(h;q)=\mu_t^{-1}\sum_{g:u_t(h)>u_t(g)}g_tq_g\).
Fix a positive integer constant \(B\). A society is given by its support \(T\), consisting of \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) counts supported types, not possible types.
The admissible team profiles are \(\mathcal G_B=\{g\in\mathbb Z_{\ge0}^{T}:1\le\sum_tg_t\le B\}\); profile inequalities are coordinatewise.
Each type has an unknown signed rational utility \(u_t(g)\), defined whenever \(g_t>0\), inducing weak preferences; strict improvement means strictly greater utility.
For every such profile, require a unique choice profile \(x_t(g)=\operatorname*{arg\,max}_{x\le g,\,x_t\ge1}u_t(x)\). For \(g_t,h_t>0\), require \(u_t(x_t(g))>u_t(x_t(h))\Rightarrow u_t(g)>u_t(h)\), and \(x_t(g)=x_t(h),\ g\le h,\ g\ne h\Rightarrow u_t(g)>u_t(h)\).
The informative representation supplies known polynomial-time decoders that, from \(u_t(g),u_t(h)\), determine whether \(u_t(x_t(g))>u_t(x_t(h))\) and whether \(x_t(g)=x_t(h)\); they do not reveal the choice profiles themselves.
The only preference observations are \(m\) independent samples \((h,(u_t(h))_{t:h_t>0})\), with \(h\) drawn from an arbitrary unknown distribution \(D\) on \(\mathcal G_B\); no utility queries are available.
An output is a rational vector \(q_g\ge0\) satisfying \(\sum_{g\in\mathcal G_B}g_tq_g=\mu_t\) for every type. Here \(g_tq_g\) is the mass of type \(t\) assigned to teams of profile \(g\).
Conditional on a deviating profile \(h\), its members are drawn independently and uniformly from their respective atomless type populations. Thus define \(p_t(h;q)=\mu_t^{-1}\sum_{g\in\mathcal G_B:\,g_t>0,\,u_t(h)>u_t(g)}g_tq_g\) and \(R_D(q)=\mathbb E_{h\sim D}[\prod_{t:h_t>0}p_t(h;q)^{h_t}]\).
For binary-rational \(0<\epsilon,\delta<1\), the required guarantee is \(\Pr[R_D(q)<\epsilon]\ge1-\delta\), for every admissible utility system and distribution; probability includes samples and algorithmic randomness. Let \(L\) be the encoding length of the society and accuracy parameters plus a bound on each utility label's bit length.
For every fixed \(B\), is this continuous PAC stabilization problem solvable with sample complexity polynomial in \(\tau,L,1/\epsilon,\log(1/\delta)\) and computation polynomial in \(m,\tau,L,1/\epsilon,\log(1/\delta)\), or is it NP-hard?
Discrete top-responsive hedonic games with informative representations admit polynomial-sample, polynomial-time PAC stabilization under arbitrary coalition distributions ([Sliwinski and Zick](https://research.illc.uva.nl/COMSOC/proceedings/comsoc-2018/SliwinskiZickCOMSOC2018.pdf)).
No result settling this precise continuous formulation was located.
The computational classification remains unresolved for unrestricted fixed $B\ge3$. The following results are proved below:
$$
O\!\left(\frac{\tau B\log(\tau+B)+\log(1/\delta)}{\epsilon}\right)
$$
suffices. This improves the bound in the notes.
All uses of the notes are stated and justified here.
Write $|g|=\sum_tg_t$, and let $e_t$ denote the singleton profile of type $t$. Stars and bars gives
$$
N:=|\mathcal G_B|=\binom{\tau+B}{B}-1.
$$
In particular, $N$ is polynomial in $\tau$ when $B$ is fixed.
For a feasible allocation $q$, define
$$
a_t(h;q)=
\frac1{\mu_t}
\sum_{\substack{g:g_t>0\\u_t(g)\ge u_t(h)}}g_tq_g.
$$
The mass equation for type $t$ implies
$$
p_t(h;q)=1-a_t(h;q).
$$
Consequently, the blocking probability of $h$ is zero if and only if some participating type $t$ receives all its mass in profiles weakly preferred to $h$. Utility ties belong on the weakly preferred side because improvement is strict.
We use the following form of Scarf’s lemma. If $A$ is nonnegative with no zero column, $b$ is positive, and each row strictly orders its incident columns, then some extreme point of
$$
P=\{z\ge0:Az\le b\}
$$
dominates every column. A column $h$ is dominated in row $t$ when $A_{th}>0$, $A_tz=b_t$, and every positively allocated column incident to $t$ ranks at least as highly as $h$. This is [Lemma 1 of Biró, Csáji, and Schlotter](https://drops.dagstuhl.de/storage/00lipics/lipics-vol334-icalp2025/html/LIPIcs.ICALP.2025.31/LIPIcs.ICALP.2025.31.html).
Apply the theorem with
$$
A_{tg}=g_t,\qquad b_t=\mu_t,
$$
and order profiles by utility, resolving ties arbitrarily. Every column is nonzero. The singleton column $e_t$ can be dominated only in row $t$, so domination of all singletons forces
$$
Aq=\mu.
$$
A domination witness for $h$ receives mass only in profiles weakly preferred to $h$ under the original utilities: resolving ties never reverses a strict comparison. Hence every profile has zero blocking probability.
Proved conclusion. A zero-risk feasible allocation exists for every utility system, without requiring top responsiveness.
The positively supported columns of the extreme point are linearly independent. Otherwise there is a nonzero vector $d$, supported on its positive coordinates, with $Ad=0$. For sufficiently small $\lambda>0$, both $q+\lambda d$ and $q-\lambda d$ are nonnegative and preserve every row total. This contradicts extremality.
Thus the support has at most $\tau$ profiles. If its size is $s$, choose $s$ rows giving a nonsingular square subsystem. The supported coordinates are uniquely determined by that subsystem. Its integer coefficients lie between $0$ and $B$; its right-hand side consists of input masses. Cramer’s rule therefore gives rational coordinates of polynomial bit length.
We will also use the following observation:
If a feasible allocation stabilizes a collection of profiles, every feasible allocation whose support is contained in its support stabilizes the same collection.
Indeed, for each stabilized profile, its witness type originally receives mass only in weakly preferred profiles. Restricting the support preserves that fact; feasibility restores the full mass of that type.
Consequently, a feasible empirical stabilizer can be made sparse in polynomial time. On its existing support $F$, find an extreme point of the nonempty rational polytope
$$
\{z\ge0:A_Fz=\mu\}.
$$
This polytope is bounded, since every column is nonzero. Polynomial-time rational linear programming can return an extreme point, whose support has at most $\tau$ by the same independence argument.
Let $S$ be the distinct sampled profiles and put
$$
E=S\cup\{e_t:t\in T\}.
$$
We allocate mass only to profiles in $E$.
Define auxiliary utilities $\widehat u$ as follows. Preserve every observed utility label. If $e_t$ was not observed but type $t$ appeared in a sample, assign its singleton a value one unit below its minimum observed utility. If type $t$ never appeared, assign its singleton any rational value.
These labels have polynomial bit length. They need not satisfy top responsiveness; Scarf’s lemma permits arbitrary row orders.
Apply Section 1 to the columns in $E$. It gives a feasible allocation supported on at most $\tau$ profiles that dominates every column of $E$ in the auxiliary preferences.
To transfer this statement to the actual utilities, fix an observed profile $h$ and an auxiliary domination witness $t$. An artificial singleton of type $t$ ranks strictly below $h$, so it cannot receive positive mass at this witness. Every other positively allocated profile incident to $t$ was observed and retains its actual label. Therefore
$$
q_g>0,\quad g_t>0
\quad\Longrightarrow\quad
u_t(g)\ge u_t(h).
$$
Feasibility then gives $p_t(h;q)=0$.
Proved conclusion. Every sample has zero actual blocking probability.
This also supplies a finite algorithm. Enumerate independent subsets $F\subseteq E$ of size at most $\tau$, solve
$$
A_Fq_F=\mu,
$$
reject inconsistent or negative solutions, and check auxiliary domination of the observed profiles. The guaranteed sparse allocation occurs among the candidates. Each candidate requires polynomial work, but the number of candidates can be exponential in $\tau$.
The improved bound uses sparsity, rather than the probability mass of all unseen profiles.
For a fixed subset $F\subseteq\mathcal G_B$, define
$$
C_F=
\left\{
h:
\text{for every }t\text{ with }h_t>0,\
\text{some }g\in F\text{ satisfies }g_t>0
\text{ and }u_t(h)>u_t(g)
\right\}.
$$
The utility system is fixed, so $C_F$ is fixed independently of the samples.
If $F$ is the positive support of a feasible $q$, then
$$
h\in C_F
\quad\Longleftrightarrow\quad
\prod_{t:h_t>0}p_t(h;q)^{h_t}>0.
$$
This follows because each summand defining $p_t$ is nonnegative, and a summand indexed by an incident profile in the positive support is positive exactly when that profile is strictly worse than $h$. Thus
$$
R_D(q)\le D(C_F).
$$
There are at most
$$
K_0:=\sum_{s=0}^{\tau}\binom Ns\le(N+1)^\tau
$$
possible supports of size at most $\tau$. For the inequality, encode a subset as its increasing list of indices, padded with zeros to length $\tau$.
For any fixed $F$ with $D(C_F)\ge\epsilon$, the probability that every sample avoids $C_F$ is at most
$$
(1-\epsilon)^m\le e^{-m\epsilon}.
$$
A union bound therefore gives
$$
\Pr\!\left[
\exists F,\ |F|\le\tau:
D(C_F)\ge\epsilon
\text{ and every sample avoids }C_F
\right]
\le (N+1)^\tau e^{-m\epsilon}.
$$
The sparse allocation from Section 2 stabilizes every sample, so its support satisfies the avoidance condition. Hence it is enough to take
$$
m\ge
\left\lceil
\frac{\tau\ln(N+1)+\ln(1/\delta)+1}{\epsilon}
\right\rceil.
$$
The displayed failure bound is then at most $\delta/e$, which is strictly below $\delta$. Outside that failure event,
$$
R_D(q)\le D(C_F)<\epsilon.
$$
Finally,
$$
N+1=\binom{\tau+B}{B}\le(\tau+B)^B.
$$
Proved conclusion. For every fixed $B$, polynomially many samples suffice, with
$$
m=
O\!\left(
\frac{\tau B\log(\tau+B)+\log(1/\delta)}{\epsilon}
\right).
$$
This is an information-theoretic bound with a finite exponential-time implementation. It does not establish polynomial computation for unrestricted $B\ge3$.
For $B=1$, the unique feasible allocation is
$$
q_{e_t}=\mu_t.
$$
Every admissible profile has zero blocking probability, without samples.
Now let $B=2$, and use the auxiliary instance $E$ from Section 2. For each type $t$, choose a most-preferred homogeneous profile
$$
H_t\in
\operatorname*{arg\,max}_{g\in E:\operatorname{supp}(g)=\{t\}}
\widehat u_t(g).
$$
It is either $e_t$ or $2e_t$; write $k_t=|H_t|$.
Retain an observed mixed pair $h=e_s+e_t$ as a graph edge precisely when
$$
\widehat u_s(h)>\widehat u_s(H_s),
\qquad
\widehat u_t(h)>\widehat u_t(H_t).
$$
Give vertex $t$ quota $\mu_t$ and edge $\{s,t\}$ capacity $\min(\mu_s,\mu_t)$. Order incident edges by auxiliary utility, resolving ties arbitrarily.
We use the nonbipartite fractional stable-allocation theorem: rational quotas and capacities admit a polynomial-time computable allocation $y$ such that every edge is either at capacity or has an endpoint whose quota is entirely assigned to edges ranked at least as highly as it. Unassigned mass is last-ranked. [Dean and Munshi, Section 5](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf) give such an algorithm; explicit rotation comparison gives a strongly polynomial implementation. Its arithmetic uses additions, subtractions, comparisons, and division by two, so polynomially many operations preserve polynomial rational encoding length.
All hypotheses hold for the graph just constructed. Define
$$
r_t=\mu_t-\sum_{s:\{s,t\}\text{ retained}}y_{st},
$$
and output
$$
q_{e_s+e_t}=y_{st},
\qquad
q_{H_t}=\frac{r_t}{k_t},
$$
with every other coordinate zero. Nonnegativity and the mass equalities follow directly from graph feasibility.
Every observed profile has an auxiliary domination witness:
These cases cover all profiles when $B=2$. Section 2 transfers auxiliary domination to actual stabilization. If necessary, apply the support reduction from Section 1 before using the sharper sample bound.
The graph has at most $\tau$ vertices and $O(\tau^2)$ edges. Its construction, solution, and conversion to $q$ are polynomial in $m,\tau,L$.
Proved conclusion. The task is polynomial-time solvable for $B\le2$.
This is an additional tractable empirical case.
On the auxiliary profile set $E$, construct a directed graph with an arc $g\to h$ whenever some type incident to both profiles satisfies
$$
\widehat u_t(g)>\widehat u_t(h).
$$
Assume this directed graph is acyclic. A topological ordering then places every strict improvement before the profile it improves upon.
Process profiles in that order. Initially let $r_t=\mu_t$. When processing $g$, assign
$$
q_g=\min_{t:g_t>0}\frac{r_t}{g_t},
$$
and replace each incident residual by $r_t-g_tq_g$.
All residuals remain nonnegative. When $e_t$ is processed, it consumes all remaining mass of type $t$. Thus the final allocation is feasible.
Fix a processed profile $h$. If its allocation is zero, some incident type already has zero residual. If its allocation is positive, some incident type reaches zero residual during this step. Choose such a type $t$. Every positively allocated profile incident to $t$ was processed no later than $h$.
None of those earlier profiles can be strictly worse than $h$ for $t$: otherwise the arc from $h$ to that profile would force it to occur later. No later incident profile receives positive mass because $r_t=0$. Hence all mass of $t$ is assigned to profiles weakly preferred to $h$.
Every observed profile is therefore stabilized. Each positive allocation exhausts at least one previously unexhausted type, so the support has at most $\tau$ profiles.
Proved conclusion. If the auxiliary observed preferences admit this common ordering, empirical stabilization is polynomial-time computable for arbitrary fixed $B$.
The condition is efficiently checkable. It is a sufficient condition, not a consequence of the task’s axioms.
The preceding algorithms stabilize samples exactly. The following conditional result shows that a polynomial approximation algorithm would also suffice.
Consider this auxiliary problem:
Feasibility uses the original mass equalities. Blocking probabilities use the supplied labels. Section 1 guarantees that a zero-risk solution exists.
Conditional claim. A solver for this problem running in time polynomial in its input length and $1/\eta$ would solve the original PAC task in the requested polynomial time.
The proof requires two ingredients.
Construct $E$ and $\widehat u$ from the samples as in Section 2. Let $q$ be any feasible allocation supported on $E$.
Fix an observed $h$ and a participating type $t$. Every assigned profile other than an artificial singleton has its actual observed label. An artificial singleton is strictly worse than $h$ in the auxiliary preferences. Its mass is therefore counted in the auxiliary $p_t(h;q)$, regardless of whether its unknown actual utility is worse than $h$.
Consequently,
$$
p_t^{\mathrm{actual}}(h;q)
\le
p_t^{\mathrm{auxiliary}}(h;q).
$$
Taking products preserves this inequality. Thus the actual empirical average risk is at most the auxiliary empirical average risk.
This comparison holds for approximate allocations, not merely zero-risk allocations.
Fix the actual utility system. For every profile $g$, let
$$
c_g=\min_{t:g_t>0}\frac{\mu_t}{g_t}.
$$
Every feasible allocation satisfies $0\le q_g\le c_g$, so write
$$
q_g=c_gz_g,\qquad z_g\in[0,1].
$$
For arbitrary $z\in[0,1]^N$, define
$$
P_t(h;z)=
\min\!\left\{
1,\
\sum_{\substack{g:g_t>0\\u_t(h)>u_t(g)}}
\frac{g_tc_g}{\mu_t}z_g
\right\},
$$
and
$$
F_z(h)=\prod_{t:h_t>0}P_t(h;z)^{h_t}.
$$
For a feasible $q$, these equal its actual dissatisfaction fractions and blocking probabilities. Every coefficient in the sum is at most one.
If $\|z-z'\|_\infty\le\rho$, clipping is Lipschitz and therefore
$$
|P_t(h;z)-P_t(h;z')|\le N\rho.
$$
View $F_z(h)$ as a product of $|h|$ factors, repeating the factor for type $t$ exactly $h_t$ times. A telescoping expansion of two products whose factors lie in $[0,1]$ gives
$$
|F_z(h)-F_{z'}(h)|\le |h|N\rho\le BN\rho.
$$
Set
$$
K=\left\lceil\frac{8BN}{\epsilon}\right\rceil.
$$
The coordinate grid with spacing $1/K$ has $(K+1)^N$ points, and every $z$ is within $1/K$ of a grid point.
For a fixed grid point, the sample values $F_z(H_i)$ are independent and lie in $[0,1]$. Hoeffding’s inequality gives
$$
\Pr\!\left[
\left|
\frac1m\sum_{i=1}^mF_z(H_i)
-\mathbb E_D[F_z(h)]
\right|>\frac{\epsilon}{4}
\right]
\le2e^{-m\epsilon^2/8}.
$$
A union bound over the grid shows that, if
$$
m\ge
\left\lceil
\frac8{\epsilon^2}
\left(
N\ln(K+1)+\ln(2/\delta)+1
\right)
\right\rceil,
$$
then with probability at least $1-\delta$, every grid point has error at most $\epsilon/4$.
For arbitrary $z$, transferring to its nearby grid point changes each of the empirical average and expectation by at most
$$
\frac{BN}{K}\le\frac{\epsilon}{8}.
$$
Hence, on the same event, every feasible $q$ satisfies
$$
R_D(q)\le
\frac1m\sum_{i=1}^m
\prod_{t:(H_i)_t>0}p_t(H_i;q)^{(H_i)_t}
+\frac{\epsilon}{2}.
$$
Invoke the hypothetical finite solver on the auxiliary labels with $\eta=\epsilon/4$. Section 5.2 bounds its actual empirical risk by $\epsilon/4$. Uniform convergence then gives
$$
R_D(q)\le\frac{3\epsilon}{4}<\epsilon.
$$
For fixed $B$, the sample bound and all reduction work are polynomial in the required parameters. The grid is used only in the proof; the algorithm does not enumerate it.
Proved conclusion. A polynomial-time approximation solver for the finite full-information problem above would settle the original task positively. Such a solver has not been established here.
We now justify the embedded matching problem and its accuracy dependence.
For any feasible $q$, define
$$
d(h;q)=\min_{t:h_t>0}p_t(h;q).
$$
Because all dissatisfaction fractions lie in $[0,1]$ and $1\le|h|\le B$,
$$
d(h;q)^B
\le
\prod_{t:h_t>0}p_t(h;q)^{h_t}
\le
d(h;q).
$$
The first inequality follows by replacing every factor by the minimum and then using $d^{|h|}\ge d^B$. The second follows by retaining a minimum factor and bounding all other factors by one.
Thus
$$
\mathbb E_D[d(h;q)^B]\le R_D(q)\le\mathbb E_D[d(h;q)].
$$
In particular, under the uniform distribution on $M$ profiles,
$$
R_D(q)<\epsilon
\quad\Longrightarrow\quad
d(h;q)<(M\epsilon)^{1/B}
$$
for every profile in the distribution’s support.
Fix $B\ge2$. Let $(V,\mathcal E)$ be a $B$-uniform hypergraph with strict incident-edge preferences $\succ_t$. A fractional matching consists of nonnegative coordinates $x_e$ satisfying
$$
\sum_{e\ni t}x_e\le1.
$$
Call it $\eta$-stable if every edge $e$ has a vertex $t\in e$ satisfying
$$
x_e+\sum_{\substack{f\ni t\\f\succ_t e}}x_f\ge1-\eta.
$$
Pad $V$ with isolated types until its size $\tau$ is a power of two, and give every type mass $1/\tau$. Each edge corresponds to its incidence profile $g_e$.
For each type $t$, rank its incident profiles injectively within each cardinality layer, using ranks
$$
1\le r_t(g)\le N.
$$
In the layer of size $B$, rank all designated edge profiles above every undesignated profile and order the designated profiles according to $\succ_t$. Define
$$
u_t(g)=N|g|+r_t(g).
$$
Every proper subprofile has smaller utility: even the largest rank at cardinality $k$ is below the smallest rank at cardinality $k+1$. Therefore
$$
x_t(g)=g
$$
uniquely. The choice-value implication becomes the identical utility implication. Equal choices imply equal profiles, so the equal-choice strict-containment requirement has no applicable antecedent.
Labels are injective for each type. Numerical comparison and equality therefore provide the two required informative decoders. Their outputs are the required Boolean values. Label lengths are polynomial.
Given any feasible society allocation $q$, put
$$
x_e=\tau q_{g_e}.
$$
Then
$$
\sum_{e\ni t}x_e
\le\tau\sum_g g_tq_g=1,
$$
so $x$ is a fractional matching.
The profiles weakly preferred to $g_e$ by type $t\in e$ are exactly $g_e$ and the designated incident edges preferred to it. Hence
$$
p_t(g_e;q)
=
1-x_e-\sum_{\substack{f\ni t\\f\succ_t e}}x_f.
$$
Let $M=|\mathcal E|\ge1$, and let $J$ be the smallest power of two at least $M$. Sample uniformly from a list of $J$ designated profiles containing every edge at least once. Every edge then has probability at least $1/J$, and the distribution is exactly samplable with $\log_2J$ random bits.
If $R_D(q)<\epsilon$, nonnegativity of the risk contributions gives, for each edge $e$,
$$
\prod_{t\in e}p_t(g_e;q)<J\epsilon.
$$
Thus some vertex satisfies
$$
p_t(g_e;q)<(J\epsilon)^{1/B}.
$$
For dyadic $0<\eta<1$, choose
$$
\epsilon=\frac{\eta^B}{2J}.
$$
The extracted matching is then $\eta$-stable. Moreover,
$$
\frac1\epsilon=\frac{2J}{\eta^B},
$$
which is polynomial in $M$ and $1/\eta$ for fixed $B$. All sampled labels can be computed from the hypergraph preferences.
Conversely, an $\eta$-stable fractional matching yields a feasible society allocation by assigning
$$
q_{g_e}=\frac{x_e}{\tau},
\qquad
q_{e_t}=\frac{1-\sum_{e\ni t}x_e}{\tau}.
$$
These profiles are distinct because $B\ge2$. The same dissatisfaction formula holds. Every designated edge has some dissatisfaction fraction at most $\eta$, so its blocking probability is at most $\eta$.
Proved conclusion. A polynomial-time PAC algorithm for fixed $B$ would give a randomized algorithm for $\eta$-stable fractional matching in $B$-uniform hypergraphs, with time polynomial in the instance size and $1/\eta$.
The approximate fractional matching theorem cited in the notes uses tolerance
$$
\eta=2^{-20M^4}
$$
in its exact-recovery argument. This is explicit in [Ishizuka and Kamiyama, Lemma 8](https://drops.dagstuhl.de/storage/00lipics/lipics-vol123-isaac2018/LIPIcs.ISAAC.2018.11/LIPIcs.ISAAC.2018.11.pdf).
Its reciprocal is exponential. Consequently, that argument does not exclude an algorithm polynomial in $1/\eta$, and it does not establish the requested $\mathrm{NP}$-hardness.
The sample requirement is polynomial for every fixed $B$, and computation is polynomial for $B\le2$. The new common-order algorithm settles another nontrivial case for arbitrary $B$. The full-information reduction shows that an approximation algorithm, rather than an exact Scarf algorithm, would suffice.
For unrestricted fixed $B\ge3$, neither the required polynomial-time approximation algorithm nor a hardness reduction with compatible reciprocal accuracy has been proved here.
⟨structured verdict parsed — rendered above⟩
The appropriate verdict is partial. The output establishes substantial results, including polynomial sample complexity for every fixed $B$ and polynomial computation for $B\le2$. It does not resolve the requested computational classification for unrestricted fixed $B\ge3$.
I found no central false step in the arguments establishing these partial results. The remaining issues are the explicitly unresolved target and several minor qualifications.
The count
$$
|\mathcal G_B|=\binom{\tau+B}{B}-1
$$
is correct: it counts all nonnegative integer profiles of total size at most $B$, excluding the zero profile. For fixed $B$, this is polynomial in $\tau$.
The identity
$$
p_t(h;q)=1-a_t(h;q)
$$
follows from feasibility and the partition of incident profiles into those strictly worse than $h$ and those weakly preferred to $h$. Positive masses ensure that normalization by $\mu_t$ is valid.
The zero-blocking characterization is also correct. Each participating type has a positive exponent, and all dissatisfaction fractions are nonnegative. Consequently, the product vanishes exactly when some participating type has dissatisfaction fraction zero. The placement of utility ties on the weakly preferred side correctly implements strict improvement.
The stated domination theorem agrees with Lemma 1 in the cited source. Its hypotheses are satisfied: the profile matrix is nonnegative, every column is nonzero, the masses are positive, and tie-breaking supplies strict incident-column orders. The source guarantees a dominating extreme point and a finite algorithm. [Biró, Csáji, and Schlotter, Lemma 1](https://drops.dagstuhl.de/storage/00lipics/lipics-vol334-icalp2025/html/LIPIcs.ICALP.2025.31/LIPIcs.ICALP.2025.31.html)
The singleton argument correctly forces every row to be saturated. A singleton column can be dominated only in its own type’s row. Thus the resulting point satisfies the mass equalities.
Tie-breaking does not reverse strict utility comparisons. Therefore domination under the refined orders implies domination under the original weak preferences.
Verified: a feasible zero-risk allocation exists for arbitrary utilities, without top responsiveness.
The linear-independence argument is valid. A nonzero kernel direction supported on positive coordinates would permit two distinct nearby feasible points whose midpoint is the alleged extreme point.
The resulting support bound of $\tau$ is correct. Selecting a nonsingular square subsystem and applying Cramer’s rule establishes rational coordinates of polynomial bit length because the coefficients are bounded integers and the masses have finite rational encodings.
The support-restriction observation is correct for exact stabilization: removing supported profiles preserves the witness type’s weak-preference condition, while feasibility supplies its full mass.
The support-reduction polytope is nonempty and bounded. Every column has a positive entry, so a row mass constraint bounds each coordinate. Standard polynomial-time rational linear programming can obtain an extreme point.
No substantive issue found in this section.
The auxiliary singleton construction is valid even though it need not preserve top responsiveness. The existence theorem used here does not require that property.
For any observed profile $h$, an unobserved singleton of a participating type receives an auxiliary utility strictly below that type’s observed utility at $h$. Therefore such a singleton cannot carry positive mass at an auxiliary domination witness for $h$.
All remaining positively allocated incident profiles at that witness have observed labels, so their comparisons transfer to the actual utilities. Types that never appeared in a sample do not affect this transfer.
The enumeration algorithm is valid:
Verified: every sample admits a rational, sparse, exactly stabilizing allocation obtainable by a finite algorithm. Polynomial computation is not established by this enumeration.
The family $C_F$ is fixed once the utility system and support $F$ are fixed. It therefore remains legitimate to union-bound over this family even though the algorithm selects its support after seeing the samples.
For a feasible allocation whose positive support is $F$, the equivalence
$$
h\in C_F
\quad\Longleftrightarrow\quad
\prod_{t:h_t>0}p_t(h;q)^{h_t}>0
$$
is correct. Positivity of supported coordinates ensures that an incident strictly worse profile contributes positive dissatisfaction mass.
Since every blocking probability lies in $[0,1]$,
$$
R_D(q)\le D(C_F)
$$
is valid.
The support count
$$
\sum_{s=0}^{\tau}\binom Ns\le(N+1)^\tau
$$
is justified by the stated padded-list encoding.
For a fixed support with $D(C_F)\ge\epsilon$, sample avoidance has probability at most $e^{-m\epsilon}$. The union bound and the displayed sample threshold are correct. The additional constant in the numerator gives failure probability at most $\delta/e$.
Outside the failure event, the selected support has
$$
D(C_F)<\epsilon,
$$
which correctly yields the task’s strict risk bound.
Finally,
$$
\binom{\tau+B}{B}\le(\tau+B)^B
$$
gives the asserted asymptotic sample complexity.
Verified: polynomial sample complexity for every fixed $B$, with a finite exponential-time implementation.
Minor issue: the assertion that this “improves the bound in the notes” cannot be audited because those notes and their baseline bound were not supplied. The displayed bound itself is established.
Only singleton profiles are admissible. The mass equalities determine the stated allocation, and each deviation compares a singleton with itself.
Verified: zero risk without samples.
The fallback selection and retained-edge criterion are correct. Every retained edge is strictly preferred to the fallback at both endpoints.
The cited nonbipartite stable-allocation result supports the required algorithm. Its model includes vertex quotas, edge capacities, strict preferences, and last-ranked unassigned mass. Section 5 also describes explicit rotation comparisons yielding a strongly polynomial implementation, so the output need not rely on the faster randomized hashing implementation. [Dean and Munshi, Section 5](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf)
The conversion to $q$ satisfies nonnegativity and the mass equalities, including the factor $k_t$ for homogeneous pairs.
All three domination cases check out:
Tie-breaking preserves the required weak comparisons under the original auxiliary utilities. The artificial-singleton transfer applies because its proof uses feasibility and domination, rather than any special property of the Scarf solution.
Support reduction permits use of the sharper sample bound.
Verified: the requested polynomial-time PAC guarantee for $B\le2$.
The orientation of the preference arcs is correct. A topological ordering places strictly preferred profiles earlier.
The residual allocation rule preserves nonnegativity. Processing each singleton exhausts its type’s remaining mass, establishing feasibility.
For every processed profile, the selected witness type is exhausted either before that profile or during its allocation. Earlier allocated incident profiles cannot be strictly worse, because that would contradict the topological ordering. Later incident profiles receive no positive mass.
Each positive allocation exhausts a previously unexhausted type, proving the support bound.
Verified: a polynomial-time empirical algorithm under the stated acyclicity condition. The output correctly identifies this as an additional assumption, rather than a consequence of the task’s axioms.
The comparison
$$
p_t^{\mathrm{actual}}(h;q)
\le p_t^{\mathrm{auxiliary}}(h;q)
$$
is correct. Artificial singleton mass is always counted as dissatisfied in the auxiliary instance for observed $h$, whereas it may or may not be dissatisfied under the actual utility.
Products preserve this inequality because all factors are nonnegative.
Every feasible coordinate satisfies $q_g\le c_g$. Every coefficient in the definition of $P_t$ is at most one.
The clipping and product bounds are valid:
$$
|P_t(h;z)-P_t(h;z')|\le N\rho,
$$
and
$$
|F_z(h)-F_{z'}(h)|\le BN\rho.
$$
The grid cardinality and covering radius are correct. Hoeffding’s inequality at tolerance $\epsilon/4$ gives the stated exponent:
$$
2e^{-m\epsilon^2/8}.
$$
The union bound is correct. Transferring both the empirical average and expectation from a grid point contributes at most $\epsilon/8$ each, giving total uniform error at most $\epsilon/2$.
Combining auxiliary empirical risk at most $\epsilon/4$ with uniform convergence yields
$$
R_D(q)\le\frac{3\epsilon}{4}<\epsilon.
$$
For fixed $B$, the dimension and sample bound are polynomial in the requested parameters. The grid is solely a proof device.
Verified: the conditional implication from the stated finite approximation solver to a polynomial-time PAC algorithm.
Minor issue: the finite computational problem specifies only $\eta>0$, without specifying its encoding. To make the computational statement precise, it should identify $\eta$ as a finitely encoded positive rational and include its encoding length in the input length. The reduction itself uses the supplied rational $\epsilon/4$, so this does not invalidate the implication.
Both bounds
$$
d(h;q)^B
\le
\prod_{t:h_t>0}p_t(h;q)^{h_t}
\le d(h;q)
$$
are correct. They use positive integer multiplicities, fractions in $[0,1]$, and $|h|\le B$.
The pointwise consequence under a uniform distribution follows from nonnegativity of every risk contribution.
Padding to a power-of-two type count gives positive binary-rational masses summing to one.
The utility construction strictly separates cardinality layers and is injective within each type’s incident profiles. Thus every proper subprofile has smaller utility, and the unique choice is the profile itself.
Both responsiveness requirements then hold as stated. Numerical comparison and equality supply the required informative decoder outputs.
For fixed $B$, the ranks and sampled labels can be computed by polynomial-size profile enumeration.
Verified: the embedding satisfies the task’s utility restrictions.
The extracted coordinates satisfy the fractional matching inequalities. The dissatisfaction formula is correct because the only profiles weakly preferred to a designated edge are that edge and its strictly preferred designated incident edges.
The power-of-two list distribution is exactly samplable and assigns every edge probability at least $1/J$.
The implication from total risk to each edge’s product bound is valid. With
$$
\epsilon=\frac{\eta^B}{2J},
$$
the resulting witness dissatisfaction is strictly below $\eta$. Reciprocal accuracy is polynomial in instance size and $1/\eta$ for fixed $B$.
Verified: the forward reduction from a successful PAC allocation to an approximate stable fractional matching.
Two minor qualifications remain:
The cited recovery lemma uses tolerance
$$
2^{-20M^4}.
$$
The output correctly distinguishes polynomial encoding length from polynomial reciprocal accuracy. That recovery argument does not establish hardness against algorithms allowed time polynomial in $1/\eta$. [Ishizuka and Kamiyama, Lemma 8](https://drops.dagstuhl.de/storage/00lipics/lipics-vol123-isaac2018/LIPIcs.ISAAC.2018.11/LIPIcs.ISAAC.2018.11.pdf)
Verified: the stated limitation of this hardness argument.
The output is internally consistent about being partial. Its established results are substantive, but the general algorithm-or-hardness question remains unanswered for unrestricted fixed $B\ge3$.
The minimum clarifications needed for the existing write-up are:
Completing USER_TASK requires an additional computational result for unrestricted fixed $B\ge3$. That requires new mathematics, rather than an expositional repair. No such result is supplied here.
⟨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.