Winner determination in geometrical combinatorial auctions
研究了物品可排成行的拍卖场景，提出一种动态规划算法在多项式时间内求解无间隙连通投标的k行胜者确定问题，并证明了2行有间隙投标问题的NP难性。
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.