Advanced Search
MyIDEAS: Login to save this paper or follow this series

Non-linear anonymous pricing in combinatorial auctions

Contents:

Author Info

  • Drexl, Andreas

    ()
    (Lehrstuhl für Produktion und Logistik, Institut für Betriebswirtschaftslehre, Christian-Albrechts-Universität zu Kiel)

  • Jörnsten, Kurt

    ()
    (Dept. of Finance and Management Science, Norwegian School of Economics and Business Administration)

  • Knof, Diether

    ()
    (Fachgruppe Stochastik, Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel)

Abstract

In combinatorial auctions the pricing problem is of main concern since it is the means by which the auctioneer signals the result of the auction to the participants. In order for the auction to be regarded as fair among the various participants the price signals should be such that a participant that has won a subset of items knows why his bid was a winning bid and that agents that have not acquired any item easily can detect why they lost. The problem in the combinatorial auction setting is that the winner determination problem is a hard integer programming problem and hence in general there does not exist a linear pricing scheme supporting the optimal allocation. This means that single item prices, that support the optimal allocation can in general not be found. In this article we present an alternative. From integer programming duality theory we know that there exist non-linear anonymous price functions that support the optimal allocation. In this paper we will provide a means to obtain a simple form of a non-linear anonymous price system that supports the optimal allocation. Our method relies on the fact that we separate the solution of the winner determination problem and the pricing problem. This separation yields a non-linear price function of a much simpler form compared to when the two problems are solved simultaneously. The pure pricing problem is formulated as a mixed-integer program. If solving this program is too demanding computationally a heuristic can be used which essentially requires us to solve a sequence of linear programming relaxations of a new mixed-integer programming formulation of the pricing problem. The procedure is computationally tested using instances of the combinatorial auctions test suite.

Download Info

If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
File URL: http://www.nhh.no/for/dp/2005/0605.pdf
Our checks indicate that this address may not be valid because: 404 Not Found. If this is indeed the case, please notify (Stein Fossen)
Download Restriction: no

Bibliographic Info

Paper provided by Department of Business and Management Science, Norwegian School of Economics in its series Discussion Papers with number 2005/6.

as in new window
Length: 22 pages
Date of creation: 12 Oct 2005
Date of revision:
Handle: RePEc:hhs:nhhfms:2005_006

Contact details of provider:
Postal: NHH, Department of Business and Management Science, Helleveien 30, N-5045 Bergen, Norway
Phone: +47 55 95 92 93
Fax: +47 55 95 96 50
Email:
Web page: http://www.nhh.no/en/research-faculty/department-of-business-and-management-science.aspx
More information through EDIRC

Related research

Keywords: Combinatorial auctions; set packing; duality theory; non-linear anonymous prices;

Find related papers by JEL classification:

This paper has been announced in the following NEP Reports:

References

References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
as in new window
  1. Milgrom, Paul, 1998. "Putting auction theory to work : the simultaneous ascending auction," Policy Research Working Paper Series 1986, The World Bank.
  2. DeMartini, Christine & Kwasnica, Anthony M. & Ledyard, John O. & Porter, David, 1998. "A New and Improved Design For Multi-Object Iterative Auctions," Working Papers 1054, California Institute of Technology, Division of the Humanities and Social Sciences.
  3. Paul J. Brewer, 1999. "Decentralized computation procurement and computational robustness in a smart market," Economic Theory, Springer, vol. 13(1), pages 41-92.
  4. Milgrom, Paul, 1989. "Auctions and Bidding: A Primer," Journal of Economic Perspectives, American Economic Association, vol. 3(3), pages 3-22, Summer.
  5. Paul Klemperer, 2000. "What Really Matters in Auction Design," Economics Series Working Papers 2000-W26, University of Oxford, Department of Economics.
  6. 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.
  7. Wilson, Robert, 1997. "Nonlinear Pricing," OUP Catalogue, Oxford University Press, number 9780195115826, September.
  8. 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.
  9. 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.
  10. 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.
  11. John McMillan, 1994. "Selling Spectrum Rights," Journal of Economic Perspectives, American Economic Association, vol. 8(3), pages 145-162, Summer.
  12. Karla L. Hoffman & Manfred Padberg, 1993. "Solving Airline Crew Scheduling Problems by Branch-and-Cut," Management Science, INFORMS, vol. 39(6), pages 657-682, June.
  13. Xia, Mu & Stallaert, Jan & Whinston, Andrew B., 2005. "Solving the combinatorial double auction problem," European Journal of Operational Research, Elsevier, vol. 164(1), pages 239-251, July.
  14. Michael H. Rothkopf & Aleksandar Peke\v{c} & Ronald M. Harstad, 1998. "Computationally Manageable Combinational Auctions," Management Science, INFORMS, vol. 44(8), pages 1131-1147, August.
  15. Drexl, Andreas & Jörnsten, Kurt, 2005. "Reflections about pseudo-dual prices in combinatorial auctions," Discussion Papers 2005/1, Department of Business and Management Science, Norwegian School of Economics.
  16. 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.
  17. McAfee, R Preston & McMillan, John, 1987. "Auctions and Bidding," Journal of Economic Literature, American Economic Association, vol. 25(2), pages 699-738, June.
  18. Bikhchandani, Sushil & Ostroy, Joseph M., 2002. "The Package Assignment Model," Journal of Economic Theory, Elsevier, vol. 107(2), pages 377-406, December.
  19. 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.
  20. Herbert E. Scarf, 1989. "Mathematical Programming and Economic Theory," Cowles Foundation Discussion Papers 930, Cowles Foundation for Research in Economics, Yale University.
Full references (including those not matched with items on IDEAS)

Citations

Lists

This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

Statistics

Access and download statistics

Corrections

When requesting a correction, please mention this item's handle: RePEc:hhs:nhhfms:2005_006. See general information about how to correct material in RePEc.

For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Stein Fossen).

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 references are entirely missing, you can add them using this form.

If the full references list an item that is present in RePEc, but the system did not link 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 profile, as there may be some citations waiting for confirmation.

Please note that corrections may take a couple of weeks to filter through the various RePEc services.