一句话：将 Shapley 值引入查询回答，量化元组对合取与聚合查询答案的贡献，并给出复杂度与近似算法。
本文研究如何用合作博弈论中的 Shapley 值量化数据库元组对查询答案的贡献。作者针对合取查询和聚合查询定义相应的联盟博弈，使元组的 Shapley 值反映其边际影响。论文系统分析该值计算的算法与复杂度，给出可处理情形和难解情形，并为难解情形设计近似算法。该工作将 Shapley 值引入数据管理中的查询回答，为解释查询结果和元组责任归因提供新工具。
We investigate the application of the Shapley value to quantifying the contribution of a tuple to a query answer. The Shapley value is a widely known numerical measure in cooperative game theory and in many applications of game theory for assessing the contribution of a player to a coalition game. It has been established already in the 1950s, and is theoretically justified by being the very single wealth-distribution measure that satisfies some natural axioms. While this value has been investigated in several areas, it received little attention in data management. We study this measure in the context of conjunctive and aggregate queries by defining corresponding coalition games. We provide algorithmic and complexity-theoretic results on the computation of Shapley-based contributions to query answers; and for the hard cases we present approximation algorithms.
@article{paperbot1281,
title = {The Shapley Value of Tuples in Query Answering},
author = {Ester Livshits and Leopoldo Bertossi and Benny Kimelfeld and Moshe Sebag},
journal = {Logical Methods in Computer Science},
volume = {Volume 17, Issue 3},
year = {2021},
doi = {10.46298/lmcs-17(3:22)2021}
}