Approximation methodology of Shapley values and generalization of values toward egalitarian approaches to Shapley values Pohang University of Science and Technology

Abstract

The study of solution concepts in cooperative game theory, such as the Shapley value, can be broadly categorized into two major streams: computational aspects and axiomatic aspects. This dissertation explores both directions, providing innovative computational methods and theoretical advancements that enhance the understand- ing and application of Shapley values in various contexts. By integrating these two perspectives, this research offers a comprehensive approach to addressing the com- plexities and nuances of cooperative game theory. The Shapley value is a cornerstone solution concept in coalitional game theory, renowned for providing a unique and fair solution. Its recent applications in machine learning and the sharing economy have sparked significant interest. However, the exact computation of Shapley values remains computationally intensive due to the ne- cessity of evaluating all possible player coalitions, an exponential process relative to the number of players. To address this, we propose a novel method for approximat- ing the Shapley value in linear time for general coalitional games. Additionally, we introduce a groundbreaking method to obtain the supremum of error bound (SEB) for the approximated Shapley value, providing a new and valuable measure of accuracy. Furthermore, we develop an innovative algorithm for the inverse Shapley value with its corresponding error bound. Our experimental results, involving over 300 play- ers, demonstrate that our method not only achieves significant time efficiency but also upholds the critical efficiency property of the Shapley value. In parallel, we explore a new class of solutions that generalize the weighted- egalitarian Shapley values, allowing for player heterogeneity in both the Shapley value and the equal division value. This study introduces axioms such as weak monotonic- ity, weak differential null player out, efficiency, null game, ratio invariance for null players, and weak superweak differential marginality to derive the proposed value. These axioms support the formulation of a robust and flexible solution concept that accommodates a diverse range of player contributions and preferences. Moreover, we contribute to the ongoing debate on economic distribution, which seeks a balance between marginalism and egalitarianism in allocation problems. We advance the generalization of transferable utility (TU) values. Our research delineates the axiomatic properties of four classes of TU-values, including convex combinations of weighted division values with Shapley values, positively weighted Shapley values, weighted Shapley values, random order values, and the Harsanyi set. We show that the axiomatization of these adjacent classes differs by only one axiom, highlighting a systematic progression in the generalization of solution classes and the corresponding weakening of axioms. – III –