[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/p/zbw/cauman/624.html
   My bibliography  Save this paper

Column aggregation-based pricing combinatorial auctions

Author

Listed:
  • Drexl, Andreas
  • Jørnsten, Kurt
  • Knof, Diether
Abstract
Combinatorial auctions permitting bids on bundles of items have been developed to remedy the exposure problem associated with single-item auctions. Given winning bundle prices a set of item prices is called market clearing or equilibrium if all the winning bids are greater than or equal and if all the losing bids are less than or equal to the total price of the bundle items. However, the prices for individual items are not readily computed once the winner determination problem is solved. This is due to the duality gap of integer programming caused by the indivisibility of the items. In this paper we propose a family of linear programming models the optimal solution of which is integral "almost always", producing linear prices at the expense of having reduced cost zero for the aggregate winning bids only. We provide a computational proof of this conjecture by an in-depth experimental study of 18,000 instances from the combinatoriaI auction test suite (CATS; see [13]). Summarizing this analysis we have linear prices for all but five of the whole bunch of instances and, hence, there exists a linear price function that supports the optimal allocation of winning bundles.

Suggested Citation

  • Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2007. "Column aggregation-based pricing combinatorial auctions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 624, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    • Handle: RePEc:zbw:cauman:624
    as

    Download full text from publisher

    File URL: https://www.econstor.eu/bitstream/10419/147677/1/manuskript_624.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. A Drexl & K Jørnsten, 2007. "Reflections about pseudo-dual prices in combinatorial auctions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1652-1659, December.
    2. Aleksandar Pekev{c} & Michael H. Rothkopf, 2003. "Combinatorial Auction Design," Management Science, INFORMS, vol. 49(11), pages 1485-1503, November.
    3. Anthony M. Kwasnica & John O. Ledyard & Dave Porter & Christine DeMartini, 2005. "A New and Improved Design for Multiobject Iterative Auctions," Management Science, INFORMS, vol. 51(3), pages 419-434, March.
    4. Paul Milgrom, 2000. "Putting Auction Theory to Work: The Simultaneous Ascending Auction," Journal of Political Economy, University of Chicago Press, vol. 108(2), pages 245-272, April.
    5. Xia, Mu & Koehler, Gary J. & Whinston, Andrew B., 2004. "Pricing combinatorial auctions," European Journal of Operational Research, Elsevier, vol. 154(1), pages 251-270, April.
    6. Bikhchandani, Sushil & Ostroy, Joseph M., 2002. "The Package Assignment Model," Journal of Economic Theory, Elsevier, vol. 107(2), pages 377-406, December.
    7. Michael H. Rothkopf & Aleksandar Pekev{c} & Ronald M. Harstad, 1998. "Computationally Manageable Combinational Auctions," Management Science, INFORMS, vol. 44(8), pages 1131-1147, August.
    8. Oktay Günlük & Lászlo Ladányi & Sven de Vries, 2005. "A Branch-and-Price Algorithm and New Test Problems for Spectrum Auctions," Management Science, INFORMS, vol. 51(3), pages 391-406, March.
    9. R. H. Kwon & G. Anandalingam & L. H. Ungar, 2005. "Iterative Combinatorial Auctions with Bidder-Determined Combinations," Management Science, INFORMS, vol. 51(3), pages 407-418, March.
    10. Sven de Vries & Rakesh V. Vohra, 2003. "Combinatorial Auctions: A Survey," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 284-309, August.
    11. Peter R. Wurman & Michael P. Wellman, 1999. "Equilibrium Prices in Bundle Auctions," Working Papers 99-09-064, Santa Fe Institute.
    12. Delorme, Xavier & Gandibleux, Xavier & Rodriguez, Joaquin, 2004. "GRASP for set packing problems," European Journal of Operational Research, Elsevier, vol. 153(3), pages 564-580, March.
    13. John McMillan, 1994. "Selling Spectrum Rights," Journal of Economic Perspectives, American Economic Association, vol. 8(3), pages 145-162, Summer.
    14. S.J. Rassenti & V.L. Smith & R.L. Bulfin, 1982. "A Combinatorial Auction Mechanism for Airport Time Slot Allocation," Bell Journal of Economics, The RAND Corporation, vol. 13(2), pages 402-417, Autumn.
    15. Tuomas Sandholm & Subhash Suri & Andrew Gilpin & David Levine, 2005. "CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions," Management Science, INFORMS, vol. 51(3), pages 374-390, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2009. "Non-linear anonymous pricing combinatorial auctions," European Journal of Operational Research, Elsevier, vol. 199(1), pages 296-302, November.
    2. Briskorn, Dirk & Knust, Sigrid, 2008. "On Circular 2-Factorizations of the Complete Tripartite Graph," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 636, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.

    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. Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2009. "Non-linear anonymous pricing combinatorial auctions," European Journal of Operational Research, Elsevier, vol. 199(1), pages 296-302, November.
    2. A Drexl & K Jørnsten, 2007. "Reflections about pseudo-dual prices in combinatorial auctions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1652-1659, December.
    3. Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    4. Avenali, Alessandro, 2009. "Exploring the VCG mechanism in combinatorial auctions: The threshold revenue and the threshold-price rule," European Journal of Operational Research, Elsevier, vol. 199(1), pages 262-275, November.
    5. 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.
    6. G. Anandalingam & Robert W. Day & S. Raghavan, 2005. "The Landscape of Electronic Market Design," Management Science, INFORMS, vol. 51(3), pages 316-327, March.
    7. R. H. Kwon & G. Anandalingam & L. H. Ungar, 2005. "Iterative Combinatorial Auctions with Bidder-Determined Combinations," Management Science, INFORMS, vol. 51(3), pages 407-418, March.
    8. Martin Bichler & Pasha Shabalin & Alexander Pikovsky, 2009. "A Computational Analysis of Linear Price Iterative Combinatorial Auction Formats," Information Systems Research, INFORMS, vol. 20(1), pages 33-59, March.
    9. Oktay Günlük & Lászlo Ladányi & Sven de Vries, 2005. "A Branch-and-Price Algorithm and New Test Problems for Spectrum Auctions," Management Science, INFORMS, vol. 51(3), pages 391-406, March.
    10. Tuomas Sandholm & David Levine & Michael Concordia & Paul Martyn & Rick Hughes & Jim Jacobs & Dennis Begg, 2006. "Changing the Game in Strategic Sourcing at Procter & Gamble: Expressive Competition Enabled by Optimization," Interfaces, INFORMS, vol. 36(1), pages 55-68, February.
    11. Richard Li-Yang Chen & Shervin AhmadBeygi & Amy Cohn & Damian R. Beil & Amitabh Sinha, 2009. "Solving Truckload Procurement Auctions Over an Exponential Number of Bundles," Transportation Science, INFORMS, vol. 43(4), pages 493-510, November.
    12. Gediminas Adomavicius & Alok Gupta & Mochen Yang, 2022. "Bidder Support in Multi-item Multi-unit Continuous Combinatorial Auctions: A Unifying Theoretical Framework," Information Systems Research, INFORMS, vol. 33(4), pages 1174-1195, December.
    13. Dirk Briskorn & Kurt Jørnsten & Jenny Nossack, 2016. "Pricing combinatorial auctions by a set of linear price vectors," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(4), pages 1043-1070, October.
    14. Tuomas Sandholm & Subhash Suri & Andrew Gilpin & David Levine, 2005. "CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions," Management Science, INFORMS, vol. 51(3), pages 374-390, March.
    15. Marcelo Olivares & Gabriel Y. Weintraub & Rafael Epstein & Daniel Yung, 2012. "Combinatorial Auctions for Procurement: An Empirical Study of the Chilean School Meals Auction," Management Science, INFORMS, vol. 58(8), pages 1458-1481, August.
    16. Gediminas Adomavicius & Shawn P. Curley & Alok Gupta & Pallab Sanyal, 2012. "Effect of Information Feedback on Bidder Behavior in Continuous Combinatorial Auctions," Management Science, INFORMS, vol. 58(4), pages 811-830, April.
    17. 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.
    18. Anthony M. Kwasnica & John O. Ledyard & Dave Porter & Christine DeMartini, 2005. "A New and Improved Design for Multiobject Iterative Auctions," Management Science, INFORMS, vol. 51(3), pages 419-434, March.
    19. Lehmann, Benny & Lehmann, Daniel & Nisan, Noam, 2006. "Combinatorial auctions with decreasing marginal utilities," Games and Economic Behavior, Elsevier, vol. 55(2), pages 270-296, May.
    20. Lawrence M. Ausubel & Peter Cramton & Paul Milgrom, 2012. "System and Method for a Hybrid Clock and Proxy Auction," Papers of Peter Cramton 12acmhc, University of Maryland, Department of Economics - Peter Cramton, revised 2012.

    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:zbw:cauman:624. 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: ZBW - Leibniz Information Centre for Economics (email available below). General contact details of provider: https://edirc.repec.org/data/ibkiede.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.