| paper | Dynamic Proportional Rankings |
| authors | Jonas Israel, Markus Brill |
| venue | IJCAI 2021 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 12
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), a finite support \(T\subseteq 2^C\) of approval types, rational masses \(\mu_t\geq 0\) with \(\sum_{t\in T}\mu_t=1\), a sequence \(X\) of implemented candidates, and a fixed tie-breaking order, define \(H_q=\sum_{j=1}^{q}1/j\) and \(F_\mu(S)=\sum_{t\in T}\mu_tH_{|t\cap S|}\). Compute the complete ranking \(r\) of \(C\setminus X\) such that each \(r_k\) is the tie-broken maximizer of \(F_\mu(X\cup r_{<k}\cup\{c\})-F_\mu(X\cup r_{<k})\) over all remaining candidates.
A high-multiplicity approval electorate in which types \(t\subseteq C\) carry mass \(\mu_t\), candidates and implemented questions remain indivisible, and dynamic seqPAV greedily constructs a discrete ranking from mass-weighted harmonic marginal contributions.
The mirror directly covers Proposition 12 and naturally extends to Proposition 13 by replacing voter sums with mass-weighted sums; it does not establish a continuous formulation for Proposition 16 or the paper's proportionality and experimental results.
The strongest honest case is a continuous mirror of the paper’s dynamic seqPAV computation. I would make this the lead, and deliberately not pretend that the paper contains a hardness result: it does not. Its named computational results are polynomial-time bounds.
The natural regime is a large live Q&A or public-consultation platform. There may be millions of participants, but their relevant information is their approval set over the currently submitted questions. A type is therefore an approval set \(t\subseteq C\), and \(\mu_t\) is the fraction of the audience with that approval set. Topic-oriented audiences, recurring user segments, or organization-wide consultations make \(n\gg\tau\) plausible, where \(n\) is the number of participants and \(\tau\) is the number of distinct approval types. Candidates remain discrete questions; implementing a question remains an indivisible decision \(x_t\in C\). Only the population is continuized.
My lead anchor is Proposition 12, proved in this paper’s appendix rather than cited from elsewhere:
Given an approval profile \(A\) and a sequence \(X\) of implemented candidates, dynamic seqPAV outputs a ranking of all not-yet-implemented candidates in time \(\mathcal{O}(m^3n)\).
The exact continuous question is:
Continuous Dynamic-seqPAV Ranking. An instance consists of a finite candidate set \(C\), a finite support \(T\subseteq 2^C\) of approval types, rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), a sequence \(X\) of already implemented candidates, and a fixed tie-breaking order. Define \(H_q=\sum_{j=1}^q 1/j\) and the population PAV score \(F_\mu(S)=\sum_{t\in T}\mu_t H_{|t\cap S|}\). Compute a ranking \(r=(r_1,\ldots,r_{|C\setminus X|})\) such that, at every position \(k\), \(r_k\) is a tie-broken maximizer of \(F_\mu(X\cup r_{<k}\cup\{c\})-F_\mu(X\cup r_{<k})\) over all remaining candidates \(c\).
A solution is the complete ranking satisfying those greedy marginal inequalities; the first element is the platform’s recommended next question, while a moderator may choose another question from the permitted top \(h\) positions.
This is recognizably the authors’ problem. The harmonic PAV objective is unchanged, the implemented candidates \(X\) still affect every later marginal contribution, and the output is still a ranking intended to preserve proportional exposure over time. The only change is that the sum over individually listed voters becomes a mass-weighted sum over indistinguishable voter types. No outcome is fractional and no voter is targeted at fractional granularity.
The expected classification is Class A. The same greedy algorithm evaluates every marginal contribution by scanning the \(\tau\) supported types, yielding a bound polynomial in \(m\), \(\tau\), and the encoding length \(L\), for example \(O(m^3\tau)\) score operations under a straightforward implementation. When \(n\) is enormous but \(\tau\) is moderate, this is a genuine high-multiplicity representation rather than an algorithm whose cost scales with the population size.
There is also an exact bridge to the discrete problem. If every \(\mu_t\) is rational, choose \(q\) such that \(q\mu_t\) is integral and construct a finite profile with \(q\mu_t\) voters of type \(t\). Then \(F_\mu(S)=\mathrm{tsc}_A(S)/q\), so every marginal comparison, and hence the entire ranking, is identical under the same tie-breaking rule. Conversely, every finite approval profile induces \(\mu_t=n_t/n\). Thus this is not merely an analogy: it is the high-multiplicity version of the paper’s rule, with a two-way dictionary.
The paper’s other algorithmic propositions could be mirrored similarly, but I would not rely on them as separate anchors. Proposition 13 gives the analogous \(O(m^2n)\) computation for myopic seqPAV; its continuous version simply ranks candidates by \(F_\mu(X\cup\{c\})-F_\mu(X)\). Proposition 16 gives an \(O(m^2n^2)\) algorithm for dynamic Phragmén, though its continuous formulation requires more care because voter debts become mass distributions and must be represented by finitely many debt layers. The seqPAV mirror is therefore the cleanest and strongest case.
The main further questions are whether the proportionality guarantee in Theorem 6 transfers verbatim to measurable voter groups under \(\mu\), how rankings behave under small perturbations of \(\mu\) near ties, and whether the ranking can be updated efficiently as candidates are implemented or the population distribution changes.
My weakest point is that Proposition 12 is already polynomial-time in the finite model. This mirror does not demonstrate discrete hardness dissolving in the continuum; it demonstrates exact compression from \(n\) voters to \(\tau\) types. Moreover, if nearly every participant has a distinct approval set, then \(\tau\approx n\) and the advantage disappears. Still, the paper itself is not already a continuous-population model, and the proposed question is faithful, mathematically precise, and natural in a genuinely high-multiplicity audience regime.
The best negative case is that Proposition 12 does not yield a new continuous-computational problem; it yields a weighted-input implementation of the same ranking rule.
For every approval profile, group identical approval sets \(t\) and let \(n_t\) be their multiplicity. Then, for every candidate set \(S\),
\[ \mathrm{tsc}_A(S)=\sum_t n_t H_{|t\cap S|} =n\sum_t \mu_t H_{|t\cap S|}. \]
The factor \(n\) cancels in every marginal comparison. Thus the proposed continuous dynamic-seqPAV algorithm is exactly the finite algorithm after run-length encoding its rows. If the finite profile is given explicitly, constructing that encoding already costs \(O(nm)\); if the masses are given directly, the input is simply a weighted approval profile. Nothing resembling the programme’s characteristic continuous optimization appears: there are no mass-transfer variables, fractional interventions, separation problems, or new feasibility geometry. The output remains an ordinary discrete ranking of questions.
Changing the type space does not repair this. A type can be coarser than an approval set only if the authors’ rule is changed, because future marginal contributions depend on every incidence \(c\in t\), including after arbitrary choices of \(X\). Refining the type by user identity or metadata merely destroys multiplicity without changing the computation. A plausible high-multiplicity Q&A cohort therefore gives a legitimate weighted version, but not a substantive continuous mirror: population mass is only a sufficient statistic already implicit in the paper’s additive score.
Proposition 13 is even more plainly this same phenomenon. Its myopic score is just
\[ \sum_t \mu_t \left(H_{|t\cap X|+\mathbf 1[c\in t]}-H_{|t\cap X|}\right), \]
followed by sorting. The continuous formulation compresses repeated approval ballots but introduces no new computational question.
Proposition 16 is a less clean candidate. A faithful mass version of dynamic Phragmén would need to track debt layers within each approval type, since equal-type voters can acquire different loads during partial payments. That may be a worthwhile implementation exercise, but it weakens rather than strengthens the case: the required state is an endogenous histogram of loads, not simply the proposed society distribution, and any richer formulation would be a co-modified Phragmén process rather than a direct mirror of the paper’s input model. The paper itself supplies only a voter-level runtime bound, not a complexity phenomenon whose continuous analogue would illuminate the ChoCo landscape.
This is not an objection that the continuous answer happens to equal the discrete answer; equality is perfectly acceptable when it is a substantive theorem. Here the equality is immediate from the definition and explains why the population axis contributes no new computation. The difficulty is not that the mirror is false or unnatural. It is that Proposition 12 survives as a valid high-multiplicity reformulation, while failing to be a worthwhile ChoCo case study beyond weighted compression. The universal negative is therefore weak: the proponent has identified a genuine, author-recognisable mirror, but its computational content is considerably thinner than the programme’s intended LP-and-complexity agenda.
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.