Proportional Aggregation of Preferences for Sequential Decision Making

The paper offers faithful continuous-population formulations, especially weighted PAV and fluid Phragmén. However, none of its numbered results asserts complexity or an algorithmic guarantee in the required sense; the relevant complexity claims are external or unnumbered. Thus the paper fails bit (a), despite the mirror being mathematically worthwhile.

The objection that survived

Neither proposed anchor is a numbered computational result in this paper; the PAV hardness and Phragmén polynomial-time claims are cited or stated outside the paper's own qualifying results.

What the mirror covers

The mirror covers the PAV, Sequential Phragmén, and potentially MES rule formulations, but not the impossibility theorems, empirical results, or strategic discussion.

Open questions for a prover

The case FOR (proponent)

I would argue for a genuine mirror, with Weighted-PAV∞ as my lead anchor and Fluid-Sequential-Phragmén∞ as the strongest tractable companion.

There is one qualification. The paper has no numbered theorem literally stating “this problem is in P” or “this problem is NP-hard.” Its explicit PAV hardness claim is in prose and cites Brill et al. (2022, Thm. 5.1). The paper’s own numbered results are nevertheless computationally meaningful: Theorem 4.1 gives an efficiently implementable online rule with a proportionality guarantee, and Theorem 4.5 gives an offline optimization rule with Strong EJR. I would treat the paper as a substantive mirror candidate, while flagging that strict complexity-theorem screening may regard it as borderline.

The natural population model is almost forced by the paper. Let the horizon be \(H\), with alternatives \(C_r\) in round \(r\). A type \(\theta\) is a complete approval trajectory
\[ (A_{\theta,1},\ldots,A_{\theta,H}), \]
and the society is a rational distribution \(\mu\) over finitely many such types. A decision sequence \(D=(d_1,\ldots,d_H)\) still selects one discrete alternative per round; only the voter population is continuous.

For a type \(\theta\), define
\[ u_\theta(D)=|\{r:d_r\in A_{\theta,r}\}|. \]
A coalition is represented by submasses \(q_\theta\leq\mu_\theta\). It has mass \(\sum_\theta q_\theta\), agrees in a set \(K\) of rounds if the types in its support share an approved alternative in every round of \(K\), and is happy in round \(r\) if \(d_r\) is approved by at least one supported type. Thus Strong PJR becomes: if a coalition of mass at least \(\ell/|K|\) agrees in \(K\), it must be happy in at least \(\ell\) rounds. Strong EJR replaces “happy” by requiring some supported type to have utility at least \(\ell\).

The appropriate regime is a large virtual-democracy or policy-coalition population: millions of respondents, party members, country cohorts, or demographic groups, but perhaps only tens or hundreds of stable approval-pattern types. This is especially plausible because the paper itself studies country-level preference models and repeated policy decisions. For rational \(\mu\), multiplying by a common denominator produces an ordinary finite electorate with repeated copies of each type, so this is a genuine high-multiplicity relaxation rather than merely a metaphor.

Lead: Weighted-PAV∞. The anchor is Theorem 4.5, proved in this paper: “PAV and Local-Search PAV satisfy Strong EJR.” The computational hardness attached to the rule is the paper’s explicit statement that PAV optimization is NP-hard, citing Brill et al. (2022, Thm. 5.1), which is cited from elsewhere.

The continuous problem is:

Given \(H\), the sets \(C_r\), the finite type set \(\Theta\), rational masses \(\mu_\theta\), and approval sets \(A_{\theta,r}\), find a decision sequence \(D\) maximizing
\[ \operatorname{PAV}_\infty(D) = \sum_{\theta\in\Theta}\mu_\theta H_{u_\theta(D)}, \]
where \(H_j=1+\frac12+\cdots+\frac1j\) and \(H_0=0\).

A solution is an exact maximizing sequence \(D\), with the associated continuous Strong-EJR guarantee as the fairness property of interest.

