Solving Combinatorial Exchanges: Optimality via a Few Partial Bids

摘要

In the paper, we have shown a sharp division between markets with superadditive and subadditive valuation functions. The markets where valuation functions are super-additive can be optimally solved using a small number of partial bids (depending on the number of distinct item types). On other hand, if the valuation functions are sub-additive, then even accepting bids partially does not help clear the market.