Abstract: Currently, portal websites are selling their advertising slots via negotiation which not only results in a lot of trading cost but can’t guarantee the optimal revenue of portals. In this paper, we build a combinatorial auction model aiming at the advertising slots allocation problem which can reduce the middle cost. The model can let advertisers express their non-discriminate and super-additive utility of advertising slots. Through a special case of our model, we prove the optimization is a NP hard problem. By using the intrinsic characters of this model, we design four types of heuristic information for bid and two problem solvers: the binary ant colony algorithm and the greedy algorithm. The experiment results show that the performance of different type of heuristic information varies from different contexts and the binary ant colony algorithm is always better than the greedy algorithm.

Key words: management science and engineering, advertising slots allocation, combinatorial auctions, winner determination problem, binary ant colony algorithm

摘要： 目前门户网站的广告机会销售主要通过价格协商的方式,这种方式不仅导致大量的中间交易成本而且分配结果常常无法达到最优。针对该情形,本文结合门户网站广告机会的特点,建立了广告机会分配的组合拍卖模型。该模型能让广告主自由的表达广告机会之间的无差异及互补效用。通过将该模型的特例转化为一般背包问题,文中证明了该问题求解的NP难特性。因此本文针对标的本身的结构提出了四种启发式信息及两种求解器:二元蚁群算法及贪婪算法。最后通过数值实验给出了在不同情况下,不同启发信息的性能并表明了在任何情况下二元蚁群算法比贪婪算法的寻优性更强。

关键词: 管理科学与工程, 广告机会分配, 组合拍卖, 胜出者决定问题, 二元蚁群算法