IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2609.36346.html

Solving the Arctic Product-Mix Auction

Author

Listed:
  • Elizabeth Baldwin
  • Paul Klemperer
  • Edwin Lock

Abstract

Arctic product-mix auctions allow budget-constrained bidders to express preferences over multiple substitute goods. We give the first strongly polynomial algorithm to find the competitive equilibria when the auctioneer has separable convex piecewise-linear costs. It combines a strongly polynomial reduction to the costless Arctic auction with an existing strongly polynomial algorithm for costless Arctic auctions. We also give a polynomial-time Turing reduction from costless Arctic auctions to linear Fisher markets, and a strongly polynomial many-to-one reduction to linear Arrow-Debreu exchange markets. If a good is sold in positive quantity in two competitive equilibria, its price is the same in both.

Suggested Citation

  • Elizabeth Baldwin & Paul Klemperer & Edwin Lock, 2026. "Solving the Arctic Product-Mix Auction," Papers 2609.36346, arXiv.org.
    • Handle: RePEc:arx:papers:2609.36346
    as

    Download full text from publisher

    File URL: https://arxiv.org/pdf/2609.36346
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Simon Finster & Paul W Goldberg & Edwin Lock, 2025. "Competitive and Revenue-Optimal Pricing with Budgets," Post-Print hal-05234001, HAL.
    2. Elizabeth Baldwin & Paul Klemperer & Edwin Lock, 2024. "Implementing Walrasian Equilibrium: The Languages of Product-Mix Auctions," Economics Series Working Papers 1060, University of Oxford, Department of Economics.
    3. Paul Klemperer, 2010. "The Product-Mix Auction: A New Auction Design for Differentiated Goods," Journal of the European Economic Association, MIT Press, vol. 8(2-3), pages 526-536, 04-05.
    4. Finster, Simon & Goldberg, Paul W. & Lock, Edwin, 2025. "Competitive and revenue-optimal pricing with budgets," Theoretical Economics, Econometric Society, vol. 20(4), November.
    5. Simon Finster & Paul W. Goldberg & Edwin Lock, 2023. "Competitive and Revenue-Optimal Pricing with Budgets," Papers 2310.03692, arXiv.org, revised Apr 2025.
    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. Ingebretsen Carlson, Jim, 2015. "An Approximate Auction," Working Papers 2015:19, Lund University, Department of Economics.
    2. Benedikt Bünz & Benjamin Lubin & Sven Seuken, 2022. "Designing Core-Selecting Payment Rules: A Computational Search Approach," Information Systems Research, INFORMS, vol. 33(4), pages 1157-1173, December.
    3. Fabra, Natalia & Montero, Juan Pablo, 2020. "Technology-Neutral vs. Technology-Specific Procurement," CEPR Discussion Papers 15554, Centre 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. Estrella Alonso & Joaquín Sánchez-Soriano & Juan Tejada, 2020. "Mixed Mechanisms for Auctioning Ranked Items," Mathematics, MDPI, vol. 8(12), pages 1-26, December.
    6. 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.
    7. Siddharth Prasad & Maria-Florina Balcan & Tuomas Sandholm, 2025. "Weakest Bidder Types and New Core-Selecting Combinatorial Auctions," Papers 2505.13680, arXiv.org.
    8. Koulischer, François & Struyven, Daan, 2014. "Central bank liquidity provision and collateral quality," Journal of Banking & Finance, Elsevier, vol. 49(C), pages 113-130.
    9. Gentry, Matthew & Komarova, Tatiana & Schiraldi, Pasquale & Shin, Wiroy, 2019. "On monotone strategy equilibria in simultaneous auctions for complementary goods," Journal of Mathematical Economics, Elsevier, vol. 85(C), pages 109-128.
    10. Arozamena, Leandro & Weinschelbaum, Federico & Wolfstetter, Elmar G., 2018. "Procuring substitutes with (fine-tuned) first-price auctions," Economics Letters, Elsevier, vol. 171(C), pages 115-118.
    11. Simon Finster & Paul W. Goldberg & Edwin Lock & Matilde Tullii, 2026. "Decentralized Trading Networks: Equilibria and Fairness," Papers 2602.20868, arXiv.org.
    12. Vijay V. Vazirani, 2025. "Arctic Auctions, Linear Fisher Markets, and Rational Convex Programs," Papers 2511.21637, arXiv.org, revised Aug 2026.
    13. Shengwu Li, 2024. "Designing Simple Mechanisms," Journal of Economic Perspectives, American Economic Association, vol. 38(4), pages 175-192, Fall.
    14. Nobel Prize Committee, 2020. "Improvements to auction theory and inventions of new auction formats," Nobel Prize in Economics documents 2020-2, Nobel Prize Committee.
    15. Pär Holmberg & Keith Ruddell & Bert Willems, 2025. "Multi-product supply function equilibria," Working Papers EPRG2522, Energy Policy Research Group, Cambridge Judge Business School, University of Cambridge.
    16. Satoru Fujishige & Zaifu Yang, 2026. "A Universally Efficient Dynamic Auction for All Unimodular Demand Types," Mathematics of Operations Research, INFORMS, vol. 51(1), pages 829-851, January.
    17. Simon Finster, 2020. "Strategic Bidding in Product-Mix, Sequential, and Simultaneous Auctions," Economics Papers 2020-W03, Economics Group, Nuffield College, University of Oxford.
    18. Fichtl, Maximilian, 2021. "On the expressiveness of assignment messages," Economics Letters, Elsevier, vol. 208(C).
    19. Ingebretsen Carlson, Jim, 2016. "An Auction with Approximated Bidder Preferences - When an Auction has to be Quick," Working Papers 2016:12, Lund University, Department of Economics.
    20. Paul Dütting & Vasilis Gkatzelis & Tim Roughgarden, 2017. "The Performance of Deferred-Acceptance Auctions," Mathematics of Operations Research, INFORMS, vol. 42(4), pages 897-914, November.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:arx:papers:2609.36346. 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: arXiv administrators (email available below). General contact details of provider: https://arxiv.org/ .

    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.