Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems

DOI10.1016/j.tcs.2008.03.025zbMath1151.90013OpenAlexW2106072776WikidataQ56609430 ScholiaQ56609430MaRDI QIDQ935148

Guido Schäfer, Janina A. Brenner

Publication date: 31 July 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.03.025

zbMATH Keywords

scheduling problemsmechanism designcooperative game theorycost sharing mechanismstruthful mechanisms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (4)

Is Shapley cost sharing optimal? ⋮ The complexity of egalitarian mechanisms for linear programming games ⋮ Integer programming methods to identify Nash equilibrium solutions for platform-based scheduling games ⋮ Cost-sharing mechanisms for scheduling under general demand settings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cross-monotonic cost sharing methods for connected facility location games
• Approximation algorithms for scheduling unrelated parallel machines
• Hardness results for multicast cost sharing.
• Approximation and collusion in multicast cost sharing
• Scheduling with Deadlines and Loss Functions
• New trade-offs in cost-sharing mechanisms
• Fair Cost-Sharing Methods for Scheduling Jobs on Parallel Machines
• Multiprocessor Scheduling of Unit-Time Jobs with Arbitrary Release Times and Deadlines
• `` Strong NP-Completeness Results
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Applications of approximation algorithms to cooperative games
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Optimal Efficiency Guarantees for Network Design Mechanisms
• Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems
• Algorithms – ESA 2005
• Automata, Languages and Programming
• Decentralization and Mechanism Design for Online Machine Scheduling
• Algorithmic mechanism design
• Sharing the cost of multicast transmissions
• Strategyproof sharing of submodular costs: budget balance versus efficiency

This page was built for publication: Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems