| paper | d4-conf-ecai-2023-0081 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), and ordered types \(i\in\{1,\ldots,\tau\}\) with approval sets \(A_i\subseteq C\) and positive rational masses \(\mu_i\) summing to \(1\), where each candidate’s approving types form an interval, choose a committee \(W\subseteq C\) of size \(k\) and mass assignments \(x_{i,c}\geq 0\) with \(\sum_{c\in W}x_{i,c}=\mu_i\) and \(\sum_i x_{i,c}=1/k\) for every \(c\in W\), minimizing \(\sum_i\sum_{c\in W}x_{i,c}\mathbf{1}[c\notin A_i]\).
The society is a unit mass over ordered approval-block types; \(x_{i,c}\) assigns type \(i\)'s mass to a selected candidate, each selected candidate represents exactly \(1/k\) of the population, and the objective is total mass assigned to an unapproved candidate.
The mirror covers the sum-misrepresentation variant of Theorem 2. It leaves the maximum variant’s limit dictionary unresolved and does not cover the paper’s CC, linear-preference, or deletion-parameter results.
My lead is a continuous mirror of the paper’s single-crossing approval Monroe result.
Theorem 2 (the full version’s numbering) says: “For SC profiles, \(\app-\Monroe-\summw\) and \(\app-\Monroe-\maxmw\) can be solved in polynomial time.” The paper proves this result here, using a dynamic program. It covers both sum and maximum misrepresentation for approval profiles whose approving voters form an interval in a common voter order. I don’t see a numbered in-paper hardness result for this same problem to anchor instead.
Call the mirror Continuous Single-Crossing Approval Monroe. An instance has candidates \(C\), committee size \(k\), and an ordered list of \(\tau\) contiguous voter blocks. Block \(i\) has approval set \(A_i\subseteq C\) and rational mass \(\mu_i>0\), with \(\sum_i\mu_i=1\). Require that, for each candidate \(c\), the indices \(i\) with \(c\in A_i\) form an interval. The blocks describe a unit-mass population along the single-crossing order; they are the types, with position in that order included in the type description. Adjacent identical blocks can be merged. Since each candidate’s approval region has two endpoints, this representation has at most \(2m+1\) blocks.
A solution chooses \(W\subseteq C\), \(|W|=k\), and masses \(x_{i,c}\geq 0\), where \(x_{i,c}=0\) for \(c\notin W\), such that
\[
\sum_{c\in W}x_{i,c}=\mu_i
\quad\text{and}\quad
\sum_i x_{i,c}=\frac1k\ \text{for each }c\in W.
\]
Thus every unit of population is assigned one committee member, and each member represents exactly \(1/k\) of the population. For the sum variant, minimize
\[
\sum_i\sum_{c\in W}x_{i,c}\,\mathbf{1}[c\notin A_i].
\]
For the maximum variant, minimize the essential maximum of \(\mathbf{1}[c\notin A_i]\) over assignments receiving positive mass. A solution is the committee and its mass assignment, not fractional representation for any individual: the assignment splits a continuum of agents of the same type.
The regime is a large electorate arranged along a one-dimensional policy or geographic order, where each candidate is approved by a contiguous stretch of that population. Many people share each ballot block, so the number of agents can greatly exceed \(\tau\); indeed \(\tau\leq 2m+1\) in this representation. A citywide consultation or large membership vote could fit this pattern if approval regions track contiguous constituencies. Monroe’s equal-representation condition becomes a population share of \(1/k\). That is the natural limit of the paper’s floor-or-ceiling voter quota as population grows, and the approval dissatisfaction and committee-selection question remain theirs. The authors should recognize this as their winner-determination problem under a high-multiplicity population regime.
I expect the sum version to be tractable (Class A). For a fixed committee, the assignment is a linear optimization problem; the interval structure is the reason to look for a polynomial algorithm for choosing the committee as well, perhaps through an interval-flow formulation or a rational-capacity version of the paper’s dynamic program. That is a research prediction, not a consequence of Theorem 2: its voter-indexed dynamic program does not by itself give a polynomial-time bound in the bit length of binary-rational masses. For the maximum variant, I expect a similar result, but its continuous meaning is the essential maximum: any positive mass of unhappy voters makes the value \(1\).
The main further question is whether the continuous optimum agrees with the limit of finite Monroe optima as block proportions converge to \(\mu\), and whether either variant has an algorithm polynomial in \(m,\tau\), and the mass encoding length \(L\). The maximum variant especially needs a support-aware dictionary: an exceptional set whose mass vanishes in the limit can still affect the finite electorate’s maximum dissatisfaction.
The weakest point is that an unordered distribution over approval sets loses the single-crossing order. The mirror therefore has to retain the ordered block structure, including separate positions when the same ballot recurs in disjoint parts of the order. That is a real structural feature of the paper’s domain, but it does not change the object being continuized: the population is still continuous, while the order specifies which continuous societies count as single-crossing. This case covers Theorem 2’s approval Monroe sum and maximum results; it does not claim mirrors for the paper’s CC, linear-preference, or deletion-parameter results.
The strongest objection reaches only the maximum-misrepresentation half of Theorem 2. Its natural continuous objective is an essential maximum, so it ignores exceptions whose mass vanishes. With \(k=1\), suppose almost everyone approves candidate \(a\), but one voter out of \(n\) does not. Every finite election has maximum misrepresentation \(1\); the limiting society can have value \(0\). That makes the maximum variant a poor mirror if the goal is to track limits of finite elections. A support-sensitive version can retain every positive-mass type, but then the answer can change discontinuously as a type’s mass approaches zero.
That objection does not defeat the sum variant. The proposed ordered blocks are complete types: agents in a block have the same approval set and the same position relative to every approval interval. Many agents can share each block, and with \(m\) candidates there are at most \(2m+1\) such blocks. A mass assignment with each selected candidate representing \(1/k\) of society is a natural continuous Monroe model. Dividing a type’s mass among representatives is a standard population-level allocation, and the normalized finite quota converges to that share. A large electorate distributed across ordered constituencies is a plausible setting for the paper’s approval and single-crossing assumptions.
Nor does the dependence on voter order defeat the mirror: an unordered distribution over ballots would lose essential structure, but the ordered-block model retains it. Theorem 2 is a named computational result, and the text supplies no existing continuous computational treatment that would make this a collision. The fact that the paper’s algorithm indexes voters does not show the mass version is uninteresting; whether rational block masses admit an efficient algorithm is precisely a new computational question.
So the maximum variant has a real limit-dictionary problem, but I cannot honestly defeat the sum anchor. The negative case is weak: the continuous single-crossing approval Monroe question remains well posed in a plausible high-multiplicity regime.
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.