| paper | d4-conf-aaai-2018-0404 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-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 in \(m,\tau,k,L\), with running time \((\tau k+L)^{O(1)}\) using axis compression. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given \(m\) candidates on a common axis, a committee size \(k\), and \(\tau\) interval-approval types with positive rational masses \(\mu_t\) summing to \(1\), find a size-\(k\) committee \(W\) maximizing \(\sum_{t=1}^{\tau}\mu_t H_{|W\cap I_t|}\), where \(I_t\) is type \(t\)'s approved interval and \(H_q=\sum_{\ell=1}^{q}1/\ell\).
A rational distribution over interval-approval voter types; the decision is a discrete size-\(k\) committee \(W\), and its objective is population-weighted PAV utility. The paper's TU formulation yields an integral optimal committee, with running time polynomial in \(m\), \(\tau\), and the mass bit length.
The mirror covers the PAV specialization of Theorem 7; it leaves the rest of the α-PAV family, Chamberlin–Courant, broader OWA rules, and the paper's extensions untreated.
The strongest mirror I would defend is mass-weighted PAV on interval approval ballots.
Take \(m\) candidates on a common axis and a support \(T\) of \(\tau\) approval types. Each type \(t\) approves an interval \(I_t\) of the axis and has rational mass \(\mu_t\ge 0\), with \(\sum_t\mu_t=1\). A plausible regime is a large association electing a \(k\)-member representative committee from candidates with platforms on one main issue: many members, but far fewer distinct approval bands. The decision remains a discrete committee \(W\) of size \(k\). Its objective is the population share’s PAV utility, \(\sum_{t\in T}\mu_t H_{|W\cap I_t|}\), where \(H_q=\sum_{\ell=1}^q 1/\ell\). The question is to find a committee maximizing that objective; a solution is the maximizing committee.
My anchor is Theorem 7, proved in this paper. It says that \(\alpha\)-PAV winner determination is polynomial-time solvable when approval preferences are single-peaked, for non-increasing scoring vectors \(\alpha\). Standard PAV is the case \(\alpha_\ell=1/\ell\). The paper proves the result using its integer-program formulation and total unimodularity. The article also reports NP-completeness for unrestricted PAV, citing Aziz et al. (2015), but that is not a numbered result proved here, so it is not my anchor.
For the continuous problem, use variables \(y_c\) for committee membership and \(x_{t,\ell}\) for whether type \(t\) receives at least its \(\ell\)-th approved committee member. The optimization is:
\(\displaystyle \max \sum_{t\in T}\mu_t\sum_{\ell=1}^k \frac{x_{t,\ell}}{\ell} \quad\text{subject to}\quad \sum_{c} y_c=k,\qquad \sum_{\ell=1}^k x_{t,\ell}\le \sum_{c\in I_t}y_c\ \ (t\in T),\qquad 0\le x_{t,\ell},y_c\le 1. \)
For a fixed committee, the best \(x\)-values give type \(t\) exactly \(H_{|W\cap I_t|}\), so this computes the underlying PAV problem, not merely an encoding. Along the axis, the interval rows have consecutive ones; appending the committee-size row and the \(x\)-variable columns preserves total unimodularity. The right-hand sides are integral, so the LP has an integral optimal vertex even though the objective uses rational masses. It therefore returns an actual committee in time polynomial in \(m\), \(\tau\), and the bit length of the masses.
This is a high-multiplicity mirror the authors should recognize: candidates, committee size, ballots, and PAV welfare are unchanged; each voter’s unit contribution is simply aggregated into that ballot type’s mass. A finite profile with \(n_t\) voters of type \(t\) maps to \(\mu_t=n_t/n\), preserving the winning committee. Conversely, rational masses can be expanded using a common denominator, though that electorate may be enormous relative to the encoded input. The expected classification is Class A, by the paper’s consecutive-ones/TU argument.
A natural further question is whether mass-weighted PAV remains tractable when approval sets are arbitrary rather than intervals. The paper’s cited finite PAV hardness transfers to that version because any finite profile gives such a rational mass distribution; this is a boundary question, not another anchor for my case.
The mirror covers the paper’s PAV result on single-peaked approval preferences, not its Chamberlin–Courant or broader OWA results. Its weakest point is that it mostly repackages a tractable finite problem as a weighted, high-multiplicity input: it does not show that continuization dissolves PAV’s unrestricted hardness. That limits the novelty claim, but not the model fit. The continuous population and type masses are exactly the object this programme proposes to study.
The strongest objection is that this mirror adds little new algorithmically. Theorem 7 already gives the key structure: interval approval sets produce a totally unimodular constraint matrix, and the objective coefficients do not affect that property. Replacing each voter’s unit contribution with a rational type mass therefore carries the same LP argument over directly. For a fixed committee, the type masses simply weight the same PAV utilities. The proof needs no new combinatorial insight, and the committee remains a discrete set of candidates.
That makes this a modest result: its main computational gain is handling a compact, high-multiplicity input in time polynomial in the support size and the masses’ bit lengths. But that criticism does not defeat the mirror under the programme’s criteria. The input society really is a distribution over voter types; PAV depends only on those types’ masses; and the interval-type regime is plausible for a large organization choosing a committee from candidates on a shared issue axis. The objective remains nontrivial as the masses vary. Neither voter identity nor a disappearing continuum blocks the model.
I cannot honestly rule out this anchor. Calling it a reweighting of the finite proof is the best negative case, but it is essentially an argument that the answer is immediate. By the stated standard, an easy or already-known answer does not make a well-posed continuous-population question unworthy. The proposed mass-weighted PAV problem survives.
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.