Truthful Bundle/Multiunit Double Auctions

We address the mechanism design problem for a market with multiple buyers and sellers. Each buyer demands some bundle(s) of various commodities, and each seller supplies multiple units of one commodity. To design truthful double-auction mechanisms, we propose a novel “padding” method that intentionally creates imbalances between the supply availability and demand requirement by introducing a phantom buyer with unlimited budget. To the best of our knowledge, this “padding” method leads to a class of mechanisms that are the first strategy-proof, individually rational, budget-balanced, and asymptotically efficient mechanisms for the specified exchange environment. Furthermore, these mechanisms dominate known truthful bundle/single-unit mechanisms with higher efficiency, lower buying prices, and higher selling prices.