Optimization in Electronic Markets: Examples in Combinational 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 complexity 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.