IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v31y2016i3d10.1007_s10878-014-9817-y.html
   My bibliography  Save this article

On revenue maximization with sharp multi-unit demands

Author

Listed:
  • Ning Chen

    (Nanyang Technological University)

  • Xiaotie Deng

    (Shanghai Jiao Tong University)

  • Paul W. Goldberg

    (University of Oxford)

  • Jinshan Zhang

    (University of Liverpool)

Abstract

We consider markets consisting of a set of indivisible items, and buyers that have sharp multi-unit demand. This means that each buyer $$i$$ i wants a specific number $$d_i$$ d i of items; a bundle of size less than $$d_i$$ d i has no value. We consider the objective of setting prices and allocations in order to maximize the total revenue of the market maker. The pricing problem with sharp multi-unit demand buyers has a number of properties that the unit-demand model does not possess, and is an important question in algorithmic pricing. We consider the problem of computing a revenue maximizing solution for two solution concepts: competitive equilibrium and envy-free pricing. For unrestricted valuations, these problems are NP-complete; we focus on a realistic special case of “correlated values” where each buyer $$i$$ i has a valuation $$v_iq_j$$ v i q j for item $$j$$ j , where $$v_i$$ v i and $$q_j$$ q j are positive quantities associated with buyer $$i$$ i and item $$j$$ j respectively. We present a polynomial time algorithm to solve the revenue-maximizing competitive equilibrium problem. For envy-free pricing, if the demand of each buyer is bounded by a constant, a revenue maximizing solution can be found efficiently; the general demand case is shown to be NP-hard.

Suggested Citation

  • Ning Chen & Xiaotie Deng & Paul W. Goldberg & Jinshan Zhang, 2016. "On revenue maximization with sharp multi-unit demands," Journal of Combinatorial Optimization, Springer, vol. 31(3), pages 1174-1205, April.
    • Handle: RePEc:spr:jcomop:v:31:y:2016:i:3:d:10.1007_s10878-014-9817-y
    DOI: 10.1007/s10878-014-9817-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-014-9817-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-014-9817-y?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Richard Engelbrecht-Wiggans & Charles M. Kahn, 1998. "Multi-unit auctions with uniform prices," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 12(2), pages 227-258.
    2. Benjamin Edelman & Michael Ostrovsky & Michael Schwarz, 2007. "Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords," American Economic Review, American Economic Association, vol. 97(1), pages 242-259, March.
    3. repec:ulb:ulbeco:2013/151705 is not listed on IDEAS
    4. Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
    5. John Hatfield, 2009. "Strategy-proof, efficient, and nonbossy quota allocations," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 33(3), pages 505-515, September.
    6. Pesendorfer, Martin & Cantillon, Estelle, 2007. "Combination Bidding in Multi-Unit Auctions," CEPR Discussion Papers 6083, C.E.P.R. Discussion Papers.
    7. Unknown, 2005. "Internet Advertising and the Generalized Second Price Auction: Selling Billions of Dollars Worth of Keywords," Department of Economics, Working Paper Series qt8w16v26k, Department of Economics, Institute for Business and Economic Research, UC Berkeley.
    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. Marcos Salvatierra & Juan G. Colonna & Mario Salvatierra Jr. & Alcides de C. Amorim Neto, 2024. "On Complexity Classes of Envy-Free Pricing Problems: A Short Survey," SN Operations Research Forum, Springer, vol. 5(4), pages 1-25, December.

    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. Axel Ockenfels & David Reiley & Abdolkarim Sadrieh, 2006. "Online Auctions," NBER Working Papers 12785, National Bureau of Economic Research, Inc.
    2. Eric Budish & Judd B. Kessler, 2022. "Can Market Participants Report Their Preferences Accurately (Enough)?," Management Science, INFORMS, vol. 68(2), pages 1107-1130, February.
    3. Lawrence M. Ausubel & Paul Milgrom, 2004. "Ascending Proxy Auctions," Discussion Papers 03-035, Stanford Institute for Economic Policy Research.
    4. Satoru Fujishige & Zaifu Yang, 2020. "A Universal Dynamic Auction for Unimodular Demand Types: An Efficient Auction Design for Various Kinds of Indivisible Commodities," Discussion Papers 20/08, Department of Economics, University of York.
    5. 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.
    6. Maria-Florina Balcan & Siddharth Prasad & Tuomas Sandholm, 2023. "Bicriteria Multidimensional Mechanism Design with Side Information," Papers 2302.14234, arXiv.org, revised Oct 2024.
    7. Evgenia Christoforou & Antonio Fernández Anta & Agustín Santos, 2016. "A Mechanism for Fair Distribution of Resources without Payments," PLOS ONE, Public Library of Science, vol. 11(5), pages 1-20, May.
    8. Cumpston, Anne & Khezr, Peyman, 2020. "Multi-Unit Auctions: A Survey of Theoretical Literature," MPRA Paper 101336, University Library of Munich, Germany.
    9. Moldovanu, Benny & Ewerhart II, Christian, 2001. "The German UMTS Design: Insights From Multi-Object Auction Theory," Sonderforschungsbereich 504 Publications 02-05, Sonderforschungsbereich 504, Universität Mannheim;Sonderforschungsbereich 504, University of Mannheim.
    10. Dütting, Paul & Fischer, Felix & Parkes, David C., 2019. "Expressiveness and robustness of first-price position auctions," LSE Research Online Documents on Economics 85877, London School of Economics and Political Science, LSE Library.
    11. Mueller-Frank, Manuel & M. Pai, Mallesh, 2015. "Do Online Social Networks Increase Welfare?," IESE Research Papers D/1118, IESE Business School.
    12. Ausubel Lawrence M & Milgrom Paul R, 2002. "Ascending Auctions with Package Bidding," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 1(1), pages 1-44, August.
    13. Chen, Ning & Ghosh, Arpita & Lambert, Nicolas S., 2014. "Auctions for social lending: A theoretical analysis," Games and Economic Behavior, Elsevier, vol. 86(C), pages 367-391.
    14. 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).
    15. Emmanuel LORENZON, 2016. "Collusion with a Greedy Center in Position Auctions," Cahiers du GREThA (2007-2019) 2016-08, Groupe de Recherche en Economie Théorique et Appliquée (GREThA).
    16. Feldman, Michal & Fu, Hu & Gravin, Nick & Lucier, Brendan, 2020. "Simultaneous auctions without complements are (almost) efficient," Games and Economic Behavior, Elsevier, vol. 123(C), pages 327-341.
    17. Yongmin Chen & Chuan He, 2011. "Paid Placement: Advertising and Search on the Internet," Economic Journal, Royal Economic Society, vol. 121(556), pages 309-328, November.
    18. Tomoya Kazumura & Debasis Mishra & Shigehiro Serizawa, 2017. "Strategy-proof multi-object allocation: Ex-post revenue maximization with no wastage," Working Papers e116, Tokyo Center for Economic Research.
    19. Snehalkumar & S. Gaikwad & Durim Morina & Adam Ginzberg & Catherine Mullings & Shirish Goyal & Dilrukshi Gamage & Christopher Diemert & Mathias Burton & Sharon Zhou & Mark Whiting & Karolina Ziulkoski, 2019. "Boomerang: Rebounding the Consequences of Reputation Feedback on Crowdsourcing Platforms," Papers 1904.06722, arXiv.org.
    20. Peyman Khezr & Kendall Taylor, 2024. "Artificial Intelligence for Multi-Unit Auction design," Papers 2404.15633, arXiv.org, revised Aug 2024.

    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:spr:jcomop:v:31:y:2016:i:3:d:10.1007_s10878-014-9817-y. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.