Optimization in electronic markets: examples in combinatorial auctions

Combinatorial auctions provide an important tool for mechanism design in multi-agent systems. When implemented they require to solve combinatorial optimization problems such as set packing and partitioning problems. We present in this paper an analysis of the com-plexity of the problem to assign bids to bidders in combinatorial auctions. We show that the case of identical assets can be solved in polynomial time. The case of non-identical assets is in its general version NP-hard. Extra structure, like a complete ordering of assets, or mild side conditions make the problem solvable. Finally, we present an algorithm to solve small and medium sized instances in a limited time using standard software