IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v69y2021i1p188-206.html
   My bibliography  Save this article

A Simple and Approximately Optimal Mechanism for a Buyer with Complements

Author

Listed:
  • Alon Eden

    (Computer Science Department, Harvard University, Cambridge, Massachusetts 02139, Simons Institute for the Theory of Computing, Berkeley, California 94720)

  • Michal Feldman

    (Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel, Microsoft Research, Herzliya 4672513, Israel)

  • Ophir Friedler

    (Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel)

  • Inbal Talgam-Cohen

    (Computer Science Department, Technion, Haifa 3200003, Israel)

  • S. Matthew Weinberg

    (Simons Institute for the Theory of Computing, Berkeley, California 94720, Computer Science Department, Princeton University, Princeton, New Jersey 08540)

Abstract

We consider a revenue-maximizing seller with m heterogeneous items and a single buyer whose valuation for the items may exhibit both substitutes and complements. We show that the better of selling the items separately and bundling them together— guarantees a Θ ( d ) -fraction of the optimal revenue, where d is a measure of the degree of complementarity; it extends prior work showing that the same simple mechanism achieves a constant-factor approximation when buyer valuations are subadditive (the most general class of complement-free valuations). Our proof is enabled by a recent duality framework, which we use to obtain a bound on the optimal revenue in the generalized setting. Our technical contributions are domain specific to handle the intricacies of settings with complements. One key modeling contribution is a tractable notion of “degree of complementarity” that admits meaningful results and insights—we demonstrate that previous definitions fall short in this regard.

