Answer: Polynomial-time solvable: efficiently realizable PAC learnable.
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet H be a class of HGs that admits a compact HCN representation. Suppose that for every set of rules Ri, we know the corresponding set of formulas Φ. Then, H is efficiently PAC learnable. While the class presented above includes Additively Sep- arable, Fractional, and Anonymous HGs, which have all been shown to be efficiently PAC learnable, there exist other learnable classes which do not fall within the above charac- terization.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set with rational masses μ, compact known type-level HCN predicates over coalition-composition vectors, unknown shared rule coefficients, and i.i.d. labeled samples drawn with type marginal μ, output a hypothesis whose μ-weighted prediction error is below ε with confidence 1−δ, and determine polynomial sample and runtime bounds.
A society is given by its support: the list of the \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
A coalition composition is \(x\in\mathbb{Q}^{\tau}\) with \(0\leq x_t\leq\mu_t\); an example concerning type \(t\) must satisfy \(x_t>0\).
The known type-level hedonic coalition net consists of explicitly listed predicates \(\phi_{tj}(x)\in\{0,1\}\), for \(t\in\{1,\ldots,\tau\}\) and \(j\in\{1,\ldots,r\}\). Each predicate is a Boolean formula whose atoms are rational affine inequalities \(a\cdot x\leq b\). Unknown coefficients \(\beta\in\mathbb{Q}^r\), shared across types and unrestricted in sign, determine \(v_t(x)=\sum_{j=1}^r\beta_j\phi_{tj}(x)\); all satisfied rules contribute, and an empty sum is zero.
Samples \((t,x,v_t(x))\) are noiseless and i.i.d. from an arbitrary unknown distribution with type marginal \(\mu\) and conditional composition distributions \(D_t\) on the admissible domain. A hypothesis must have the same predicates and a shared rational coefficient vector \(\widehat\beta\).
For rational \(0<\varepsilon,\delta<1\), require \(\sum_t\mu_t\Pr_{x\sim D_t}[\widehat v_t(x)\neq v_t(x)]<\varepsilon\) with probability at least \(1-\delta\). Write \(m\) for sample size and \(L\) for the known instance's encoding length plus the maximum encoding length of one observed example.
Is this realizable PAC learning problem solvable with sample size polynomial in \(\tau,r,\varepsilon^{-1},\log(\delta^{-1})\) and running time polynomial in \(m,\tau,r,L,\varepsilon^{-1},\log(\delta^{-1})\), or is it NP-hard?
For finite agents, compact hedonic coalition nets with known rule formulas are efficiently PAC learnable under arbitrary coalition distributions and exact valuation-mismatch loss. [Fioravanti et al.](https://arxiv.org/html/2301.13756)
No result for exactly the composition-domain model specified here was located in the literature search.
The specified problem is efficiently realizable PAC learnable. A deterministic learner evaluates the known predicates on the samples and solves a rational linear system. A sufficient sample size is
\(m=O\!\left(\dfrac{r^2+\log(1/\delta)}{\varepsilon}\right).\)
The proof below applies directly to the composition domain and exact valuation-mismatch loss. It does not require solving predicate feasibility problems.
Define the admissible example domain by
\(\mathcal X=\{(t,x):t\in\{1,\ldots,\tau\},\ x\in\mathbb Q^\tau,\ 0\leq x_s\leq\mu_s\text{ for every }s,\ x_t>0\}.\)
For each admissible example, define its feature vector
\(z(t,x)=(\phi_{t1}(x),\ldots,\phi_{tr}(x))\in\{0,1\}^r.\)
Then the target valuation is \(v_t(x)=z(t,x)\cdot\beta\).
Given samples \((t_i,x_i,y_i)\), form the matrix \(A\in\{0,1\}^{m\times r}\) whose \(i\)-th row is \(z(t_i,x_i)\), and let \(y=(y_1,\ldots,y_m)\). The learner returns any rational solution \(\widehat\beta\) of
\(A\widehat\beta=y.\)
Realizability guarantees consistency: the unknown rational vector \(\beta\) solves this system. The returned hypothesis uses the prescribed predicates and the single shared vector \(\widehat\beta\).
If \(r=0\), every valuation is zero, so the empty coefficient vector is already an exact hypothesis. Henceforth assume \(r\geq1\).
Let
\(W=\operatorname{span}_{\mathbb Q}\{z(t_i,x_i):1\leq i\leq m\}.\)
Lemma. Every admissible example whose feature vector belongs to \(W\) is predicted exactly.
Proof. Put \(d=\widehat\beta-\beta\). Sample consistency gives \(z(t_i,x_i)\cdot d=0\) for every \(i\). If \(z(t,x)\in W\), there are rational coefficients \(\lambda_i\) such that \(z(t,x)=\sum_i\lambda_i z(t_i,x_i)\). Therefore
\(z(t,x)\cdot d=\sum_i\lambda_i\bigl(z(t_i,x_i)\cdot d\bigr)=0.\)
Thus \(\widehat v_t(x)=v_t(x)\). \(\square\)
Let \(P\) denote the joint example distribution: it chooses type \(t\) with probability \(\mu_t\), then composition \(x\) according to \(D_t\). Define
\(p(W)=\Pr_{(t,x)\sim P}[z(t,x)\notin W].\)
The lemma implies
\(\sum_t\mu_t\Pr_{x\sim D_t}[\widehat v_t(x)\neq v_t(x)]\leq p(W).\)
Consequently, it suffices to prove that \(p(W)<\varepsilon\) with high probability.
Consider the finite family
\(\mathcal W=\{\operatorname{span}_{\mathbb Q}(S):S\subseteq\{0,1\}^r\}.\)
Every member has a basis of at most \(r\) Boolean vectors. Padding a basis with zero vectors produces an ordered tuple of length \(r\) with the same span. There are \((2^r)^r=2^{r^2}\) such tuples, so
\(|\mathcal W|\leq2^{r^2}.\)
This family is used only in the proof; the learner never enumerates it.
Fix \(U\in\mathcal W\) with \(p(U)\geq\varepsilon\). Independence of the samples gives
\(\Pr[z(t_i,x_i)\in U\text{ for every }i]=(1-p(U))^m\leq(1-\varepsilon)^m\leq e^{-\varepsilon m}.\)
If the sampled span \(W\) satisfies \(p(W)\geq\varepsilon\), then some member \(U\in\mathcal W\) with \(p(U)\geq\varepsilon\) contains every sampled feature vector: take \(U=W\). A union bound therefore yields
\(\Pr[p(W)\geq\varepsilon]\leq2^{r^2}e^{-\varepsilon m}.\)
For an explicit sufficient sample size, set
\(k=\lceil\log_2(1/\delta)\rceil,\qquad m=\left\lceil\dfrac{r^2+k+1}{\varepsilon}\right\rceil.\)
Since \(e^{-u}\leq2^{-u}\) for \(u\geq0\),
\(\Pr[p(W)\geq\varepsilon]\leq2^{r^2-\varepsilon m}\leq2^{-k-1}<\delta.\)
Thus, with probability at least \(1-\delta\), the required loss is strictly less than \(\varepsilon\). No lower bound on individual type masses is needed.
At a supplied rational composition, each atom \(a\cdot x\leq b\) can be evaluated by exact rational arithmetic. Products and sums of the explicitly encoded rationals have bit lengths polynomial in \(\tau\) and \(L\). Evaluating the surrounding Boolean formula then takes time polynomial in its explicit length.
Hence constructing \(A\) takes time polynomial in \(m,\tau,r,L\). Negations and boundary equalities cause no difficulty because comparisons are exact.
Let \(q=\operatorname{rank}(A)\). If \(q=0\), realizability implies \(y=0\), and the learner returns \(\widehat\beta=0\).
Otherwise, exact elimination identifies \(q\) independent rows, forming a matrix \(B\), and \(q\) columns whose restriction gives an invertible matrix \(C\in\{0,1\}^{q\times q}\). Let \(b\) be the labels of those rows. Set all coefficients outside these columns to zero and solve \(C\widehat\beta_J=b\).
This satisfies every sample equation. Indeed, any row \(a_i\) of \(A\) has the form \(a_i=\lambda^\top B\). Realizability gives \(y_i=a_i\beta=\lambda^\top b\), while the constructed vector satisfies \(B\widehat\beta=b\). Therefore \(a_i\widehat\beta=y_i\).
To bound the output length, write \(b_i=p_i/d_i\), with positive denominators and numerator and denominator bit lengths at most \(L\). Put
\(D=\prod_{i=1}^q d_i,\qquad c=Db\in\mathbb Z^q.\)
Then \(D\leq2^{qL}\) and \(\max_i|c_i|\leq2^{(q+1)L}\). Cramer’s rule gives
\(\widehat\beta_{J_j}=\dfrac{\det C^{(j)}(c)}{D\det C},\)
where \(C^{(j)}(c)\) replaces column \(j\) by \(c\). The determinant expansion bounds these integers by
\(|\det C|\leq q!,\qquad |\det C^{(j)}(c)|\leq q!\,2^{(q+1)L}.\)
Each output coefficient therefore has bit length \(O(qL+q\log(q+1))\).
Standard fraction-free elimination computes the ranks, selected rows and columns, and these determinants in polynomial bit time. Its intermediate integers are bounded by minors of the relevant integer matrices; the same determinant bounds give polynomial bit lengths. Thus the entire learner runs in time polynomial in \(m,\tau,r,L\), and consequently meets the requested running-time bound.
[Fioravanti et al., Theorem 4.3](https://arxiv.org/html/2301.13756) establishes efficient learning for finite-agent compact hedonic coalition nets with known formulas. The argument above proves the specified composition-domain result directly, including shared rational coefficients, arbitrary conditional composition distributions, and exact valuation-mismatch loss.
⟨structured verdict parsed — rendered above⟩
The prover resolves the specified task: the learning problem is solvable with polynomial sample size and polynomial running time. The argument is correct, including the strict error requirement and the rational output-size bound. No major or minor mathematical issues were found.
The admissible domain correctly includes every restriction in the task: rational compositions, coordinate bounds determined by the support masses, and positive participation by the sampled type.
The feature representation \(z(t,x)\in\{0,1\}^r\) is valid because the predicates are explicitly known Boolean formulas. The identity \(v_t(x)=z(t,x)\cdot\beta\) respects additive rule contributions, coefficients of either sign, and a shared coefficient vector across all types.
The learner returns a hypothesis of the required form. Realizability ensures that the rational system \(A\widehat\beta=y\) is consistent. Section 4 supplies a concrete deterministic way to select a rational solution, so the initial instruction to return “any rational solution” does not leave an algorithmic gap.
The treatment of \(r=0\) is correct if that case is permitted: every valuation is zero.
The lemma is correct. Sample consistency implies that \(\widehat\beta-\beta\) is orthogonal to each sampled feature vector, hence to their rational span.
All vectors and coefficients involved are rational, so the stated use of \(\operatorname{span}_{\mathbb Q}\) is appropriate. The lemma establishes exact valuation agreement, which is the loss required by the task.
The conversion to the task’s weighted loss is also correct. Under the joint distribution \(P\), the mismatch probability equals the sum of the conditional mismatch probabilities weighted by \(\mu_t\). Consequently, bounding the probability of a feature vector outside the sampled span suffices.
The bound \(|\mathcal W|\leq 2^{r^2}\) is valid.
Every span generated by Boolean vectors has a basis drawn from its generating vectors and of size at most \(r\). Padding that basis with zero vectors gives an ordered tuple of exactly \(r\) Boolean vectors with the same span. There are \(2^{r^2}\) possible tuples.
Distinct tuples may generate the same span; that only makes this upper bound looser. Including spans generated by feature vectors that are unrealizable on the composition domain is also harmless, since this family is used solely for an upper bound and is never enumerated.
For each fixed \(U\), independence gives the stated probability \((1-p(U))^m\) that all sampled features lie in \(U\). When \(p(U)\geq\varepsilon\), this is at most \(e^{-\varepsilon m}\).
The union bound handles the sample-dependent span correctly: whenever \(p(W)\geq\varepsilon\), the realized span \(W\) itself is a member of the fixed finite family and contains every sampled feature.
The explicit constants check out. With the stated choices of \(k\) and \(m\),
\[ 2^{r^2}e^{-\varepsilon m} \leq 2^{r^2-\varepsilon m} \leq 2^{-k-1} \leq \delta/2 <\delta. \]
Here \(e^{-u}\leq 2^{-u}\) holds for every nonnegative \(u\). Thus the proof controls the event \(p(W)\geq\varepsilon\), ensuring loss strictly below \(\varepsilon\) on the complementary event.
The sample size has the claimed polynomial dependence. No minimum type mass is needed because the required loss is the joint, mass-weighted loss.
The evaluation argument is sound. Each explicitly encoded affine atom can be evaluated at the supplied rational composition using exact arithmetic with polynomial bit lengths. The Boolean formula can then be evaluated in time polynomial in its explicit size.
This includes negations and points on inequality boundaries. No feasibility search over compositions is required. Building the feature matrix therefore has the stated polynomial running time.
The construction using independent rows and pivot columns is valid. The selected square matrix \(C\) is invertible, and solving its system while setting the other coefficients to zero satisfies every selected row.
The subsequent argument correctly extends consistency to all sample rows. Realizability ensures that the labels obey the same linear dependencies as the rows, which is essential here.
The denominator-clearing and determinant bounds are correct:
These bounds establish polynomial output bit length. Reduction of the resulting rational fractions cannot increase that length.
The invoked fraction-free elimination applies to the integer matrices described in the proof. Their dimensions and entry lengths are polynomially bounded; their minors also have polynomial bit lengths. This supports the claimed polynomial bit running time for rank computation, pivot selection, and solving the selected system.
The rank-zero case is handled correctly.
The description of the finite-agent result matches [Fioravanti et al., Theorem 4.3](https://arxiv.org/html/2301.13756): it assumes a compact HCN representation with known rule formulas and concludes efficient PAC learnability.
The prover does not use that theorem to justify an unsupported transfer to the composition domain. Its composition-domain result follows from the independent argument audited above.
No repair or additional clarification is necessary. The proof establishes the requested efficient learning algorithm; it need not establish optimal sample complexity.
⟨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.