New trade-offs in cost-sharing mechanisms

DOI10.1145/1132516.1132528MaRDI QIDQ2931372zbMATH OpenOpenAlexFDO

Authors Tim Roughgarden, Mukund Sundararajan

Publication date 25 November 2014

Published in Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1132516.1132528

zbMATH Keywords

random graphsselfish routingBraess's paradox

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Auctions, bargaining, bidding and selling, and other market models (91B26) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Production theory, theory of the firm (91B38)

Recommendations

• Optimal Efficiency Guarantees for Network Design Mechanisms
• Quantifying inefficiency in cost-sharing mechanisms
• Strategyproof sharing of submodular costs: budget balance versus efficiency
• Is Shapley cost sharing optimal?
• The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms

Cited in

(31)

• Strategyproof sharing of submodular costs: budget balance versus efficiency
• Cost sharing in two-sided markets
• Almost budget-balanced VCG mechanisms to assign multiple objects
• Quantifying inefficiency in cost-sharing mechanisms
• Group strategyproof cost sharing: the role of indifferences
• Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems
• Designing cost-sharing methods for Bayesian games
• Budget-balanced and strategy-proof auctions for ridesharing
• Beyond Moulin mechanisms
• Asymmetric cost sharing mechanisms
• Subscription mechanisms for network formation.
• Responsibility and cross-subsidization in cost sharing
• Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems
• An efficient and almost budget balanced cost sharing method
• Group-Strategyproof Cost Sharing for Metric Fault Tolerant Facility Location
• Approximation and Online Algorithms
• Black-box reductions for cost-sharing mechanism design
• Mechanism design for set cover games with selfish element agents
• From cost sharing mechanisms to online selection problems
• Online cooperative cost sharing
• On demand responsiveness in additive cost sharing
• Is Shapley Cost Sharing Optimal?
• Limitations of cross-monotonic cost-sharing schemes
• Combinatorial reallocation mechanisms
• Cost-sharing models in participatory sensing
• Limitations of cross-monotonic cost sharing schemes
• New efficiency results for makespan cost sharing
• A subsidized Vickrey auction for cost sharing
• Cost sharing under increasing returns: A comparison of simple mechanisms
• Optimal Efficiency Guarantees for Network Design Mechanisms
• On the Approximability of Combinatorial Exchange Problems

This page was built for publication: New trade-offs in cost-sharing mechanisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931372)