Approximating the Shapley Value via Multi-Issue Decomposition

DSpace/Manakin Repository

Approximating the Shapley Value via Multi-Issue Decomposition

Citable link to this page


Title: Approximating the Shapley Value via Multi-Issue Decomposition
Author: Soufiani, Hossein Azari; Chickering, David M.; Charles, Denis X.; Parkes, David C.

Note: Order does not necessarily reflect citation order of authors.

Citation: Soufiani, Hossein Azari, Denis J. Charles, David M. Chickering, and David C. Parkes. 2014. Approximating the Shapley Value via Multi-Issue Decomposition. Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2014), Lomuscio, Scerri, Bazzan, Huhns (eds.), May 5–9, 2014, Paris, France, 1209-1216.
Full Text & Related Files:
Abstract: The Shapley value provides a fair method for the division of value in coalitional games. Motivated by the application of crowdsourcing for the collection of suitable labels and features for regression and classification tasks, we develop a method to approximate the Shapley value by identifying a suitable decomposition into multiple issues, with the decomposition computed by applying a graph partitioning to a pairwise similarity graph induced by the coalitional value function. The method is significantly faster and more accurate than existing random-sampling based methods on both synthetic data and data representing user contributions in a real world application of crowdsourcing to elicit labels and features for classification.
Published Version:
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search