Computing Shapley Value in Supermodular Coalitional Games

Title:
Computing Shapley Value in Supermodular Coalitional Games
Authors:
Liben-Nowell, David; Sharp, Alexa; Wexler, Tom; Woods, Kevin
Abstract:
Coalitional games allow subsets (“coalitions”) of players to cooperate to receive a collective payoff. This payoff is then distributed “fairly” among the members of that coalition according to some division scheme. Various solution concepts have been proposed as reasonable schemes for generating fair allocations. The Shapley value is one classic solution concept: player i’s share is precisely equal to i’s expected marginal contribution if the players join the coalition one at a time, in a uniformly random order. In this paper, we consider the class of supermodular games (sometimes called “convex” games), define and survey computational results on other standard solution concepts, and contrast these results with new results regarding the Shapley value. In particular, we give a fully polynomial-time randomized approximation scheme (FPRAS) to compute the Shapley value to within a (1 plus/minus epsilon) factor in monotone supermodular games. We show that this result is tight in several senses: no deterministic algorithm can approximate Shapley value as well, no randomized algorithm can do better, and both monotonicity and supermodularity are required for the existence of an efficient (1 plus/minus epsilon)-approximation algorithm. We also argue that, relative to supermodularity, monotonicity is a mild assumption, and we discuss how to transform supermodular games to be monotonic.
Citation:
Liben-Nowell, David, Alexa Sharp, Tom Wexler, and Kevin Woods. 2012. "Computing Shapley Value in Supermodular Coalitional Games," in Proceedings of the International Meeting of the Computing and Combinatorics Conference.
Publisher:
Springer
DATE ISSUED:
2012
Department:
Mathematics
Type:
Conference Proceedings
PUBLISHED VERSION:
10.1007/978-3-642-32241-9_48
PERMANENT LINK:
http://hdl.handle.net/11282/309649

Full metadata record

DC FieldValue Language
dc.contributor.authorLiben-Nowell, Daviden_US
dc.contributor.authorSharp, Alexaen_US
dc.contributor.authorWexler, Tomen_US
dc.contributor.authorWoods, Kevinen_US
dc.date.accessioned2013-12-23T16:14:04Zen
dc.date.available2013-12-23T16:14:04Zen
dc.date.issued2012en
dc.identifier.citationLiben-Nowell, David, Alexa Sharp, Tom Wexler, and Kevin Woods. 2012. "Computing Shapley Value in Supermodular Coalitional Games," in Proceedings of the International Meeting of the Computing and Combinatorics Conference.en_US
dc.identifier.urihttp://hdl.handle.net/11282/309649en
dc.description.abstractCoalitional games allow subsets (“coalitions”) of players to cooperate to receive a collective payoff. This payoff is then distributed “fairly” among the members of that coalition according to some division scheme. Various solution concepts have been proposed as reasonable schemes for generating fair allocations. The Shapley value is one classic solution concept: player i’s share is precisely equal to i’s expected marginal contribution if the players join the coalition one at a time, in a uniformly random order. In this paper, we consider the class of supermodular games (sometimes called “convex” games), define and survey computational results on other standard solution concepts, and contrast these results with new results regarding the Shapley value. In particular, we give a fully polynomial-time randomized approximation scheme (FPRAS) to compute the Shapley value to within a (1 plus/minus epsilon) factor in monotone supermodular games. We show that this result is tight in several senses: no deterministic algorithm can approximate Shapley value as well, no randomized algorithm can do better, and both monotonicity and supermodularity are required for the existence of an efficient (1 plus/minus epsilon)-approximation algorithm. We also argue that, relative to supermodularity, monotonicity is a mild assumption, and we discuss how to transform supermodular games to be monotonic.en_US
dc.language.isoen_USen_US
dc.publisherSpringeren_US
dc.identifier.doi10.1007/978-3-642-32241-9_48en
dc.subject.departmentMathematicsen_US
dc.titleComputing Shapley Value in Supermodular Coalitional Gamesen_US
dc.typeConference Proceedingsen_US
dc.subject.keywordAlgorithmic game theoryen_US
dc.identifier.isbn978-3-642-32240-2en_US
All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.