Tractable combinatorial auctions and b-matching

摘要

Auctions are the most widely used strategic game-theoretic mechanisms in the Internet. Auctions have been mostly studied from a game-theoretic and economic perspective, although recent work in AI and OR has been concerned with computational aspects of auctions as well. When faced from a computational perspective, combinatorial auctions are perhaps the most challenging type of auctions. Combinatorial auctions are auctions where agents may submit bids for bundles of goods. Given that finding an optimal allocation of the goods in a combinatorial auction is in general intractable, researchers have been concerned with exposing tractable instances of combinatorial auctions. In this work we expose the use of b-matching techniques in the context of combinatorial auctions, and apply them in a non-trivial manner in order to introduce polynomial solutions for a variety of combinatorial auctions.