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. Funding: A. Braun was funded by the Deutsche Forschungsgemeinschaft [Grant 437739576].