Research On Revenue Maximization Problem Of Sponsored Search Auction

Sponsored search is the most important type of internet advertising. It has been fur-ther researched by industry and academia in recent years. As the platform of sponsored search, search engine has to trade off the auctioneer revenue, user experience and adver-tiser profit in order to attract more users and advertisers. To simplify the problem, we only focus on the revenue maximization of single-item second-price auction in this paper. Firstly, we analysis the prior schemes and propose a new scheme:quasi-regular expres-sion scheme. Compared with prior schemes, quasi-regular expression scheme is not only more natural but also increases the auctioneer revenue. We prove the revenue maximiza-tion via quasi-regular expression scheme is strongly NP-hard and design a heuristic algo-rithm. Then, we compare with the optimal revenue of quasi-regular expression scheme, the revenue of heuristic algorithm and the optimal revenue of other prior schemes via three datasets. The experiments show that the optimal revenue of quasi-regular expres-sion scheme is obviously better than attribute hiding scheme and the revenue of heuristic algorithm is nearly equal to the optimal revenue of quasi-regular expression scheme. Fi-nally, on account of the unreason of setting the valuation for each context one by one, we design the GUI that advertisers need to fill out when submitting the advertisement infor-mation. It involves the bidding constraint, that is each row in valuation matrix has only one type of non-zero value. We analysis the K-anonymous signaling scheme and K cardi-nality constraint signaling scheme with this bidding constraint. We prove that the revenue maximization of K-anonymous signaling scheme is NP-hard, the revenue maximization and welfare maximization of K cardinality constraint signaling scheme are NP-hard.