Group Strategyproof Mechanisms via Primal-Dual Algorithms

We develop a general method for turning a primal-dual algorithm into a group strategy proof cost-sharing mechanism. We use our method to design approximately budget balanced cost sharing mechanisms for two NP-complete problems: metric facility location, and single source rent-or-buy network design. Both mechanisms are competitive, group strategyproof and recover a constant fraction of the cost. For the facility location game our cost-sharing method recovers a 1/3rd of the total cost, while in the network design game the cost shares pay for a 1/15 fraction of the cost of the solution.

Authors

• Martin Pál
• Éva Tardos

Keywords

• Costs
• Turning
• Design methodology
• NP-complete problem
• IP networks
• Computer science
• Primal-dual Algorithm
• Group Strategy-proof
• Network Design
• Local Facilities
• Fraction Of The Cost
• Cost Of Solution
• Undirected
• Estimation Algorithm
• Shortest Path
• Set Of Behaviors
• Original Algorithm
• Group Of Agents
• Nash Equilibrium
• Sum Of Costs
• Ball Of Radius
• Operation Of Facilities
• Cost Recovery
• Network Cost
• Facilities In Settings
• Cost Allocation
• Facility Location Problem
• Network Design Problem
• Subset Of Users
• Source Vertex