MIDA: A Multi Item-type Double-Auction Mechanism

In a seminal paper, McAfee (1992) presented a truthful mechanism for double auction, attaining asymptotically-optimal gain-from-trade without any prior information on the valuations of the traders. McAfee's mechanism handles single-parametric agents, allowing each seller to sell a single item and each buyer to buy a single item. In this paper, we present a double-auction mechanism that handles multi-parametric agents and allow multiple items per trader. Each seller is endowed with several units of a pre-specified type and has diminishing marginal returns. Each buyer may buy multiple types and has a gross-substitute valuation function. Both buyers and sellers are quasi-linear in money. The mechanism is prior-free, ex-post individually-rational, dominant-strategy truthful and strongly budget-balanced. Its gain-from-trade approaches the optimum when the market in all item-types is sufficiently large.