Shapley Revisited: Tractable Responsibility Measures for Query Answers

Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade · 2025

Read Shapley Revisited: Tractable Responsibility Measures for Query Answers by Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-22358.txt.

Description

Meghyn Bienvenu, Diego Figueira, and Pierre Lafourcade rethink, in a 2025 database theory paper, how to assign blame to facts when a query answer comes out true. A popular game-based score is elegant but brutally hard to compute, even for simple queries. The authors propose a new family of scores built from weighted sums over the smallest fact sets that already force the answer.

Their scores meet the intuitive fairness demands one would list. A surprise theorem shows each of them is secretly the game score of a suitably built game. Better still, they are cheap to compute for wide query classes, including unions of simple patterns. The paper maps where the cheapness holds and where it breaks.

Catalog record

CREATORMeghyn Bienvenu, Diego Figueira, Pierre Lafourcade
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE97 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-22358

Browse the full library · About the Tower of Babel