Beyond Moulin mechanismsAranyak Mehta, Tim Roughgarden and Mukund Sundararajan Games and Economic Behavior, 2009, vol. 67, issue 1, pages 125-155 Abstract: The only known general technique for designing truthful and approximately budget-balanced cost-sharing mechanisms with good efficiency or computational complexity properties is due to Moulin [1999. Incremental cost sharing: Characterization by coalition strategy-proofness. Soc. Choice Welfare 16 (2), 279-320]. For many fundamental cost-sharing applications, however, Moulin mechanisms provably suffer from poor budget-balance, poor economic efficiency, or both. We propose acyclic mechanisms, a new framework for designing truthful and approximately budget-balanced cost-sharing mechanisms. Acyclic mechanisms strictly generalize Moulin mechanisms and offer three important advantages. First, it is easier to design acyclic mechanisms than Moulin mechanisms: many classical primal-dual algorithms naturally induce a non-Moulin acyclic mechanism with good performance guarantees. Second, for important classes of cost-sharing problems, acyclic mechanisms have exponentially better budget-balance and economic efficiency than Moulin mechanisms. Finally, while Moulin mechanisms have found application primarily in binary demand games, we extend acyclic mechanisms to general demand games, a multi-parameter setting in which each bidder can be allocated one of several levels of service. Date: 2009 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: http://EconPapers.repec.org/RePEc:eee:gamebe:v:67:y:2009:i:1:p:125-155 Access Statistics for this article Games and Economic Behavior is edited by E. Kalai More articles in Games and Economic Behavior from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
Swedish Business School at Örebro University.