| paper | d4-conf-atal-2013-0285 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: A deterministic polynomial-time \((1-1/e)\)-approximation exists; it achieves the stronger guarantee \(1-(1-1/K)^K\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(m\) alternatives, committee size \(K\), a positional scoring vector \(\alpha\), and \(\tau\) complete rankings with positive rational masses \(\mu_t\) summing to \(1\), compute a \(K\)-alternative committee \(W\) and a feasible assignment \(x_{t,a}\ge 0\) satisfying \(\sum_{a\in W}x_{t,a}=\mu_t\) for every type \(t\) and \(\sum_t x_{t,a}=1/K\) for every \(a\in W\), whose score \(\sum_t\sum_{a\in W}x_{t,a}\alpha(\operatorname{pos}_t(a))\) is at least \((1-1/e)\) times the optimum.
A society is a rational distribution over complete ranking types. For a partial committee \(S\), score its best assignment with capacity at most \(1/K\) per selected alternative; greedily add the alternative with greatest marginal score, then find a balanced assignment for the final committee. The assignment steps are transportation problems over the \(\tau\) types.
Covers the \((1-1/e)\)-approximation for Monroe winner computation with arbitrary positional scoring functions. It leaves the paper’s experiments, Chamberlin–Courant results, and exact winner-computation complexity aside.
My strongest positive case is the Monroe branch, and it rests on one anchor: Theorem 1, proved in this paper. It states that Algorithm GM is a \((1-1/e)\)-approximation for the Monroe election problem for every positional scoring function \(\alpha\). In each of \(K\) rounds, GM adds the alternative that gives the greatest increase in the best Monroe satisfaction achievable with the selected alternatives so far; after choosing \(K\), it returns the best Monroe assignment for that committee. The guarantee is relative to the optimal Monroe satisfaction, where each selected alternative represents roughly \(n/K\) voters. The authors prove the theorem here using submodularity and the greedy approximation result of Nemhauser et al. The paper also describes Monroe winner computation as NP-hard, but those claims are prose summaries citing earlier work, not numbered results in this paper, so I do not count them as a second anchor.
The mirror is Continuous Monroe \((1-1/e)\)-Approximation. An instance has \(m\) alternatives, a committee size \(K\), an explicit positional scoring vector \(\alpha\), and \(\tau\) distinct rankings \(t\) with positive rational masses \(\mu_t\) summing to \(1\). A ranking is the type: agents with the same ranking are interchangeable for this problem. A solution is a committee \(W\) of \(K\) alternatives and nonnegative assignments \(x_{t,a}\), where \(x_{t,a}\) is the fraction of the whole population of type \(t\) represented by \(a\). Require
\[
\sum_{a\in W}x_{t,a}=\mu_t
\quad\text{for every }t,
\qquad
\sum_t x_{t,a}=\frac{1}{K}
\quad\text{for every }a\in W.
\]
The objective is to maximize
\[
\sum_t\sum_{a\in W}x_{t,a}\,\alpha(\operatorname{pos}_t(a)).
\]
The approximation task is to return a feasible committee and assignment with value at least \((1-1/e)\) times the optimum. Thus the continuous model keeps both parts of Monroe’s question: which representatives to select, and how to balance representation among them.
A plausible regime is a large electorate—say millions of voters ranking a fixed slate—with many repeated ballots: \(n\) far larger than \(\tau\), perhaps millions of voters but hundreds or thousands of distinct ranking types. Each \(\mu_t\) is the share of voters with that ranking. This is a direct high-multiplicity version of the paper’s electoral setting. The quota \(1/K\) is the per-capita form of Monroe’s roughly \(n/K\) representatives-per-voter balance, and the objective is per-capita satisfaction. Allowing a type’s mass to split across representatives is the natural population-level counterpart of assigning individual voters.
The greedy mirror is concrete. For a partial committee \(S\), compute the best score by assigning at most \(1/K\) mass to each selected alternative, allowing some mass to remain unrepresented. Repeatedly add the alternative giving the largest increase, then compute a balanced assignment for the final \(K\). Each partial assignment is a transportation problem over \(\tau\) types and the selected alternatives. The paper’s proof establishes the relevant finite-profile guarantee. For rational masses, scaling by a common denominator and \(K\) gives integer type supplies and quotas; the corresponding flow problems have integral optima. This gives a route to carry the guarantee over while computing directly on the compact type representation, in time polynomial in \(m,\tau\), and the input bit length.
For the approximation task, I expect Class A: the continuous greedy procedure should retain the \((1-1/e)\) guarantee and can evaluate its steps on the \(\tau\)-type flow rather than on a list of all voters. The exact optimization problem behind that guarantee is a separate question. I expect its hardness to transfer for the usual hard Monroe settings, because the committee-selection combinatorics remain; whether that holds under the exact fractional quotas for each specific scoring rule deserves a direct reduction. Further questions include whether the Borda-specific guarantee can be improved and how the exact continuous complexity varies with \(m\) and \(\tau\).
The authors should recognize this as their problem: the continuous version preserves Monroe’s committee choice, scoring objective, and balanced representation condition. The paper itself studies performance as electorates grow, which supports the regime’s plausibility. My weakest point is scope: this mirrors one theorem about approximation, not the paper’s central experimental findings as a whole, and the paper does not report how its datasets’ numbers of distinct rankings compare with their voter counts. The case is strongest where large populations really do have comparatively small ranking support.
The strongest case against is that the proposed mirror may add little new mathematics. For any rational society \(\mu\), choose a common denominator \(q\) and replicate it as a finite election with \(n=qK\) voters. Each type then has \(n\mu_t\) voters, and each Monroe representative’s quota is exactly \(q\). After scaling, the assignment problem is a transportation flow with integer supplies and capacities, so it has an integral optimum. The continuous optimum and the greedy values in Theorem 1 therefore match those of this replicated finite election. Aggregating identical voters lets the algorithm run on the \(\tau\) types rather than all \(n\) voters, but the committee-selection problem and its guarantee transfer directly.
That makes the result look like a compact high-multiplicity implementation of an existing theorem, rather than a new continuous optimization phenomenon. But this does not defeat the anchor under ChoCo’s rules: high multiplicity is evidence that the regime is sensible, and a direct transfer or an unsurprising answer does not make a well-posed mirror unworthy. The paper has a named approximation theorem, and its electoral setting admits large populations with repeated rankings. I cannot honestly argue that this mirror fails; the negative case is weak, and this anchor 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.