Research On Web Advertisement Allocation Based On Combinationary Auction

As a part of the most widely distributed multimedia market,the internet advertisement became a major component of emerging advertising media by its abundant content,vivid form,great amount of browsing and exponential growth rate.It brought huge profits to the operators of the website and the advertisers involved every year.The publisher use auctions to determine a reasonable allocation rule and a payment rull for each advertiser.These auction mechanisms maintain the flexibility of participators preferences,convenient allocation of esadvertising resources,and optimization profits of all participants.In the auction system,the auction organizer need to design a reasonable mechanism,to ensure the system of incentive compatibility,individual rationality,efficiency and other positive properties;auction participants as rational game participants,have to develop the most beneficial bidding strategy according to the opponent's information.From the perspective of resource owner and bidder,this dissertation focuses on the theoretical research and practical application of internet advertisement combination auction mechanism and aims at optimizing the benefits of all parties.According to the non-incentive compatibility of the existing auction mechanism,an optimal bid strategy is presented.For the emerging internet video advertising market,the video advertisement auction problem is formally defined.Two auction mechanisms are designed to enhance the auctioneer's profit and the overall efficiency.In order to solve the problem which optimal objective can not be solved in polynomial time in practical application,we design efficient evolutionary algorithms for the optimization.The main research contents and innovations in this paper are shown as below:(1)From the perspective of resource competitors,we analyzed the bidding strategy in general second price auction,and presented an effective bidding model.This model can be converted to a multimensinal multi-choice knapsack problem(MMKP).An improved quantum behavior partial swarm optimizing algorithm is proposed to find the approximate optimal reasult in the bidding model which can be solved in polynomial time.In addition to the history optimal position and the global optimal position of particles,the algorithm used the motion trend between two iterations,which keep the diversity of the population.The Algorithm is applied to the standard benchmark test instance and compared with other evolutionary algorithms.Besides it is used in the simulation in general second price auction in the proposed bidding model and shown a better profit than other bidding strategies.(2)In order to maximize the revenue of resource owners,a truthful auction mechanism from heterogeneous multi-item under budget constraint has been designed: We present a formal description,bidding language and definitions of properties according to characteristics of video ad firstly.We designed an individual rationality,incentive compatibility and non-positive transform mechanism according to the characteristics of video advertising issues without limiting the distribution of the bidder's valuations.Besides these properties,we analyzed the revenue of this mechanism mathematically and gave the upper bound and lower bound of the revenue.At the end of this chapter,the mechanism is simulated and compared with VCG and greedy mechanism with social welfare and revenue properties.(3)From the object of optimize the allocation efficiency,the improved binary quantum particle swarm optimization algorithm is used to solve the the winner determination problem(WDP).The winner determination problem is a key point in the combinational auction mechanism.A globe optimal solution of WDP is the precondition of incentive compatible for the mechanism.Hence,we focus on the WDP and proposed an improved binary quantum partial swam optimization algorithm.In this algorithm,a modified pre-initialization operator,local attractor and transfer function are proposed,and a penalty function is used to convert the objective function of constraint optimization as non-constrained optimization.Furthermore,a disturbance factor is added according to the diversity of the population to help the algorithm escaped from the local optimal solution.The validity of the algorithm is verified by a series of experiments.(4)To maximize the efficiency of the video advertisement auction system,we design a video auction mechanism based on VCG mechanism and give an approximate optimization solution.we relaxed the budget constrain.An efficiency truthfulness mechanism.is designed for the environment of video advertisement market,in which use the optimal allocation of social resources as the target.In this mechanism,the allocation function is abstracted as a nonlinear programming problem and solved by a quantum particle swarm optimization algorithm.We verified the results of this mechanism has better performent than the other evolutionary algrithems by simulation experiments.