For the online problem of Internet Search Engines’ Keyword Advertisement-place auction, two online models are present in this paper. The number of the auction phases is known or unknown beforehand respectively in the two models. For the first model we propose the Multi-Level of Accepted Price Strategy (abbr. MLAP) and prove it to be O(Φ1/4 )-competitive, where Φ is the ratio of the highest bid to the lowest one in the auction. For the second model a strategy similar to the first one (abbr. MLAP1) is put forward and proved to be (2√ Φ − 1)-competitive. Furthermore, the experimental results show that in both models the experimental ratios between what the optimal strategy and the online strategies gain are much better than the theoretical ones, indicating that the two strategies perform much better in practice than in theory. In practice, these strategies may help to realize the automatic auction of heterogeneous objects that have similar traits to advertisement-places.
Zhang, E, "Competitive Strategies for On-Line Advertisement-Place Auction" (2005). ICEB 2005 Proceedings. 44.