About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ACM Conference on Electronic Commerce 2007
Conference paper
Beyond moulin mechanisms
Abstract
The only known general technique for designing truthful, approximatelybudget-balanced cost-sharing mechanisms is due to Moulin. While Moulin mechanisms have been successfully designed for a widerange of applications, recent negative results show that for manyfundamental cost-sharing problems, Moulin mechanisms inevitably sufferfrom poor budget-balance, poor economic efficiency, or both. We propose acyclic mechanisms, a new framework for designingtruthful, approximately budget-balanced cost-sharing mechanisms. Acyclic mechanisms strictly generalize Moulin mechanisms andoffer three important advantages. First, it is easier to design acyclic mechanisms than Moulinmechanisms: many classical primal-dual algorithms naturallyinduce a non-Moulin acyclic mechanism with good performanceguarantees. Second, for several important classes of cost-sharing problems, acyclicmechanisms have exponentially better budget-balance and economicefficiency 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. Copyright 2007 ACM.