This is an exceptionally faithful mirror. If \(\mu_\theta=n_\theta/n\), then multiplying the objective by \(n\) gives exactly the ordinary PAV score of the electorate containing \(n_\theta\) copies of type \(\theta\). The paper’s swapping proof for Strong EJR is based on sums over voters and coalition-size inequalities; those become weighted sums and mass inequalities without changing their substance.

I expect the general exact problem to be Class B: hardness transfers. The sequential model contains the paper’s multi-winner special case, and rational equal-mass profiles recover ordinary PAV instances. Continuization therefore does not make every problem easy; here the combinatorics live in the sequence of alternatives and the committee-like agenda, not in the names of voters. That is precisely the programme’s “hardness-transfer” arm.

The important follow-up questions are whether Weighted-PAV∞ is fixed-parameter tractable in the number of types, whether approximate optimization is polynomial for small \(\tau\), and whether the polynomial-time local-search guarantee claimed in the paper survives arbitrary rational masses and bit-length-sensitive termination bounds.

Strongest Class-A companion: Fluid-Sequential-Phragmén∞. The anchor is Theorem 4.1, proved here: “Sequential Phragmén satisfies Strong PJR.” The paper also states that Sequential Phragmén is polynomial-time computable, citing Lackner and Maly (2023), although that complexity claim is not given as a numbered theorem in this paper.

The continuous rule maintains a load \(x_\theta\) per unit mass of type \(\theta\). For candidate \(c\in C_r\), define its water level by
\[ \lambda_r(c) = \min\left\{\lambda: \sum_{\theta:c\in A_{\theta,r}} \mu_\theta(\lambda-x_\theta)_+ \geq 1 \right\}. \]
The rule chooses an alternative minimizing \(\lambda_r(c)\). It then raises the loads of approving types below that water level to \(\lambda_r(c)\), thereby distributing one unit of load across the continuous population.

The problem is: given the streaming type-mass profile, compute the online decision sequence and load schedule generated by this rule. A valid output must satisfy the continuous Strong-PJR condition defined above for every coalition submass, every \(\ell\), and every agreeing round set \(K\).

I expect this problem to be Class A: tractable. For explicit finite type supports, each round’s water level is found by sorting the current loads of the approving types and scanning the resulting breakpoints. With rational masses, exact rational arithmetic remains polynomial in \(H\), \(\tau\), the number of alternatives, and the encoding length.

The proof of Theorem 4.1 appears to transfer almost verbatim. If a coalition of mass \(s\geq\ell/k\) agrees in \(k\) rounds but is happy fewer than \(\ell\) times, at most \(\ell-1\) units of load can have been assigned to it in those rounds. A commonly approved alternative therefore has water level at most \(\ell/s\). Every bad round assigns load outside the coalition, while each outside unit can receive at most \(\ell/s\) load in those rounds. The resulting upper bound is \(k-\ell\), contradicting the existence of at least \(k-\ell+1\) bad rounds. This is exactly the discrete proof with cardinalities replaced by masses.

This mirror covers the paper’s online result and gives it a computational interpretation that is arguably more natural than the finite version: the rule is balancing proportional load across population mass. It also raises a clean open question corresponding to the paper’s discussion: can any online continuous rule satisfy Strong EJR, rather than merely Strong PJR?

The paper’s MES result, Theorem 4.3, would admit the same kind of semi-online mirror by replacing \(p=n/H\) with \(p=1/H\) and replacing voter sums by mass integrals. I would regard that as supporting evidence, but not add it as a separate anchor because it is structurally similar to Fluid-Sequential-Phragmén∞.

The weakest point is the translation of EJR’s existential individual guarantee. In an atomless population, an individual has zero mass, so “some voter in the coalition” must become “some positive-mass supported type.” That is the correct high-multiplicity translation when types are complete descriptions, but an opponent can fairly argue that it changes the philosophical meaning of EJR. This is why the Phragmén/PJR mirror is my more convincing Class-A case: its guarantee is fundamentally about coalition mass and collective approval, whereas EJR is intrinsically individual-looking.

