DIMACS Workshop on Computational Issues in Auction Design

October 7 - 8, 2004
DIMACS Center, CoRE Building, Rutgers University

Jayant Kalagnanam, IBM Watson Lab, jayant@us.ibm.com
Eric Maskin, School of Social Science, Institute for Advanced Study, maskin@ias.edu
David Parkes, Harvard University, parkes@eecs.harvard.edu
Aleksandar Pekec, Fuqua School of Business, Duke University, pekec@duke.edu
Michael Rothkopf, Rutgers University, rothkopf@rutcor.rutgers.edu
Presented under the auspices of the Special Focus on Computation and the Socio-Economic Sciences.

Recent advances in information technology and its rapid acceptance by the business community have allowed for expediting of complex business transactions. The most prominent example involves use of auctions in corporate procurement and in government deregulation efforts. When many items with interrelated values are being sold, economic efficiency can be increased by allowing bids on combinations of items. Procedures for auctioning combinations of items have inherent computational problems to overcome, and the emergence of these issues has sparked considerable research activity in the computer science and combinatorial optimization communities. The most prominent example is combinatorial auctions in which multiple goods are auctioned and bidders have and wish to express different valuations on which goods complement each other and which goods substitute for each other. (For recent reviews see [Cramton, Shoham, and Steinberg (2003), DeVries and Vohra, Pekec and Rothkopf.) Allowing bidders to submit "all-or-nothing'' bids for combinations of goods yields NP-complete allocation problems that need to be solved efficiently when proper care is given to designing an auction [Rothkopf, Pekec, and Harstad (1998)]. Furthermore, bidders face computational and communication problems in combinatorial auctions since they might not be feasibly able to express all possible preferences for all subsets of goods. Another area of auction design that has been developing rapidly in research and in practice is short-term electricity auctions in which allowing bidders to make bids that reflect their nonconvex costs requires solving large mixed integer programming problems and finding prices that support decentralized generation and transmission operations [Hobbs, Rothkopf, O'Neill, and Chao (2001)].

In addition to the research community, these combinatorial and optimization problems that are involved with auction design and general microeconomic considerations have generated interest from IT businesses such as IBM, industrial users of combinatorial procurement auctions such as Mars, Inc. [Hohner, Rich, Reid, Davenport, Kalagnanam,Lee], and government agencies such as the FCC [FCC Combinatorial Bidding Conference (2000), FCC Second Combinatorial Bidding Conference (2001), The Federal Communications Commission Public Notice (2002)]and the FERC-regulated electricity system operators PJM and NYISO (see www.pjm.com, and www.nyiso.com). This workshop will bring together researchers in computer science, optimization, operations research and economics who are working on computational aspects of auction design. The aim is to discuss the most prominent issues in auction design and try to design implementable and efficient auction procedures that allow for a large preference space while maintaining several desirable properties such as fairness, failure-freeness, and computational feasibility for all participants.


Cramton, P., Shoham, Y., and Steinberg, R. (eds.), Combinatorial Auctions, 2005, to appear.

DeVries, S., and Vohra, R.V., "Combinatorial auctions: A survey,'' INFORMS Journal of Computing, 15, 2003, 284-309.

FCC 2002, The Federal Communications Commission Public Notice DA02-260.

FCC Combinatorial Bidding Conference, Wye River Conf. Center, Queenstown, MD, 2000.

FCC Second Combinatorial Bidding Conference, Wye River Conf. Center, Queenstown, MD, 2001.

Hobbs, B. F., Rothkopf, M.H., O'Neill, R.P., and Chao, H. (eds.), Power Generation Unit Commitment Models: The Next Generation, Kluwer, Norwell, MA, 2001.

Hohner, G., J. Rich, G. Reid, A.J. Davenport; J.R. Kalagnanam, H.S. Lee, C., "Combinatorial and quality discount procurement auctions with mutual benefits at Mars Incorporated,'' Interfaces, 33, 2003, 23-35.

Pekec, A., and Rothkopf, M.H., "Combinatorial auction design,'' Management Science, 49, 2003, 1485-1503.

Rothkopf, M.H., Pekec, A, and Harstad, R.M., "Computationally manageable combinational auctions, Management Science, 44, 1998, 1131-1147.

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on September 27, 2004.