Winner determination in geometrical combinatorial auctions

B. Vangerven, D.R. Goossens, F.C.R. Spieksma

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)


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 programing 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 programing algorithm to solve the case where bidders submit connected, but not necessarily gap-free bids in a 2-row and a 3-row problem.

Original languageEnglish
Pages (from-to)254-263
Number of pages10
JournalEuropean Journal of Operational Research
Issue number1
Publication statusPublished - 1 Apr 2017
Externally publishedYes


  • Auctions
  • Dynamic programing
  • Winner determination problem
  • Complexity
  • Rows


Dive into the research topics of 'Winner determination in geometrical combinatorial auctions'. Together they form a unique fingerprint.

Cite this