Double Auctions in Markets for Multiple Kinds of Goods

Double Auctions in Markets for Multiple Kinds of Goods

Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 489-497. https://doi.org/10.24963/ijcai.2018/68

Motivated by applications such as stock exchanges and spectrum auctions, there is a growing interest in mechanisms for arranging trade in two-sided markets. However, existing mechanisms are either not truthful, do not guarantee an asymptotically-optimal gain-from-trade, rely on a prior on the traders' valuations, or operate in limited settings such as a single type of good. We extend the random-sampling technique used in earlier works to multi-good markets where traders have gross-substitute valuations. We show a prior free, truthful and strongly-budget-balanced mechanism which guarantees near-optimal gain from trade when the market sizes of all goods grow to infinity at a similar rate.
Keywords:
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems