Answer: Polynomial-time solvable in \(m,\tau,L\), including exclusion witnesses.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe veto core can be computed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), ranking types \(T\), and rational masses \(\mu_t\) summing to \(1\), compute exactly the candidates \(c\) such that for every \(B\subseteq C\setminus\{c\}\), \(\sum_{t:B\subseteq A_t(c)}\mu_t\leq (|C|-|B|)/|C|\), together with witnesses \(B\) for excluded candidates.
Let \(C\) be a nonempty candidate set with \(m=|C|\). Each type \(t\) is a strict linear order \(\succ_t\) on \(C\); define \(A_t(c)=\{a\in C:a\succ_t c\}\).
A society is given by its support: the list \(T\) of its \(\tau\) distinct types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
Define \(K=\{c\in C:\forall B\subseteq C\setminus\{c\},\ \sum_{t\in T:B\subseteq A_t(c)}\mu_t\leq(m-|B|)/m\}\). Equality does not exclude a candidate.
The computational problem is to output exactly \(K\) and, for every excluded candidate \(c\), a set \(B\subseteq C\setminus\{c\}\) satisfying \(\sum_{t\in T:B\subseteq A_t(c)}\mu_t>(m-|B|)/m\).
Is this exact computation problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For explicitly listed finite voters, the proportional veto core is computable in polynomial time ([Ianovski and Kondratev](https://ojs.aaai.org/index.php/AAAI/article/view/16691)).
The generalized weighted veto core covers exactly this mass-based definition ([Kizilkaya and Kempe](https://arxiv.org/html/2305.19632v2)); its characterization implies polynomial computation with witnesses. This complexity implication is an inference from their result, so the stated target is already settled.
The exact computation problem is solvable in time polynomial in \(m,\tau,L\), including all requested exclusion witnesses.
Treat each listed type \(t\) as one weighted voter with weight \(p(t)=\mu_t\), and give each candidate weight \(q(a)=1/m\). These are probability vectors. For a fixed candidate \(c\) and set \(B\subseteq C\setminus\{c\}\), define
\(H_c(B)=\{t\in T:B\subseteq A_t(c)\}\).
Every coalition unanimously preferring \(B\) to \(c\) is contained in \(H_c(B)\). Consequently, such a coalition has weight exceeding \(1-|B|/m\) exactly when \(H_c(B)\) does. Thus the given definition is precisely the generalized weighted veto core. Its matching characterization appears in [Kizilkaya and Kempe, Theorem 4 and Corollary 5](https://arxiv.org/html/2305.19632v2).
The following direct flow proof establishes the algorithm, witness extraction, and bit-complexity bound.
Fix \(c\in C\). Define
\(D_t(c)=C\setminus A_t(c)\).
Since the rankings are strict linear orders, this consists of \(c\) and the candidates ranked below \(c\). In particular, \(c\in D_t(c)\) for every type.
Construct a directed network with a source \(s\), a sink \(z\), one vertex \(u_t\) per listed type, and one vertex \(v_a\) per candidate. All these vertices are distinct. Its arcs and capacities are:
Let \(F_c\) be the maximum flow value. The total capacity leaving the source is \(1\), so \(F_c\leq 1\).
We prove that \(c\in K\) if and only if \(F_c=1\), and construct the required witness whenever \(F_c<1\).
Write \(\mu(X)=\sum_{t\in X}\mu_t\) for \(X\subseteq T\).
A cut is specified by its source side \(U\), with \(s\in U\) and \(z\notin U\). Let
\(X=\{t:u_t\in U\}\) and \(Y=\{a:v_a\in U\}\).
If no type-to-candidate arc crosses the cut, its capacity is exactly
\(\operatorname{cap}(U)=1-\mu(X)+|Y|/m.\)
Indeed, the crossing arcs are precisely the source arcs to types outside \(X\) and the sink arcs from candidates in \(Y\).
Suppose \(B\subseteq C\setminus\{c\}\) satisfies
\(\mu(H_c(B))>(m-|B|)/m.\)
Choose the cut with \(X=H_c(B)\) and \(Y=C\setminus B\). For every \(t\in X\), we have \(B\subseteq A_t(c)\), hence
\(D_t(c)\subseteq C\setminus B=Y\).
Therefore no type-to-candidate arc crosses this cut. Its capacity is
\(\operatorname{cap}(U)=1-\mu(H_c(B))+(m-|B|)/m<1.\)
Every flow value is bounded by every cut capacity, so \(F_c<1\).
Suppose \(F_c<1\). The max-flow/min-cut theorem applies because the network is finite and all capacities are nonnegative. Obtain a minimum cut \(U\) of capacity \(F_c\), and define \(X,Y\) as above.
No type-to-candidate arc crosses this cut: such an arc alone would contribute capacity \(2>F_c\). It follows that \(D_t(c)\subseteq Y\) for every \(t\in X\), and
\(1-\mu(X)+|Y|/m=F_c<1.\)
Consequently, \(\mu(X)>|Y|/m\). This also implies \(X\neq\varnothing\), because an empty \(X\) has weight zero. Since every \(D_t(c)\) contains \(c\), we obtain \(c\in Y\).
Return \(B=C\setminus Y\). Then \(B\subseteq C\setminus\{c\}\). Moreover, for every \(t\in X\), the containment \(D_t(c)\subseteq Y\) implies \(B\subseteq A_t(c)\). Thus \(X\subseteq H_c(B)\), and
\(\sum_{t:B\subseteq A_t(c)}\mu_t=\mu(H_c(B))\geq\mu(X)>|Y|/m=(m-|B|)/m.\)
This is exactly the requested strict exclusion witness.
Both directions prove \(c\in K\iff F_c=1\). In particular, equality in the defining inequalities does not cause exclusion.
Write each input mass as \(\mu_t=p_t/q_t\), with positive binary integers \(p_t,q_t\). Set
\(Q=m\prod_{t\in T}q_t.\)
Multiply every network capacity by \(Q\). The resulting capacities are the integers \(p_tQ/q_t\), \(2Q\), and \(Q/m\). Their bit lengths are polynomially bounded, because
\(\log_2 Q=\log_2 m+\sum_{t\in T}\log_2 q_t=O(L+\log m).\)
The products and exact divisions required to construct these capacities also take polynomial time.
Each network has \(V=\tau+m+2\) vertices and at most \(E=\tau m+\tau+m\) arcs. Use Edmonds–Karp, whose standard bound is \(O(VE^2)\) arithmetic and graph operations, independently of capacity magnitudes. Starting from zero flow, its augmentations maintain integer flows and residual capacities bounded by \(2Q\). Thus all capacity arithmetic uses \(O(L+\log m)\)-bit integers, and each maximum-flow computation takes polynomial bit time.
After termination, the vertices reachable from \(s\) through positive residual capacity form a minimum cut. To verify this extraction, every original arc leaving that set is saturated, while every original arc entering it carries zero flow; otherwise its reverse residual arc would make its tail reachable. Summing flow conservation over the set therefore identifies its cut capacity with the flow value.
For every \(c\in C\), compute the scaled maximum flow:
There are \(m\) maximum-flow computations, and at most \(m\) witnesses, each containing at most \(m-1\) candidates. The entire computation and output therefore have size and running time polynomial in \(m,\tau,L\). Every comparison is exact.
⟨structured verdict parsed — rendered above⟩
The output resolves the task, with one minor quantifier ambiguity in its introductory explanation. The direct flow argument correctly establishes polynomial-time exact computation of \(K\), including a strict exclusion witness for every excluded candidate. No blocking mathematical issue remains.
The assignment \(p(t)=\mu_t\), \(q(a)=1/m\) satisfies the required probability-vector conditions: the masses are positive and sum to \(1\), and \(m\geq 1\).
For a fixed \(B\), the set \(H_c(B)\) contains exactly the listed types that unanimously rank every element of \(B\) above \(c\). Therefore every eligible coalition is contained in \(H_c(B)\), and its weight cannot exceed \(\mu(H_c(B))\).
There is one wording issue:
“Consequently, such a coalition has weight exceeding \(1-|B|/m\) exactly when \(H_c(B)\) does.”
If “such a coalition” denotes an arbitrary eligible coalition, this is false. For example, take three candidates with two distinct types \(a\succ b\succ c\) and \(b\succ a\succ c\), each of mass \(1/2\), and let \(B=\{a\}\). Then \(H_c(B)\) has mass \(1>2/3\), but either singleton coalition has mass \(1/2\).
The intended existential reading is correct. Severity: minor, because the subsequent direct proof does not rely on the ambiguous assertion.
The bibliographic claim is accurate: Theorem 4 identifies the generalized veto core with dominant candidates, and Corollary 5 identifies membership with admitting the corresponding weighted matching. The assigned weights satisfy their hypotheses. These results are background here; the direct proof establishes the needed equivalence independently. [Kizilkaya and Kempe, Section 3.2](https://arxiv.org/html/2305.19632v2#S3.SS2)
The definition \(D_t(c)=C\setminus A_t(c)\) is correct. Strictness of the rankings ensures that \(D_t(c)\) contains precisely \(c\) and the candidates below it.
All capacities are nonnegative, the network is finite, and the source has total outgoing capacity \(1\). Thus \(F_c\leq 1\). Capacity \(2\) on the middle arcs is sufficient for the later cut argument.
When no middle arc leaves the source side, the only crossing arcs are:
Their total capacity is exactly \(1-\mu(X)+|Y|/m\). No crossing arc is omitted.
For the proposed cut \(X=H_c(B)\), \(Y=C\setminus B\), the implication
\(B\subseteq A_t(c)\Rightarrow D_t(c)\subseteq Y\) is valid.
Consequently, its capacity is \(1-\mu(H_c(B))+(m-|B|)/m<1\). The flow–cut inequality then gives \(F_c<1\). The strict inequality is preserved correctly.
The max-flow/min-cut theorem applies to this finite network with nonnegative finite capacities and yields a cut of capacity \(F_c\).
A middle arc cannot cross that cut: its capacity \(2\) would exceed the entire cut capacity. Therefore \(D_t(c)\subseteq Y\) for every \(t\in X\), and the cut formula gives \(\mu(X)>|Y|/m\).
This entails \(X\neq\varnothing\). Since every \(D_t(c)\) contains \(c\), it also entails \(c\in Y\). Hence the returned \(B=C\setminus Y\) excludes \(c\), as required.
Finally, \(X\subseteq H_c(B)\) and nonnegative masses give
\(\mu(H_c(B))\geq\mu(X)>|Y|/m=(m-|B|)/m\).
This verifies both the witness’s domain and its strict exclusion inequality.
The two directions establish \(c\in K\iff F_c=1\), using the previously established upper bound \(F_c\leq1\).
The boundary cases are covered:
No additional domain assumption is needed.
The scaling factor \(Q=m\prod_tq_t\) is divisible by every denominator and by \(m\), so all scaled capacities are integers.
The estimate \(\log_2Q=O(L+\log m)\) is correct: the denominator bit lengths are included in the input length. Constructing the product and the exact quotients therefore requires polynomial bit time.
The vertex and arc counts are correct. Edmonds–Karp applies to the scaled finite network and has the stated capacity-independent \(O(VE^2)\) operation bound.
The claimed arithmetic-size bound also holds. Each original capacity is at most \(2Q\); feasible arc flows and forward and reverse residual capacities remain bounded by \(2Q\). Thus the graph-operation bound translates into polynomial bit time.
At termination, the sink is not reachable through positive residual capacity. Every original arc leaving the reachable set is saturated, and every original arc entering it carries zero flow. The supplied flow-conservation argument correctly identifies the resulting cut capacity with the flow value.
Running this procedure for each candidate therefore outputs exactly \(K\) and all requested witnesses. Both the number of computations and the output length are polynomial in the stated parameters.
Replace “such a coalition has weight exceeding” with “there exists such a coalition whose weight exceeds.” This removes the arbitrary-versus-existential coalition ambiguity. No change to the flow proof or algorithm is required.
⟨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.