| paper | d4-conf-atal-2020-0071 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: NP-hard, even with \(m=\tau=1\), sole mass \(1\), and \(R_x=R_g=\varnothing\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite norm net \(\langle N,R\rangle\), value set \(V\), support map, and rational-mass distribution \(\mu\) over \(\tau\) complete weak rankings \(\succeq_t\) of \(V\), define \(M_\mu(v,w)=\sum_{t:v\succeq_t w}\mu_t\) and \(v\succeq_\mu w\) iff \(M_\mu(v,w)\ge \tfrac12\). For inputs where \(\succeq_\mu\) is transitive, find a sound \(\Omega\subseteq N\) maximizing the norm-system ranking induced from \(\succeq_\mu\) by preference induction, lex-cel grounding, and anti-lex-cel lifting.
Residents are grouped by complete weak rankings of moral values, with rational mass \(\mu_t\) for each type. The norm net and support map are shared; the city selects one sound norm system, using the majority-induced value ranking and the paper’s selection procedure. The population affects the ranking input, while norms and compliance remain indivisible.
Only the aggregate majority ranking enters the selection step, so many distinct stakeholder distributions collapse to the same input and the paper’s single-decision-maker computation remains the core.
fatal: False
The mirror covers Theorem 3’s optimization equivalence and the norm-selection formulation used for the airport example; it leaves the paper’s ranking constructions and axiomatic properties outside the population model.
My lead is Continuous Stakeholder MVANS. Consider a city choosing one sound system of rules for all residents. The instance contains the paper’s finite norm net \(\langle N,R\rangle\), value set \(V\), and norm-to-value support map. Residents share that normative context; their relevant differences are their complete, possibly indifferent rankings of \(V\). Let \(T\) be the rankings present in the population, with rational masses \(\mu_t\) summing to \(1\). In a plausible regime, the city has millions of residents but only a modest support of value-priority types.
To supply the single value ranking assumed by the paper, define \(M_\mu(v,w)\) as the mass ranking \(v\) above \(w\). Set \(v\succeq_\mu w\) when \(M_\mu(v,w)\ge \tfrac12\), treating an exact tie as indifference. Restrict inputs to those for which this majority relation is transitive, so it is a ranking of \(V\). The problem is: find a sound \(\Omega\subseteq N\) that is maximal under the paper’s preference-induction, lex-cel grounding, and anti-lex-cel lifting process using \(\succeq_\mu\). The solution is a single norm system enacted for the population; mass is the share of residents of each value-priority type, not a fractional norm or fractional compliance decision.
The anchor is Theorem 3, proved in this paper. It says that, given a norm net and value system, a solution \(\Omega^*\) to MVANSP is also a solution \(\Omega_{\max}\) maximizing the paper’s value-alignment function over sound norm systems; if the optimum is not unique, the solutions are indifferent under the induced norm-system ranking. This is an optimization-equivalence result, not a theorem that the problem is in P. The paper uses it with an objective linear in norm-selection variables: for each norm \(n\), \(x_n\in\{0,1\}\) indicates whether \(n\) is selected, and the objective is
\[ \max \sum_{i=1}^{r} \left(\sum_{n\in\Xi_i}x_n\right) \left(\sum_{j=i+1}^{r}\operatorname{al}(\Xi_j)+1\right), \]
subject to the constraints enforcing soundness: mutually exclusive and substitutable pairs, ancestor relations, and direct-successor constraints. The authors compute the airport example using this encoding. Theorem 3 and that computed formulation are my anchor; the paper proves them here rather than citing them. The continuous version uses the majority-derived ranking where the original uses one decision maker’s ranking, then asks the same underlying norm-selection question.
I expect this mirror to be hardness-transferring (Class B), not tractable merely because the population is continuous. In fact, the norm-selection problem has a simple maximum-independent-set encoding: use one norm and one uniquely supported value per graph vertex; make all values indifferent; encode graph edges as exclusivity relations; leave other relations empty. Sound systems are then exactly independent sets. Since all norms are tied, the induced ranking prefers larger sound systems, so finding the selected system solves maximum independent set. This is a derivation from the paper’s definitions, not a hardness result claimed by its authors. It also persists with one stakeholder type, so the combinatorics live in the candidate norm set, not in population multiplicity. For the proposed mirror, computing \(\succeq_\mu\) is polynomial in \(\tau\) and \(|V|\); it does not remove that selection difficulty.
The weakest point is that the paper has one decision maker, while this mirror adds a collective-preference step. Majority ranking is a reasonable way for affected residents to provide the value ranking a regulator needs, but it is an added social-choice assumption, and the transitivity restriction excludes some populations. The setting is still plausible for a shared city-wide policy: the norm net and promotion semantics are common, while many affected residents fall into a small number of value-priority types.
There is also a caveat about the paper’s claimed tractability: its selection variables are defined as binary, but the displayed LP constraints do not impose integrality. With arbitrary exclusivity relations, the continuous relaxation can be fractional—for a triangle of pairwise exclusions, \(x_n=\tfrac12\) for each norm satisfies the pairwise constraints. Theorem 3 establishes the alignment equivalence; by itself it does not establish that an ordinary LP solves the discrete selection problem. This does not weaken the mirror question. It makes the distinction between the paper’s proved ranking result and its claimed algorithmic consequence especially relevant to investigate.
The strongest objection is that Theorem 3 is not a complexity result about a population. Its input is already a single ranking of values; it proves that two ways of selecting a sound norm system give the same optimum. In the proposed mirror, the population first supplies a ranking—through weighted majority—and then Theorem 3 applies exactly as before. The theorem says nothing about that aggregation step or about how the norm-selection problem behaves as the population distribution varies. The paper also does not formulate a finite-stakeholder version whose high-multiplicity relaxation this would be.
The proposed majority rule makes the gap visible. Majority rankings can cycle, so the mirror excludes societies where they do. One could instead use a social ranking rule, or aggregate each resident’s induced ranking over norm systems. Those are plausible improvements, but they add a collective-choice rule that the paper does not provide. The first turns a distribution over residents into the paper’s existing single-ranking input; the second changes the task into collective choice among norm systems. Either may be a worthwhile follow-up, but neither is a direct continuization of the result proved in Theorem 3.
There is also little population-dependent computation in the proposed version: the distribution is used to calculate pairwise value majorities, after which the selected norm system depends only on the resulting finite ranking. Many distinct mass distributions therefore produce the same input to the paper’s optimization problem. That is a mismatch with the programme’s aim of making the society itself the computational object. The paper’s displayed LP raises a separate concern because it describes selection variables as binary without displaying integrality constraints. That weakens the claimed algorithmic consequence; it does not, by itself, defeat a continuous mirror.
This negative case remains weak against the user’s hardest test. A city choosing one policy for millions of residents, with residents grouped by complete rankings of values, is a plausible high-multiplicity setting. The selected system is a shared policy, and aggregating stakeholders’ values before applying the paper’s norm-selection method is recognizable as a norm-selection question. The authors’ single decision maker does not rule out that scenario. I can argue that the population layer is an added aggregation problem rather than a continuization of Theorem 3, but I cannot honestly rule out the mirror as worthwhile in every plausible scenario.
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.