| paper | Multi-user Norm Consensus |
| authors | — |
| venue | AAMAS 2024 |
| filed under | frontier · ja |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper has no numbered theorem, lemma, corollary, or proposition asserting an algorithmic or complexity result, so bit (a) fails. The proposed \(q<1\) population model is plausible and author-recognisable, but it is an extension of the paper’s semantics and cannot repair the missing computational anchor.
fails bit a — no named computational result to mirror
The formulation covers the consensus-norm construction, preference propagation and cancellation, and its set-cover search, but neither Lemma 1 nor Theorem 1 gives a named complexity classification.
The strongest honest case is modest: this paper admits a plausible population mirror, but it has no qualifying named computational-complexity anchor.
The only numbered results are Lemma 1, “\(Con^+\) is the smallest search space for positive consensuses,” and Theorem 1, “\(N\) is the solution of the norm consensus problem.” Both are proved by the authors (with proof sketches in the paper and full proofs in the supplement). Neither asserts that a problem is NP-hard, in P, FPT, or otherwise classifies its complexity. Section 4.2 only gives the unnumbered observation that consensus detection is equivalent to set cover and is therefore NP-hard, citing the set-cover literature. Under the programme’s rules, that is not an eligible anchor.
If a correctness result is accepted as a weaker anchor, my lead would be Theorem 1, mirrored by Mass-Continuized Norm Consensus.
An instance consists of a finite action set \(A\), a finite relevant context universe \(\mathcal C\) with the paper’s generalisation relation \(g\), a finite set of complete preference types \(T\), and a rational distribution \(\mu\in\mathbb Q_{\ge 0}^{T}\) with \(\sum_{t\in T}\mu_t=1\). A type is a complete preference profile \(p_t:A\times\mathcal C\to\{-1,0,1\}\), including the same unknown entries represented by \(0\) in the paper. The paper’s preference-propagation and cancellation procedures (Definitions 13 and 14) are applied to each type.
For a fixed action \(a\), let \(S\subseteq Con_\mu^+(a)\) be a set of candidate positive contexts, where \(Con_\mu^+(a)\) is constructed exactly as the paper constructs \(Con^+\), replacing the set of users by the positive-mass types \(T_\mu=\{t:\mu_t>0\}\). Define its covered mass by \(\operatorname{cov}_\mu^+(S)=\sum_{t:\exists c\in S,\ p_t^*(a,c)=1}\mu_t\). For a threshold \(q\in(0,1]\), \(S\) is a positive \(q\)-consensus if every selected context has zero opposing mass, \(\operatorname{cov}_\mu^+(S)\ge q\), no two selected contexts are related by \(g\), and \(S\) is non-redundant: no proper subset reaches mass \(q\). It must also satisfy the paper’s generality condition, excluding another \(q\)-cover whose additional contexts are strictly more general.
Among admissible sets, use the paper’s objective \(w(S)=\sum_{c\in S}(1+|\{c'\in Con_\mu^+(a):c'g c\}|)\), retaining all tied minimal and maximally general solutions. Each such \(S\) produces the norm \(\langle\bigwedge_{c\in S}c,\operatorname{Per}(a)\rangle\). Negative consensuses are defined symmetrically by exchanging approval and disapproval and producing prohibition norms. A solution is the complete set of norms obtained for every action and every positive or negative consensus, not merely one selected cover.
At \(q=1\), this is exactly the paper’s problem after grouping users with identical complete profiles: if a discrete population has \(n_t\) users of type \(t\), set \(\mu_t=n_t/n\). At \(q<1\), it becomes the mass-sensitive version of the threshold relaxation explicitly suggested in Section 4.2. Thus it is not merely fractionalising the outcome or adding noise; the population itself is the continuous object.
A convincing regime is a large care-home campus, university, hospital, or public smart-assistant deployment with thousands of recurring users but a small number of stable preference profiles. Types might be privacy-conservative residents, ordinary residents, staff, visitors, and so on, but a type must include the entire action-context profile, not merely a demographic label. The norm is computed for the standing population distribution or expected active population, with \(\tau=|T|\) perhaps tens or hundreds while the number of users is in the thousands or more. This is more plausible than the paper’s three-person meeting example, but it uses exactly the same action/context language and the same consensus-to-norm mechanism.
I would expect the \(q=1\) mirror to remain hard: the set-cover combinatorics live in the contexts and their approval sets, not in the number of individually named users. The continuous version therefore looks like a Class B problem, with possible fixed-parameter algorithms when \(\tau\) is small. For \(q<1\), it becomes a weighted set-cover variant, where the weights are the masses \(\mu_t\). The continuous formulation may support parameterized or approximation results, but it should not be advertised as automatically tractable.
The main further questions are whether consensus can be computed efficiently when the conjunction context universe is implicit, whether single-consensus computation is FPT in \(\tau\), how to enumerate all consensus norms output-sensitively, and how the norm set changes when \(\mu\) is perturbed.
The weakest point is that exact unanimity makes \(\mu\) matter mainly through its support: duplicating a type does not change the answer. The \(q<1\) version uses mass genuinely, but it weakens the paper’s exact consensus requirement. Moreover, the paper’s motivating users are often small, ad hoc groups, so the high-multiplicity scenario must be supplied rather than read directly from the experiments.
So the positive conclusion is: a credible continuous population formulation exists, and the public-assistant setting makes it recognisable to the authors. But strictly under the requested anchoring rule, this paper has no named computational result to support a full positive verdict.
The negative case is strongest at the programme’s source gate: this paper has no qualifying named computational result. Lemma 1 is a structural statement about a search space, and Theorem 1 is a correctness claim that the generated norms satisfy the authors’ three properties. Neither gives a complexity classification, an algorithmic runtime, an approximation guarantee, or a parameterized result. The NP-hardness statement in Section 4.2 is an unnumbered observation inherited from set cover, while Section 4.4 reports CPLEX timings rather than a complexity theorem. Under ChoCo’s rules, there is therefore no computational anchor to continuize.
The proposed Mass-Continuized Norm Consensus does not repair that defect. At \(q=1\), the masses are mathematically inert. After propagation and cancellation, the paper uses only whether each user belongs to an approval or disapproval set. If two distributions have the same positive-support types, they produce exactly the same candidate contexts, coverage constraints, objective \(w(S)\), and norm set, regardless of the values of \(\mu_t\). Clearing denominators merely creates cloned users whose duplicate constraints can already be removed from the discrete instance. This is legitimate high-multiplicity compression, but it is not a new continuous computational object and it cannot mirror a complexity result the paper never states.
The \(q<1\) rescue is more genuinely mass-sensitive, but it changes the theorem’s subject. The paper’s consensus requires all users to be covered; the proposed version permits a norm to be generated while some positive-mass types remain outside the consensus. Consequently, it no longer has the paper’s preference-alignment and maximal-regulation semantics. The paper does mention threshold agreement as a possible modification, so this is an author-recognisable extension, but it is still an extension: a weighted set-cover problem with a new agreement notion, not a continuization of Theorem 1. The theorem and its proof establish nothing about that weighted problem.
The best possible version would make the distinction explicit. One could study a distribution over complete reported preference types, a threshold or expected-coverage objective, and perhaps the minimum mass of users whose preferences must be changed before a consensus norm exists. That could be a worthwhile new problem. But the first two are new threshold semantics, and the last introduces robustness or campaigning, neither of which occurs in the paper. Reintroducing the paper’s exact unanimity restores the mass-invariance; making masses consequential requires departing from the paper’s computational object.
There is also a mismatch with the paper’s motivating setting. The assistant is meant to respond to the particular users currently present, while a campus-wide distribution \(\mu\) describes only an aggregate population. The norm for a realised group is generally not recoverable from the expected type distribution: co-presence correlations, group composition, and partial reports matter. A single norm valid for the entire standing population may be nearly empty under exact unanimity; a norm for sampled groups requires a distribution over groups and a risk or threshold criterion. Those are sensible stochastic population models, but they are new models rather than mirrors of the static norm-consensus problem.
I would therefore give a negative verdict under the stated programme. The proponent is right that a typed population formulation is plausible and that large deployments provide a believable high-multiplicity story. That is the weak point in the negative case: I cannot honestly claim that no population-level norm-consensus problem could ever be interesting. The stronger and defensible conclusion is that this paper supplies no named computational result, its exact mirror makes masses irrelevant, and every version in which masses matter changes the consensus semantics enough to become a new research 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.