Black-box reductions for cost-sharing mechanism design
From MaRDI portal
Publication:1735730
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
linear programmingapproximation algorithmsalgorithmic mechanism designblack-box reductionscost-sharing mechanisms
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