IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2107.08813.html
   My bibliography  Save this paper

Competitive equilibrium always exists for combinatorial auctions with graphical pricing schemes

Author

Listed:
  • Marie-Charlotte Brandenburg
  • Christian Haase
  • Ngoc Mai Tran

Abstract

We show that a competitive equilibrium always exists in combinatorial auctions with anonymous graphical valuations and pricing, using discrete geometry. This is an intuitive and easy-to-construct class of valuations that can model both complementarity and substitutes, and to our knowledge, it is the first class besides gross substitutes that have guaranteed competitive equilibrium. We prove through counter-examples that our result is tight, and we give explicit algorithms for constructive competitive pricing vectors. We also give extensions to multi-unit combinatorial auctions (also known as product-mix auctions). Combined with theorems on graphical valuations and pricing equilibrium of Candogan, Ozdagar and Parrilo, our results indicate that quadratic pricing is a highly practical method to run combinatorial auctions.

Suggested Citation

  • Marie-Charlotte Brandenburg & Christian Haase & Ngoc Mai Tran, 2021. "Competitive equilibrium always exists for combinatorial auctions with graphical pricing schemes," Papers 2107.08813, arXiv.org, revised Nov 2021.
    • Handle: RePEc:arx:papers:2107.08813
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Ozan Candogan & Asuman Ozdaglar & Pablo A. Parrilo, 2015. "Iterative Auction Design for Tree Valuations," Operations Research, INFORMS, vol. 63(4), pages 751-771, August.
    2. Danilov, Vladimir & Koshevoy, Gleb & Murota, Kazuo, 2001. "Discrete convexity and equilibria in economies with indivisible goods and money," Mathematical Social Sciences, Elsevier, vol. 41(3), pages 251-273, May.
    3. Elizabeth Baldwin & Paul Klemperer, 2019. "Understanding Preferences: “Demand Types”, and the Existence of Equilibrium With Indivisibilities," Econometrica, Econometric Society, vol. 87(3), pages 867-932, May.
    4. Paes Leme, Renato, 2017. "Gross substitutability: An algorithmic survey," Games and Economic Behavior, Elsevier, vol. 106(C), pages 294-316.
    5. Nisan, Noam, 2015. "Algorithmic Mechanism Design," Handbook of Game Theory with Economic Applications,, Elsevier.
    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. Elizabeth Baldwin & Paul W. Goldberg & Paul Klemperer & Edwin Lock, 2019. "Solving Strong-Substitutes Product-Mix Auctions," Economics Papers 2019-W08, Economics Group, Nuffield College, University of Oxford.
    2. Elizabeth Baldwin & Omer Edhan & Ravi Jagadeesan & Paul Klemperer & Alexander Teytelboym, 2020. "The Equilibrium Existence Duality: Equilibrium with Indivisibilities & Income Effects," Papers 2006.16939, arXiv.org.
    3. Chao Huang, 2021. "Stable matching: an integer programming approach," Papers 2103.03418, arXiv.org, revised Apr 2022.
    4. Ngoc Mai Tran & Josephine Yu, 2015. "Product-Mix Auctions and Tropical Geometry," Papers 1505.05737, arXiv.org, revised Oct 2017.
    5. Martin Bichler & Johannes Knörr & Felipe Maldonado, 2023. "Pricing in Nonconvex Markets: How to Price Electricity in the Presence of Demand Response," Information Systems Research, INFORMS, vol. 34(2), pages 652-675, June.
    6. Ozan Candogan & Markos Epitropou & Rakesh V. Vohra, 2021. "Competitive Equilibrium and Trading Networks: A Network Flow Approach," Operations Research, INFORMS, vol. 69(1), pages 114-147, January.
    7. Kazuo Murota, 2016. "Discrete convex analysis: A tool for economics and game theory," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 1(1), pages 151-273, December.
    8. Elizabeth Baldwin & Paul Klemperer, 2019. "Understanding Preferences: “Demand Types”, and the Existence of Equilibrium With Indivisibilities," Econometrica, Econometric Society, vol. 87(3), pages 867-932, May.
    9. Chao Huang, 2021. "Unidirectional substitutes and complements," Papers 2108.12572, arXiv.org.
    10. Martin Bichler & Hans Ulrich Buhl & Johannes Knörr & Felipe Maldonado & Paul Schott & Stefan Waldherr & Martin Weibelzahl, 2022. "Electricity Markets in a Time of Change: A Call to Arms for Business Research," Schmalenbach Journal of Business Research, Springer, vol. 74(1), pages 77-102, March.
    11. Cheng Guo & Merve Bodur & Joshua A. Taylor, 2021. "Copositive Duality for Discrete Markets and Games," Papers 2101.05379, arXiv.org, revised Jan 2021.
    12. Chao Huang, 2022. "Two-sided matching with firms' complementary preferences," Papers 2205.05599, arXiv.org, revised May 2022.
    13. Ozan Candogan & Saša Pekeč, 2018. "Efficient Allocation and Pricing of Multifeatured Items," Management Science, INFORMS, vol. 64(12), pages 5521-5543, December.
    14. Hatfield, John William & Kominers, Scott Duke & Nichifor, Alexandru & Ostrovsky, Michael & Westkamp, Alexander, 2019. "Full substitutability," Theoretical Economics, Econometric Society, vol. 14(4), November.
    15. Daniel Lehmann, 2019. "Revealed Preferences for Matching with Contracts," Papers 1908.08823, arXiv.org, revised Mar 2020.
    16. Miralles, Antonio & Pycia, Marek, 2021. "Foundations of pseudomarkets: Walrasian equilibria for discrete resources," Journal of Economic Theory, Elsevier, vol. 196(C).
    17. Saurabh Amin & Patrick Jaillet & Haripriya Pulyassary & Manxi Wu, 2023. "Market Design for Dynamic Pricing and Pooling in Capacitated Networks," Papers 2307.03994, arXiv.org, revised Nov 2023.
    18. Schwarz, Gregor & Bichler, Martin, 2022. "How to trade thirty thousand products: A wholesale market design for road capacity," Transportation Research Part A: Policy and Practice, Elsevier, vol. 164(C), pages 167-185.
    19. 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.
    20. 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.

    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:2107.08813. 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: http://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.