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.