Computational complexity of the winner determination problem for geometrical combinatorial auctions

We consider auctions of items that can be arranged in rows, for instance pieces of land for real estate development. The objective is, given bids on subsets of items, to nd a subset of bids that maximizes auction revenue (often referred to as the winner determination problem). We show that for a k-row problem with connected and gap-free bids, the winner determination problem can be solved in polynomial time, using a dynamic programming algorithm. 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