Truthful Mechanisms for Two-Sided Markets via Prophet Inequalities

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.