Winner determination in geometrical combinatorial auctions
- Author
- Bart Vangerven (UGent) , Dries Goossens (UGent) and Frits Spieksma
- Organization
- Abstract
- We consider auctions of items that can be arranged in rows. Examples of such a setting appear in allocating pieces of land for real estate development, or seats in a theater or stadium. The objective is, given bids on subsets of items, to find a subset of bids that maximizes auction revenue (often referred to as the winner determination problem). We describe a dynamic programming algorithm which, for a k-row problem with connected and gap-free bids, solves the winner determination problem in polynomial time. We study the complexity for bids in a grid, complementing known results in literature. Additionally, we study variants of the geometrical winner determination setting. We provide a NP-hardness proof for the 2-row setting with gap-free bids. Finally, we extend this dynamic programming algorithm to solve the case where bidders submit connected, but not necessarily gap-free bids in a 2-row and a 3-row problem.
- Keywords
- complexity, rows, dynamic programming, winner determination problem, Auctions
Downloads
-
Winner Determination in Geometrical Combinatorial Auctions.pdf
- full text
- |
- open access
- |
- |
- 530.26 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU-8058943
- MLA
- Vangerven, Bart, et al. “Winner Determination in Geometrical Combinatorial Auctions.” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol. 258, no. 1, 2017, pp. 254–63, doi:10.1016/j.ejor.2016.08.037.
- APA
- Vangerven, B., Goossens, D., & Spieksma, F. (2017). Winner determination in geometrical combinatorial auctions. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 258(1), 254–263. https://doi.org/10.1016/j.ejor.2016.08.037
- Chicago author-date
- Vangerven, Bart, Dries Goossens, and Frits Spieksma. 2017. “Winner Determination in Geometrical Combinatorial Auctions.” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 258 (1): 254–63. https://doi.org/10.1016/j.ejor.2016.08.037.
- Chicago author-date (all authors)
- Vangerven, Bart, Dries Goossens, and Frits Spieksma. 2017. “Winner Determination in Geometrical Combinatorial Auctions.” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 258 (1): 254–263. doi:10.1016/j.ejor.2016.08.037.
- Vancouver
- 1.Vangerven B, Goossens D, Spieksma F. Winner determination in geometrical combinatorial auctions. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. 2017;258(1):254–63.
- IEEE
- [1]B. Vangerven, D. Goossens, and F. Spieksma, “Winner determination in geometrical combinatorial auctions,” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol. 258, no. 1, pp. 254–263, 2017.
@article{8058943, abstract = {{We consider auctions of items that can be arranged in rows. Examples of such a setting appear in allocating pieces of land for real estate development, or seats in a theater or stadium. The objective is, given bids on subsets of items, to find a subset of bids that maximizes auction revenue (often referred to as the winner determination problem). We describe a dynamic programming algorithm which, for a k-row problem with connected and gap-free bids, solves the winner determination problem in polynomial time. We study the complexity for bids in a grid, complementing known results in literature. Additionally, we study variants of the geometrical winner determination setting. We provide a NP-hardness proof for the 2-row setting with gap-free bids. Finally, we extend this dynamic programming algorithm to solve the case where bidders submit connected, but not necessarily gap-free bids in a 2-row and a 3-row problem.}}, author = {{Vangerven, Bart and Goossens, Dries and Spieksma, Frits}}, issn = {{0377-2217}}, journal = {{EUROPEAN JOURNAL OF OPERATIONAL RESEARCH}}, keywords = {{complexity,rows,dynamic programming,winner determination problem,Auctions}}, language = {{eng}}, number = {{1}}, pages = {{254--263}}, title = {{Winner determination in geometrical combinatorial auctions}}, url = {{http://doi.org/10.1016/j.ejor.2016.08.037}}, volume = {{258}}, year = {{2017}}, }
- Altmetric
- View in Altmetric
- Web of Science
- Times cited: