Answer: —
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAssume that there exists β ∈(0, 1/2) such that all competence levels are in [β, 1 −β]. Then for any α ∈ (0, 1 −2β), GREEDYCAP with cap C : N →N such that C(n) ∈ω(1) and C(n) ∈o(√log n) satisfies the PG and DNH properties. The theorem’s rather technical proof is relegated to the full version of the paper. Here we provide a proof sketch.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(\beta,\alpha\), a finite type set \(T\) with \(p_t\in[\beta,1-\beta]\), a mass vector \(\mu\in\Delta(T)\), and a finite network template specifying approved incidences and overlaps, compute the limiting GREEDYCAP mass flow on high-multiplicity realizations with \(C(N)\to\infty\) and \(C(N)=o(\sqrt{\log N})\), and decide whether its limiting correctness probability weakly dominates direct voting for every admissible \(\mu\) and is strictly better for some \(\mu\).
A type \(t\in T\) has competence \(p_t\in[\beta,1-\beta]\), where \(0<\beta<1/2\), and \(0<\alpha<1-2\beta\); a mass vector is \(\mu\in\Delta(T)\).
For each \(N\), a network template yields an approved graph \(G_N\) on \(n_t(N)\) voters of type \(t\), with \(n_t(N)/N\to\mu_t\); an approval \(x\to y\) requires \(p_y>p_x+\alpha\).
Votes are independent and correct with their type competence. GREEDYCAP repeatedly chooses a remaining voter with the most remaining approved in-neighbors, delegates up to \(C(N)-1\) such neighbors to that voter, and removes all selected voters, where \(C(N)\to\infty\) and \(C(N)=o(\sqrt{\log N})\).
Let \(P_{\mathrm{GC}}(\mu)\) and \(P_{\mathrm{D}}(\mu)\) be the resulting limiting correctness probabilities; the required predicate is \(P_{\mathrm{GC}}(\mu)\ge P_{\mathrm{D}}(\mu)\) for every admissible \(\mu\), with strict inequality for some \(\mu\).
Is the continuous GREEDYCAP mass-flow-and-dominance problem solvable in polynomial time, or is it NP-hard?
For finite voter graphs, GREEDYCAP has constant positive gain on some arbitrarily large instances and asymptotically nonnegative worst-case gain under the stated bounds on competences and \(C\).
No result for this exact high-multiplicity type-mass formulation was verified.
The stated premises do not yet define a decision problem to which a polynomial-time or NP-hardness classification can be assigned. In particular, the limiting probabilities need not exist.
Below are rigorous counterexamples and a concentration lemma that narrows the dominance question for any formulation in which the limits do exist. These results do not establish either complexity classification.
Write \(P_{\mathrm D,N}\) and \(P_{\mathrm{GC},N}\) for the finite-population correctness probabilities. We use weighted majority: a representative selected with \(k\) delegators casts a vote of weight \(k+1\). Any convention for an exact majority tie is allowed; the estimates below cover all such conventions.
All constructions have exactly \(N\) voters. GREEDYCAP makes its choices independently of the realized votes. When needed, “up to the cap” means selecting the minimum of the available number of in-neighbors and the cap minus one.
Fix any allowed \(\beta,\alpha\). Take two types with competences \(p_L=\beta\) and \(p_H=1-\beta\), and let every graph be edgeless. Such graphs satisfy the approval restriction vacuously.
For all sufficiently large \(N\), set
\(
n_H(N)=\left\lfloor N/2+(-1)^N N^{3/4}\right\rfloor
\)
and \(n_L(N)=N-n_H(N)\). Choose arbitrary valid counts for the finitely many smaller populations. Both type proportions converge to \(1/2\).
Let \(S_N\) be the number of correct votes, and put \(g=1-2\beta>0\). Independence gives
\(
\mathbb E S_N-N/2=g\bigl(n_H(N)-N/2\bigr)
\)
and
\(
\operatorname{Var}(S_N)=N\beta(1-\beta)\le N/4.
\)
For even \(N\), the expectation exceeds \(N/2\) by at least \(g(N^{3/4}-1)\). Chebyshev’s inequality therefore gives
\(
\Pr(S_N\le N/2)\le
N/\bigl(4g^2(N^{3/4}-1)^2\bigr)\longrightarrow0.
\)
Hence \(P_{\mathrm D,N}\longrightarrow1\) along even populations.
For odd \(N\), the expectation lies below \(N/2\) by at least \(gN^{3/4}\). The same inequality gives
\(
\Pr(S_N\ge N/2)\le N/(4g^2N^{3/2})\longrightarrow0.
\)
Hence \(P_{\mathrm D,N}\longrightarrow0\) along odd populations.
Because the graphs are edgeless, GREEDYCAP leaves every voter with weight one. Consequently \(P_{\mathrm{GC},N}=P_{\mathrm D,N}\) for every \(N\), and neither limiting probability exists.
There is also a failure of determination by mass alone even when limits exist. Replacing \((-1)^N\) by the constant \(1\) gives both limits equal to \(1\); replacing it by the constant \(-1\) gives both limits equal to \(0\). The limiting mass and the edgeless graph rule remain identical.
Thus a critical-mass discretization rule, or additional information beyond limiting mass, is necessary.
Assume finitely many types. Fix any GREEDYCAP execution and let its final blocks be \(B_1,\ldots,B_r\), with representatives \(v_1,\ldots,v_r\) and weights \(w_j=|B_j|\). Then
\(
\sum_jw_j=N
\)
and \(1\le w_j\le C(N)\).
Let \(X_j\) indicate whether representative \(v_j\) votes correctly. The total correct weight is \(W_N=\sum_jw_jX_j\). Distinct representatives have independent votes, so
\(
\operatorname{Var}(W_N)
=\sum_jw_j^2p_{v_j}(1-p_{v_j})
\le\frac14\sum_jw_j^2
\le\frac{NC(N)}4.
\)
Let \(d_N=N-r\) be the number of delegated voters. Every delegated voter \(u\) approves its representative, so \(p_{v_j}>p_u+\alpha\). It follows that
\(
\mathbb E W_N-\sum_up_u
=\sum_j\sum_{u\in B_j\setminus\{v_j\}}(p_{v_j}-p_u)
\ge\alpha d_N.
\)
Define the population-average competence \(m_N=N^{-1}\sum_up_u\). For every fixed \(\varepsilon>0\), if
\(
m_N+\alpha d_N/N\ge1/2+\varepsilon,
\)
then
\(
\Pr(W_N\le N/2)
\le C(N)/(4\varepsilon^2N)\longrightarrow0.
\)
Here the last implication follows from the stated bound on \(C(N)\), which implies \(C(N)/N\longrightarrow0\).
In particular, write \(m(\mu)=\sum_t\mu_tp_t\). Since there are finitely many types, \(m_N\longrightarrow m(\mu)\).
Therefore, any failure of weak dominance among masses with existing limits must lie on the hyperplane \(m(\mu)=1/2\). This conclusion does not establish existence of the GREEDYCAP limit away from that hyperplane.
Use the same two competences, now with \(n_H(N)=\lfloor N/4\rfloor\). The limiting average competence is
\(
m(\mu)=\beta+(1-2\beta)/4=1/4+\beta/2<1/2.
\)
Thus \(P_{\mathrm D,N}\longrightarrow0\).
For even \(N\), use the complete directed bipartite graph from low-type voters to high-type voters. Every edge is approved because \(1-2\beta>\alpha\). For odd \(N\), use an edgeless graph. This is a fixed, explicit template rule permitted by the stated restrictions.
On even populations, let \(c_N=\lfloor C(N)\rfloor\). For sufficiently large \(N\), we have \(c_N\ge2\). While both types remain, each high-type voter has positive in-degree and each low-type voter has zero in-degree. GREEDYCAP therefore selects a high-type representative and delegates \(\min\{c_N-1,\text{remaining low voters}\}\) voters to it.
The number of high-type representatives needed to absorb all low-type voters is
\(
\left\lceil n_L(N)/(c_N-1)\right\rceil=o(N),
\)
whereas \(n_H(N)/N\longrightarrow1/4\). Hence all low-type voters are absorbed before the high-type voters run out. Every final representative consequently has competence \(1-\beta\).
Thus \(\mathbb E W_N=(1-\beta)N\), and the variance bound proves \(P_{\mathrm{GC},N}\longrightarrow1\) along even populations. Along odd populations, the graph is edgeless, so \(P_{\mathrm{GC},N}=P_{\mathrm D,N}\longrightarrow0\).
This counterexample uses ordinary rounding of fixed proportions. A restriction on templates is therefore needed in addition to a discretization rule.
A complexity classification requires a specified class of finitely encoded instances: the template representation, numerical representation, admissible masses, and GREEDYCAP tie-breaking and neighbor-selection rules. The formulation must also guarantee the relevant limits or explicitly replace them with another asymptotic predicate.
The counterexamples establish defects in the present definition. The concentration lemma advances any repaired formulation by localizing possible failures of weak dominance to critical masses. Neither result decides the complexity of a suitably specified continuous mass-flow problem.
⟨structured verdict parsed — rendered above⟩
The output establishes valid obstructions to the stated formulation and a valid concentration lemma. It does not establish polynomial-time solvability or NP-hardness. Its own claim of partial progress is accurate.
No substantive mathematical error was found in the arguments under the conventions explicitly stated by the prover.
The prover uses weighted majority, vote-independent GREEDYCAP choices, and maximal filling of each selected block up to the cap. These conventions are stated explicitly.
The maximal-filling convention matters in Section 4: merely permitting delegation of “up to” the cap does not force the algorithm to absorb the low-type voters. Consequently, that construction establishes nonconvergence under the stated maximal-filling implementation, rather than under every interpretation of the underspecified algorithm. This is sufficient to demonstrate that the premises, without further specification, do not guarantee convergence.
The edgeless construction in Section 2 does not depend on this distinction.
The construction satisfies the stated competence bounds. Edgeless graphs satisfy the approval restriction because there are no edges to check.
The counts are valid for all sufficiently large \(N\), and the permitted arbitrary choices for smaller \(N\) do not affect any limit. Since \(N^{3/4}/N\to0\), both type proportions converge to \(1/2\).
The expectation identity
\[
\mathbb E S_N-N/2=(1-2\beta)(n_H(N)-N/2)
\]
is correct. Both types have vote variance \(\beta(1-\beta)\), so the displayed variance identity is also correct.
The floor estimates have the correct directions:
Both Chebyshev bounds tend to zero. They establish opposite correctness limits on the two parity subsequences. Exact-majority tie conventions do not affect these conclusions.
In an edgeless graph, every representative has weight one, so the equality of GREEDYCAP and direct-voting correctness probabilities holds at every population size.
The two constant-sign variants likewise establish different existing limits at the same limiting mass. Thus limiting mass alone does not determine correctness under the permitted population sequences.
Finding: Correct. This independently defeats the unconditional existence and mass-only determination of the probabilities used in the target predicate.
For a fixed execution, the final blocks partition the voters, their weights sum to \(N\), and each weight is at most \(C(N)\). Representatives are distinct. Because the execution does not depend on realized votes, their vote indicators retain the independence and competence probabilities used in the calculation.
The variance bound follows correctly from \(w_j^2\le C(N)w_j\).
The expectation-gain identity counts each delegated voter exactly once. Every such voter approves its representative, so its competence improvement exceeds \(\alpha\). The weaker aggregate bound \(\alpha d_N\) is valid, including when \(d_N=0\).
The stated margin condition places the expectation at least \(\varepsilon N\) above the majority threshold. Chebyshev therefore gives the claimed bound. The assumption on \(C(N)\) indeed implies \(C(N)/N\to0\).
Finiteness of the type set is explicitly assumed here and justifies convergence of the population-average competence. The two off-critical conclusions follow:
The localization statement is properly restricted to masses where the limits exist. It establishes neither a strict-dominance witness nor convergence below the critical hyperplane.
Finding: Correct within its explicitly stated finite-type scope.
The limiting average competence is correctly calculated and is strictly below \(1/2\). Every low-to-high edge satisfies the approval condition.
On even populations, while both types remain, only high-type voters have positive approved in-degree. Thus GREEDYCAP selects a high-type representative. Under the stated maximal-filling convention, the number needed to absorb all low-type voters is the displayed ceiling.
Since \(c_N\to\infty\), that number is \(o(N)\), whereas the available high-type population is asymptotic to \(N/4\). Hence enough high-type representatives exist for complete absorption.
All final representatives then have competence \(1-\beta\). The expectation and concentration argument yield correctness tending to one on even populations. The edgeless odd populations yield correctness tending to zero.
Finding: Correct under the explicitly stated implementation. The parity-dependent rule is not excluded by any explicit restriction in the supplied task.
The output correctly identifies why the supplied premises do not support the requested complexity classification. It does not classify any formally specified continuous decision problem.
To make a subsequent classification claim verifiable, the problem must specify its finite inputs and encoding, permissible templates, admissible masses, population discretization, and algorithmic selection rules. It must also specify whether limit existence is promised, proved from restrictions, or replaced by another predicate.
A subsequent prover must then address both universal weak dominance and the existence of a strict-dominance witness, and provide an algorithm with a complexity analysis or a valid hardness reduction. Those are outstanding tasks, not consequences of the present concentration lemma.
⟨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.