Efficient Black-Box Reductions for Separable Cost Sharing

• 成果类型: Article
• 署名作者: Harks, Tobias; Hoefer, Martin; Schedel, Anja; Surek, Manuel
• 署名单位: University of Augsburg; Goethe University Frankfurt
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2020.1050
• 发表日期: 2021
• 页码: 134-158
• 关键词: Facility location; approximation algorithm; Network design; spanning tree; price; STABILITY; equilibria; allocation; core

摘要

In cost-sharing games with delays, a set of agents jointly uses a subset of resources. Each resource has a fixed cost that has to be shared by the players, and each agent has a nonshareable player-specific delay for each resource. A separable cost-sharing protocol determines cost shares that are budget-balanced, separable, and guarantee existence of pure Nash equilibria (PNE). We provide black-box reductions reducing the design of such a protocol to the design of an approximation algorithm for the underlying cost-minimization problem. In this way, we obtain separable cost-sharing protocols in matroid games, single-source connection games, and connection games on n-series-parallel graphs. All these reductions are efficiently computable - given an initial allocation profile, we obtain a cheaper profile and separable cost shares turning the profile into a PNE. Hence, in these domains, any approximation algorithm yields a separable cost-sharing protocol with price of stability bounded by the approximation factor.