Title: Reducing Bidding Complexity in Machine Learning-based Combinatorial Auctions
Abstract: Combinatorial Auctions (CAs) allowing multiple items to be auctioned at the same time, have a wide variety of applications in the public sector. One of the main problems of CAs is that it is complex for a bidder to express his valuation of all possible bundles and recent literature has shown that this is a major cause of inefficiencies. To counter these inefficiencies Brero, Lubin and Seuken (2017) introduced a new machine learning-based CA design reducing bidding complexity significantly. This thesis focuses on further reducing bidding complexity by exploring two ideas: allowing a bidder to submit range bids with a lower- and upper-bound and to report preferences in the form of: "I prefer bundle s1 at price p1 over s2 at price p2". Experimental results show that allowing a bidder to submit range bids comes at the price of a small efficiency loss but also leads to a significant reduction of runtime. This computational advantage is an interesting result for applying the design in bigger auctions.The results suggest further, that allowing preferences in the form of: "I prefer bundle s1 at price p1 over s2 at price p2" leads to higher efficiency but at the price of a longer runtime.