| paper | d4-conf-atal-2017-0025 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 5
statement extracted from the paper’s text layer
Given \(C\), \(k\), \(\epsilon\), and a one-pass stream of binary-rational records \((A_i,w_i)\) with approval types \(A_i\subseteq C\) and total mass \(1\), what is the minimum space for a randomized algorithm that outputs, with high probability, a size-\(k\) committee \(S\) that wins in some society \(\nu\) satisfying \(\tfrac12\lVert\mu-\nu\rVert_1\le\epsilon\)? Here \(S\) wins when it maximizes its continuous Monroe score, defined by assigning each type’s mass to committee members with each member receiving exactly \(1/k\) mass.
The society is a distribution \(\mu\) over approval types \(A\subseteq C\), supplied as a one-pass stream of rational mass records. For a size-\(k\) committee \(S\), its continuous Monroe score is \(V_\mu(S)=\max_x\sum_{A,c\in S}x_{A,c}\mathbf{1}[c\in A]\), subject to \(\sum_{c\in S}x_{A,c}=\mu_A\) for each type and \(\sum_A x_{A,c}=1/k\) for each committee member. The computational task is to find an \(\epsilon\)-winning committee in one pass and characterize the required memory in terms of \(m,k,\epsilon,\tau\), and mass bit length \(L\).
The mirror covers Approval-M in Theorem 3 and the Approval-M instance of Theorem 5’s lower bound, whose proof uses \(k=1\), where Approval-M and Approval-CC coincide. It leaves the Borda variants and the paper’s other results unaddressed.
The strongest positive case is narrow but concrete: this paper has a credible continuous mirror for the streaming space complexity of approval-based Monroe winner finding. Monroe is especially well suited to the programme’s allowance for co-modification: when voters become mass, its per-candidate quotas become exactly \(1/k\) of the population.
Take the candidates \(C\), and let a type be an approval set \(A\subseteq C\). A society is a distribution \(\mu\) over approval types, supplied as a one-pass stream of records \((A_i,w_i)\), where the rational masses sum to \(1\). Let \(\tau\) be the number of distinct types. For a committee \(S\), its continuous Monroe score is
\[ V_\mu(S)=\max_x \sum_{A,c\in S}x_{A,c}\mathbf{1}[c\in A], \]
subject to
\[ \sum_{c\in S}x_{A,c}=\mu_A \quad\text{for every }A, \qquad \sum_A x_{A,c}=\frac1k \quad\text{for every }c\in S. \]
Here \(x_{A,c}\) is the mass of type \(A\) assigned to representative \(c\). The committee remains a discrete set; the assignment is fractional at the aggregate level.
For this mirror, an \(\epsilon\)-winning committee is one that wins in some society \(\nu\) with \(\tfrac12\|\mu-\nu\|_1\le\epsilon\). That distance is the minimum population mass whose approval types must change. The problem is: given the streamed rational masses, find an \(\epsilon\)-winning size-\(k\) committee in one pass with high probability, using as little working memory as possible. This makes the population the continuous object while retaining the paper’s streaming-access model.
The most revealing anchor is Theorem 5, proved here: *there is an \(\epsilon>0\) such that any \(\epsilon\)-approximate streaming algorithm for Approval-CC or Approval-M needs \(\Omega(m)\) space.* Its proof reduces from Set Disjointness. In the continuous mirror, the reduction has a particularly clean form at \(k=1\), where Approval-M and Approval-CC coincide. Put mass \(2/7\) on Alice’s approval set \(A\), mass \(2/7\) on Bob’s set \(B\), and mass \(3/7\) on a type that approves only \(d\). If \(A\cap B=\emptyset\), \(d\) scores \(3/7\) and every other candidate scores at most \(2/7\). If \(A\cap B\ne\emptyset\), some \(c_i\) scores \(4/7\), beating \(d\)’s \(3/7\). The society has only three types, regardless of the number of voters it represents.
For the mass-edit version, I would set \(\epsilon<1/14\). Changing \(\eta\) mass can change the score difference between two candidates by at most \(2\eta\), so that budget is too small to erase the \(1/7\) winner gap. Thus an \(\epsilon\)-winning output identifies which side of the disjointness reduction holds. Streaming \(A\) before \(B\) then gives the \(\Omega(m)\)-bit communication lower bound. The paper’s theorem is existential in \(\epsilon\); the continuous transfer needs this smaller fixed constant rather than blindly copying the proof’s displayed \(1/7\).
This lower bound survives at arbitrarily large population size: repeat each type in the same proportions, or treat each mass record as a large cohort. In either case \(\tau=3\), while the combinatorics remain in \(m\). I would expect this anchor to yield a transferred streaming-space lower bound, not NP-hardness or a claim that the continuous problem is intractable: \(\Omega(m)\) space is still polynomial in the explicit parameters.
The constructive companion is Theorem 3, proved here: *there is an \(\epsilon\)-approximate streaming algorithm for Approval-M using \(O(\epsilon^{-2}k^3m\log m)\) space.* Its proof samples voters and uses preserving subsets to control the Monroe assignments. In the mass formulation, the same idea is to sample from \(\mu\); the equal-size assignment condition is already the exact \(1/k\) constraint. For binary-rational masses, a weighted-record implementation will need the corresponding arithmetic overhead in the mass bit length \(L\). I expect this general-\(k\) mirror to be tractable in streaming memory, with the theorem’s bound independent of population size. Theorem 3 is the constructive anchor; Theorem 5 is the strongest evidence that the continuous mirror retains a nontrivial lower-bound side.
The regime is plausible. A municipality with millions of voters and a comparatively small number of recurring approval ballots is a natural example: voters sharing a ballot are indistinguishable for the model, so their group’s mass is meaningful. Monroe’s equal representation requirement becomes a per-capita mass quota, precisely the sort of co-modification the programme permits. The paper’s own online-shopping example offers another setting if products are candidates and approval sets are customer preferences.
This covers Approval-M and the \(k=1\) Approval-CC/Approval-M lower-bound case. It does not establish a continuous result for Borda-M or for the paper’s other rules. Nor does it claim that continuization makes committee selection polynomial-time: the paper’s results concern space, and finding the winning committee in the sampled election may itself be computationally expensive. The follow-up questions are whether the \(O(\epsilon^{-2}k^3m\log m)\) memory bound can approach the \(\Omega(m)\) lower bound, how \(\tau\) and \(L\) affect the optimum, and what changes for exact winner finding.
The weakest point is that this is a close bridge from a paper already about huge voter streams to a rational-mass input model; much of the adaptation may follow from weighted sampling. That makes the novelty modest, and the results do not supply the continuous-optimization tractability story one might want for the broader programme. But it is a sensible population-continuous computational question: type masses are the society, Monroe’s assignment is defined directly over those masses, and the paper’s space bounds and Set Disjointness reduction give concrete algorithmic and lower-bound anchors.
The strongest negative case is about marginal gain. The paper already studies huge electorates through one-pass sampling, and Theorem 3’s algorithm can be adapted to a stream of rational masses: draw sample points in \([0,1]\), use cumulative mass to select their types, then run the paper’s sampled-election algorithm. The weighted input adds arithmetic in the mass bit length \(L\), and the sampled Monroe instance should use a sample size divisible by \(k\) so its equal quotas match the continuous quotas. That makes the upper-bound mirror look like a short adaptation of the paper’s method, rather than a new use of continuous optimization.
That objection does not defeat the anchor. The input model changes from individual ballots to a distribution over types, and the mass-edit version of \(\epsilon\)-winning is well defined. The paper does not give an algorithm whose input is an explicit rational distribution. A direct adaptation may be modest, but under the programme’s novelty standard, an outside answer changes what should be proved; it does not make a sensible mirror disappear.
Theorem 5 is an even harder anchor to attack. Its reduction survives the move to masses: assign masses \(2/7\), \(2/7\), and \(3/7\) to Alice’s approval set, Bob’s approval set, and the candidate \(d\)’s singleton type. If the sets intersect, a shared candidate beats \(d\) by \(1/7\); if they are disjoint, \(d\) wins by that margin. Since changing mass \(\eta\) can change a pairwise score difference by at most \(2\eta\), any \(\epsilon<1/14\) preserves the distinction. Scaling the proportions gives arbitrarily large populations with only three types. The lower bound is driven by remembering an \(m\)-bit approval set, rather than by the population size, but that limits what the result says about population multiplicity; it does not make the continuous question ill posed.
So the best case against is that these mirrors may offer less new technique than the broader continuization programme seeks: one is a sampling adaptation, and the other transfers a communication lower bound whose combinatorics already sit in the candidate set. Neither point is a fundamental obstruction. The proposed Monroe model has a plausible high-multiplicity setting, its mass quotas are natural, and both anchors survive the stronger formulations. I cannot make a persuasive case that no worthwhile continuous mirror exists here; the negative case is weak.
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.