Is Shapley cost sharing optimal?

• 成果类型: Article
• 署名作者: Dobzinski, Shahar; Mehta, Aranyak; Roughgarden, Tim; Sundararajan, Mukund
• 署名单位: Weizmann Institute of Science; Alphabet Inc.; Google Incorporated; Stanford University; Stanford University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2017.03.008
• 发表日期: 2018
• 页码: 130-138
• 关键词: Shapley value; Cost-sharing mechanisms; Approximate efficiency

摘要

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. (C) 2017 Elsevier Inc. All rights reserved.