d4-conf-ecai-2023-0062

My strongest positive case is narrow: this paper has one named computational anchor worth mirroring, and the mirror is a high multiplicity version of its query answering problem.

Theorem 2, proved in this paper, says that for a multi-stakeholder preference query \(\psi\), an outcome belongs to the query’s answer under semantics \(i\) exactly when it satisfies the corresponding translated alternation-free \(\mu\)-calculus formula \(\mathrm{Tr}_i(\psi)\) on the induced preference graph. This covers the consensus and collaborative semantics defined in the paper. It is a correctness result for the model-checking algorithm, not a theorem that the problem is in P for succinct inputs. The paper gives linear model-checking time in the formula and explicit state space, while noting that the outcome space can be exponential in the number of attributes. It contains no named NP-hardness result or comparable complexity classification to anchor on.

A plausible high multiplicity regime is a large public planning process: many affected residents express qualitative preferences over plans described by attributes such as housing cost, transport access, and green space. Residents with the same complete preference specification and the same role in the query form a type. There might be hundreds of thousands of residents but only dozens or hundreds of such types. That is a more plausible regime than treating a small committee of named institutions as a continuum. The authors would have to accept a large constituency as a stakeholder population; the paper’s application framing makes that plausible, though not certain.

The lead mirror is Mass-Supported Multi-Stakeholder Preference Query. An instance has a finite set of outcome attributes \(X\), their domains, a finite support of stakeholder types \(T_\mu\), and a rational distribution \(\mu\) with \(\mu_t>0\) for each supported type. Each type specifies its members’ complete qualitative preferences and their eligibility for a queried coalition \(B\subseteq T_\mu\). The instance also gives a query \(\psi_1 P_B \psi_2\) and one of the paper’s semantics. Require \(\mu(B)>0\).

Build the induced preference graph with edges annotated by the types whose preferences induce them. For a finite-support society, the continuum version uses the represented types \(S_B=\{t\in B:\mu_t>0\}\): consensus requires agreement for almost every selected stakeholder; collective collaboration accepts a witness supplied by a positive-mass set of types; constructive collaboration permits a path assembled from edges induced by selected types. Agreement conditions use the corresponding almost-everywhere or no-path condition. These are the paper’s semantics lifted from named stakeholders to preference-homogeneous groups.

The solution is the set of outcomes satisfying \(\psi_1\) that pass the selected witness and agreement conditions against outcomes satisfying \(\psi_2\). Equivalently, for the consensus case, if \(R_t\) is the paper’s single-type answer set, the output is
\[ \{o\in\llbracket\psi_1\rrbracket : \mu_B(\{t\in B:o\in R_t\})=1\}, \]
where \(\mu_B\) is the distribution restricted and normalized to \(B\). The other semantics use the paper’s collective or constructive witness and agreement conditions on the type-labelled graph.

I expect this mirror to be tractable relative to an explicit induced preference graph: Theorem 2’s translation and model checking apply to the continuous query, with the type support taking the place of the finite stakeholder set. That is not a claim of polynomial time in the compact attribute description: the state space may still be exponential in the number of attributes. The mirror covers Theorem 2’s query-answering result, not the entire paper or its experimental claims.

Its soft spot is that, with finite support, the query often depends on which types have positive mass, not on their exact mass values. That makes this a thinner continuation than a mass-transfer problem: the distribution represents a large society, but these semantics do not give larger groups more influence. Still, a consensus or compromise question that treats every represented constituency as relevant regardless of size is coherent, and the theorem’s algorithm transfers directly to that object.

The immediate follow-up questions are whether the algorithm can exploit succinct preference descriptions with guarantees in the number of attributes and support size; which parameters, such as query nesting depth or \(\tau=|T_\mu|\), control the cost; and whether mass-weighted or quorum semantics can be added while retaining an efficient model-checking formulation. A discrete-to-continuous identity for repeated stakeholders is also natural here: a finite electorate with proportions \(\mu_t=n_t/N\) has the same answer under these support-based semantics.