On Simple Mechanisms for Dependent Items
研究了当买家对物品的估值存在依赖关系时，简单机制（如单独定价或捆绑销售）的表现，发现其性能与物品数量无关，仅随依赖程度而下降。
In “On Simple Mechanisms for Dependent Items,” the authors study the performance of simple mechanisms—such as item pricing or bundling—in settings where a buyer’s valuations for items are dependent. Previous research has largely focused on the setting with independent item valuations, which, although theoretically appealing, is unrealistic. Other studies have either examined limited forms of dependency or allowed arbitrary dependencies, but in the latter case, the resulting approximation ratios are exponential in the number of items, making them too weak to be practical for real-world applications. To bridge this gap, the authors use Markov random fields (MRFs), a graphical model well suited for representing complex dependencies among random variables, to capture correlations among items. They establish a parametric approximation, showing that the performance of simple mechanisms is independent of the number of items and degrades gracefully with the degree of dependency among items, as characterized by the MRF. This framework extends to general valuation functions, enabling it to account for practical constraints faced by practitioners, such as cardinality constraints.