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

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