Combinatorial Reallocation Mechanisms

We consider reallocation problems in settings where the initial endowment of each agent consists of a subset of the resources. The private information of the players is their value for every possible subset of the resources. The goal is to redistribute resources among agents to maximize efficiency. Monetary transfers are allowed, but participation is voluntary. We develop incentive-compatible, individually-rational and budget-balanced mechanisms for two settings in which agents have complex multi-parameter valuations, both settings include double auctions as a special case. The first setting is combinatorial exchanges, where we provide a mechanism that achieves a logarithmic approximation to the optimal efficiency when valuations are subadditive. The second setting is Arrow–Debreu markets for a single divisible good, where we present a constant approximation mechanism. The first result is given for a Bayesian setting, where the latter result is for prior-free environments.