On Simple Mechanisms for Dependent Items

• 成果类型: Article
• 署名作者: Cai, Yang; Oikonomou, Argyris
• 署名单位: Yale University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0552
• 发表日期: 2025
• 页码: 1849-1875
• 关键词: Revenue maximization; INEQUALITY

摘要

We study the problem of selling n heterogeneous items to a single buyer, whose values for different items are dependent. Under arbitrary dependence, others show that no simple mechanism can achieve a nonnegligible fraction of the optimal revenue even with only two items. We consider the setting where the buyer's type is drawn from a correlated distribution that can be captured by a Markov random field (MRF), one of the most prominent frameworks for modeling high-dimensional distributions with structure. We show how the performance of simple mechanisms depends on some natural parameters of the MRF for several fundamental classes of the buyer's valuations. Our results are based on the duality framework by of others and a new concentration inequality for XOR-of-OR-ofSingletons functions over dependent random variables.