Black-box reductions for cost-sharing mechanism design

DOI10.1016/j.geb.2013.08.012zbMath1419.91146OpenAlexW2013973040MaRDI QIDQ1735730

Konstantinos Georgiou, Chaitanya Swamy

Publication date: 29 March 2019

Published in: Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.geb.2013.08.012

zbMATH Keywords

linear programmingapproximation algorithmsalgorithmic mechanism designblack-box reductionscost-sharing mechanisms

Mathematics Subject Classification ID

Linear programming (90C05) Other game-theoretic models (91A40) Approximation algorithms (68W25)

Related Items (2)

On the Integrality Gap of the Prize-Collecting Steiner Forest LP ⋮ Introduction to the special issue -- Algorithmic Game Theory -- STOC/FOCS/SODA 2012

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A unified approach to approximating partial covering problems
• Cross-monotonic cost sharing methods for connected facility location games
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity
• Beyond Moulin mechanisms
• A factor 2 approximation algorithm for the generalized Steiner network problem
• New efficiency results for makespan cost sharing
• Fair cost-sharing methods for scheduling jobs on parallel machines
• A necessary and sufficient condition for rationalizability in a quasilinear context
• Primal-dual algorithms for connected facility location problems
• Incremental cost sharing: Characterization by coalition strategy-proofness
• Cost-sharing mechanisms for network design
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Bayesian algorithmic mechanism design
• Black-Box Reductions in Mechanism Design
• Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation
• Approximation Algorithms for Metric Facility Location Problems
• Quantifying inefficiency in cost-sharing mechanisms
• A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
• Cost Sharing Methods for Makespan and Completion Time Scheduling
• Strategy-Proof Allocation Mechanisms at Differentiable Points
• Optimal Auction Design
• Incentives in Teams
• A General Approximation Technique for Constrained Forest Problems
• Limitations of cross-monotonic cost-sharing schemes
• An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
• Applications of approximation algorithms to cooperative games
• Provisioning a virtual private network
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Optimal Efficiency Guarantees for Network Design Mechanisms
• Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems
• Is Shapley Cost Sharing Optimal?
• Group-Strategyproof Cost Sharing for Metric Fault Tolerant Facility Location
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders
• Sharing the cost of multicast transmissions
• Strategyproof sharing of submodular costs: budget balance versus efficiency

This page was built for publication: Black-box reductions for cost-sharing mechanism design