DROPS

Document

Short Paper

DOI: 10.4230/LIPIcs.SAT.2026.33

Shapley-Shubik Attribution from Minimal Subsets (Short Paper)

Authors: Pablo Martínez-Naredo, Raúl Mencía, Joao Marques-Silva, and Carlos Mencía

Published in: LIPIcs, Volume 377, 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)

Abstract

We address the problem of attributing responsibility to individual clauses for the unsatisfiability of a propositional formula. Recent work adopted the Shapley-Shubik power index, proposing a probabilistic approximation algorithm. However, although polynomial, the required number of SAT solver calls becomes impractical when the input formula is not easy to solve. In such cases, it is often possible to enumerate a partial set of minimal unsatisfiable subsets (MUSes) and minimal correction subsets (MCSes). In this paper, we demonstrate that these subsets can be leveraged to efficiently bound and approximate the Shapley-Shubik index. We introduce a framework that exploits the structural information provided by the available sets to derive useful attribution explanations.

Cite as

Pablo Martínez-Naredo, Raúl Mencía, Joao Marques-Silva, and Carlos Mencía. Shapley-Shubik Attribution from Minimal Subsets (Short Paper). In 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 377, pp. 33:1-33:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{martineznaredo_et_al:LIPIcs.SAT.2026.33,
  author =	{Mart{\'\i}nez-Naredo, Pablo and Menc{\'\i}a, Ra\'{u}l and Marques-Silva, Joao and Menc{\'\i}a, Carlos},
  title =	{{Shapley-Shubik Attribution from Minimal Subsets}},
  booktitle =	{29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)},
  pages =	{33:1--33:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-431-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{377},
  editor =	{Ignatiev, Alexey and Szeider, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2026.33},
  URN =		{urn:nbn:de:0030-drops-263398},
  doi =		{10.4230/LIPIcs.SAT.2026.33},
  annote =	{Keywords: Unsatisfiability, Shapley-Shubik index, MUSes and MCSes}
}

Search Results

Documents authored by Martínez-Naredo, Pablo

Shapley-Shubik Attribution from Minimal Subsets (Short Paper)

Abstract

Cite as

Thanks for your feedback!

Could not send message