d4-conf-ecai-2023-0062 (d4-conf-ecai-2023-0062)

Given outcome attributes \(X\) with finite domains, a finite support \(T_\mu\) of stakeholder types carrying complete qualitative preference specifications, rational masses \(\mu_t>0\), a coalition \(B\subseteq T_\mu\) with \(\mu(B)>0\), a query \(\psi_1 P_B \psi_2\), and one of the paper’s semantics, return the outcomes satisfying \(\psi_1\) that meet that semantics’ witness and agreement conditions on the type-labelled preference graph. Consensus and collective agreement quantify over \(\mu_B\)-almost every type; collective witnesses may come from any positive-mass set of types; constructive paths may use edges induced by any type in \(B\).

Let \(X=\{X_1,\ldots,X_m\}\) have explicitly listed nonempty finite domains \(D_i\), and let \(O=\prod_i D_i\). A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type supplies a finite list of direct strict preferences between outcomes and statements \([c](X_i=v)\succ(X_i=v')[Y]\), where \(v\ne v'\), \(c\) is a partial assignment, and \(Y\subseteq X\setminus\{X_i\}\). Such a statement induces an edge from \(u\) to \(w\) when both satisfy \(c\), \(u_i=v'\), \(w_i=v\), and they agree outside \(\{X_i\}\cup Y\); coordinates in \(Y\) may change arbitrarily. Direct preferences induce their stated edges. Cycles are allowed; no total-order assumption is imposed.
The graph is induced succinctly by these lists, rather than supplied explicitly. Add a state \(\bot\) and edges \(\bot\to o\) for every \(o\in O\), labelled by every type; each other edge is labelled by exactly the types inducing it. Write \(uR_t v\) for a positive-length path using only type \(t\)'s edges, and \(uR_Bv\) for one whose every edge has a label in \(B\).
Queries use attribute-value atoms, Boolean connectives, constants, and nested operators \(\psi_1P_B\psi_2\), with \(B\subseteq T_\mu\) and \(\mu(B)>0\). Atoms are false at \(\bot\); \(\mathrm{tt}\) denotes \(O\cup\{\bot\}\), \(\mathrm{ff}\) denotes the empty set, negation takes complement within \(O\), and preference operators return only members of \(O\). Fix one semantics throughout recursive evaluation.
For \(S=\llbracket\psi_2\rrbracket\), define \(w_t(o)\iff\exists s\in S\;sR_to\), \(a_t(o)\iff\nexists s\in S\;oR_ts\), and define \(w_B,a_B\) identically using \(R_B\). Let \(\mu_B\) be the normalized restriction of \(\mu\) to \(B\).
Consensus accepts \(o\in\llbracket\psi_1\rrbracket\cap O\) iff \(w_t(o)\land a_t(o)\) holds for \(\mu_B\)-almost every type. Collaborative semantics \(W_iA_j\), \(i,j\in\{1,2\}\), accepts such an \(o\) iff both selected conditions hold: \(W_1:\mu_B(\{t:w_t(o)\})>0\), \(W_2:w_B(o)\), \(A_1:a_t(o)\) for \(\mu_B\)-almost every type, and \(A_2:a_B(o)\).
Query answering returns all accepted outcomes. Its membership decision problem additionally receives \(o\in O\) and asks whether it is accepted. Let \(L\) be the total binary input length, \(q\) the query length, and \(d=\max_i|D_i|\); state running times in \(m,\tau,L,q,d\).

For each of the five semantics, is this membership decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For finite stakeholder lists, query semantics admit a correct translation into alternation-free modal \(\mu\)-calculus; evaluation is linear in the translated formula size and the explicit graph size, which can be exponential in \(m\). [Source](https://faculty.ist.psu.edu/vhonavar/Papers/ecai23.pdf)
Dominance testing for general CP-nets is \(\mathrm{PSPACE}\)-complete; this concerns individual dominance rather than the query problem defined here. [Source](https://arxiv.org/abs/1401.3453)
No result settling this precise mass-based query problem was located.

Classification

All five membership decision problems are \(\mathrm{NP}\)-hard under polynomial-time many-one reductions:

| Semantics | Proven classification |
|---|---|
| Consensus | \(\mathrm{NP}\)-hard |
| \(W_1A_1\) | \(\mathrm{NP}\)-hard |
| \(W_1A_2\) | \(\mathrm{NP}\)-hard |
| \(W_2A_1\) | \(\mathrm{NP}\)-hard |
| \(W_2A_2\) | \(\mathrm{NP}\)-hard |

Hardness holds with binary domains, support size \(\tau=1\), one preference statement, and one occurrence of the preference operator. Thus a polynomial-time algorithm for any of these problems would imply \(\mathrm{P}=\mathrm{NP}\).

1. Positive masses and singleton support

Because every listed mass is strictly positive, for every admissible \(B\) and every \(C\subseteq B\),
\[ \mu_B(C)>0\quad\Longleftrightarrow\quad C\ne\varnothing, \]
and
\[ \mu_B(C)=1\quad\Longleftrightarrow\quad C=B. \]
Indeed, normalization divides every positive mass by the positive number \(\mu(B)\). A nonempty subset consequently has positive mass, and omitting any member of \(B\) omits positive mass.

In particular, take \(T_\mu=B=\{t\}\) and \(\mu_t=1\). Then \(R_B=R_t\). At every preference operator, all five semantics accept precisely those \(o\in\llbracket\psi_1\rrbracket\cap O\) satisfying
\[ w_t(o)\land a_t(o). \]
This follows directly: both witness conditions reduce to \(w_t(o)\), both absence conditions reduce to \(a_t(o)\), and consensus requires their conjunction for the sole type.

2. Reduction from Boolean satisfiability

We reduce from \(\mathrm{3SAT}\), the \(\mathrm{NP}\)-complete problem of deciding whether a Boolean formula in conjunctive normal form, with three literals per clause, has a satisfying assignment.

Let \(F\) be such a formula over variables \(x_1,\ldots,x_n\). Introduce attributes
\[ X_1,\ldots,X_n,Z \]
with domain \(\{0,1\}\) for every attribute. Thus \(m=n+1\) and \(d=2\).

Use one type \(t\), of mass \(1\), whose preference list contains exactly the statement
\[ [\,](Z=1)\succ(Z=0)[\{X_1,\ldots,X_n\}], \]
where the condition is the empty partial assignment.

By the stipulated edge semantics, this statement induces an edge from every outcome with \(Z=0\) to every outcome with \(Z=1\): all other attributes belong to the set allowed to change arbitrarily. It induces no other edges between outcomes.

Translate \(F\) into an attribute formula \(F^\ast\) by replacing each positive literal \(x_i\) by \((X_i=1)\), and each negative literal \(\neg x_i\) by \((X_i=0)\), preserving conjunctions and disjunctions. For every outcome \(s\),
\[ s\models F^\ast \quad\Longleftrightarrow\quad (s(X_1),\ldots,s(X_n))\text{ satisfies }F. \]

Construct the query
\[ \psi=(Z=1)\;P_{\{t\}}\;\bigl((Z=0)\land F^\ast\bigr) \]
and the membership candidate
\[ o^\ast(Z)=1,\qquad o^\ast(X_i)=0\quad(1\leq i\leq n). \]

All domains, the statement, the query, and the candidate have total encoding length polynomial in the encoding length of \(F\). This is therefore a polynomial-time construction.

3. Correctness of the reduction

Fix any one of the five semantics. Write
\[ S=\llbracket(Z=0)\land F^\ast\rrbracket. \]

We verify every condition governing membership.

The candidate satisfies the left operand. By construction, \(o^\ast(Z)=1\), so
\[ o^\ast\in\llbracket Z=1\rrbracket\cap O. \]

The right operand contains exactly the satisfying assignments in the lower layer. At outcomes, its elements are precisely the assignments satisfying \(F\), together with \(Z=0\). Consequently,
\[ S\ne\varnothing\quad\Longleftrightarrow\quad F\text{ is satisfiable}. \]
Also, \(\bot\notin S\), because the atom \((Z=0)\) is false at \(\bot\).

The witness condition is equivalent to satisfiability. If \(S\ne\varnothing\), choose \(s\in S\). Since \(s(Z)=0\) and \(o^\ast(Z)=1\), the sole preference statement induces the edge \(s\to o^\ast\). This is a positive-length type-\(t\) path. Conversely, if \(S=\varnothing\), the existential condition defining \(w_t(o^\ast)\) is false. Therefore,
\[ w_t(o^\ast)\quad\Longleftrightarrow\quad F\text{ is satisfiable}. \]

The absence condition always holds. The outcome \(o^\ast\) has no outgoing edge. Every edge induced by the preference statement starts at an outcome with \(Z=0\), while all added edges involving \(\bot\) start at \(\bot\). Thus no positive-length path starts at \(o^\ast\), and
\[ a_t(o^\ast)=\mathrm{true}. \]

By the singleton-support equivalence established above, for each of the five semantics,
\[ o^\ast\in\llbracket\psi\rrbracket \quad\Longleftrightarrow\quad w_t(o^\ast)\land a_t(o^\ast) \quad\Longleftrightarrow\quad F\text{ is satisfiable}. \]
This proves all five hardness claims. The constructed graph is acyclic, so cycles are not needed for the reduction.

4. A running-time bound for arbitrary nested queries

Let
\[ N=|O|+1=1+\prod_{i=1}^{m}|D_i|\leq 1+d^m. \]
A direct explicit-graph algorithm evaluates any of the five semantics in time
\[ O\!\left((q+1)(\tau+1)(1+d^m)^2 \,\operatorname{poly}(L+m+\log(d+1))\right). \]

Here is a justification independent of any query translation.

First enumerate the \(N\) states and test each ordered pair against the listed preference descriptions. Checking a direct preference or a conditional statement takes polynomial time in the input length: check the condition at both endpoints, the specified values, and agreement on every coordinate required to remain unchanged. This constructs the labelled graph in
\[ N^2\operatorname{poly}(L+m+\log(d+1)) \]
time.

Next evaluate the query bottom-up, storing each subquery’s truth set, including its truth value at \(\bot\). Boolean operations use exactly the prescribed conventions; in particular, negation complements within \(O\).

For a preference operator with right-operand set \(S\), use either a singleton type graph or the union graph for \(B\). In the selected graph:

• Compute \(\{o:\exists s\in S,\ sR_Ho\}\) by starting with the immediate successors of \(S\), then closing under forward reachability.
• Compute \(\{o:\exists s\in S,\ oR_Hs\}\) by starting with the immediate predecessors of \(S\), then closing under backward reachability. Its complement within \(O\) gives the absence condition.

Starting with immediate neighbors enforces positive-length reachability, including the correct treatment of cycles. Each computation takes \(O(N+|E_H|)\), bounded by \(O(N^2)\). At most \(\tau+1\) selected graphs are needed per operator. Intersections and unions implement the required universal and existential conditions, using positivity of the masses from Section 1.

The explicit-graph model-checking approach discussed in the supplied [multi-stakeholder query paper](https://faculty.ist.psu.edu/vhonavar/Papers/ecai23.pdf) likewise measures evaluation against an explicit graph. Such bounds permit exponential dependence on \(m\), because the outcome space itself can have size \(d^m\).

5. Scope of the conclusion

The requested classification is completely settled: every semantics is \(\mathrm{NP}\)-hard. The proof does not assert that unrestricted membership belongs to \(\mathrm{NP}\), or establish its exact complexity beyond this hardness result.

⟨structured verdict parsed — rendered above⟩

The prover’s output is correct and rigorous. It establishes \(\mathrm{NP}\)-hardness for all five membership problems and supplies a valid exponential-time upper bound for arbitrary nested queries. No major or minor mathematical issues were found.

1. Positive masses and singleton support

Both mass equivalences are correct. Because every listed type has strictly positive mass and \(\mu(B)>0\), normalization preserves positivity. Thus a subset of \(B\) has positive normalized mass exactly when it is nonempty, and has normalized mass one exactly when it equals \(B\).

The singleton instance is admissible: \(\tau=1\), \(\mu_t=1\), and \(B=\{t\}\). Its union graph equals its individual type graph, so \(R_B=R_t\). Consequently:

• Both witness conditions reduce to \(w_t(o)\).
• Both absence conditions reduce to \(a_t(o)\).
• Consensus requires that same conjunction for the sole positive-mass type.

The claimed equivalence of all five semantics on singleton support is therefore exact.

2. Reduction construction and encoding

The reduction uses the standard \(\mathrm{NP}\)-complete decision problem \(\mathrm{3SAT}\), stated with its satisfiability criterion.

Every constructed input component satisfies the task’s requirements:

• All \(n+1\) domains are explicitly listed, finite, nonempty, and binary.
• The sole mass is a positive binary rational and is normalized.
• The statement has distinct preferred and dispreferred values.
• Its condition is the empty partial assignment.
• Its change set excludes \(Z\) and contains every other attribute.
• The query uses permitted atoms, Boolean connectives, and one admissible preference operator.
• The candidate is an explicitly specified member of \(O\).

The construction writes only these succinct descriptions, not the exponential outcome graph. Their combined encoding length is polynomial in the encoding length of \(F\). The polynomial-time construction claim is justified.

3. Induced edges

The statement induces exactly the asserted edges between outcomes.

An edge’s source must have \(Z=0\), and its target must have \(Z=1\). The empty condition imposes no restriction. Since every other coordinate belongs to \(Y\), the agreement requirement outside \(\{Z\}\cup Y\) imposes no additional restriction.

Thus every lower-layer outcome has an edge to every upper-layer outcome, and the statement induces no other outcome-to-outcome edges. The additional edges all originate at \(\bot\). In particular, every upper-layer outcome has no outgoing edge.

The acyclicity claim also holds, including the added state.

4. Right operand and satisfiability

The literal translation is correct on the binary domains: positive literals are represented by \(X_i=1\), and negative literals by \(X_i=0\). Preserving conjunction and disjunction therefore preserves the truth of \(F\) at each outcome.

Accordingly, the right operand denotes precisely the outcomes whose Boolean assignment satisfies \(F\) and whose \(Z\)-coordinate equals zero. Its nonemptiness is equivalent to satisfiability.

The treatment of \(\bot\) is correct: the atom \(Z=0\) is false there, so \(\bot\) cannot enter the right operand. No special convention for negation or constants affects this query.

5. Membership equivalence

The candidate satisfies the left operand because its \(Z\)-coordinate is one.

If the right operand is nonempty, every selected source has a direct type-\(t\) edge to the candidate. This is a positive-length path, so the witness condition holds. If the right operand is empty, the witness existential is false. Hence the witness condition is equivalent to satisfiability.

The absence condition always holds because the candidate has no outgoing edge. This excludes every positive-length path from the candidate, including paths that might otherwise arise through cycles. The added edges from \(\bot\) do not change this fact.

Combining these facts with the singleton-support equivalence establishes the displayed membership equivalence for each of the five semantics. This is a valid polynomial-time many-one reduction.

6. Running-time bound

The state count \(N=1+\prod_i|D_i|\leq 1+d^m\) is correct.

Testing ordered endpoint pairs against the explicitly listed preference descriptions takes polynomial time per pair in the input length and coordinate representation. Scanning the type lists and recording edge labels is covered by that polynomial factor. Thus the graph-construction bound is valid.

The reachability computations correctly enforce positive path length by initializing from immediate successors or predecessors. Subsequent closure includes precisely the endpoints of positive-length paths, including returns through cycles. Taking the backward-reachable set’s complement within \(O\) gives the required absence condition.

Bottom-up evaluation avoids repeated recursive evaluation of already computed subqueries. Each preference operator needs at most \(\tau\) individual graphs and one union graph. Boolean operations and the required intersections and unions fit within the stated bound:
\(O((q+1)(\tau+1)(1+d^m)^2\operatorname{poly}(L+m+\log(d+1)))\).

The ancillary source comparison is accurate: the supplied paper measures model checking against the explicit transition system and notes exponential outcome-space growth. The prover’s bound is justified independently of that translation. [Referenced paper, Section 5](https://faculty.ist.psu.edu/vhonavar/Papers/ecai23.pdf)

7. Scope and repair feedback

All five requested hardness classifications are established, including the claimed restrictions on domains, support size, statement count, and preference-operator count.

The prover correctly leaves unrestricted membership’s exact complexity open. Its implication concerning polynomial-time algorithms is conditional on \(\mathrm{P}\ne\mathrm{NP}\), as required.

Minimum additional clarification needed: none. No repair is necessary.

⟨structured verdict parsed — rendered above⟩