Efficiency and budget balance in general quasi-linear domains

We consider efficiency and budget balance in general quasi-linear domains. Green and Laffont (1979) proved that one cannot generically achieve both. We consider strategyproof budget-balanced mechanisms with bounded valuations that are approximately efficient. We show that a deterministic, strategyproof, and budget-balanced mechanism must have a sink whose valuation is ignored in the decision, and is compensated with all the leftover money. We find a tight lower bound on the inefficiencies of strategyproof, budget-balanced mechanisms using this result. The bound shows that the inefficiency asymptotically disappears when the number of agents is large-we provide worst-case bounds and the best possible rate of convergence. We provide results for convex combination of inefficiency and budget imbalance and for randomized mechanisms. Experiments with real data from two applications show that the inefficiency for a simple randomized mechanism is 5-100 times smaller than the worst case. (C) 2018 Elsevier Inc. All rights reserved.