IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2005087.html

Mechanism design for multiple item procurement using a distributed ellipsoid algorithm

Author

Listed:
  • MILLER, Andrew J.
  • MISHRA, Debasis
  • VEERAMANI, Dharmaraj

Abstract

We study a problem in a procurement setting in which an Original Equipment Manufacturer (OEM) wants to procure a set of items from a set of suppliers. Each supplier incurs a cost for supplying any subset/bundle of items, and each supplier's cost information is known only to him. The goal is to determine (i) an efficient allocation of suppliers to items and (ii) appropriate payments for suppliers. We formulate the problem of determining which supplier should supply what items as an integer program. We develop a method, which is based on the ellipsoid method, that solves the dual of the linear relaxation of the problem in polynomial time. We also show that the linear relaxation has an integral optimal solution.

Suggested Citation

  • MILLER, Andrew J. & MISHRA, Debasis & VEERAMANI, Dharmaraj, 2005. "Mechanism design for multiple item procurement using a distributed ellipsoid algorithm," LIDAM Discussion Papers CORE 2005087, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2005087
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp2005.html
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. de Vries, Sven & Schummer, James & Vohra, Rakesh V., 2007. "On ascending Vickrey auctions for heterogeneous objects," Journal of Economic Theory, Elsevier, vol. 132(1), pages 95-118, January.
    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. Mishra, Debasis & Parkes, David C., 2007. "Ascending price Vickrey auctions for general valuations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
    2. , & ,, 2015. "Strategy-proofness and efficiency with non-quasi-linear preferences: a characterization of minimum price Walrasian rule," Theoretical Economics, Econometric Society, vol. 10(2), May.
    3. Bikhchandani, Sushil & Ostroy, Joseph M., 2006. "Ascending price Vickrey auctions," Games and Economic Behavior, Elsevier, vol. 55(2), pages 215-241, May.
    4. Siddharth Prasad & Maria-Florina Balcan & Tuomas Sandholm, 2025. "Weakest Bidder Types and New Core-Selecting Combinatorial Auctions," Papers 2505.13680, arXiv.org.
    5. Tomoya Kazumura & Shigehiro Serizawa, 2016. "Efficiency and strategy-proofness in object assignment problems with multi-demand preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(3), pages 633-663, October.
    6. Zhiling Guo & Gary J. Koehler & Andrew B. Whinston, 2012. "A Computational Analysis of Bundle Trading Markets Design for Distributed Resource Allocation," Information Systems Research, INFORMS, vol. 23(3-part-1), pages 823-843, September.
    7. Mingrong Wang & Mingxi Wang & Lihua Lang, 2017. "Reconsidering Carbon Permits Auction Mechanism: An Efficient Dynamic Model," The World Economy, Wiley Blackwell, vol. 40(8), pages 1624-1645, August.
    8. Mishra, Debasis & Talman, Dolf, 2010. "Characterization of the Walrasian equilibria of the assignment model," Journal of Mathematical Economics, Elsevier, vol. 46(1), pages 6-20, January.
    9. Ervasti, Valtteri & Leskelä, Riikka-Leena, 2010. "Allocative efficiency in simulated multiple-unit combinatorial auctions with quantity support," European Journal of Operational Research, Elsevier, vol. 203(1), pages 251-260, May.
    10. Shirata, Yasuhiro, 2017. "First price package auction with many traders," Journal of Mathematical Economics, Elsevier, vol. 69(C), pages 71-83.
    11. 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.
    12. Minghui Lai & Weili Xue & Qian Hu, 2019. "An Ascending Auction for Freight Forwarder Collaboration in Capacity Sharing," Transportation Science, INFORMS, vol. 53(4), pages 1175-1195, July.
    13. Eickhoff, Katharina & Neuwohner, Meike & Peis, Britta & Rieken, Niklas & Vargas Koch, Laura & Végh, Lázló A., 2025. "Faster dynamic auctions via polymatroid sum," LSE Research Online Documents on Economics 127980, London School of Economics and Political Science, LSE Library.
    14. Martin Bichler & Stefan Waldherr, 2022. "Core Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions," Operations Research, INFORMS, vol. 70(1), pages 241-264, January.
    15. Andersson, Tommy & Erlanson, Albin, 2013. "Multi-item Vickrey–English–Dutch auctions," Games and Economic Behavior, Elsevier, vol. 81(C), pages 116-129.
    16. De Liu & Adib Bagh, 2020. "Preserving Bidder Privacy in Assignment Auctions: Design and Measurement," Management Science, INFORMS, vol. 66(7), pages 3162-3182, July.
    17. Lamy, Laurent, 2012. "On minimal ascending auctions with payment discounts," Games and Economic Behavior, Elsevier, vol. 75(2), pages 990-999.
    18. Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    19. Zhang, Xieji, 2024. "The ascending auction with flexible reporting," Mathematical Social Sciences, Elsevier, vol. 132(C), pages 28-39.
    20. Laurent Lamy, 2007. "The Ausubel-Milgrom Proxy Auction with Final Discounts," Working Papers 2007-25, Center for Research in Economics and Statistics.

    More about this item

    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:cor:louvco:2005087. 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: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    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.