Click here to flash read.
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.
