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. 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.
    2. Pesendorfer, Martin & Cantillon, Estelle, 2007. "Combination Bidding in Multi-Unit Auctions," CEPR Discussion Papers 6083, C.E.P.R. Discussion Papers.
    3. 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.
    4. 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.
    5. repec:ulb:ulbeco:2013/151705 is not listed on IDEAS
    6. Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
    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)

    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. Maria-Florina Balcan & Siddharth Prasad & Tuomas Sandholm, 2023. "Bicriteria Multidimensional Mechanism Design with Side Information," Papers 2302.14234, arXiv.org, revised Jun 2023.
    3. Cumpston, Anne & Khezr, Peyman, 2020. "Multi-Unit Auctions: A Survey of Theoretical Literature," MPRA Paper 101336, University Library of Munich, Germany.
    4. 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.
    5. 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.
    6. 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.
    7. D Laffey & C Hunka & J A Sharp & Z Zeng, 2009. "Estimating advertisers' values for paid search clickthroughs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(3), pages 411-418, March.
    8. Paul Milgrom, 2006. "Package Auctions and Package Exchanges: the 2004 Fisher-Schultz Lecture," Levine's Bibliography 321307000000000131, UCLA Department of Economics.
    9. Arash Asadpour & MohammadHossein Bateni & Kshipra Bhawalkar & Vahab Mirrokni, 2019. "Concise Bid Optimization Strategies with Multiple Budget Constraints," Management Science, INFORMS, vol. 65(12), pages 5785-5812, December.
    10. Paul Dütting & Felix Fischer & David C. Parkes, 2019. "Expressiveness and Robustness of First-Price Position Auctions," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 196-211, February.
    11. Eric Budish & Judd B. Kessler, 2022. "Can Market Participants Report Their Preferences Accurately (Enough)?," Management Science, INFORMS, vol. 68(2), pages 1107-1130, February.
    12. Lawrence M. Ausubel & Paul Milgrom, 2004. "Ascending Proxy Auctions," Discussion Papers 03-035, Stanford Institute for Economic Policy Research.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. Mueller-Frank, Manuel & M. Pai, Mallesh, 2015. "Do Online Social Networks Increase Welfare?," IESE Research Papers D/1118, IESE Business School.
    18. 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.
    19. 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).
    20. 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).

    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.