Properties of the DGS-Auction Algorithm
(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:
https://lup.lub.lu.se/record/2409872
- author
- Andersson, Tommy LU and Andersson, Christer
- organization
- publishing date
- 2012
- 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
- 2016-04-01 14:48:04
- date last changed
- 2022-01-28 02:31:28
@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}},
keywords = {{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}},
doi = {{10.1007/s10614-010-9237-8}},
volume = {{39}},
year = {{2012}},
}