Auctions and bidding: A guide for computer scientists SIMON PARSONS Department of Computer and Information Science, Brooklyn College, City University of New York, 2900 Bedford Avenue, Brooklyn, NY 11210, USA. [email protected]
and JUAN A. RODRIGUEZ-AGUILAR IIIA, Institut d’Investigaci´o en Intel·lig`encia Artificial, CSIC, Spanish Scientific Research Council, Campus de la UAB, 08193 Bellaterra, SPAIN. [email protected]
and MARK KLEIN Center for Coordination Science, Massachusetts Institute of Technology, 3 Cambridge Center, NE20-336, Cambridge, MA 02142, USA. m [email protected]
There is a veritable menagerie of auctions — single dimensional, multi-dimensional, single sided, double sided, first price, second price, English, Dutch, Japanese, sealed bid — and these have been extensively discussed and analysed in the economics literature. The main purpose of this paper is to survey this literature from a computer science perspective, primarily from the viewpoint of computer scientists who are interested in learning about auction theory, and to provide pointers into the economics literature for those who want a deeper technical understanding. In addition, since auctions are an increasingly important topic in computer science, we also look at work on auctions from the computer science literature. Overall, our aim is to identifying what both these bodies of work these tell us about creating electronic auctions. Categories and Subject Descriptors: J.4 [Computer Applications]: Social and Behavioural Sciences—Economics; I.2.11 [Distributed Artificial Intelligence]: Multiagent Systems General Terms: Economics, Design, Algorithms
ACM Journal Name, Vol. V, No. N, Month 20YY, Pages 1–0??.
1. INTRODUCTION For years most people’s view of an auction was that formed by films and television news. Auctions were the way that paintings by Picasso or Van Gogh were sold. They took place in stately halls where a man with an imperious manner stood on a stage at a lectern calling out fairy-tale prices, “Am I bid 20 million?, Thank you ma’am, 21 million?”, to a hushed room. Ranged in front of the stage were rows of chairs occupied by nervous bidders. As the prices were called, the bidders nodded, or winked, or coughed and the auctioneer would acknowledge them with a nod of his own. If this was a news report, the painting would be sold to a Japanese bank and the sale would be proclaimed a record. If it was a film comedy, somebody would cough in the wrong place, or wave to a friend, and end up accidentally buying a painting they couldn’t afford.1 If one had more direct experience of auctions, it would most likely have been with an auction that was recognisably a variation of the film/TV version. However, in recent years, this has changed. Now many more people than ever before are taking part in auctions over the internet, both buying and selling goods. Even those of us who don’t use the auction facilities provided by eBay or its competitors2 may know of the auctions run by governments worldwide to allocate the radio-frequency spectrum to mobile phone operators. Even before the number of auctions started to multiply, there was a considerably variety of different types of auctions — as discussed below, the traditional auction used to sell fish in Spain and agricultural goods in the Netherlands differs from our parody example, and there are many other kinds of auctions described by [Cassady 1967]. In recent years, this variety has increased, driven by problems with traditional kinds of auction, both in terms of the way that they end up deciding who gets what is being auctioned and how they might be implemented in settings such as the internet. Indeed, a veritable menagerie of auctions exists and crops up in various places — single dimensional, multi-dimensional, single sided, double sided, first price, second price, kth price, English, Dutch, Japanese, open-cry sealed bid, and combinatorial. This profusion can be overwhelming for a newcomer to the field, specially computer scie