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
| CREATOR | Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-22358