IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v118y2019icp648-667.html
   My bibliography  Save this article

Welfare maximization with production costs: A primal dual approach

Author

Listed:
  • Huang, Zhiyi
  • Kim, Anthony

Abstract

We study online auctions with production costs using an online primal dual framework. The seller allocates items to buyers and can produce multiple copies of each item subject to a non-decreasing marginal cost per copy. The buyers have arbitrary valuation functions and arrive one by one online in some arbitrary order. The goal is to design an online mechanism that maximizes the social welfare, that is, the sum of the buyers' values less the total production cost. For any strictly convex and differentiable production cost function, we characterize the optimal competitive ratio achievable by online mechanisms and, more generally, algorithms without incentive guarantees. We show that online posted pricing mechanisms, which are incentive compatible, can achieve competitive ratios arbitrarily close to the optimal, and construct lower bound instances on which no online algorithms, not necessarily incentive compatible, can do better.

Suggested Citation

  • Huang, Zhiyi & Kim, Anthony, 2019. "Welfare maximization with production costs: A primal dual approach," Games and Economic Behavior, Elsevier, vol. 118(C), pages 648-667.
    • Handle: RePEc:eee:gamebe:v:118:y:2019:i:c:p:648-667
    DOI: 10.1016/j.geb.2018.03.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825618300344
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2018.03.003?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. Dughmi, Shaddin & Vondrák, Jan, 2015. "Limitations of randomized mechanisms for combinatorial auctions," Games and Economic Behavior, Elsevier, vol. 92(C), pages 370-400.
    2. 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.
    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. Andrés Abeliuk & Gerardo Berbeglia & Pascal Van Hentenryck, 2015. "Bargaining Mechanisms for One-Way Games," Games, MDPI, vol. 6(3), pages 1-21, September.
    2. Alaei, Saeed & Hartline, Jason & Niazadeh, Rad & Pountourakis, Emmanouil & Yuan, Yang, 2019. "Optimal auctions vs. anonymous pricing," Games and Economic Behavior, Elsevier, vol. 118(C), pages 494-510.
    3. Debasis Mishra & Kolagani Paramahamsa, 2022. "Selling to a principal and a budget-constrained agent," Discussion Papers 22-02, Indian Statistical Institute, Delhi.
    4. Phuong Le, 2017. "Mechanisms for combinatorial auctions with budget constraints," Review of Economic Design, Springer;Society for Economic Design, vol. 21(1), pages 1-31, March.
    5. Briest, Patrick & Chawla, Shuchi & Kleinberg, Robert & Weinberg, S. Matthew, 2015. "Pricing lotteries," Journal of Economic Theory, Elsevier, vol. 156(C), pages 144-174.
    6. 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.
    7. Cai, Yang & Daskalakis, Constantinos, 2015. "Extreme value theorems for optimal multidimensional pricing," Games and Economic Behavior, Elsevier, vol. 92(C), pages 266-305.
    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. Blumrosen, Liad & Dobzinski, Shahar, 2021. "(Almost) efficient mechanisms for bilateral trading," Games and Economic Behavior, Elsevier, vol. 130(C), pages 369-383.
    10. Hart, Sergiu & Nisan, Noam, 2017. "Approximate revenue maximization with multiple items," Journal of Economic Theory, Elsevier, vol. 172(C), pages 313-347.
    11. Yannai A. Gonczarowski & Nicole Immorlica & Yingkai Li & Brendan Lucier, 2021. "Revenue Maximization for Buyers with Costly Participation," Papers 2103.03980, arXiv.org, revised Nov 2023.
    12. Li, Yongli & Wu, Chong & Wang, Xiaoyu & Luo, Peng, 2014. "A network-based and multi-parameter model for finding influential authors," Journal of Informetrics, Elsevier, vol. 8(3), pages 791-799.
    13. 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.
    14. Sankar Kumar Mridha & Malay Bhattacharyya, 2018. "A network based mechanism for managing decomposable tasks via crowdsourcing," Electronic Commerce Research, Springer, vol. 18(4), pages 869-881, December.
    15. Saeed Alaei & Ali Makhdoumi & Azarakhsh Malekian & Rad Niazadeh, 2022. "Descending Price Auctions with Bounded Number of Price Levels and Batched Prophet Inequality," Papers 2203.01384, arXiv.org.
    16. Yann Disser & John Fearnley & Martin Gairing & Oliver Göbel & Max Klimm & Daniel Schmand & Alexander Skopalik & Andreas Tönnis, 2020. "Hiring Secretaries over Time: The Benefit of Concurrent Employment," Mathematics of Operations Research, INFORMS, vol. 45(1), pages 323-352, February.
    17. 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.
    18. Aadityan Ganesh & Jason Hartline, 2023. "Combinatorial Pen Testing (or Consumer Surplus of Deferred-Acceptance Auctions)," Papers 2301.12462, arXiv.org, revised Dec 2024.
    19. Azar, Pablo D. & Kleinberg, Robert & Weinberg, S. Matthew, 2019. "Prior independent mechanisms via prophet inequalities with limited information," Games and Economic Behavior, Elsevier, vol. 118(C), pages 511-532.
    20. Constantinos Daskalakis & Maxwell Fishelson & Brendan Lucier & Vasilis Syrgkanis & Santhoshini Velusamy, 2020. "Multi-item Non-truthful Auctions Achieve Good Revenue," Papers 2002.06702, arXiv.org, revised Sep 2022.

    More about this item

    Keywords

    Combinatorial auctions; Online algorithms; Mechanism design; Competitive analysis; Posted pricing mechanisms; Welfare maximization;
    All these keywords.

    JEL classification:

    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis

    Statistics

    Access and download statistics

    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:eee:gamebe:v:118:y:2019:i:c:p:648-667. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    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.