Answer: All listed exact winner-determination problems are in \(\mathrm{P}\), including PAV on \(\mathrm{VI}\) supports with unrestricted \(s\).
Theorem 13 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a dichotomous profile P = (v1, . . . , vn) over a candidate set C = {c1, . . . , cm} and a target commit- tee size k, if P satisfies VEI, CEI, WSC or PART, we can find a winning committee under MAV and PAV in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a candidate set \(C\), committee size \(k\), and a rational distribution \(\mu\) over approval types \(A\subseteq C\), with positive-mass types satisfying VEI, CEI, WSC, or PART, compute a size-\(k\) committee maximizing \(\sum_A \mu_A H_{|W\cap A|}\) for PAV or minimizing \(\max_{\mu_A>0}(|W\setminus A|+|A\setminus W|)\) for MAV. A second variant restricts every type to \(|A|\le s\) and requires VI, asking for the corresponding PAV winner.
Definitions. A rational approval society has finite candidate set \(C\), committee size \(k\), and rational masses \(\mu_A\) on approval types \(A\subseteq C\), summing to \(1\); let \(S=\{A:\mu_A>0\}\). A committee \(W\) has PAV score \(\sum_{A\in S}\mu_A H_{|W\cap A|}\), where \(H_0=0\) and \(H_t=\sum_{j=1}^t1/j\), and MAV score \(\max_{A\in S}(|W\setminus A|+|A\setminus W|)\).
A support \(S\) is \(\mathrm{VEI}\) if its types can be ordered so that, for every candidate, approving types form a prefix or suffix; it is \(\mathrm{CEI}\) if candidates can be ordered so every type is a prefix or suffix. It is \(\mathrm{PART}\) if \(S\) is a partition of \(C\). It is \(\mathrm{WSC}\) if its types can be ordered so that, for every \(a,b\in C\), the types approving only \(a\), only \(b\), and either both or neither are intervals, with the last interval between the first two. It is \(\mathrm{VI}\) if types can be ordered so every candidate's approving types form an interval.
Target. Is exact winner determination for these rational-mass problems in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard: PAV and MAV on \(\mathrm{VEI}\), \(\mathrm{CEI}\), \(\mathrm{WSC}\), or \(\mathrm{PART}\) supports; and PAV on \(\mathrm{VI}\) supports with \(|A|\le s\) for every \(A\in S\)?
Known results. For finite unweighted profiles satisfying \(\mathrm{VEI}\), \(\mathrm{CEI}\), \(\mathrm{WSC}\), or \(\mathrm{PART}\), PAV and MAV winner determination is polynomial-time solvable. For finite \(\mathrm{VI}\) profiles with \(|A|\le s\), PAV winner determination is fixed-parameter tractable in \(s\). No result for these exact rational-mass formulations is assumed here.
All the listed problems are polynomial-time solvable, with running time polynomial in the binary encoding length of the masses. For PAV on \(\mathrm{VI}\) supports, this holds even when \(s\) is unrestricted.
| Support restriction | PAV | MAV |
|---|---|---|
| \(\mathrm{VEI}\) | \(\mathrm P\) | \(\mathrm P\) |
| \(\mathrm{CEI}\) | \(\mathrm P\) | \(\mathrm P\) |
| \(\mathrm{WSC}\) | \(\mathrm P\) | \(\mathrm P\) |
| \(\mathrm{PART}\) | \(\mathrm P\) | \(\mathrm P\) |
| \(\mathrm{VI}\), with \(\lvert A\rvert\le s\) | \(\mathrm P\), even for unrestricted \(s\) | Not asked |
The \(\mathrm{VI}\) conclusion uses an additional, precisely stated theorem below. The other arguments are direct or use the unweighted results supplied in the question.
Assume the candidates and positive-mass approval types are explicitly listed. Write \(m=\lvert C\rvert\), \(q=\lvert S\rvert\), and \(\mu_A=p_A/d_A\), with positive integers \(p_A,d_A\) encoded in binary. Assume \(0\le k\le m\); otherwise no feasible committee exists.
Exact rational arithmetic does not cause an exponential running time. Indeed, for \(m\ge1\), let
\(Q=m!\prod_{A\in S}d_A.\)
Every marginal contribution \(\mu_A/j\), for \(1\le j\le m\), becomes an integer after multiplication by \(Q\). Moreover,
\(\log Q=O\!\left(m\log m+\sum_{A\in S}\log d_A\right).\)
Thus scaled committee scores and all arithmetic used below have polynomial bit length. This scaling concerns numerical coefficients; it does not create voters.
Construct an unweighted profile containing exactly one voter with approval set \(A\) for each \(A\in S\). For every committee \(W\), its MAV score in this profile is exactly
\(\max_{A\in S}\bigl(\lvert W\setminus A\rvert+\lvert A\setminus W\rvert\bigr),\)
which is the rational society’s MAV score.
The profile has \(q\) voters. Each promised structural property is preserved: the same type or candidate order witnesses \(\mathrm{VEI}\), \(\mathrm{CEI}\), or \(\mathrm{WSC}\), and a partition support remains a partition profile.
Consequently, the given polynomial-time unweighted MAV algorithms apply to a profile of polynomial size and return an exact rational-society winner. This proves all four MAV classifications.
We prove the stronger statement for any support whose approval sets are intervals in some candidate order. Every \(\mathrm{CEI}\) support has this property because prefixes and suffixes are intervals.
The case \(k=0\) is immediate. Otherwise, introduce variables \(y_c\) for candidates and \(x_{A,j}\) for \(A\in S\), \(1\le j\le k\). Consider the linear program with objective
\(\displaystyle \max \sum_{A\in S}\sum_{j=1}^{k}\frac{\mu_A}{j}x_{A,j},\)
subject to
\(\displaystyle \sum_{c\in C}y_c=k,\)
\(\displaystyle \sum_{j=1}^{k}x_{A,j}-\sum_{c\in A}y_c\le0 \qquad(A\in S),\)
and bounds \(0\le y_c\le1\), \(0\le x_{A,j}\le1\).
Let \(B\) be the approval incidence matrix, with rows indexed by types and columns by candidates. Append an all-ones row, obtaining \(D\). In a witnessing candidate order, every row of \(D\) has consecutive ones.
Here is the relevant total-unimodularity argument. The column form of the Ghouila-Houri criterion states that an integer matrix is totally unimodular if every subset of columns can be signed so that every signed row sum belongs to \(\{-1,0,1\}\). For \(D\), sign any selected columns alternately in their candidate order. Each row meets these columns in a consecutive subsequence, so its signed sum belongs to \(\{-1,0,1\}\). Therefore \(D\) is totally unimodular.
The constraint matrix of the displayed program is obtained from \(D\) by:
All these operations preserve total unimodularity. For unit rows or columns this follows by determinant expansion; an opposite duplicate row either makes a selected determinant zero or reduces to a sign change.
The right-hand sides are integral. Hence every vertex of the feasible polytope is integral. The polytope is nonempty and bounded, so it has an integral optimal vertex, computable by polynomial-time rational linear programming. A witnessing order need not be supplied to the algorithm: its existence establishes integrality of the explicitly constructed program.
At an integral solution, let \(W=\{c:y_c=1\}\). Then \(\lvert W\rvert=k\). For a type \(A\), put \(t=\lvert W\cap A\rvert\). Its constraints permit at most \(t\) of its \(x\)-variables to equal one. Since
\(\mu_A\ge\mu_A/2\ge\cdots\ge\mu_A/k>0,\)
the maximum contribution for this fixed committee is obtained by setting precisely \(x_{A,1},\ldots,x_{A,t}\) to one. That contribution is \(\mu_AH_t\).
Thus optimizing the linear program returns exactly a PAV-winning committee. Its size and coefficient bit lengths are polynomial.
Call two candidates equivalent if they belong to exactly the same approval types.
Lemma. A \(\mathrm{WSC}\) support has at most four candidate equivalence classes.
Proof. Fix a witnessing order \(A_1,\ldots,A_q\). Assign each candidate \(c\) its endpoint signature
\(\sigma(c)=\bigl(\mathbf1_{c\in A_1},\mathbf1_{c\in A_q}\bigr)\in\{0,1\}^2.\)
Suppose \(\sigma(a)=\sigma(b)\). Both endpoint types approve either both candidates or neither. By the \(\mathrm{WSC}\) condition, the types approving both or neither form an interval. Since that interval contains both endpoints, it contains every type. Therefore \(a\) and \(b\) have identical approval incidence throughout the support.
There are only four endpoint signatures, proving the lemma. \(\square\)
Compute the equivalence classes directly from the incidence matrix; no witnessing order is required. Let these classes be \(G_1,\ldots,G_r\), where \(r\le4\), and write \(n_i=\lvert G_i\rvert\).
Enumerate all integer vectors satisfying
\(0\le z_i\le n_i,\qquad \sum_{i=1}^{r}z_i=k.\)
There are at most \((m+1)^4\) vectors. Each approval type contains either all or none of each class. Consequently, every committee selecting \(z_i\) candidates from \(G_i\) has score
\(\displaystyle F(z)=\sum_{A\in S}\mu_AH_{\sum_{i:\,G_i\subseteq A}z_i}.\)
Every committee induces one enumerated vector, and every enumerated vector is realizable. Evaluating all these scores exactly and retaining a maximizing vector therefore returns a PAV winner in polynomial time.
Write the partition as \(S=\{A_1,\ldots,A_q\}\), and put \(n_i=\lvert A_i\rvert\), \(\mu_i=\mu_{A_i}\). A committee is characterized, for scoring purposes, by counts \(t_i=\lvert W\cap A_i\rvert\), satisfying
\(0\le t_i\le n_i,\qquad \sum_i t_i=k.\)
Its score is
\(\displaystyle \sum_i\mu_iH_{t_i}=\sum_i\sum_{j=1}^{t_i}\frac{\mu_i}{j}.\)
For each part, form its marginal list
\(\mu_i,\ \mu_i/2,\ \ldots,\ \mu_i/n_i.\)
There are exactly \(m\) entries altogether. Sort them in nonincreasing order and select the first \(k\).
This selection respects every list’s prefix condition: if \(\mu_i/j\) is selected, each earlier entry of that list is strictly larger and must also be selected. Hence the selected entries define feasible counts \(t_i\).
Any feasible committee selects \(k\) entries from these lists, specifically prefixes. Its sum cannot exceed the sum of the globally largest \(k\) entries. The constructed counts attain that upper bound, proving optimality. Sorting and reconstructing a committee take polynomial time with exact arithmetic.
First handle candidates approved by nobody. Let \(C^+=\bigcup_{A\in S}A\). If \(k\ge\lvert C^+\rvert\), select all of \(C^+\) and fill remaining places arbitrarily; this simultaneously maximizes every type’s contribution. If \(k<\lvert C^+\rvert\), an optimal committee contains no unapproved candidate: replacing one by a missing approved candidate strictly increases the score. Thus unapproved candidates can be deleted in this case.
We now use the following external result.
Generalized Thiele theorem. On a voter-interval profile, an optimal size-\(k\) committee for the objective
\(\displaystyle \sum_v\sum_{j=1}^{\lvert A_v\cap W\rvert}w^v_j\)
is computable in polynomial time when each sequence is nonincreasing, its entries lie in \([0,1]\), and the rational entries through the number of candidates are supplied in binary. This is Theorem 10, with the input conventions of Section 2, of [Manurangsi and Sornat, *Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences*](https://arxiv.org/html/2604.05953v1).
Create one voter per support type and set \(w^A_j=\mu_A/j\). These sequences are nonincreasing, lie in \([0,1]\), and have polynomial total encoding length. The profile is voter-interval by hypothesis, and its generalized objective equals \(\sum_A\mu_AH_{\lvert A\cap W\rvert}\). All theorem hypotheses therefore hold.
This proves polynomial-time rational PAV on unrestricted \(\mathrm{VI}\), hence also under \(\lvert A\rvert\le s\). Finally, every \(\mathrm{VEI}\) support is \(\mathrm{VI}\), because every prefix or suffix is an interval, so the same result applies.
⟨structured verdict parsed — rendered above⟩
Verdict: proved, under the explicitly stated encoding of candidates and positive-mass approval types. All nine requested classifications are established. The external theorem used for VI is correctly stated and applies to the rational weights constructed here. I found no major or minor mathematical issues requiring repair.
The output addresses PAV and MAV on each of VEI, CEI, WSC, and PART, plus PAV on VI with bounded approval-set size. Its stronger claim for unrestricted VI is supported by the cited theorem.
Explicitly listing candidates and support types makes \(m\), \(q\), and the incidence matrix polynomial in the input length. The proof does not claim polynomial time for an unspecified succinct representation.
The scaling factor \(Q=m!\prod_{A\in S}d_A\) has the asserted divisibility: for each relevant \(j\), both \(d_A\mid\prod_{B\in S}d_B\) and \(j\mid m!\). Thus \(Q\mu_A/j\) is integral. The bound on \(\log Q\) is correct, and sums of polynomially many such contributions retain polynomial bit length. No replication proportional to denominator values occurs.
The support is nonempty because its masses sum to one. Infeasible committee sizes are explicitly excluded. When \(m=0\), the only feasible committee is empty; the argument does not require the scaling formula in that case.
Replacing each positive-mass type by one voter preserves every committee’s MAV score exactly: the objective depends on the support, not on the positive masses.
The constructed profile has polynomial size. VEI, CEI, and WSC witnesses remain valid because the approval types are unchanged. PART is also preserved.
Consequently, the supplied unweighted polynomial-time results apply directly. This establishes all four MAV classifications without any unproved weighted extension.
The claimed extension to candidate-interval supports is justified: every prefix and suffix is an interval.
The total-unimodularity argument is correct. For any subset of columns, a row’s selected nonzero columns form a consecutive subsequence of the selected columns. Alternating their signs therefore gives a signed row sum in \(\{-1,0,1\}\). The stated column form of the Ghouila-Houri criterion applies.
Each subsequent matrix operation preserves total unimodularity:
The right-hand side is integral. Feasibility follows from \(0\le k\le m\), and the variable bounds ensure boundedness. The standard integral-polyhedron theorem therefore guarantees an integral optimal vertex. Polynomial-time rational linear programming can obtain such a vertex; the claim is stronger than merely assuming an arbitrary optimal point is integral.
At an integral solution, the cardinality constraint gives a committee of exactly \(k\) candidates. For fixed \(W\), the type constraint allows at most \(|W\cap A|\) auxiliary variables to equal one. Positivity and decreasing coefficients make the stated initial segment optimal, with contribution exactly \(\mu_AH_{|W\cap A|}\).
The formulation has polynomially many variables and constraints, with polynomial coefficient bit lengths. No witnessing order is needed to construct it. The case \(k=0\) is explicitly handled.
The four-class lemma follows from the precise WSC definition in the task. If two candidates have the same endpoint signature, both endpoint types lie in their “both or neither” interval. An interval containing both endpoints contains the whole ordered support. Hence the candidates agree on every type.
This reasoning also covers \(q=1\). It establishes an upper bound of four incidence classes; it need not show that four classes are attainable.
Every type contains either all or none of an incidence class. Therefore the displayed score depends only on the selected class counts. The enumeration covers every feasible committee’s count vector, and every enumerated vector can be realized.
The bound \((m+1)^4\) is valid, and exact score evaluation and committee reconstruction are polynomial. No order-recognition assumption is hidden in this algorithm.
The partition condition ensures that the counts account for all selected candidates and that the marginal lists contain exactly \(m\) entries.
Within each nonempty part, the marginal contributions strictly decrease because its mass is positive. Consequently, selecting globally largest entries cannot include a later entry while excluding an earlier entry from the same part. Ties across different parts do not affect this argument.
Every feasible committee corresponds to \(k\) marginal entries arranged as prefixes. The chosen entries attain the unrestricted upper bound given by the globally largest \(k\) entries and satisfy those prefix constraints. Optimality follows.
Both \(k=0\) and \(k=m\) are covered by the same selection rule. Exact comparisons and reconstruction have polynomial cost.
The preprocessing of unapproved candidates is sound. If all approved candidates fit, including all of them maximizes each type’s contribution. Otherwise, replacing an unapproved selected candidate by a missing approved candidate loses no approvals and strictly increases at least one positive-mass type’s contribution. Deleting unapproved candidates preserves VI.
I verified the external citation. Theorem 10 states polynomial-time solvability of Generalized Thiele on VI profiles. Section 2 permits voter-specific nonincreasing sequences in \([0,1]\), explicitly allows their first entries to differ from one, and specifies binary rational weights through the number of candidates. It also addresses finding a VI ordering. The theorem is therefore not restricted to uniform weights or unary numerical inputs. [Manurangsi and Sornat, Sections 2 and 4](https://arxiv.org/html/2604.05953v1)
The substitution \(w_j^A=\mu_A/j\) satisfies all these hypotheses: the masses lie in \((0,1]\), the sequences decrease, and there are only \(qm\) required entries with polynomial total encoding length. One voter per type gives exactly the claimed PAV objective.
Thus unrestricted VI is covered. The approval-size restriction selects a subclass, and VEI is a subclass of VI. Both requested conclusions follow.
Actionable feedback: No repair is required. The explicit input representation and the precise external theorem citation are essential qualifications and should be retained. The VI and VEI conclusions are established by a verified application of that theorem, rather than by the supplied unweighted results alone.
⟨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.