| paper | d4-conf-atal-2018-0175 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Observation 3.1
statement extracted from the paper’s text layer
Given \(m\) candidates, committee size \(k\), a support of \(\tau\) complete rankings with rational masses \(\mu_t\ge 0\) summing to \(1\), and a rational threshold \(\theta\), is there a size-\(k\) committee \(S\) and assignment masses \(y_{t,c}\ge 0\) such that \(\sum_{c\in S}y_{t,c}=\mu_t\), \(\sum_t y_{t,c}=1/k\) for every \(c\in S\), and \(\sum_t\sum_{c\in S}y_{t,c}(m-\operatorname{pos}_t(c))\ge\theta\)?
A society is a distribution \(\mu\) over complete rankings. Select \(k\) candidates and assign each type’s mass fractionally among them to maximize total Borda satisfaction, subject to every selected candidate receiving mass \(1/k\); equivalently, decide whether satisfaction reaches \(\theta\).
The paper’s cited Monroe hardness results are not shown to hold when the number of voters is divisible by \(k\), which the exact-equality \(X=1\) mirror requires.
fatal: False
The mirror covers the satisfaction-threshold winner-determination problem at \(X=1\). It leaves the general \(X\)-spectrum, the paper’s FPT claims, experiments, and approximation analysis aside.
My lead is a mass version of the paper’s \(X\)-BalancedCC winner-determination problem, with the \(X=1\) Monroe case as its strongest, cleanest slice.
The regime I find most convincing is a large recurring professional-development program: thousands or tens of thousands of teachers choose among a catalog of courses, and many share the same ranking patterns. A type is one complete ranking of the courses; its mass \(\mu_t\) is the fraction of participants with that ranking. The support \(\tau\) might be a few hundred types even when the cohort is much larger. The organizers select \(k\) courses, assign each participant to one selected course, and seek high Borda satisfaction while keeping the largest course group at most \(X\) times the size of the smallest. This scales up the paper’s own course-assignment example and preserves its central choice: proportionality versus diversity in who gets represented by each selected option.
Precisely, an instance gives \(m\) candidates, a committee size \(k\), a support of \(\tau\) complete rankings with binary-rational masses \(\mu_t\ge 0\) summing to \(1\), a rational \(X\ge 1\), and a satisfaction threshold \(\theta\). Ask whether there are a committee \(S\) of \(k\) candidates and nonnegative assignment masses \(y_{t,c}\) such that every type is fully assigned, \(\sum_{c\in S}y_{t,c}=\mu_t\), and the selected candidates’ district masses \(q_c=\sum_t y_{t,c}\) satisfy \(\max_{c\in S}q_c\le X\min_{c\in S}q_c\), with total Borda satisfaction \(\sum_{t}\sum_{c\in S}y_{t,c}(m-\operatorname{pos}_t(c))\ge\theta\). A solution is the committee and the assignment masses. The committee remains discrete; the fractions describe how a large population of identical-type participants is distributed in aggregate. At \(X=1\), each selected candidate represents exactly \(1/k\) of the population.
My anchor is Observation 3.1. It states that for every rational \(X\ge1\), deciding whether a discrete election has a size-\(k\) committee and an \(X\)-balanced assignment achieving a given satisfaction threshold is NP-complete; the problem is also FPT parameterized by either the number of voters or the number of candidates. The paper presents this observation, but its proof draws on earlier NP-hardness results for Monroe and CC [28, 32, 35], and adapts the FPT algorithms of Betzler et al. [6]. In the continuous mirror, I predict hardness transfers at \(X=1\), hence the \(X\)-parameterized family is NP-hard. I would not claim that the same transfer is established for every fixed \(X>1\).
The reason the \(X=1\) transfer is unusually solid is that the fractional assignment does not improve the optimum there. Take a discrete Monroe instance with \(N\) voters, \(k\mid N\), and type counts \(n_t\), and set \(\mu_t=n_t/N\). For any fixed committee, multiplying a continuous assignment by \(N\) gives a transportation problem with integer supplies \(n_t\) and integer district demands \(N/k\). Its assignment polytope is integral, so an optimal fractional assignment has an integral counterpart with the same Borda score. Thus the continuous optimum is exactly the discrete optimum divided by \(N\). This gives the mass problem a direct hardness-transfer argument, not just a resemblance to Monroe. The continuous problem is also in NP: for a proposed committee the assignment constraints are a rational linear program with polynomial-size certificates.
The model has a tractable structure once the committee is fixed. For any finite \(X\), the balance constraint can be written with a variable \(z\) as \(z\le q_c\le Xz\) for each selected candidate \(c\). Together with the type-mass constraints, this is a linear program. Enumerating committees therefore gives an FPT algorithm in \(m\), with running time \(2^m\operatorname{poly}(m,\tau,L)\), where \(L\) is the input bit length. That matches the paper’s candidate-parameter result in a natural way. Its voter-parameter result has no automatic continuous counterpart: a mass instance has no explicit voter count, so whether support size \(\tau\) or denominator size plays that role is an open question.
This mirror covers Observation 3.1’s winner-determination complexity, particularly its Monroe endpoint. It does not attempt to continuize the paper’s experiments, approximability results, or the whole \(X\)-spectrum. Further questions are whether hardness transfers for each fixed rational \(X>1\), whether the mass problem is FPT or otherwise tractable in \(\tau\), and what approximation guarantees hold as functions of \(X\), \(m\), \(\tau\), and \(L\).
My weakest point is that the exact hardness argument is strongest at \(X=1\). For \(X>1\), fractional mass assignments could change which district sizes are feasible and may erase a discrete reduction. Also, the course-program scenario needs genuinely repeated ranking types to have small \(\tau\); that is plausible for a large recurring program with a standardized catalog, but it is an instance regime rather than a claim about every training program. The case still stands at its lead point: the \(X=1\) mirror preserves the authors’ committee, assignment, satisfaction, and balance question, and has a precise discrete-to-continuous identity.
I cannot make a persuasive case that no worthwhile continuous mirror exists. Observation 3.1 is a named computational result, and the \(X=1\) winner-determination problem has a credible high-multiplicity setting: a large recurring course program with a standardized catalog and many participants sharing preference rankings. The objective uses rankings and assignments, not personal identities, and the paper itself offers course assignment as an application. In the mass model, each course receives exactly \(1/k\) of the population. For a fixed committee, scaling the rational masses turns assignment into a transportation problem with an integral optimum. That gives a precise bridge to an equal-district discrete instance; the committee-selection problem remains computationally nontrivial. Nothing in the paper already solves that continuous computational question.
The best objection I can make is narrower: the proponent’s hardness transfer needs care. The paper’s discrete Monroe assignments allow districts of sizes \(\lfloor n/k\rfloor\) and \(\lceil n/k\rceil\), while the continuous \(X=1\) mirror requires exactly equal masses. The transportation integrality argument establishes an identity after scaling, but it does not by itself show that the cited hardness reduction still works on discrete instances with \(k\mid n\). That claim needs a reduction or a hardness result for the divisible case. Still, this weakens a particular complexity claim, not the case for asking the mirror question. The program treats high-multiplicity work as supporting evidence, and an exact discrete-to-continuous identity can itself be a worthwhile result. So the strongest anchor survives; I do not see an honest argument that defeats it across all plausible scenarios.
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.