# 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)

http://www.sciencedirect.com/science/article/pii/S0899825617300520

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:** https://EconPapers.repec.org/RePEc:eee:gamebe:v:108:y:2018:i:c:p:130-138

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 ().