Suggested Citation

  • Alon Eden & Michal Feldman & Ophir Friedler & Inbal Talgam-Cohen & S. Matthew Weinberg, 2021. "A Simple and Approximately Optimal Mechanism for a Buyer with Complements," Operations Research, INFORMS, vol. 69(1), pages 188-206, January.
    • Handle: RePEc:inm:oropre:v:69:y:2021:i:1:p:188-206
    DOI: 10.1287/opre.2020.2039
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/opre.2020.2039
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2020.2039?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Pavlov Gregory, 2011. "Optimal Mechanism for Selling Two Goods," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 11(1), pages 1-35, February.
    2. Sergiu Hart & Noam Nisan, 2013. "The Menu-Size Complexity of Auctions," Discussion Paper Series dp637, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    3. Hart, Sergiu & Nisan, Noam, 2017. "Approximate revenue maximization with multiple items," Journal of Economic Theory, Elsevier, vol. 172(C), pages 313-347.
    4. Chawla, Shuchi & Malec, David & Sivan, Balasubramanian, 2015. "The power of randomness in Bayesian optimal mechanism design," Games and Economic Behavior, Elsevier, vol. 91(C), pages 297-317.
    5. Jean-Charles Rochet & Philippe Chone, 1998. "Ironing, Sweeping, and Multidimensional Screening," Econometrica, Econometric Society, vol. 66(4), pages 783-826, July.
    6. John Riley & Richard Zeckhauser, 1983. "Optimal Selling Strategies: When to Haggle, When to Hold Firm," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 98(2), pages 267-289.
    7. Shahar Dobzinski & Noam Nisan & Michael Schapira, 2010. "Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders," Mathematics of Operations Research, INFORMS, vol. 35(1), pages 1-13, February.
    8. Nguyen, Thành & Peivandi, Ahmad & Vohra, Rakesh, 2016. "Assignment problems with complementarities," Journal of Economic Theory, Elsevier, vol. 165(C), pages 209-241.
    9. , & , J., 2015. "Maximal revenue with multiple goods: nonmonotonicity and other observations," Theoretical Economics, Econometric Society, vol. 10(3), September.
    10. Levin, Jonathan, 1997. "An Optimal Auction for Complements," Games and Economic Behavior, Elsevier, vol. 18(2), pages 176-192, February.
    11. Shuchi Chawla & Jason Hartline & David Malec & Balasubramanian Sivan, 2010. "Sequential Posted Pricing and Multi-parameter Mechanism Design," Discussion Papers 1486, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    12. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    13. Nisan, Noam & Segal, Ilya, 2006. "The communication requirements of efficient allocations and supporting prices," Journal of Economic Theory, Elsevier, vol. 129(1), pages 192-224, July.
    14. Jason D. Hartline & Brendan Lucier, 2015. "Non-optimal Mechanism Design," American Economic Review, American Economic Association, vol. 105(10), pages 3102-3124, October.
    15. Thanassoulis, John, 2004. "Haggling over substitutes," Journal of Economic Theory, Elsevier, vol. 117(2), pages 217-245, August.
    16. Robert Day & Paul Milgrom, 2008. "Core-selecting package auctions," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 393-407, March.
    17. Paul Milgrom, 2007. "Package Auctions and Exchanges," Econometrica, Econometric Society, vol. 75(4), pages 935-965, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Shixin Wang, 2023. "The Power of Simple Menus in Robust Selling Mechanisms," Papers 2310.17392, arXiv.org.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hart, Sergiu & Nisan, Noam, 2017. "Approximate revenue maximization with multiple items," Journal of Economic Theory, Elsevier, vol. 172(C), pages 313-347.
    2. Tang, Pingzhong & Wang, Zihe, 2017. "Optimal mechanisms with simple menus," Journal of Mathematical Economics, Elsevier, vol. 69(C), pages 54-70.
    3. Bikhchandani, Sushil & Mishra, Debasis, 2022. "Selling two identical objects," Journal of Economic Theory, Elsevier, vol. 200(C).
    4. Hart, Sergiu & Nisan, Noam, 2019. "Selling multiple correlated goods: Revenue maximization and menu-size complexity," Journal of Economic Theory, Elsevier, vol. 183(C), pages 991-1029.
    5. Devanur, Nikhil R. & Haghpanah, Nima & Psomas, Alexandros, 2020. "Optimal multi-unit mechanisms with private demands," Games and Economic Behavior, Elsevier, vol. 121(C), pages 482-505.
    6. Sergiu Hart & Noam Nisan, 2013. "Selling Multiple Correlated Goods: Revenue Maximization and Menu-Size Complexity (old title: "The Menu-Size Complexity of Auctions")," Papers 1304.6116, arXiv.org, revised Nov 2018.
    7. Briest, Patrick & Chawla, Shuchi & Kleinberg, Robert & Weinberg, S. Matthew, 2015. "Pricing lotteries," Journal of Economic Theory, Elsevier, vol. 156(C), pages 144-174.
    8. Chen, Xi & Diakonikolas, Ilias & Paparas, Dimitris & Sun, Xiaorui & Yannakakis, Mihalis, 2018. "The complexity of optimal multidimensional pricing for a unit-demand buyer," Games and Economic Behavior, Elsevier, vol. 110(C), pages 139-164.
    9. Yeon-Koo Che & Weijie Zhong, 2021. "Robustly Optimal Mechanisms for Selling Multiple Goods," Papers 2105.02828, arXiv.org, revised Aug 2022.
    10. Kazumura, Tomoya & Mishra, Debasis & Serizawa, Shigehiro, 2020. "Strategy-proof multi-object mechanism design: Ex-post revenue maximization with non-quasilinear preferences," Journal of Economic Theory, Elsevier, vol. 188(C).
    11. Tim Roughgarden & Inbal Talgam-Cohen & Qiqi Yan, 2019. "Robust Auctions for Revenue via Enhanced Competition," Operations Research, INFORMS, vol. 68(4), pages 1074-1094, July.
    12. Alexander Teytelboym & Shengwu Li & Scott Duke Kominers & Mohammad Akbarpour & Piotr Dworczak, 2021. "Discovering Auctions: Contributions of Paul Milgrom and Robert Wilson," Scandinavian Journal of Economics, Wiley Blackwell, vol. 123(3), pages 709-750, July.
    13. Debasis Mishra & Kolagani Paramahamsa, 2022. "Selling to a principal and a budget-constrained agent," Discussion Papers 22-02, Indian Statistical Institute, Delhi.
    14. Pavlov Gregory, 2011. "A Property of Solutions to Linear Monopoly Problems," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 11(1), pages 1-18, February.
    15. Tomoya Kazumura & Debasis Mishra & Shigehiro Serizawa, 2017. "Strategy-proof multi-object auction design: Ex-post revenue maximization with no wastage," ISER Discussion Paper 1001, Institute of Social and Economic Research, Osaka University.
    16. Chawla, Shuchi & Malec, David & Sivan, Balasubramanian, 2015. "The power of randomness in Bayesian optimal mechanism design," Games and Economic Behavior, Elsevier, vol. 91(C), pages 297-317.
    17. Jean‐Charles Rochet & John Thanassoulis, 2019. "Intertemporal price discrimination with two products," RAND Journal of Economics, RAND Corporation, vol. 50(4), pages 951-973, December.
    18. Babaioff, Moshe & Gonczarowski, Yannai A. & Nisan, Noam, 2022. "The menu-size complexity of revenue approximation," Games and Economic Behavior, Elsevier, vol. 134(C), pages 281-307.
    19. Moshe Babaioff & Michal Feldman & Yannai A. Gonczarowski & Brendan Lucier & Inbal Talgam-Cohen, 2020. "Escaping Cannibalization? Correlation-Robust Pricing for a Unit-Demand Buyer," Papers 2003.05913, arXiv.org, revised Aug 2020.
    20. Ran Ben-Moshe & Sergiu Hart & Noam Nisan, 2022. "Monotonic Mechanisms for Selling Multiple Goods," Papers 2210.17150, arXiv.org.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:69:y:2021:i:1:p:188-206. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.