AlgorithmAlgorithm: AI-adaptedProof: Not applicablePipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Monte Carlo permutation estimator for Shapley effects

Definition

Input: A finite player set $[d]$ , exact coalition values $v (S)$ with $v (\emptyset) = 0$ , $v ([d]) = V > 0$ , and a declared integer sample size $n \geq 2$ .

Draw $n$ independent permutations $π_{1}, \dots, π_{n}$ , each uniformly from the $d!$ permutations of $[d]$ .
For each row $r$ and each $i$ , compute $Δ_{i}^{(r)} = v (P_{i}^{π_{r}} \cup {i}) - v (P_{i}^{π_{r}})$ .
Return ${\hat{ϕ}}_{i} = (n V)^{- 1} \sum_{r} Δ_{i}^{(r)}$ and the standard-error covariance estimate ${\hat{Σ}}_{Δ} / (n V^{2})$ , where ${\hat{Σ}}_{Δ} = (n - 1)^{- 1} \sum_{r} (Δ^{(r)} - \overset{ˉ}{Δ}) (Δ^{(r)} - \overset{ˉ}{Δ})^{T}$ .

The exact conditional-variance evaluation is an input oracle. This permutation sampling procedure does not supply a conditional sampler or bound its numerical error.

Depends on

Shapley effects for dependent inputs

Used by

Monte Carlo permutation Shapley effects have a joint CLT Theorem

Dependency tree · two levels

4 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Eunhye Song, Barry L. Nelson, and Jeremy Staum, Shapley Effects for Global Sensitivity Analysis: Theory and Computation, §4.1 (standard reference, not scraped)