A second, narrower vulnerability is the regime itself. The mirror is compelling for stable party, country, or demographic cohorts with \(\tau\ll n\), but much less so when every respondent has a genuinely idiosyncratic approval trajectory. That objection attacks the chosen regime, not the mathematical mirror: the paper’s repeated policy and virtual-democracy settings provide credible high-multiplicity scenarios, while the general formulation also correctly exposes what happens when that assumption fails.

The case AGAINST (opponent, writing after the proponent)

On the programme’s own screening rule, this paper should be rejected. Theorem 4.1 and Theorem 4.5 are axiomatic statements: Sequential Phragmén satisfies Strong PJR; PAV and Local-Search PAV satisfy Strong EJR. Theorem 4.3 is of the same kind. The impossibility results in Section 5 concern unsatisfiable fairness requirements. None is a numbered theorem about the complexity of a computational problem.

The paper’s only explicit complexity claim—“PAV optimization is NP-hard”—is an imported result from Brill et al. (2022), not a result established here. Likewise, polynomial computability of Sequential Phragmén is cited rather than proved as a complexity theorem. The proponent therefore promotes an external optimization problem into the paper’s lead anchor and treats axiomatic guarantees as computational results. Under the strict Gate-A criterion, that is decisive.

The proposed Weighted-PAV∞ is nevertheless the strongest possible rescue, and it exposes why the paper itself is a poor source for this programme. For rational masses \(\mu\), clearing denominators creates a finite electorate with repeated copies of each trajectory type. The weighted objective is exactly the ordinary PAV objective up to a constant factor, and the Strong-EJR swapping proof transfers directly. This is a coherent high-multiplicity problem, but it is not a computational question posed or classified by the paper; it is a new weighted-PAV study imported from outside it.

There is also a serious modelling cost. A type must specify an agent’s complete approval trajectory across all rounds and all round-specific alternatives. In the paper’s applications, those trajectories are generally respondent-specific: moral-machine answers vary by issue, future policy questions are not known in advance, and a country-level model is an aggregate predictor rather than a repeated population of identical voters. Grouping people by country, party, or demographic category while discarding their full trajectories changes the PAV objective, because \(H_{U_i}\) depends on the correlation of one person’s approvals across rounds. Keeping the full trajectory preserves the problem but typically creates exponentially many or nearly singleton types. A deliberately constructed fixed party-bloc agenda can avoid this, but then the worthwhile object is weighted approval-based apportionment, not a computational consequence of this paper.

Fluid Sequential Phragmén is a sounder mathematical translation, but it does not repair the screening failure. Replacing voter counts by masses and loads by load densities gives the same water-filling calculation; the Strong-PJR proof can plausibly be rewritten with masses. Yet the resulting task is merely to execute a rule already defined by local water filling and verify its axiom. It is not an optimization, feasibility, bribery, control, campaigning, or robustness problem, and the paper supplies no complexity theorem whose continuous version would be studied.

Moreover, the proponent’s one-load-per-type formulation is not automatically faithful. The finite rule maintains individual loads. If identical approval types acquire different loads through tie-breaking, a type must be represented by a distribution of loads, not a single \(x_\theta\). One can impose a symmetric tie convention and obtain a clean fluid rule, but that is a newly specified rule requiring its own theorem. If one instead insists on an atomless trajectory population, the phrase “at least one member of the coalition approves” is not invariant under null-set changes; replacing it by positive approval mass is a natural repair, but again a redefined axiom.

MES has the same profile: \(p=n/T\) becomes \(1/T\), budgets become budget densities, and the finite proof can likely be cloned. But Theorem 4.3 is again only an axiomatic guarantee, while EJR’s existential individual requirement needs a positive-mass-type reinterpretation. It supplies no independent computational anchor.

The honest limitation of this negative case is that a party-bloc or stable-cohort construction does produce legitimate weighted mirrors, and the PAV version could be an interesting Class-B problem if the programme accepts imported hardness as sufficient. But that would establish the value of a new weighted-PAV project, not the presence of a qualifying computational result in this paper. Under the stated standard, every proposed anchor is either axiomatic, externally imported, or a routine mass-weighted restatement.

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.