Winner determination in geometrical combinatorial auctions

详细信息    查看全文

• 作者：Bart Vangerven ; ^a ; ^{bart.vangerven@kuleuven.be} ; Dries R. Goossens^b ; ^{dries.goossens@ugent.be} ; Frits C.R. Spieksma^a ; ^{frits.spieksma@kuleuven.be}
• 关键词：Auctions ; Dynamic programing ; Winner determination problem ; Complexity ; Rows
• 刊名：European Journal of Operational Research
• 出版年：2017
• 出版时间：1 April 2017
• 年：2017
• 卷：258
• 期：1
• 页码：254-263
• 全文大小：1320 K
• 卷排序：258

文摘

We study the winner determination problem (WDP) in geometrical combinatorial auctions. For connected and gap-free bids we provide an efficient dynamic programing algorithm. In grid settings, the WDP is NP-hard even when bids are restricted to row/column bids. For gap-free bids, the WDP is NP-hard on 2 rows. For connected bids, the WDP is easy on 3 rows or fewer.