SCIENCE@home

Efficiency and Budget Balance in General Quasi-linear Domains

Swaprava Nath,T. Sandholm

Published 2016 in Games Econ. Behav.

ABSTRACT

Abstract 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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-35 of 35 references · Page 1 of 1

CITED BY

Showing 1-11 of 11 citing papers · Page 1 of 1