Winner determination in geometrical combinatorial auctions

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

4 Citaten (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.

Originele taal-2Engels
Pagina's (van-tot)254-263
Aantal pagina's10
TijdschriftEuropean Journal of Operational Research
Nummer van het tijdschrift1
StatusGepubliceerd - 1 apr. 2017
Extern gepubliceerdJa


Duik in de onderzoeksthema's van 'Winner determination in geometrical combinatorial auctions'. Samen vormen ze een unieke vingerafdruk.

Citeer dit