IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v44y1998i8p1131-1147.html
   My bibliography  Save this article

Computationally Manageable Combinational Auctions

Author

Listed:
  • Michael H. Rothkopf

    (Faculty of Management and Rutgers Center for Operations Research, Rutgers University, New Brunswick, New Jersey 08903-5062)

  • Aleksandar Pekev{c}

    (BRICS, Department of Computer Science, University of Aarhus, Denmark)

  • Ronald M. Harstad

    (Faculty of Management and Rutgers Center for Operations Research, Rutgers University, New Brunswick, New Jersey 08903-5062)

Abstract

There is interest in designing simultaneous auctions for situations such as the recent FCC radio spectrum auctions, in which the value of assets to a bidder depends on which other assets he or she wins. In such auctions, bidders may wish to submit bids for combinations of assets. When this is allowed, the problem of determining the revenue maximizing set of nonconflicting bids can be difficult. We analyze this problem, identifying several different structures of permitted combinational bids for which computational tractability is constructively demonstrated and some structures for which computational tractability cannot be guaranteed.

Suggested Citation

  • Michael H. Rothkopf & Aleksandar Pekev{c} & Ronald M. Harstad, 1998. "Computationally Manageable Combinational Auctions," Management Science, INFORMS, vol. 44(8), pages 1131-1147, August.
    • Handle: RePEc:inm:ormnsc:v:44:y:1998:i:8:p:1131-1147
    DOI: 10.1287/mnsc.44.8.1131
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.44.8.1131
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.44.8.1131?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. John J. Bartholdi & James B. Orlin & H. Donald Ratliff, 1980. "Cyclic Scheduling via Integer Programs with Circular Ones," Operations Research, INFORMS, vol. 28(5), pages 1074-1085, October.
    2. Rosenthal, Robert W. & Wang, Ruqu, 1996. "Simultaneous Auctions with Synergies and Common Values," Games and Economic Behavior, Elsevier, vol. 17(1), pages 32-55, November.
    3. Branco, Fernando, 1995. "Multi-object Auctions: On the Use of Combinational Bids," CEPR Discussion Papers 1216, C.E.P.R. Discussion Papers.
    4. Krishna, Vijay & Rosenthal, Robert W., 1996. "Simultaneous Auctions with Synergies," Games and Economic Behavior, Elsevier, vol. 17(1), pages 1-31, November.
    5. Michael H. Rothkopf, 1977. "Bidding in Simultaneous Auctions with a Constraint on Exposure," Operations Research, INFORMS, vol. 25(4), pages 620-629, August.
    6. Jeffrey S. Banks & John O. Ledyard & David P. Porter, 1989. "Allocating Uncertain and Unresponsive Resources: An Experimental Approach," RAND Journal of Economics, The RAND Corporation, vol. 20(1), pages 1-25, Spring.
    7. John McMillan, 1994. "Selling Spectrum Rights," Journal of Economic Perspectives, American Economic Association, vol. 8(3), pages 145-162, Summer.
    8. 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.
    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. Levin, Jonathan, 1997. "An Optimal Auction for Complements," Games and Economic Behavior, Elsevier, vol. 18(2), pages 176-192, February.
    2. Peter Cramton, 2002. "Spectrum Auctions," Papers of Peter Cramton 01hte, University of Maryland, Department of Economics - Peter Cramton, revised 16 Jul 2001.
    3. Sunnevag, Kjell J., 2000. "Designing auctions for offshore petroleum lease allocation," Resources Policy, Elsevier, vol. 26(1), pages 3-16, March.
    4. Chernomaz, Kirill & Levin, Dan, 2012. "Efficiency and synergy in a multi-unit auction with and without package bidding: An experimental study," Games and Economic Behavior, Elsevier, vol. 76(2), pages 611-635.
    5. R. Preston McAfee & John McMillan, 1996. "Analyzing the Airwaves Auction," Journal of Economic Perspectives, American Economic Association, vol. 10(1), pages 159-175, Winter.
    6. Aleksandar Pekev{c} & Michael H. Rothkopf, 2003. "Combinatorial Auction Design," Management Science, INFORMS, vol. 49(11), pages 1485-1503, November.
    7. Sven de Vries & Rakesh V. Vohra, 2003. "Combinatorial Auctions: A Survey," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 284-309, August.
    8. Martin Bichler & Alexander Pikovsky & Thomas Setzer, 2009. "An Analysis of Design Problems in Combinatorial Procurement Auctions," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 1(1), pages 111-117, February.
    9. Nicolas Gruyer & Nathalie Lenoir, 2003. "Auctioning airport slots (?)," Post-Print hal-01021718, HAL.
    10. Lawrence M. Ausubel & Peter Cramton & R. Preston McAfee & John McMillan, 1997. "Synergies in Wireless Telephony: Evidence from the Broadband PCS Auctions," Journal of Economics & Management Strategy, Wiley Blackwell, vol. 6(3), pages 497-527, September.
    11. Indranil Chakraborty, 2004. "Multi-Unit Auctions with Synergy," Economics Bulletin, AccessEcon, vol. 4(8), pages 1-14.
    12. Englmaier, Florian & Guillén, Pablo & Llorente, Loreto & Onderstal, Sander & Sausgruber, Rupert, 2009. "The chopstick auction: A study of the exposure problem in multi-unit auctions," International Journal of Industrial Organization, Elsevier, vol. 27(2), pages 286-291, March.
    13. Barbosa, Klenio & Boyer, Pierre C., 2021. "Discrimination in Dynamic Procurement Design with Learning-by-doing," International Journal of Industrial Organization, Elsevier, vol. 77(C).
    14. Cramton, Peter C, 1995. "Money Out of Thin Air: The Nationwide Narrowband PCS Auction," Journal of Economics & Management Strategy, Wiley Blackwell, vol. 4(2), pages 267-343, Summer.
    15. Branco, Fernando, 1997. "Sequential auctions with synergies: An example," Economics Letters, Elsevier, vol. 54(2), pages 159-163, February.
    16. Park, Sunju & Rothkopf, Michael H., 2005. "Auctions with bidder-determined allowable combinations," European Journal of Operational Research, Elsevier, vol. 161(2), pages 399-415, March.
    17. Ausubel Lawrence M & Milgrom Paul R, 2002. "Ascending Auctions with Package Bidding," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 1(1), pages 1-44, August.
    18. Angeles de Frutos, Maria & Rosenthal, Robert W., 1998. "On Some Myths about Sequenced Common-Value Auctions," Games and Economic Behavior, Elsevier, vol. 23(2), pages 201-221, May.
    19. Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    20. Filiz-Ozbay, Emel & Lopez-Vargas, Kristian & Ozbay, Erkut Y., 2015. "Multi-object auctions with resale: Theory and experiment," Games and Economic Behavior, Elsevier, vol. 89(C), pages 1-16.

    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:inm:ormnsc:v:44:y:1998:i:8:p:1131-1147. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.