Advanced search
1 file | 530.26 KB Add to list

Winner determination in geometrical combinatorial auctions

Author
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 fi nd 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
    • |
    • PDF
    • |
    • 530.26 KB

Citation

Please use this url to cite or link to this publication:

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 find 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: