Optimization in electronic markets: examples in combinatorial auctions
Optimization in electronic markets: examples in combinatorial auctions
复制标题
电子市场的优化：组合拍卖的例子
作者：
S. van Hoesel;R. Müller
组合拍卖为多智能体系统中的机制设计提供了重要的工具。实施时，它们需要解决组合优化问题，例如集合打包和分区问题。我们在本文中分析了组合拍卖中向投标人分配投标问题的复杂性。我们证明了相同资产的情况可以在多项式时间内解决。不同资产的情况在其一般版本中是 NP 困难的。额外的结构（例如资产的完整排序）或温和的附带条件可以使问题得到解决。最后，我们提出了一种使用标准软件在有限时间内解决中小型实例的算法。
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.