Economics at your fingertips  

Is Shapley cost sharing optimal?

Shahar Dobzinski, Aranyak Mehta, Tim Roughgarden and Mukund Sundararajan

Games and Economic Behavior, 2018, vol. 108, issue C, 130-138

Abstract: A general approach to the design of budget-balanced cost-sharing mechanisms is to use the Shapley value, applied to the given cost function, to define payments from the players to the mechanism. Is the corresponding Shapley value mechanism “optimal” in some sense? We consider the objective of minimizing worst-case inefficiency subject to a revenue constraint, and prove results in three different regimes. First, for the public excludable good problem, the Shapley value mechanism minimizes the worst-case efficiency loss over all truthful, deterministic, and budget-balanced mechanisms that satisfy equal treatment. Second, even with randomization and approximate budget-balance allowed and dropping equal treatment, the worst-case efficiency loss of the Shapley value mechanism is within a constant factor of the minimum possible. Third, for no-deficit mechanisms, we prove a general positive result: for every monotone cost function, a suitable blend of the VCG and Shapley value mechanisms is no-deficit and enjoys good approximate efficiency guarantees.

Keywords: Shapley value; Cost-sharing mechanisms; Approximate efficiency (search for similar items in EconPapers)
JEL-codes: D82 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations Track citations by RSS feed

Downloads: (external link)
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link:

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Dana Niculescu ().

Page updated 2018-08-04
Handle: RePEc:eee:gamebe:v:108:y:2018:i:c:p:130-138