| paper | d4-conf-sagt-2022-0019 |
| 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: NP-hard · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(m\) tasks with positive durations \(p_i\) and a society supported on \(\tau\) preferred schedules, each with positive binary-rational mass \(\mu_t\) summing to \(1\), compute a permutation \(S\) minimizing \(\Phi_\mu(S)=\sum_t \mu_t\sum_i |C_i(S)-d_{i,t}|\), where \(C_i(S)\) is task \(i\)’s completion time in \(S\), and \(d_{i,t}\) is its completion time in type \(t\)’s preferred schedule.
The tasks and their durations \(p_i\) are common to the society. Each type \(t\) is a complete preferred task order carrying mass \(\mu_t\); the decision is one permutation \(S\), evaluated by its population-average total completion-time deviation.
Covers Theorem 1’s strong NP-hardness result for \(\sigma_D\). It leaves the axiomatic results, the \(\sigma_T\) and PTA Kemeny rules, and the LMT approximation result outside this mirror.
My lead, and only anchor, is Theorem 1 in Section 4. It is proved in this paper: computing a schedule minimizing total absolute deviation, the problem solved by \(\sigma_D\), is strongly NP-hard. The authors prove it by reducing from the strongly NP-hard single-machine no-idle total-deviation scheduling problem, whose hardness they cite from earlier work.
A natural continuous mirror is Continuous Total Absolute Deviation Scheduling (\(\sigma_D^\infty\)). An instance has \(m\) tasks with positive integer durations \(p_i\), and a society supported on \(\tau\) preferred schedules. Each type \(t\) is a complete preferred permutation of the tasks; its rational mass \(\mu_t>0\) is the fraction of society with that preference, with \(\sum_t\mu_t=1\). Let \(d_{i,t}\) be task \(i\)’s completion time in type \(t\)’s preferred schedule. The question is to return a permutation \(S\) minimizing
\[
\Phi_\mu(S)=\sum_t \mu_t\sum_i |C_i(S)-d_{i,t}|.
\]
Equivalently, given a rational threshold \(B\), decide whether some schedule has \(\Phi_\mu(S)\le B\). A solution is one schedule of all tasks. The durations are common task data, as in the paper; population continuity enters through the weighted aggregation of preferences.
This fits a plausible large-population regime for shared public projects: many residents express preferences over the order of a fixed set of infrastructure phases, while many residents fall into the same preference types. For example, a city may have hundreds of thousands of respondents, a few dozen phases, and far fewer distinct complete orderings than respondents. A type here means exactly what the paper’s objective uses: a preferred schedule. Residents with the same schedule are indistinguishable to this problem. The case is strongest when those repeated types are a feature of the setting, rather than an imposed restriction that removes the scheduling question.
The anchor’s content carries over directly. For an explicit discrete profile with \(v\) voters and \(n_t\) voters of each type, set \(\mu_t=n_t/v\). Then \(\Phi_\mu(S)\) equals the paper’s total deviation divided by \(v\), so the minimizing schedules are identical. A discrete threshold \(K\) becomes \(B=K/v\). Thus Theorem 1 gives hardness for the continuous optimization question by embedding its finite profiles as rational-mass societies. I expect this mirror to fall in Class B, hardness transfers: the reduction encodes the combinatorics of task ordering, and every discrete instance is representable as a distribution over types.
The paper’s result and its scope are quite specific: this mirror covers the \(\sigma_D\) optimization problem, not the axiomatic results or the other aggregation rules. The authors should recognize the question as theirs because it keeps their tasks, preferred schedules, completion-time deviations, and goal of finding a consensus schedule. It changes the electorate representation from a list of voters to masses of preference types.
The main caveat is that Theorem 1 does not establish hardness specifically in a regime with very small support relative to the population. Its reduction proves hardness for profiles that can be converted to distributions; it does not show whether \(\sigma_D^\infty\) becomes tractable when \(\tau\) is fixed or moderate. Also, a rational-mass society can be scaled to an explicit electorate using a common denominator, but that electorate may be exponentially large in the masses’ bit length. The useful follow-up questions are therefore the complexity as a function of \(\tau\), whether fixed support beyond the two-voter case admits an efficient algorithm, and whether an algorithm parameterized by \(\tau\) is possible.
The best negative case is that Theorem 1’s mirror is unusually close to a change of representation. For a schedule \(S\), define \(q_t(S)=\sum_i |C_i(S)-d_{i,t}|\). Then the proposed continuous objective is simply \(\Phi_\mu(S)=\sum_t\mu_t q_t(S)\). The paper already aggregates voters anonymously by summing their costs, so replacing repeated schedules in a voter list with their masses leaves every objective value, and therefore every optimal schedule, unchanged up to normalization. Indeed, for \(n_t\) voters of type \(t\) among \(v\) voters, \(\mu_t=n_t/v\) gives \(\Phi_\mu(S)=D(S,P)/v\).
That makes the contribution to this particular problem look limited: the population representation changes, but the decision is still to choose a permutation of the tasks, and the objective still sums completion-time penalties. The theorem’s reduction from no-idle deviation scheduling reinforces that the hard structure lies in the task order. Its reduction gives no result for fixed or moderate support \(\tau\); the support can grow with the reduction. So it does not show whether the regime where a large population is summarized by a small number of preference types has different algorithmic structure. The continuous formulation also does not, by itself, expose a fractional schedule or an evident LP pricing problem.
This is a case for lower priority, though—not a reason to reject the mirror. The missing support-sensitive complexity results are legitimate questions under ChoCo’s stated aims, and the reduction’s hardness is a valid Class B outcome rather than a defect. Nor can I rule out a convincing setting: many residents expressing preferences over a fixed set of public projects, with repeated complete schedules, is plausible and fits the paper’s own infrastructure example. The proposed mirror preserves the paper’s problem closely, and the paper has a named computational result to anchor it.
So I cannot honestly defeat this anchor or support the universal claim that no worthwhile mirror exists. The strongest case against it is that its likely incremental value depends on whether the authors and programme regard complexity under a succinct mass representation as enough when the underlying objective is already anonymous and the schedule remains discrete. That is a real reservation, but it falls short of showing the question is not worth asking.
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.