On Simple Mechanisms for Dependent Items

Yang Cai () and Argyris Oikonomou ()
Additional contact information
Yang Cai: Yale University, New Haven, Connecticut 06520
Argyris Oikonomou: Yale University, New Haven, Connecticut 06520

Operations Research, 2025, vol. 73, issue 4, 1849-1875

Abstract: 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-of-Singletons functions over dependent random variables.

Keywords: Market; Analytics; and; Revenue; Management; algorithmic game theory; mechanism design; dependent items (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0552 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:4:p:1849-1875

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().