Answer: Polynomial-time solvable by a proper realizable PAC learner with all the stated bit-complexity bounds.
Theorem 3.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor all n, m ∈N, the class Sn m is effi- ciently PAC-learnable.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For \(m\) candidates, let each society \(\mu\) be a rational distribution with support size at most \(\tau\) over complete rankings, encoded with at most \(L\) bits. Given \(m,\epsilon,\delta\) and i.i.d. labeled examples \((\mu^i,y_i)\) from an unknown distribution \(D\) over such societies, promised that all labels are winners under one unknown scoring vector \(\alpha^\star\), can an algorithm output a polynomial-size rational scoring vector \(\hat{\alpha}\) such that \(\Pr_{\mu\sim D}[f_{\hat{\alpha}}(\mu)\ne f_{\alpha^\star}(\mu)]\le\epsilon\) with probability at least \(1-\delta\), using sample size and running time polynomial in \(m,\tau,L,1/\epsilon,\log(1/\delta)\)? Define each candidate’s score by \(\sum_t\mu_t\alpha_{\operatorname{rank}_t(c)}\); resolve score ties by lexicographically comparing the mass ranking each candidate in first, second, and subsequent places, then use a fixed candidate order.
Let \(m\ge 1\) candidates have a fixed order. A society \(\mu\) is given by its support: a list of distinct strict complete rankings, each with positive binary-rational mass, with masses summing to \(1\). Write \(\tau(\mu)\) for its support size; inputs satisfy \(\tau(\mu)\le\tau\) and have total encoding length at most \(L\). Thus \(\tau\) bounds listed support size, not the number \(m!\) of possible rankings.
A scoring vector is any \(\alpha\in\mathbb R^m\) satisfying \(\alpha_1\ge\cdots\ge\alpha_m\); negative entries and constant vectors are allowed, with no normalization. Define \(p_\ell(c,\mu)=\sum_{t:\operatorname{rank}_t(c)=\ell}\mu_t\) and \(s_\alpha(c,\mu)=\sum_{\ell=1}^m p_\ell(c,\mu)\alpha_\ell\). The winner \(f_\alpha(\mu)\) maximizes this score; among tied candidates, maximize \((p_1(c,\mu),\ldots,p_m(c,\mu))\) lexicographically, then take the earliest candidate in the fixed order.
For rational \(\epsilon,\delta\in(0,1)\), a learner receives independent examples \((\mu^i,f_{\alpha^\star}(\mu^i))\), where \(D\) is an arbitrary unknown distribution over admissible societies and \(\alpha^\star\) is one unknown real scoring vector. It must output a rational scoring vector \(\hat\alpha\) of polynomial encoding length such that, with probability at least \(1-\delta\), \(\Pr_{\mu\sim D}[f_{\hat\alpha}(\mu)\ne f_{\alpha^\star}(\mu)]\le\epsilon\).
Is this proper realizable PAC-learning problem solvable with sample size, output length, and running time polynomial in \(m,\tau,L,1/\epsilon,\log(1/\delta)\) and the encoding lengths of \(\epsilon,\delta\), or is it NP-hard?
For explicit profiles of \(n\) voters, scoring rules with this tie-breaking convention are efficiently properly PAC-learnable in polynomial time in the profile representation and learning parameters ([verified discrete result](https://procaccia.info/wp-content/uploads/2020/03/learn.pdf)).
No result settling exactly the rational-mass problem with the stated bit-complexity bounds was identified in the literature search.
The problem is solvable by a proper realizable PAC learner with polynomial sample size, output length, and running time under the stated bit-complexity bounds.
The learner constructs and solves a rational linear program. The main additional argument is that, on the domain of societies with encoding length at most \(L\), every real scoring rule has an equivalent integer scoring vector of polynomial encoding length. This yields a finite-class PAC bound without enumerating societies or scoring vectors.
The consistency construction follows the approach for explicit voter profiles in [Procaccia et al., *The learnability of voting rules*](https://procaccia.info/wp-content/uploads/2020/03/learn.pdf). The proof below supplies the rational-mass and encoding-length arguments.
For \(m=1\), the sole candidate always wins, so the learner can output \((0)\) without examples. Henceforth assume \(m\ge 2\), and set \(d=m-1\).
For a scoring vector \(\alpha\), define its gaps by
\(x_j=\alpha_j-\alpha_{j+1}\), for \(1\le j\le d\).
Monotonicity is equivalent to \(x_j\ge 0\). Each candidate’s position probabilities sum to \(1\), so subtracting \(\alpha_m\) from every coordinate subtracts the same quantity from every candidate’s score. It therefore preserves the winner, including tie-breaking.
Consequently, every allowed scoring rule has an equivalent representation
\(\alpha_m=0,\qquad \alpha_\ell=\sum_{j=\ell}^{d}x_j\quad(1\le\ell\le d),\qquad x\in\mathbb R_{\ge 0}^{d}.\)
This representation includes constant scoring vectors: they correspond to \(x=0\).
For a society \(\mu\), write \(c\succ_\mu w\) when candidate \(c\) defeats candidate \(w\) under the prescribed tie-break: first compare their position-probability vectors lexicographically, then use the fixed candidate order. This defines a strict total order on candidates, independently of \(x\).
Define cumulative position probabilities by
\(P_j(c,\mu)=\sum_{\ell=1}^{j}p_\ell(c,\mu).\)
Expanding the scores in gap coordinates gives
\(s_\alpha(w,\mu)-s_\alpha(c,\mu)=\sum_{j=1}^{d}\bigl(P_j(w,\mu)-P_j(c,\mu)\bigr)x_j.\)
Therefore, \(w\) is the winner exactly when, for every \(c\ne w\),
Necessity follows because \(w\) must have maximal score and must defeat every other maximal-score candidate in the tie-break. Conversely, these conditions give precisely those two properties, so they suffice.
Write the listed masses of a society as \(\mu_t=u_t/v_t\), using positive integer numerators and denominators in binary, and put
\(Q_\mu=\prod_{t=1}^{\tau(\mu)}v_t.\)
Under the stated binary rational encoding, the total number of bits used for these denominators is at most \(L\). Thus
\(1\le Q_\mu\le 2^L.\)
For candidates \(w,c\), define the integer coefficient vector
\(a_j(\mu,w,c)=Q_\mu\bigl(P_j(w,\mu)-P_j(c,\mu)\bigr),\qquad 1\le j\le d.\)
Its coordinates are integers because \(Q_\mu\) clears every listed mass denominator. Since cumulative probabilities lie in \([0,1]\),
\(\lvert a_j(\mu,w,c)\rvert\le Q_\mu\le 2^L.\)
These coefficients can be computed directly from the listed rankings and masses using polynomial-time integer arithmetic. No enumeration of the \(m!\) possible rankings is involved.
Because \(Q_\mu>0\), the winner conditions become \(a(\mu,w,c)\cdot x>0\) or \(a(\mu,w,c)\cdot x\ge 0\), respectively.
Lemma. Let \(d\ge 1\) and \(B\ge 1\) be integers. Consider any finite feasible system
\(x\ge 0,\qquad a_r\cdot x\ge b_r,\)
where all \(a_r\) are integer vectors with coordinate magnitudes at most \(B\), and each \(b_r\) belongs to \(\{0,1\}\). Then the system has an integer solution \(z\) satisfying
\(0\le z_j\le d!B^d\qquad(1\le j\le d).\)
Proof. Let \(P\) be its feasible polyhedron and choose \(x^0\in P\). Minimize \(\sum_jx_j\) over \(P\). This minimum exists: any improving point lies in the closed, bounded set
\(P\cap\{x:\sum_jx_j\le\sum_jx_j^0\},\)
which is compact because \(x\ge 0\).
The minimizing set is also compact. Within it, successively minimize \(x_1,x_2,\ldots,x_d\), obtaining a unique point \(v\).
This point is a vertex of \(P\). Indeed, if \(v=(u+w)/2\) for \(u,w\in P\), optimality of the sum first forces both points to minimize that sum. Optimality of \(x_1\) then forces their first coordinates to equal \(v_1\). Repeating this argument coordinate by coordinate gives \(u=w=v\).
At a vertex, the active constraint normals span \(\mathbb R^d\). Otherwise, a nonzero vector orthogonal to all active normals would permit sufficiently small perturbations in both directions while retaining every constraint, contradicting the vertex property.
Choose \(d\) linearly independent active constraints and write them as
\(Mv=b.\)
Here \(M\) is an integer matrix with entries of magnitude at most \(B\); this also covers active nonnegativity constraints. Its determinant is a nonzero integer, and \(b\) has entries in \(\{0,1\}\).
By Cramer’s rule, \(v_j=\det(M_j)/\det(M)\), where \(M_j\) replaces column \(j\) by \(b\). The determinant expansion gives
\(\lvert\det(M)\rvert\le d!B^d,\qquad \lvert\det(M_j)\rvert\le d!B^{d-1}.\)
Set \(z=\lvert\det(M)\rvert v\). Its coordinates are nonnegative integers bounded by \(d!B^d\). Moreover,
\(a_r\cdot z\ge\lvert\det(M)\rvert b_r\ge b_r,\)
because \(\lvert\det(M)\rvert\ge 1\). Thus \(z\) is feasible. \(\square\)
Let \(\mathcal X\) be the domain of admissible societies: support size at most \(\tau\) and encoding length at most \(L\). This domain is finite because there are finitely many binary encodings of length at most \(L\).
Fix any real scoring rule, represented by gaps \(x^\star\ge 0\). Conceptually write the winner constraints from Section 2 for every society in \(\mathcal X\), using that rule’s winner as the designated winner.
All strict constraints have positive value at \(x^\star\). If there are any, finiteness implies that
\(\eta=\min\{a_r\cdot x^\star:\text{the constraint }r\text{ is strict}\}>0.\)
Hence \(x^\star/\eta\) satisfies the system obtained by replacing every strict constraint with \(a_r\cdot x\ge 1\), while retaining every weak constraint as \(a_r\cdot x\ge 0\). If there are no strict constraints, the corresponding system is already feasible.
Apply the lemma with \(B=2^L\). Define
\(K=d!\,2^{dL}.\)
There exists an integer gap vector \(z\in\{0,\ldots,K\}^{d}\) satisfying all these constraints. Constraints with right-hand side \(1\) ensure strictly positive score differences, and constraints with right-hand side \(0\) ensure the required weak differences. Section 1 therefore shows that \(z\) induces exactly the original winner function on all of \(\mathcal X\).
Its scoring vector has coordinates
\(\beta_m=0,\qquad \beta_\ell=\sum_{j=\ell}^{d}z_j,\)
so every coordinate is an integer between \(0\) and \(dK\). Its total encoding length is
\(O\bigl(m^2(L+\log m)\bigr).\)
In particular, the number of distinct winner functions on \(\mathcal X\) is at most
\((K+1)^d.\)
The potentially very large system in this argument is used only to prove existence and count functions. The learner never constructs it.
Take \(N\) independent labeled examples \((\mu^i,w_i)\). For every \(i\) and every \(c\ne w_i\), compute the coefficient vector from Section 2 and set
\(b_{i,c}=1\) if \(c\succ_{\mu^i}w_i\), and \(b_{i,c}=0\) otherwise.
Solve the linear feasibility problem
\(x_j\ge 0\quad(1\le j\le d),\qquad a(\mu^i,w_i,c)\cdot x\ge b_{i,c}\quad(i,c\ne w_i).\)
Realizability guarantees feasibility: apply the finite minimum-and-scaling argument from Section 4 to the sample’s strict constraints.
Use the standard exact rational linear-programming theorem: a finite rational linear feasibility problem can be solved in time polynomial in its total binary encoding length, returning a rational feasible point of polynomial encoding length when feasible. This theorem concerns binary arithmetic, including feasible sets of lower dimension; see [MIT’s notes on polynomial-time linear programming](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html).
Here its hypotheses hold explicitly:
Thus both solving the program and encoding its returned rational point require polynomial resources in \(N,m,L\). Computing the coefficients and tie orders takes time polynomial in \(N,m,\tau,L\).
For a returned feasible point \(\hat x\), output
\(\hat\alpha_m=0,\qquad \hat\alpha_\ell=\sum_{j=\ell}^{d}\hat x_j.\)
This is a rational, nonincreasing scoring vector of polynomial encoding length. By the exact winner characterization, it agrees with every sample label. The learner is therefore proper and consistent.
Let \(\mathcal H\) be the finite collection of winner functions induced by integer gaps in \(\{0,\ldots,K\}^{d}\). Section 4 proves that every allowed scoring rule—including the learner’s output—is equivalent on \(\mathcal X\) to a member of \(\mathcal H\), and that
\(\lvert\mathcal H\rvert\le(K+1)^d.\)
For any fixed \(h\in\mathcal H\) whose error against the target exceeds \(\epsilon\), independence implies that its probability of agreeing with all \(N\) sample labels is at most
\((1-\epsilon)^N\le e^{-\epsilon N}.\)
If the learner outputs a rule with error greater than \(\epsilon\), some such bad member of \(\mathcal H\) must agree with the entire sample. A union bound therefore gives
\(\Pr[\text{output error}>\epsilon]\le(K+1)^d e^{-\epsilon N}.\)
It suffices to take
\(N\ge\bigl(d\ln(K+1)+\ln(1/\delta)\bigr)/\epsilon.\)
Since \(\ln K=\ln(d!)+dL\ln 2\), this is
\(N=O\!\left(\dfrac{m^2(L+\log m)+\log(1/\delta)+1}{\epsilon}\right).\)
To compute a sufficient sample size using only integer and rational arithmetic, set
\(S=d\bigl(1+d\lceil\log_2(\max\{2,d\})\rceil+dL\bigr),\qquad r=\lceil\log_2(1/\delta)\rceil,\)
and take \(N=\lceil(S+r)/\epsilon\rceil\). Indeed, \(\log_2\lvert\mathcal H\rvert\le S\) and \(\ln(1/\delta)\le r\), so the preceding failure bound is at most \(\delta\). These integers are computable in polynomial time from the encodings of the parameters.
Combining this sample bound with Section 5 proves all requested polynomial bounds: sample size, rational output length, and running time are polynomial in \(m,\tau,L,1/\epsilon,\log(1/\delta)\) and the encoding lengths of \(\epsilon,\delta\). No bound on the target vector’s numerical precision is required.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is established. The argument gives a proper realizable PAC learner with the requested polynomial bounds for the rational-mass representation. I found no major or minor mathematical issues.
The reduction to \(d=m-1\) nonnegative gaps is correct. Since every candidate’s position probabilities sum to \(1\), subtracting \(\alpha_m\) from all scoring coordinates changes all candidate scores by the same amount. It preserves both score comparisons and ties. Negative scoring entries therefore cause no difficulty, and constant vectors are correctly represented by \(x=0\).
The expansion
\[
s_\alpha(w,\mu)-s_\alpha(c,\mu)
=\sum_{j=1}^{d}\bigl(P_j(w,\mu)-P_j(c,\mu)\bigr)x_j
\]
is correct: the coefficient of \(x_j\) in a candidate’s score is the sum of its position probabilities through position \(j\).
The tie-break defines a strict total order independently of the scoring vector, including when two candidates have identical position-probability vectors. The directions of the strict and weak inequalities are correct:
These pairwise conditions are necessary and sufficient for \(w\) to win. No assumptions about unique score maximizers are introduced.
The case \(m=1\) is explicitly and correctly handled.
The product \(Q_\mu\) clears every listed mass denominator and consequently every cumulative probability difference. Reduction of the individual fractions is unnecessary.
The bound \(Q_\mu\le 2^L\) follows from the total denominator bit length being at most \(L\). Since each cumulative probability lies in \([0,1]\), the cleared integer coefficients satisfy
\[
|a_j(\mu,w,c)|\le Q_\mu\le 2^L.
\]
Multiplication by \(Q_\mu>0\) preserves both strict and weak inequality directions.
The arithmetic claims are valid for the listed-support representation. Products, sums, and exact comparisons involve integers with polynomial bit length. The construction requires processing only listed rankings; it does not depend on enumerating possible rankings or expanding masses into individual voters.
The lemma is correct, including for unbounded or lower-dimensional feasible polyhedra.
The compactness argument establishes that the minimum of the coordinate sum is attained. Nonnegativity bounds every coordinate in the relevant sublevel set. Successive coordinate minimization takes place within compact minimizing sets and determines a unique point.
The midpoint argument correctly proves that this point is a vertex. Equality in each successive minimum forces both endpoints to share the selected coordinates.
The claim that active normals span the full ambient space is justified. With finitely many constraints, a direction orthogonal to all active normals admits sufficiently small perturbations in both directions that preserve every inactive inequality. This would contradict the vertex property.
The selected active system has integer coefficients bounded by \(B\), including nonnegativity constraints because \(B\ge1\). Its right-hand sides belong to \(\{0,1\}\).
Both determinant estimates are correct:
\[
|\det(M)|\le d!B^d,
\qquad
|\det(M_j)|\le d!B^{d-1}.
\]
In the second estimate, each determinant term contains one entry from the replacement column, whose magnitude is at most \(1\).
Multiplication by \(|\det(M)|\) produces integer coordinates even when \(\det(M)<0\). Nonnegativity is preserved, and the resulting coordinate bound is at least as strong as the stated bound.
Finally, scaling preserves feasibility because the right-hand sides are nonnegative and \(|\det(M)|\ge1\). This is the relevant hypothesis for that step, and it is explicitly satisfied.
The admissible domain is finite under the stated total encoding-length bound. Its potentially enormous size does not invalidate the existence argument.
For a fixed target rule, all designated strict winner constraints have positive value at its gap vector. Their finite minimum is therefore positive whenever strict constraints exist. Scaling by its reciprocal gives the asserted right-hand sides of \(1\), while preserving the weak constraints and nonnegativity.
The no-strict-constraints case is handled separately and remains feasible.
Applying the lemma with \(B=2^L\) is valid. The resulting integer gaps preserve every designated winner on the whole admissible domain. The argument requires preservation of winners, which the established inequalities provide; it does not rely on preserving all pairwise score signs.
The coordinate bound \(dK\), total encoding-length bound \(O(m^2(L+\log m))\), and function-count bound \((K+1)^d\) are correct. Counting multiple representations of the same winner function merely overcounts and is harmless.
The prover correctly distinguishes this conceptual global constraint system from the system actually constructed by the learner.
Realizability ensures feasibility of the sample LP by the same finite scaling argument. No numerical bound on the real target’s coordinates or margins is required.
The invoked theorem is the standard exact rational LP feasibility theorem: rational systems admit polynomial-time feasibility testing and, when feasible, a rational feasible output of polynomial encoding length. The cited [MIT notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) discuss polynomial-time LP algorithms, bit precision, and lower-dimensional feasibility.
The hypotheses are satisfied as written: the learner constructs finitely many explicitly encoded integer inequalities, with polynomially many variables and constraints and polynomial coefficient bit length. Neither boundedness nor nonempty interior is assumed.
Recovering scoring coordinates by summing rational gaps preserves polynomial encoding length. The resulting vector is nonincreasing and agrees exactly with every sample label. Properness and consistency are therefore established.
The finite-class argument applies to the learner’s output even though that output need not itself have bounded integer gaps. Section 4 supplies an equivalent member of the fixed finite class on the entire admissible domain.
For each fixed function with error greater than \(\epsilon\), independence gives the stated upper bound on sample consistency. The union bound therefore controls the event that any bad consistent function exists, which includes every possible bad output of the learner.
The logarithmic class-size calculation and resulting sample bound are correct.
The integer-computable choice of sample size is also sufficient. The stated \(S\) bounds \(\log_2|\mathcal H|\), hence also \(\ln|\mathcal H|\); similarly, \(r\) bounds \(\ln(1/\delta)\). These bounds hold for \(d=1\) as well. Computing the ceilings and rational division requires polynomial time in the parameter encodings.
Substituting this sample size into the LP resource bounds establishes all requested dependencies.
No repair or additional clarification is needed. The proof resolves the stated rational-mass learning problem under its encoding-length bound.
⟨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.