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

Braess's paradoxrandom graphsselfish routing

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

(33)

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

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)