Approximating the shapley value and shapley interactions

Kolpaczki, Patrick (2025): Approximating the shapley value and shapley interactions. Dissertation, LMU München: Fakultät für Mathematik, Informatik und Statistik

Abstract

Although the behavior of agents is often led by self-interest, many environments pose an incentive for cooperation by accomplishing a task together and thus be compensated collectively. This naturally leads to the search of a payout mechanism that assigns to each agent a share of the collective benefit which reflects its individual contribution to the completed task. Game theory models such scenarios by the notion of cooperative games in which the agents are the participating players. Within the game-theoretic framework, the Shapley value poses the most prominent solution to the emerging fair division problem, arguably capturing a widespread understanding of fairness. Over the last decade, the Shapley value has received unprecedented attention within the field of machine learning, attributing importance to entities such as features, datapoints, and structural components of predictive models. Especially the branch of explainable artificial intelligence picked it up as a means to provide understanding of the decision-making of increasingly complex and opaque models. Likewise, Shapley interactions which capture synergies between players have recently attracted attention. Unfortunately, the computational complexity of both quantities, the Shapley value and Shapley interaction, suffers from the exponential blow-up w.r.t. to the number of involved players and thus becomes quickly infeasible in practice. This incentivizes the research on approximation algorithms that return precise estimates while palpating the cooperative game as little as possible. In this thesis, we develop approximation algorithms that leverage novel representations of the Shapley value and Shapley interactions on the basis of mean estimation and weighted regression which allow for tailored sampling schemes. Given the Shapley value’s richness of applications, our methods are purposefully domain-independent without imposing structural assumptions. Consequently, they can be applied across the entire spectrum of emerging cooperative games. To this end, we place special emphasis on the variance reduction technique of stratification to develop methods that utilize the gathered information from each sample to a richer degree than in other representations possible and derive theoretical guarantees for the estimates’ precision. Empirical evaluations in the context of machine learning confirm the soundness of our propositions and their capability to display an advantage over competing methods.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Keywords: Game Theory, Shapley Value, Shapley Interaction, Approximation, Machine Learning
• Themengebiete: 000 Allgemeines, Informatik, Informationswissenschaft ; 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
• Fakultäten: Fakultät für Mathematik, Informatik und Statistik
• Sprache der Hochschulschrift: Englisch
• Datum der mündlichen Prüfung: 10. Oktober 2025
• 1. Bericht­erstatter:in: Hüllermeier, Eyke