A Unifying Formal Approach to Importance Values in Boolean Functions

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Abstract

Boolean functions and their representation through logics, circuits, machine learning classifiers, or binary decision diagrams (BDDs) play a central role in the design and analysis of computing systems. Quantifying the relative impact of variables on the truth value by means of importance values can provide useful insights to steer system design and debugging. In this paper, we introduce a uniform framework for reasoning about such values, relying on a generic notion of importance value functions (IVFs). The class of IVFs is defined by axioms motivated from several notions of importance values introduced in the literature, including Ben-Or and Linial's influence and Chockler, Halpern, and Kupferman's notion of responsibility and blame. We establish a connection between IVFs and game-theoretic concepts such as Shapley and Banzhaf values, both of which measure the impact of players on outcomes in cooperative games. Exploiting BDD-based symbolic methods and projected model counting, we devise and evaluate practical computation schemes for IVFs.

Details

Original languageEnglish
Title of host publicationProceedings of the 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023
EditorsEdith Elkind
PublisherInternational Joint Conferences on Artificial Intelligence
Pages2728-2737
Number of pages10
ISBN (electronic)978-1-956792-03-4
Publication statusPublished - 2023
Peer-reviewedYes

Publication series

SeriesIJCAI International Joint Conference on Artificial Intelligence
Volume2023-August
ISSN1045-0823

Conference

Title32nd International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI 2023
Conference number32
Duration19 - 25 August 2023
Website
Degree of recognitionInternational event
LocationSheraton Grand Macao
CityMacao
CountryChina

External IDs

ORCID /0000-0002-5321-9343/work/160951233

Keywords

ASJC Scopus subject areas