Truthful Mechanisms for Two-Sided Markets via Prophet Inequalities

Alexander Braun () and Thomas Kesselheim ()
Additional contact information
Alexander Braun: Institute of Computer Science, University of Bonn, 53115 Bonn, Germany
Thomas Kesselheim: Institute of Computer Science, University of Bonn, 53115 Bonn, Germany

Mathematics of Operations Research, 2023, vol. 48, issue 4, 1959-1986

Abstract: We design novel mechanisms for welfare maximization in two-sided markets. That is, there are buyers willing to purchase items and sellers holding items initially, both acting rationally and strategically in order to maximize utility. Our mechanisms are designed based on a powerful correspondence between two-sided markets and prophet inequalities. They satisfy individual rationality, dominant-strategy incentive compatibility, and budget balance constraints and give constant factor approximations to the optimal social welfare. We improve previous results in several settings. Our main focus is on matroid double auctions. Here, sellers hold identical items, and the set of buyers that obtain an item needs to be independent in a matroid. We construct two mechanisms, the first being a 1/3 approximation of the optimal social welfare-satisfying strong budget balance and requiring the agents to trade in a customized order and the second being a 1/2 approximation weakly budget balanced and able to deal with online arrival determined by an adversary. In addition, we construct constant factor approximations in two-sided markets with identical items when buyers need to fulfill a knapsack constraint. Also, in combinatorial double auctions with heterogeneous items, where buyers have valuation functions over item bundles instead of being interested in only one item, using similar techniques, we design a mechanism that is a 1/2 approximation of the optimal social welfare, is strongly budget balanced, and can deal with the online arrival of agents in an adversarial order.

Keywords: Primary: 91B03; secondary: 68W25; 91B70; mechanism design; two-sided markets; double auctions; bilateral trade; prophet inequalities (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1327 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:4:p:1959-1986

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().