| paper | d4-conf-atal-2018-0355 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard, already with \(\tau=1\), exclusivity alone, and unit norm weights and costs. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Lemma 1
statement extracted from the paper’s text layer
Given a finite set of institutional types \(T\), rational masses \(\mu_t\) summing to \(1\), and each type’s norm net, representation function \(\rho_t\), cost function \(c_t\), and per-capita budget \(b_t\), let \(\mathcal S_t\) be its sound norm systems. Choose masses \(y_{t,\Omega}\ge 0\) with \(\sum_{\Omega\in\mathcal S_t} y_{t,\Omega}=\mu_t\) and \(\sum_{\Omega\in\mathcal S_t} y_{t,\Omega}c_t(\Omega)\le\mu_t b_t\) for each type. Maximize \(\sum_{t\in T,\Omega\in\mathcal S_t}y_{t,\Omega}\rho_t(\Omega)\), breaking ties by minimizing aggregate cost.
Types are local norm-setting bodies identical in their norm net, representation and cost data, and budget; \(\mu_t\) is their population fraction. Each body adopts a whole sound norm system, while \(y_{t,\Omega}\) records the mass assigned to that system under a pooled per-capita budget. The objective maximizes aggregate norm representation, with aggregate cost as the tie-breaker.
The paper studies one regulator, while the mirror assigns systems across federated regulators; its fit depends on treating pooled-budget federation decisions as an extension of that regulator’s norm-selection problem.
fatal: False
The mirror covers the maximum norm-system problem and Lemma 1’s hardness result. It leaves the moral-value utility construction and the empirical runtime results aside.
My strongest honest mirror is a federation of local norm-setting bodies: for example, many municipalities, schools, or hospitals choosing from a shared catalogue of candidate rules. The continuous population consists of those bodies. A type \(t\) records everything relevant to its decision: its candidate norms, norm relationships, representation weights, deployment costs, and budget. The mass \(\mu_t\) is the fraction of bodies of that type. In a plausible regime there are many bodies and relatively few types: many institutions share the same policy context and parameters.
Call the problem Continuous Norm-System Assignment. Its input is a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), and each type’s norm net, additive representation and cost functions, and per-capita budget \(b_t\). For each type, let \(\mathcal S_t\) be its sound norm systems as defined in the paper. Choose \(y_{t,\Omega}\ge 0\), the fraction of the whole population of type \(t\) assigned system \(\Omega\), with
\[
\sum_{\Omega\in\mathcal S_t}y_{t,\Omega}=\mu_t
\quad\text{and}\quad
\sum_{\Omega\in\mathcal S_t}y_{t,\Omega}c_t(\Omega)\le \mu_t b_t.
\]
Maximize total represented norms, \(\sum_{t,\Omega}y_{t,\Omega}\rho_t(\Omega)\), breaking ties by minimizing aggregate cost. Each local body adopts a whole, sound norm system; only the population’s average cost and representation are fractional. This is a continuous population model with a clear interpretation for pooled policy budgets across many sites.
My anchor is Lemma 1, proved in the paper. It states that the maximum norm system problem is at least NP-hard. The authors prove this by reducing Maximum Independent Set: make each graph vertex a norm, each graph edge an exclusivity relationship, set every norm’s representation and cost to \(1\), and set the budget to the number of vertices. A sound system is then an independent set, and maximizing representation finds a maximum independent set. The paper cites the established hardness of that graph problem; the reduction to norm-system selection is given there.
The same reduction embeds in Continuous Norm-System Assignment with a single type of mass \(1\). Every sound system costs at most \(|V|\), so the per-capita budget is nonbinding. Any distribution over systems has average representation no greater than the maximum independent-set size, and assigning the entire mass to a maximum independent set attains it. Thus the continuous optimum gives the original hard answer exactly. The expected classification is Class B: hardness transfers. The combinatorics live in the norm agenda and its conflict graph, not in the number of bodies. Increasing the multiplicity does not erase them.
I think the authors could recognize this as a high-multiplicity deployment version of their problem: repeated local authorities select sound norm systems from shared policy structures, and the aggregate objective measures represented norms across the federation. That is the regime in which a continuum of authorities and type-level averages are natural. The mirror covers the paper’s maximum norm system problem and Lemma 1. I would not claim that it mirrors the moral-value utility construction or the empirical runtime results.
This formulation also gives useful follow-up questions. Since the assignment problem has one possible column for each sound system, its natural LP has exponentially many variables; its pricing problem asks for a sound system optimizing representation against a cost price. Which norm-relation structures make that pricing problem tractable? Can bounded treewidth or other graph parameters give fixed-parameter algorithms? How does this aggregate problem relate formally to a finite high-multiplicity federation, including the bit complexity of representing an optimal mass assignment?
The weak point is the shift from one regulator choosing a system for one society to many local bodies choosing systems across a federation. The paper’s motivating decision maker is often singular, and it does not study a population of regulatory bodies. The mirror is strongest where local authorities really can choose distinct packages under shared constraints; it weakens if the intended regime requires one identical system everywhere. Even there, the one-type reduction preserves the paper’s underlying system-selection problem, so the positive case survives as a hardness mirror, though not as evidence that continuization makes the problem easier.
Lemma 1 is the hardest anchor to defeat: it is a named computational result about a well-defined problem. The strongest objection is that the paper’s problem has no population variable. One regulator chooses one sound norm system from one norm net; the norms, their relationships, their costs, and their value support are the optimization data. A distribution over the people governed by that system does not change which systems are sound or what the paper’s objective counts. To make population mass matter, a mirror would have to add type-specific costs, effects, or preferences and aggregate them into new norm coefficients. That is possible, but it makes population an input to a modified problem, rather than the repeated-unit structure of the paper’s selection problem.
The federation of local norm-setting bodies is the strongest repair, and it has a plausible setting. But it changes the decision maker and the output: instead of one regulator enacting one system, many regulators enact different systems. If each body must obey its own budget, each type can choose its best affordable system independently; the population masses merely scale the totals. The proposed constraint \(\sum_\Omega y_{t,\Omega}c_t(\Omega)\leq \mu_t b_t\) instead allows bodies of a type to pool budgets, so some may receive systems costing more than \(b_t\). That can make the mixture meaningful, but it is a new collective allocation problem over whole norm systems. Its relevance depends on a federation actually sharing budgets and valuing aggregate representation across sites.
The one-type case does preserve the paper’s hardness reduction exactly. That is evidence for a Class B answer, and hardness transfer is not itself a reason to reject a mirror. But the reduction also shows what the continuous model adds: with one type and no pooled-budget effect, it adds no population structure to the computation. With multiple types or pooled resources, any new structure comes from the federation and its coordination rules. The pricing problem remains the original selection problem over norms.
A stronger citizen-population version faces the same gap. One could weight norm costs or value support by the masses of affected citizen types, but the paper supplies aggregate norm-level coefficients, not type-specific effects or a rule for combining citizens’ moral preferences. A reasonable model can be built, but the paper does not identify which aggregation represents its decision problem.
So the negative case is that Lemma 1’s computational core is about choosing among norms, while the proposed continuization either leaves that core untouched or replaces the single regulator’s problem with a federation’s. This is a weak basis for the universal claim that no worthwhile mirror exists. A federation with genuinely shared budgets and a meaningful aggregate objective is plausible, and its mirror could be worth studying. The most I can defend is that the proponent has not shown that their assignment model is a continuous-population version of the paper’s own norm-selection problem.
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.