| paper | d4-conf-aaai-2021-0118 |
| 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 \(\mathrm{P}\); an exact feasible completion can also be constructed in polynomial time. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 4
statement extracted from the paper’s text layer
Given alternatives \(A=\{a_1,\ldots,a_m\}\) and a rational distribution \(\mu\) over a support \(\mathcal{P}\subseteq\{0,1,?\}^m\) of partial approval reports, with \(\tau=|\mathcal{P}|\), decide whether every unit of mass can receive a complete ballot extending its report, with the completed population ordered so each alternative’s approving set is a prefix or suffix. Equivalently, decide whether there are ballots \(b_p\in\{0,1\}^m\) extending each \(p\in\mathcal{P}\) and a permutation \(\sigma\) of \(\mathcal{P}\) such that, for every \(a_i\), the sequence \(b_{\sigma(1)}(a_i),\ldots,b_{\sigma(\tau)}(a_i)\) has form \(1^*0^*\) or \(0^*1^*\); assign each type a consecutive interval of length \(\mu_p\).
Use rational masses \(\mu_p\) over the supported partial-report types \(p\in\mathcal{P}\). The decision is whether compatible complete ballots \(b_p\) and an order of the types make every alternative’s approving mass a prefix or suffix of the ordered population. Even if mass may split across ballots, the interval property lets one choose a single compatible ballot per type and place that type in one consecutive block.
A positive result establishes only that the partial reports admit a compatible completion; without a model of how missing entries arise, it says nothing about the electorate’s actual hidden ballots.
fatal: False
Covers the incomplete-profile completion results for VEI (Proposition 4) and SVEI (Proposition 3), with mass distributed over partial reports. It leaves the complete-profile forbidden-pattern characterizations (Propositions 1 and 2), the cited VI hardness result, and the broader PAV/MAV motivation untouched.
The strongest mirror is the paper’s incomplete-profile completion question, made high multiplicity: can a population of partial dichotomous reports be completed so that its voters have the paper’s common ordering structure? I would lead with VEI, which allows each alternative’s supporters to be at either end of the voter order, and use SVEI as a second anchor. The paper has no numbered in-paper hardness result to prefer; its VI-completion NP-completeness statement is cited in the introduction to [11], rather than presented as a numbered result here.
A plausible regime is a large public consultation over a fixed set of candidates, where respondents may leave some approval answers blank. Let \(A=\{a_1,\ldots,a_m\}\). A type \(p\in\{0,1,?\}^m\) records one distinct partial report, including which entries are missing. The input is a support \(P\) of \(\tau\) such types with positive rational masses \(\mu_p\) summing to \(1\). In a large survey, the number \(N\) of respondents can be far greater than \(\tau\): many respondents share the same partial report, and \(\mu_p\) records that type’s share of the population. This fits the paper’s stated reasons for incomplete information—costly reporting or preferences not yet fully formed—and its voter-ordering interpretation has a natural latent-order reading, such as ordering respondents by party loyalty.
My lead question is Continuous VEI-Completion. Given \((A,P,\mu)\), can we assign every unit of mass a complete approval ballot consistent with its partial report, and order the resulting population so that, for each alternative, its supporters form either an initial or a terminal segment? A concrete solution is a completion \(b_p\in\{0,1\}^m\) for each type \(p\), together with an order \(\sigma\) of the support types, such that \(b_p\) agrees with every known entry of \(p\), and each alternative’s bits along \(b_{\sigma(1)},\ldots,b_{\sigma(\tau)}\) have the form \(1^*0^*\) or \(0^*1^*\). Place each type’s mass in a consecutive block of length \(\mu_p\) in that order. Then each support set is a prefix or suffix of the unit interval, up to endpoints.
This block solution does not rule out fractional resolution of a type’s mass: it is sufficient whenever any continuous completion exists. In a feasible completion, the positive-mass complete ballots lie along a common order satisfying VEI. Selecting one compatible complete ballot for each partial type leaves a subset of that ordered structure; grouping each selected type’s mass into a block preserves VEI. Thus the question is about the paper’s completion problem, not a weakened version that forbids a useful fractional split.
The anchor is Proposition 4, proved in this paper: VEI-INCOMPLETE decides in time polynomial in \(m\times n\) whether an incomplete dichotomous profile has a completion satisfying VEI; when one exists, it also finds a suitable voter order and a completion. The continuous problem should be tractable: apply that algorithm to the \(m\times\tau\) matrix with one column per distinct partial type, then give each resulting column its mass. The type order gives the required mass intervals, with rational endpoints obtained from sums of input masses. This yields a bound polynomial in \(m,\tau,L\), where \(L\) is the mass encoding length. A natural next question is whether the same support-based tractability survives when resolving each unknown entry has a type-specific, mass-weighted cost to minimize.
The second question is Continuous SVEI-Completion: given the same input, find completions and an order of the type blocks such that each alternative’s supporters form an initial segment only. Equivalently, the bit strings along the ordered blocks must all have the form \(1^*0^*\). Its anchor is Proposition 3, also proved here: SVEI-INCOMPLETE decides in time polynomial in \(m\times n\) whether an incomplete profile possibly satisfies SVEI and, if so, finds an appropriate voter order that can be completed in polynomial time. The same support-compression argument predicts tractability in \(m,\tau,L\). A follow-up is a mass-weighted repair problem: if not all report types can be retained in one SVEI completion, what is the greatest population mass that can be retained?
These anchors cover only Propositions 3 and 4: possible completion of incomplete profiles into VEI or SVEI. They do not continuize the paper’s outcome space or its discussion of PAV and MAV. Their main limitation is also clear: the mass weights do not change the yes/no feasibility result. The continuous questions are exact high-multiplicity versions, and their tractability comes from compressing many repeated partial reports to \(\tau\) types—not from a new fractional optimization effect. I still think the mirror is credible: the problem’s uncertainty, domain restriction, and common voter order all remain intact, while the population is genuinely represented by rational masses.
Propositions 3 and 4 are genuine computational results, so the “no result to mirror” objection does not apply. The strongest objection is about what the continuous model would mean.
For the proposed VEI and SVEI mirrors, the mass records shares of *partial reports*. But the paper asks whether unknown entries can be filled so that some completion has the required voter order. That is a possibility test about unobserved preferences; it supplies no probability over the missing entries and no reason to treat a chosen completion as the society’s actual preferences. A positive answer therefore cannot certify that the real electorate has the restriction or that aggregation on its actual preferences will be tractable. A more operational question would need additional information—such as a model of the missing answers or a cost for obtaining them—which this paper does not provide.
That concern does not dispose of the exact mirrors. A society over partial-report types can be defined, and the proposed compression to one column per supported report type is sound. In a feasible continuous completion, choose one completed ballot for each positive-mass type. Those chosen ballots still satisfy VEI or SVEI: the restrictions persist when voters are removed. Assigning each type’s whole mass that ballot then gives a block-ordered completion. Conversely, a finite completion can be expanded into blocks with the specified masses. So allowing a type’s mass to split among different completions cannot rescue an infeasible instance. The exact continuous questions are well-posed and faithful to Propositions 3 and 4, though their yes/no answers depend only on support, not on the mass values.
The proposed follow-ups—minimizing mass-weighted imputation cost or retaining the greatest mass in a restricted domain—could make weights matter. They also add an objective absent from the paper. Imputation cost needs a model of what it costs to learn or choose an unknown answer; discarding mass changes a test about whether the whole electorate admits a completion. Neither is forced by the original completion problem.
That is the best negative case I can make: the paper’s epistemic task does not, by itself, turn masses into a useful decision variable. It does not defeat the exact VEI and SVEI mirrors. Treating repeated partial reports as a high-multiplicity population is plausible, and the paper’s propositions apply directly to that regime. Under the programme’s stated standard, I cannot honestly conclude that no worthwhile continuous mirror exists.
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.