If You Like Shapley Then You’ll Love the Core

Authors

  • Tom Yan Carnegie Mellon University
  • Ariel D. Procaccia Harvard University

Keywords:

Cooperative Game Theory

Abstract

The prevalent approach to problems of credit assignment in machine learning -- such as feature and data valuation -- is to model the problem at hand as a cooperative game and apply the Shapley value. But cooperative game theory offers a rich menu of alternative solution concepts, which famously includes the core and its variants. Our goal is to challenge the machine learning community's current consensus around the Shapley value, and make a case for the core as a viable alternative. To that end, we prove that arbitrarily good approximations to the least core -- a core relaxation that is always feasible -- can be computed efficiently (but prove an impossibility for a more refined solution concept, the nucleolus). We also perform experiments that corroborate these theoretical results and shed light on settings where the least core may be preferable to the Shapley value.

Downloads

Published

2021-05-18

How to Cite

Yan, T., & Procaccia, A. D. (2021). If You Like Shapley Then You’ll Love the Core. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5751-5759. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16721

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms