| paper | Shapley Value Computation in Ontology-Mediated Query Answering (Extended Abstract) |
| authors | Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade |
| venue | IJCAI 2025 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 7
statement extracted from the paper’s text layer
Fix \(Q=(T,q)\). Given finitely many complete case types \(t\in[\tau]\), rational masses \(\mu_t\ge0\) summing to \(1\), and partitioned local ABoxes \(A_t=X_t\uplus E_t\), compute the exact vector \(\Phi_{t,e}=\mu_t\phi_t(e)\) for \(e\in E_t\), where \(\phi_t(e)=\operatorname{Sh}(E_t,v_t,e)\) and \(v_t(S)=\mathbf{1}[(X_t\cup S,T)\u005models q]-\mathbf{1}[(X_t,T)\u005models q]\); for Theorem 8, require every \(A_t\) to be \(T\)-consistent.
A cohort of independent recurring cases: each population type is a complete partitioned local knowledge base with endogenous assertions \(E_t\), mass \(\mu_t\), and objective the exact mass-weighted expected local Shapley responsibility \(\Phi_{t,e}\); no assertion is fractionalized.
The objective \(\Phi_{t,e}=\mu_t\phi_t(e)\) is a new additive, two-level game rather than the Shapley value of the union of repeated cases under Boolean entailment, so the claimed clone-preservation dictionary is not exact for the paper's original semantics.
fatal: False
The mirror covers Theorem 7's \(\mathrm{FP}/\#\mathrm{P}\)-hard dichotomy and Theorem 8's consistent-ABox \(\#\mathrm{P}\)-hardness; it leaves Propositions 3–5, Theorem 9, and the paper's separate probabilistic-query results unmirrored.
The strongest honest mirror is a population of repeated, query-bearing cases rather than a database in which individual facts are replaced by fractional facts. That distinction matters: facts remain discrete inside each case, while the population of cases is represented by rational masses.
My lead anchor is Theorem 7, proved in this paper. Its proof uses the previously established Theorem 1 from Bienvenu et al. (2024b), but the OMQ dichotomy stated as Theorem 7 is a result of this paper: for a connected constant-free homomorphism-closed query \(q\) and an \(\mathrm{ELHI}_{\bot}\) ontology \(T\), \(SVC_{(T,q)}\equiv_P SPPQE_{(T,q)}\); moreover, the problem is in \(\mathrm{FP}\) when \((T,q)\) rewrites into a safe UCQ, and is \(\#P\)-hard otherwise.
Call the mirror Cohort-SVC\(_Q\). Fix \(Q=(T,q)\). An instance consists of finitely many case types \(t\in\{1,\ldots,\tau\}\), rational masses \(\mu_t\) summing to \(1\), and, for each type, a partitioned local ABox \(A_t=X_t\uplus E_t\). Here \(X_t\) contains exogenous assertions and \(E_t\) contains endogenous assertions whose explanatory contribution is to be measured. A case type includes the complete query-relevant structure: its local constants, assertions, endogenous/exogenous partition, and source labels. Cases of the same type are indistinguishable for the purposes of the query. The intended regime is \(N\gg\tau\): many hospital episodes, eligibility files, recipes, or compliance records, drawn from a moderate number of recurring evidence patterns.
For \(S\subseteq E_t\), define \(v_t(S)=\mathbf 1[(X_t\cup S,T)\models q]-\mathbf 1[(X_t,T)\models q]\). For each endogenous assertion \(e\in E_t\), let \(\phi_t(e)\) be its ordinary Shapley value in this local game, and report its population contribution as \(\Phi_{t,e}=\mu_t\phi_t(e)\). The computational problem is: given the rational type distribution and the local partitioned ABoxes, compute the exact vector \(\Phi\). The action being explained is disclosure or retention of an assertion in a case; the objective is expected marginal contribution to the population’s query answers. No fact, ranking, or ontology axiom is fractionalized.
This has an exact high-multiplicity dictionary. If \(\mu_t=n_t/N\), create \(n_t\) renamed copies of case type \(t\), with fresh local constants, and ask for the normalized total Shapley contribution over all cases. Conversely, any finite repeated-case population compresses to these masses. Thus clearing denominators preserves query truth, coalition values, Shapley coefficients, and certificates. The population is genuinely continuous at the outer level, while the paper’s cooperative game remains intact at the case level.
The expected complexity follows the named theorem. For a fixed safe-UCQ-rewritable \(Q\), compute the local Shapley values using the paper’s \(\mathrm{FP}\) procedure and aggregate them with the rational \(\mu_t\); this is a Class A mass-compressed problem, polynomial in the total type description, \(\tau\), and the encoding length of the masses. For a fixed non-safe \(Q\), hardness transfers: take \(\tau=1\) and \(\mu_1=1\), repeat the same case arbitrarily many times, and the requested coordinate \(\Phi_{1,e}\) is exactly the original SVC instance. The hardness lives in the query/ontology structure and the internal evidence graph, not in the number of population members. This is a Class B mirror.
A second worthwhile anchor is Theorem 8, also proved here. It removes the connectedness and constant-free restrictions: for a UCQ \(q\) and an \(\mathrm{ELHI}_{\bot}\) ontology \(T\), if \(Q=(T,q)\) is non-FO-rewritable with respect to consistent ABoxes, then \(SVC_Q\) is \(\#P\)-hard. The corresponding Consistent Cohort-SVC\(_Q\) problem uses exactly the same instance format, but requires every local ABox \(A_t\) to be consistent with \(T\), and asks for the exact population-weighted Shapley vector. Its expected classification is again Class B by the \(\tau=1\) embedding. This is not merely a safe-query artefact: constants, disconnected query structure, and ontology-mediated non-rewritability remain computationally visible even after the population is compressed.
The mirror is plausible because OMQA is naturally deployed over repeated cases rather than one-off databases: a public or institutional decision is made for a large population, while each case contains a structured evidence graph and the system must explain which assertions caused the answer. The original authors would likely recognize “compute aggregate responsibility of evidence types across a recurring case population” as an extension of their quantitative-explanation problem. The paper’s probabilistic-query connections are useful machinery here, but I am not claiming that probabilistic databases alone constitute continuization; the continuous object is the distribution of cases.
The weakest point is that this is an extension, not a literal atomless Shapley game over one global database. A naïve continuum of duplicate facts would collapse under set semantics, and individual Shapley values would become meaningless or vanish under replication. The construction avoids that defect by making cases, not facts, the population agents and by reporting mass-weighted aggregate responsibility. Consequently, the continuous layer may compress repeated instances without removing the underlying \(\#P\)-hardness. That limits the claim: this paper supports a credible high-multiplicity mirror and a transferred dichotomy, but not yet a new continuum-specific Shapley theory.
The natural follow-up questions are whether local case types admit further compact representations, whether shared evidence sources across cases can be modeled without losing identity information, and whether a genuine Aumann–Shapley limit can be obtained under a smooth aggregate-query semantics.
The strongest negative case is that the proposed continuum sits outside the paper’s computational object.
Both Theorem 7 and Theorem 8 study Shapley values of *assertions in one finite knowledge base*. The players are ABox facts or TBox axioms, and the characteristic function is Boolean entailment:
\[
v(S)=\mathbf 1[(A_X\cup S,T)\models q]-\mathbf 1[(A_X,T)\models q].
\]
A population of cases is not present in this game.
The proposed Cohort-SVC construction therefore changes the value function. If \(n\) renamed copies of a case are combined into one database, the paper’s Boolean query evaluates to an OR across the copies:
\[
V(S)=\mathbf 1[\text{some copy entails }q].
\]
The Shapley value of a fact in one copy then depends on whether other copies already make \(q\) true. It is not the local Shapley value \(\phi_t(e)\). The proponent’s desired aggregation,
\[
\sum_t \mu_t\phi_t(e),
\]
is obtained only by defining a new additive game,
\[
V(S)=\sum_i v_i(S_i),
\]
or its normalized version. That is a reasonable expected-responsibility objective, but it is not the SVC problem studied in either theorem. The claimed rational-clone preservation therefore fails at the level of coalition values, not merely at the level of notation.
The alternatives do not repair this without changing the question. If whole cases become the population agents, the result measures the responsibility of a case, not of an assertion. If assertions themselves become infinitesimal population mass, ordinary ABox semantics breaks: databases are sets, fractional facts have no interpretation, and duplicated assertions collapse. An Aumann–Shapley replacement would require a new value function on measurable coalitions, while Boolean entailment is discontinuous and often turns on one exact edge, constant, or path. The paper supplies no natural atomless Shapley object.
There is also a more structural obstruction. In the hardness results based on reachability, an assertion’s value depends on its exact endpoints and on the surrounding graph. A mass of “role assertions of type \(r\)” does not determine whether those edges form a path, whether they meet at the relevant individual, or whether they participate in a witness for the query. Preserving that information requires making the entire rooted evidence graph part of the type. At that point the type is an arbitrary finite database, with its constants, incidence structure, endogenous partition, and query target. The continuum has ceased to be a finite population of meaningful agent types and has become a distribution over complete input instances.
This is especially damaging to the \(\tau=1\) hardness argument. Taking one type with mass \(1\), where the type description contains the whole \(\#\mathrm P\)-hard ABox, proves only that an arbitrary SVC instance can be labelled a population of one case. It does not exhibit a high-multiplicity regime. Repeating that case and multiplying the final answer adds no population semantics; the hard computation remains entirely inside the single atomic type. The same trick could turn any database problem into a purported continuous-population problem.
Theorem 8 creates an additional problem rather than solving this one. Its stronger result concerns constants, disconnected UCQs, and consistency of individual ABoxes. With renamed cases, constants and joins become case-local, so the original query is changed. With shared constants, cases interact: a union can create witnesses spanning cases, alter disconnected-query satisfaction, and affect consistency. To retain the theorem’s semantics one must evaluate the query separately in every case and then average the results, which is precisely the new additive cohort model rather than a continuization of the original SVC game.
Thus Theorem 7 and Theorem 8 do not yield a direct continuous mirror. The natural direct limit is either undefined or loses the graph and identity information on which Shapley responsibility depends. The natural repair—a distribution over repeated evidence-bearing cases with an additive expected-explanation objective—is an application-inspired re-modelling. It may be useful, but its complexity is obtained by running the paper’s finite SVC procedure inside each case and aggregating the outputs; it does not expose a population-level Shapley problem.
The universal negative claim is not airtight. Repeated institutional records with genuinely recurring evidence patterns are a plausible high-multiplicity setting, and a carefully presented cohort-responsibility problem could be worthwhile as an extension. But that concession is precisely the limit of the negative case: the paper does not itself support a faithful continuous mirror of either theorem. It supports, at most, a new distribution-over-instances model whose population layer is external to the paper’s computational semantics.
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.