2016/04/21 by Erel Segal-Halevi, Avinatan Hassidim, Segal-Halevi, Erel +3
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #cs.GT
paper · pdf · doi:10.48550/arxiv.1604.06210
Full version of IJCAI-18 paper, with 2 figures. Previous names: "MIDA: A Multi Item-type Double-Auction Mechanism", "A Random-Sampling Double-Auction Mechanism". 10 pages
arxiv created 2018/05/01 · arxiv updated 2018/05/02
Motivated by applications such as stock exchanges and spectrum auctions, there is a growing interest in mechanisms for arranging trade in two-sided markets. Existing mechanisms are either not truthful, or do not guarantee an asymptotically-optimal gain-from-trade, or rely on a prior on the traders' valuations, or operate in limited settings such as a single kind of good. We extend the random market-halving technique used in earlier works to markets with multiple kinds of goods, where traders have gross-substitute valuations. We present MIDA: a Multi Item-kind Double-Auction mechanism. It is prior-free, truthful, strongly-budget-balanced, and guarantees near-optimal gain from trade when market sizes of all goods grow to ∞ at a similar rate.