Pricing combinatorial auctions by a set of linear price vectors

In combinatorial auctions, items are sold simultaneously. A substantial component of an auction mechanism is the pricing scheme. Prices determine the auctioneer’s revenue and, ideally, justify the outcome of the auction to the bidders. Each bidder should be able to see why he won or lost a certain bundle by comparing the determined price of a bundle and his bid’s value. In this paper, we pick up a non-linear anonymous pricing scheme from the literature that consists of a set of linear price vectors. We investigate whether this scheme can guarantee to find prices that support the winner allocation. Furthermore, we refine the pricing scheme by suggesting various objectives in order to evaluate different prices. We consider the computational complexity of the corresponding optimization problems and compare different objectives by means of a computational study using a well-established combinatorial auction test suite.