2010-12-01
Generalized Incremental Mechanisms for Scheduling Games
Publication
Publication
We study the problem of devising truthful mechanisms for cooperative cost sharing
games that realize (approximate) budget balance and social cost. Recent negative
results show that group-strategyproof mechanisms can only achieve very poor approximation
guarantees for several fundamental cost sharing games. Driven by these limitations,
we consider cost sharing mechanisms that realize the weaker notion of weak groupstrategyproofness.
Mehta et al. [Games and Economic Behavior, 67:125–155, 2009] recently
introduced the broad class of weakly group-strategyproof acyclic mechanisms and
show that several primal-dual approximation algorithms naturally give rise to such mechanisms
with attractive approximation guarantees. In this paper, we provide a simple yet
powerful approach that enables us to turn any r-approximation algorithm into a r-budget
balanced acyclic mechanism. We demonstrate the applicability of our approach by deriving
weakly group-strategyproof mechanisms for several fundamental scheduling problems
that outperform the best possible approximation guarantees of Moulin mechanisms.
The mechanisms that we develop for completion time scheduling problems are the first
mechanisms that achieve constant budget balance and social cost approximation factors.
Interestingly, our mechanisms belong to the class of generalized incremental mechanisms
proposed by Moulin [Social Choice and Welfare, 16:279–320, 1999].
Additional Metadata | |
---|---|
CWI | |
CWI. Probability, Networks and Algorithms [PNA] | |
Organisation | Networks and Optimization |
Brenner, J., & Schäfer, G. (2010). Generalized Incremental Mechanisms for Scheduling Games. CWI. Probability, Networks and Algorithms [PNA]. CWI. |