| paper | Verifying Proportionality in Temporal Voting |
| authors | Edith Elkind, Svetlana Obraztsova, Jannik Peters, Nicholas Teh |
| venue | AAAI 2025 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.1
statement extracted from the paper’s text layer
Given candidates P, horizon ℓ, rational masses over complete temporal approval types, and an integral outcome o∈P^ℓ, decide whether every submass whose support agrees in all ℓ rounds and has positive demand contains a type receiving positive satisfaction.
A finite list of complete temporal approval trajectories with rational masses; witnesses are submasses bounded by those masses, demand is floor(ℓ times total witness mass), and the decision condition is continuous weak-JR verification for an integral outcome.
The continuous version may add little beyond weighted high-multiplicity bookkeeping, so its methodological novelty is limited; this bounds its contribution but does not invalidate the computational mirror.
fatal: False
The mirrors cover temporal verification hardness, monotone verification algorithms, and the type-aggregated EJR welfare-optimization problem; they leave the remaining parameterized results, GCR analysis, and semi-online impossibility largely untouched.
The paper has a strong continuous mirror, and its best form is not to fractionalize the selected candidates. The candidates remain indivisible, exactly one candidate is selected in each round, and only the population is continuized.
My lead anchor is Theorem 6.2, proved in this paper. It states that, for a monotonic temporal election, verifying any of JR, PJR, or EJR is polynomial-time solvable.
Call the continuous problem Monotone Temporal EJR\(_\infty\)-Verification. An instance consists of:
A type is a complete longitudinal approval trajectory. Thus two voters have the same type only if they approve exactly the same candidates in every round. The mass \(\mu_t\) is the fraction of the electorate with that trajectory.
A possible cohesive group is a submass \(\rho\), with \(0\leq\rho_t\leq\mu_t\). Its support is the set of types with \(\rho_t>0\). Define
\[ \beta(\rho)= \left|\left\{r:\bigcap_{t\in\operatorname{supp}(\rho)} A_{t,r}\neq\varnothing\right\}\right|, \]
\[ \alpha(\rho)=\left\lfloor \beta(\rho)\sum_t\rho_t\right\rfloor, \]
and
\[ \operatorname{sat}_t(o)=|\{r:o_r\in A_{t,r}\}|. \]
The question is whether every submass \(\rho\) has some supported type \(t\) with
\[ \operatorname{sat}_t(o)\geq \alpha(\rho). \]
That is exactly continuous EJR verification. The corresponding JR and PJR versions replace the final condition with the paper’s JR and PJR conditions. There is no welfare objective here: this is deliberately a verification problem, so the adverse decision variable is a cohesive subpopulation.
This is a faithful mirror rather than a new fairness axiom. Clearing denominators in \(\mu\) produces a finite election with identical clones. Conversely, any finite election can be represented by rational type masses. The use of submasses does not create a serious semantic mismatch: for a fixed support, agreement and satisfaction do not change as mass increases, while \(\alpha\) only increases. Therefore any violating submass can be saturated to the full mass of its supported types. The continuous question is consequently equivalent to a weighted high-multiplicity version of the paper’s question.
The natural regime is a large corporation, platform, or public agency selecting one charity, project, or policy per year. Millions of customers, residents, or employees may fall into a few hundred stable longitudinal preference segments. Monotonicity is especially credible when candidates join the pool over time, or when projects become acceptable as they mature. Here \(n\) may be in the millions while the number of temporal types \(\tau\) is in the tens or hundreds. The authors should recognize this as their problem: the approval trajectories, temporal horizon, group-agreement notion, and indivisible outcome are all retained.
I expect this mirror to be Class A. The proof of Theorem 6.2 reduces potential witnesses to structured groups of voters. In a type-mass instance, those groups should become structured cohort masses, computable by summing \(\mu_t\) over types. The main proof obligation is to verify that the paper’s canonical-group argument remains valid with the floor in \(\alpha(\rho)\) and with partial type masses. If it does, the running time should be polynomial in \(m,\ell,\tau\), and the encoding length of the rational masses. The paper’s Theorem 6.1 suggests the same conclusion for weak JR, weak PJR, and weak EJR.
A second, very robust anchor is Theorem 3.1, proved in this paper. It states that verifying w-JR, w-PJR, and w-EJR is coNP-complete; w-JR and w-PJR remain hard with three candidates, and w-EJR with two.
The corresponding problem is Continuous Weak-JR\(_\infty\)-Verification. It has the same type-and-mass input as above, but the witness condition is restricted to groups with \(\beta(\rho)=\ell\). The outcome satisfies w-JR if every such group with \(\alpha(\rho)>0\) contains a type receiving positive satisfaction.
Here the hardness should transfer directly, so this is Class B, not continuum-specific hardness. The proof of Theorem 3.1 already gives the reduction. Given a CLIQUE instance with \(\nu\) vertices and target size \(\kappa\), use three candidates and \(\ell=\nu\) rounds. Give each graph vertex its own temporal approval type from the theorem’s construction, with mass \(1/(\kappa\nu)\), and give the additional \(p_3\)-type mass \((\kappa-1)/\kappa\). Let the outcome select \(p_3\) in every round.
A group of graph types agrees in every round exactly when the corresponding vertices form a clique. Since each graph type has mass \(1/(\kappa\nu)\), such a group has positive demand precisely when it contains at least \(\kappa\) types. Thus the outcome violates continuous w-JR exactly when the graph has a clique of size at least \(\kappa\).
This remains a genuinely high-multiplicity construction: replace every type mass by \(M\) identical clones. Then the population has \(M\kappa\nu\) voters but only at most \(\nu+1\) types, and the answer is unchanged. The combinatorics live in the temporal approval patterns and the three-candidate agenda, not in named voter identities. This is exactly the kind of hardness that should survive continuization.
The third possible anchor is Corollary 7.3, proved in the paper using its Theorem 7.2 and Lenstra’s fixed-dimensional integer-programming result. It gives an FPT algorithm parameterized by the number of voters for finding an EJR outcome subject to individual satisfaction lower bounds while maximizing utilitarian welfare.
Its continuous counterpart is Cohort-EJR Welfare Optimization. The input is a temporal type-mass society, integer satisfaction targets \(\delta_t\) for each positive-mass type, and the same candidate and horizon data. The task is to find an integral outcome \(o\in P^\ell\) such that:
\[ \operatorname{sat}_t(o)\geq\delta_t \]
for every type \(t\), the outcome satisfies continuous EJR, and
\[ \sum_t\mu_t\operatorname{sat}_t(o) \]
is maximized. If a discrete model gives different targets to otherwise identical voters, those target values simply become part of the type definition.
I would expect this to be Class A, fixed-parameter tractable in \(\tau\). The paper’s ILP is already designed to replace voter-level enumeration by a bounded-dimensional formulation. In the continuous version, the relevant coordinates are type-level satisfaction and the finitely many approval patterns induced across types. The natural research task is to make the number of integer variables depend on \(\tau\), rather than on the total population \(n\), while keeping the temporal outcome integral.
This third mirror is more ambitious than the first two, so I would not rely on it alone. Theorem 6.2 is the lead because it offers a plausible polynomial-time continuous result in the paper’s own natural monotone scenario. Theorem 3.1 is the strongest supporting boundary result: it shows that the mirror is not obtained by quietly erasing the paper’s difficulty.
The scope is intentionally limited. I am not claiming a mirror for Proposition 7.4’s semi-online impossibility result, because online revelation and information history are additional computational objects, not merely population multiplicity. Nor am I replacing the outcome sequence by fractional lottery probabilities; that would be outcome-space continuity, which is outside ChoCo’s scope.
The weakest point is that the best Class-A mirror uses the monotonic restriction that the paper itself introduces as a tractable special case. A sceptic could say that this is only a weighted restatement of an already polynomial theorem, and that the general nonmonotone problem gains little from continuization. That criticism has force. The response is that the regime is still meaningful: the same theorem becomes a high-multiplicity algorithm for millions of voters represented by a small number of temporal cohorts, while the companion Theorem 3.1 mirror shows that nonmonotone temporal combinatorics remain hard even when every cohort is heavily replicated.
The main follow-up questions are whether the Theorem 6.2 proof lifts exactly with rational masses, whether continuous JR/PJR/EJR verification is coNP-complete for general explicit type lists, and whether Corollary 7.3 strengthens to FPT in \(\tau\) with weighted welfare. Those are genuine computational questions about continuous populations, not merely observations that the paper already contains time or fractional-looking fairness quantities.
The strongest case against is that the proposed mirrors are mostly weighted reformulations of temporal voting, not new continuous computational objects. In particular, Theorem 6.2 does not obviously require continuous optimization: after replacing voter counts by rational masses, one can enumerate the same canonical cohesive groups, summing masses instead of counting voters. Monotonicity makes this especially easy. The result may be useful as a high-multiplicity compression, but its proof would likely be a routine weighted lift rather than a substantive continuization result.
That objection does not defeat the mirror, however. Temporal approval trajectories are legitimate complete voter types, and the natural cohort story is credible: large populations can contain many repeated longitudinal preference trajectories, especially when candidates enter over time. Rational-clone equivalence is exact. For a fixed support, agreement and satisfaction are unchanged by replacing a partial submass with the whole mass of those types; only the demand increases. The canonical-group argument therefore appears capable of surviving with weighted thresholds and, at worst, a fractional boundary type.
Theorem 3.1 is even harder to dismiss. One might argue that the CLIQUE reduction gives every graph vertex its own trajectory, so the mass is merely decorative and the true combinatorics remain in the trajectory list. But that is not a valid objection under this programme. Replicating every trajectory \(M\) times yields \(M\kappa\nu\) voters and only \(\nu+1\) types, with exactly the same answer. The reduction is therefore a genuine high-multiplicity instance, and the temporal trajectories can be interpreted as stable population cohorts. Its hardness is Class B, precisely one of the programme’s intended outcomes. Calling it “only a weighted restatement” would improperly reject the high-multiplicity regime.
Corollary 7.3 is the least secure anchor, but it also resists a decisive negative argument. Individual satisfaction targets appear identity-sensitive, yet targets can be included in the complete type. Identical trajectories with different targets simply become different types. Since welfare is additive and the outcome remains an integral sequence, aggregation loses no relevant information. The paper’s ILP may plausibly lift to a formulation whose dimension depends on \(\tau\), perhaps through approval signatures over the type set. That is an extension requiring proof, not a malformed mirror.
The only honest negative conclusion is therefore one about priority, not validity: Theorem 6.2 may yield a technically routine weighted theorem, and the FPT lift of Corollary 7.3 is conjectural. But Theorem 3.1 already supplies a faithful, natural, named Class-B mirror, while Theorem 6.2 supplies a plausible Class-A mirror. I cannot honestly defend the universal claim that no worthwhile continuous mirror exists in any scenario. The negative case is weak.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.