Efficiency and budget balance in general quasi-linear domains

• 成果类型: Article
• 署名作者: Nath, Swaprava; Sandholm, Tuomas
• 署名单位: Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Kanpur; Carnegie Mellon University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2018.11.010
• 发表日期: 2019
• 页码: 673-693
• 关键词: Quasi-linear preferences; EFFICIENCY; budget balance; Affine maximizer; Green-Laffont impossibility

摘要

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.