Optimal Efficiency Guarantees for Network Design Mechanisms

DOI10.1007/978-3-540-72792-7_35MaRDI QIDQ5429287zbMATH OpenOpenAlexFDO

Authors Tim Roughgarden, Mukund Sundararajan

Publication date 29 November 2007

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-72792-7_35

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Applications of game theory (91A80) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

• New trade-offs in cost-sharing mechanisms
• Quantifying inefficiency in cost-sharing mechanisms
• Cost-sharing mechanisms for network design
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Is Shapley cost sharing optimal?

Cited in

(23)

• Is Shapley cost sharing optimal?
• Black-box reductions for cost-sharing mechanism design
• Subscription mechanisms for network formation.
• Bayes-Nash equilibria of the generalized second-price auction
• An ascending implementation of the Vickrey-Clarke-Groves mechanism for the licensed shared access
• Cost-sharing mechanisms for network design
• Designing budget-balanced best-response mechanisms for network coordination games
• On Uniformly Optimal Networks: A Reversal of Fortune?
• New trade-offs in cost-sharing mechanisms
• From cost sharing mechanisms to online selection problems
• Near-optimal network design with selfish agents
• Cost-sharing mechanisms for scheduling under general demand settings
• A characterization of undirected graphs admitting optimal cost shares
• Efficient cost-sharing mechanisms for prize-collecting problems
• Necessary and sufficient condition for non-concave network utility maximisation
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems
• Is Shapley Cost Sharing Optimal?
• Group-Strategyproof Cost Sharing for Metric Fault Tolerant Facility Location
• Black-box reductions for cost-sharing mechanism design
• Approximation algorithms for directed weighted spanners
• Beyond Moulin mechanisms
• Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems

This page was built for publication: Optimal Efficiency Guarantees for Network Design Mechanisms

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