Tommy Andersson
Professor
Properties of the DGS-Auction Algorithm
Författare
Summary, in English
This paper investigates algorithmic properties and overall performance of the exact auction algorithm in Demange, Gale and Sotomayor (J. Polit. Economy 94: 863-872, 1986) or DGS for short. This task is achieved by interpreting DGS as a graph and by conducting a large number of computer simulations. The crucial step in DGS is when the auctioneer selects a so-called minimal overdemanded set of items because the specific selection may affect a number of performance measures such as the number of iterations and the ratio of elicited preferences. The computational results show that (i) DGS graphs are typically large even for relatively small numbers of bidders and items, (ii) DGS converges slowly and (iii) DGS performs well in terms of preference elicitation. The paper also demonstrates that the modification to DGS based on the Ford-Fulkerson algorithm outperforms all investigated rules for selecting a minimal overdemanded set of items in DGS both in terms of termination speed and preference elicitation.
Avdelning/ar
- Nationalekonomiska institutionen
Publiceringsår
2012
Språk
Engelska
Sidor
113-133
Publikation/Tidskrift/Serie
Computational Economics
Volym
39
Issue
2
Dokumenttyp
Artikel i tidskrift
Förlag
Springer
Ämne
- Economics and Business
- Economics
Nyckelord
- Multi-item auctions
- Algorithmic properties
- Graphs
- Computer
- simulations
Status
Published
ISBN/ISSN/Övrigt
- ISSN: 0927-7099