Properties of the DGS-Auction Algorithm
Author
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.
Department/s
Publishing year
2012
Language
English
Pages
113-133
Publication/Series
Computational Economics
Volume
39
Issue
2
Document type
Journal article
Publisher
Springer
Topic
- Economics and Business
- Economics
Keywords
- Multi-item auctions
- Algorithmic properties
- Graphs
- Computer
- simulations
Status
Published
ISBN/ISSN/Other
- ISSN: 0927-7099