Cost sharing over combinatorial domains : Complement-free cost functions and beyond

DOI10.4230/LIPICS.ESA.2019.20MaRDI QIDQ5075756zbMATH OpenOpenAlexFDO

Authors Georgios Birmpas, Evangelos Markakis, Guido Schäfer

Publication date 11 May 2022

Full work available at URL https://arxiv.org/abs/1910.06384

zbMATH Keywords

approximation algorithmscombinatorial cost sharingmechanism designtruthfulness

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• New trade-offs in cost-sharing mechanisms
• Limitations of cross-monotonic cost sharing schemes
• Limitations of cross-monotonic cost-sharing schemes
• Strategyproof sharing of submodular costs: budget balance versus efficiency
• The Power of Two Prices: Beyond Cross-Monotonicity

Cites work

• Beyond Moulin mechanisms
• Combinatorial auctions with decreasing marginal utilities
• Cost Sharing Methods for Makespan and Completion Time Scheduling
• Cost-sharing models in participatory sensing
• Efficient cost-sharing mechanisms for prize-collecting problems
• Group-Strategyproof Cost Sharing for Metric Fault Tolerant Facility Location
• Hardness results for multicast cost sharing.
• scientific article; zbMATH DE number 3670138 (Why is no real title available?)
• Incremental cost sharing: Characterization by coalition strategy-proofness
• Is Shapley cost sharing optimal?
• Quantifying inefficiency in cost-sharing mechanisms
• Strategyproof sharing of submodular costs: budget balance versus efficiency

Cited in

(2)

• A Characterization of Undirected Graphs Admitting Optimal Cost Shares
• Coordinating monetary contributions in participatory budgeting

This page was built for publication: Cost sharing over combinatorial domains : Complement-free cost functions and beyond

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