Parameterizing the Winner Determination Problem for Combinatorial Auctions

Combinatorial auctions (CAs) have been studied by the multiagent systems community for some time, since these auctions are an effective mechanism for resource allocation whenagents are self-interested. One challenge, however, is thatthe winner-determination problem (WDP) for combinatorialauctions is NP-hard in the general case. However, there areways to leverage meaningful structure in the auction so as toachieve a polynomial-time algorithm for the WDP. In thispaper, using the formal scope of parameterized complexitytheory, we systematically investigate alternative parameterizations of the bids made by the agents (i. e. the input tothe WDP for combinatorial auctions) and are able to determine when a parameterization reduces the complexity ofthe WDP (fixed-parameter tractable), and when a particularparameterization results in the WDP remaining hard (fixed-parameter intractable). Our results are relevant to auctiondesigners since they provide information as to what types ofbidding-restrictions are effective for simplifying the winnerdetermination problem, and which would simply limit theexpressiveness of the agents while not providing any additional computational gains.

Authors

• David Loker University of Waterloo
• Kate Larson University of Waterloo

Keywords

• Auction and mechanism design
• combinatorial auctions
• parameterized complexity