Approximating the Shapley Value via Multi-Issue Decomposition
Soufiani, Hossein Azari
Charles, Denis X.
Chickering, David M.
MetadataShow full item record
CitationSoufiani, 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.
AbstractThe 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.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:33009618
- FAS Scholarly Articles