Advanced

Properties of the DGS-Auction Algorithm

Andersson, Tommy LU and Andersson, Christer (2012) In Computational Economics 39(2). p.113-133
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Multi-item auctions, Algorithmic properties, Graphs, Computer, simulations
in
Computational Economics
volume
39
issue
2
pages
113 - 133
publisher
Springer
external identifiers
  • wos:000299919200001
  • scopus:84856254111
ISSN
0927-7099
DOI
10.1007/s10614-010-9237-8
language
English
LU publication?
yes
id
ced98974-55e3-4bc0-89ec-ac01deda57fb (old id 2409872)
date added to LUP
2012-03-27 12:02:50
date last changed
2017-01-01 06:26:31
@article{ced98974-55e3-4bc0-89ec-ac01deda57fb,
  abstract     = {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.},
  author       = {Andersson, Tommy and Andersson, Christer},
  issn         = {0927-7099},
  keyword      = {Multi-item auctions,Algorithmic properties,Graphs,Computer,simulations},
  language     = {eng},
  number       = {2},
  pages        = {113--133},
  publisher    = {Springer},
  series       = {Computational Economics},
  title        = {Properties of the DGS-Auction Algorithm},
  url          = {http://dx.doi.org/10.1007/s10614-010-9237-8},
  volume       = {39},
  year         = {2012},
}