Efficiency and budget balance in general quasi-linear domains

DOI10.1016/J.GEB.2018.11.010zbMATH Open1419.91244arXiv1610.01443OpenAlexW2575112216WikidataQ128882271 ScholiaQ128882271MaRDI QIDQ1735779FDOQ1735779

Authors: Swaprava Nath, Tuomas Sandholm 

Publication date: 29 March 2019

Published in: Games and Economic Behavior (Search for Journal in Brave)

Abstract: We study efficiency and budget balance for designing mechanisms in general quasi-linear domains. Green and Laffont (1979) proved that one cannot generically achieve both. We consider strategyproof budget-balanced mechanisms that are approximately efficient. For deterministic mechanisms, we show that a strategyproof and budget-balanced mechanism must have a sink agent whose valuation function is ignored in selecting an alternative, and she is compensated with the payments made by the other agents. We assume the valuations of the agents come from a bounded open interval. Using this result, we find a tight lower bound on the inefficiencies of strategyproof, budget-balanced mechanisms in this domain. The bound shows that the inefficiency asymptotically disappears when the number of agents is large---a result close in spirit to Green and Laffont (1979, Theorem 9.4). However, our results provide worst-case bounds and the best possible rate of convergence. Next, we consider minimizing any convex combination of inefficiency and budget imbalance. We show that if the valuations are unrestricted, no deterministic mechanism can do asymptotically better than minimizing inefficiency alone. Finally, we investigate randomized mechanisms and provide improved lower bounds on expected inefficiency. We give a tight lower bound for an interesting class of strategyproof, budget-balanced, randomized mechanisms. We also use an optimization-based approach---in the spirit of automated mechanism design---to provide a lower bound on the minimum achievable inefficiency of any randomized mechanism. 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. This relative difference increases with the number of agents.

Full work available at URL: https://arxiv.org/abs/1610.01443

Recommendations

• Efficiency and Budget Balance
• A note on the incompatibility of strategy-proofness and Pareto-optimality in quasi-linear settings with public budgets
• A simple budget-balanced mechanism
• An efficient dynamic mechanism
• Balanced ranking mechanisms

zbMATH Keywords

efficiencybudget balancequasi-linear preferencesaffine maximizerGreen-Laffont impossibility

Mathematics Subject Classification ID

Individual preferences (91B08) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04)

Cites Work

• Eigentaste: A constant time collaborative filtering algorithm
• Title not available (Why is that?)
• Almost budget-balanced VCG mechanisms to assign multiple objects
• Title not available (Why is that?)
• Incentives in Teams
• Strategyproof sharing of submodular costs: budget balance versus efficiency
• Worst-case optimal redistribution of VCG payments in multi-unit auctions
• Thirteen Reasons Why the Vickrey-Clarke-Groves Process Is Not Practical
• Mix and match: a strategyproof mechanism for multi-hospital kidney exchange
• Truthful randomized mechanisms for combinatorial auctions
• Characterization of Revenue Equivalence
• Roberts' theorem with neutrality: a social welfare ordering approach
• Quantifying inefficiency in cost-sharing mechanisms
• Redistribution mechanisms for assignment of heterogeneous objects
• Better redistribution with inefficient allocation in multi-unit auctions
• Optimal-in-expectation redistribution mechanisms
• Automated mechanism design: a new application area for search algorithms
• On cost sharing in the provision of a binary and excludable public good
• A simple budget-balanced mechanism

Cited In (6)

• Optimal private good allocation: the case for a balanced budget
• Efficiency and Budget Balance
• A note on the incompatibility of strategy-proofness and Pareto-optimality in quasi-linear settings with public budgets
• Diffusion auction design
• An efficient dynamic mechanism
• A simple budget-balanced mechanism

Uses Software

• Gurobi
• Eigentaste
• MovieLens

This page was built for publication: Efficiency and budget balance in general quasi-linear domains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1735779)