The Shapley Axiomatization for Values in Partition Function Games
One of the long-debated issues in coalitional game theory is how to extend the Shapley value to games with externalities (partition-function games). When externalities are present, not only can a player’s marginal contribution—a central notion to the Shapley value—be defined in a variety of ways, bu...
| Main Authors: | , , |
|---|---|
| Format: | Report |
| Published: |
DCS
2013
|
| _version_ | 1826267787272650752 |
|---|---|
| author | Skibski, O Michalak, T Wooldridge, M |
| author_facet | Skibski, O Michalak, T Wooldridge, M |
| author_sort | Skibski, O |
| collection | OXFORD |
| description | One of the long-debated issues in coalitional game theory is how to extend the Shapley value to games with externalities (partition-function games). When externalities are present, not only can a player’s marginal contribution—a central notion to the Shapley value—be defined in a variety of ways, but it is also not obvious which axiomatization should be used. Consequently, a number of authors extended the Shapley value using complex and often unintuitive axiomatizations. Furthermore, no algorithm to approximate any extension of the Shapley value to partition-function games has been proposed to date. Given this background, we prove in this paper that, for any well-defined measure of marginal contribution, Shapley’s original four axioms imply a unique value for games with externalities. As an consequence of this general theorem, we show that values proposed by Macho-Stadler et al., McQuillin and Bolger can be derived from Shapley’s axioms. Building upon our analysis of marginal contribution, we develop a general algorithm to approximate extensions of the Shapley value to games with externalities using a Monte Carlo simulation technique. |
| first_indexed | 2024-03-06T20:59:34Z |
| format | Report |
| id | oxford-uuid:3a6ccb3a-6bf5-4e76-b182-0a48deb775ea |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:59:34Z |
| publishDate | 2013 |
| publisher | DCS |
| record_format | dspace |
| spelling | oxford-uuid:3a6ccb3a-6bf5-4e76-b182-0a48deb775ea2022-03-26T14:01:27ZThe Shapley Axiomatization for Values in Partition Function GamesReporthttp://purl.org/coar/resource_type/c_93fcuuid:3a6ccb3a-6bf5-4e76-b182-0a48deb775eaDepartment of Computer ScienceDCS2013Skibski, OMichalak, TWooldridge, MOne of the long-debated issues in coalitional game theory is how to extend the Shapley value to games with externalities (partition-function games). When externalities are present, not only can a player’s marginal contribution—a central notion to the Shapley value—be defined in a variety of ways, but it is also not obvious which axiomatization should be used. Consequently, a number of authors extended the Shapley value using complex and often unintuitive axiomatizations. Furthermore, no algorithm to approximate any extension of the Shapley value to partition-function games has been proposed to date. Given this background, we prove in this paper that, for any well-defined measure of marginal contribution, Shapley’s original four axioms imply a unique value for games with externalities. As an consequence of this general theorem, we show that values proposed by Macho-Stadler et al., McQuillin and Bolger can be derived from Shapley’s axioms. Building upon our analysis of marginal contribution, we develop a general algorithm to approximate extensions of the Shapley value to games with externalities using a Monte Carlo simulation technique. |
| spellingShingle | Skibski, O Michalak, T Wooldridge, M The Shapley Axiomatization for Values in Partition Function Games |
| title | The Shapley Axiomatization for Values in Partition Function Games |
| title_full | The Shapley Axiomatization for Values in Partition Function Games |
| title_fullStr | The Shapley Axiomatization for Values in Partition Function Games |
| title_full_unstemmed | The Shapley Axiomatization for Values in Partition Function Games |
| title_short | The Shapley Axiomatization for Values in Partition Function Games |
| title_sort | shapley axiomatization for values in partition function games |
| work_keys_str_mv | AT skibskio theshapleyaxiomatizationforvaluesinpartitionfunctiongames AT michalakt theshapleyaxiomatizationforvaluesinpartitionfunctiongames AT wooldridgem theshapleyaxiomatizationforvaluesinpartitionfunctiongames AT skibskio shapleyaxiomatizationforvaluesinpartitionfunctiongames AT michalakt shapleyaxiomatizationforvaluesinpartitionfunctiongames AT wooldridgem shapleyaxiomatizationforvaluesinpartitionfunctiongames |