The Model And Algorithms For Combinatorial Auction In Internet

With the boom and development of the global E-Business,new commercial patterns and opportunities are created.The online auction seizes this golden chance of human society civilization development and has become an important way of commodity transactions.Many researches about online auction protocol and algorithm have been done.In these researches,combinatorial auction which sells multiple goods with interdependent value simultaneously and allow bidders to bid on any combination of goods is a new hot field.It tends to lead to more efficient allocations than traditional auctions in multi-item auctions,while keeping low risks for bidders.However,the winner determination problem in combinatorial auctions is NP-hard.And there exists no effective method to solve this problem at present.So with the analysis of its characteristics,this thesis proposes an advanced EO algorithm embedded with Fitting-First heuristic.Compared with the traditional algorithms,it is easy to operate and can get better results.The contents of this thesis are as follows:First,this thesis systematically summarizes and analyzes the contents and methods of traditional auction theory and also shows a general view of the research development,auction theory,winner determination problem,and mechanic designs for combinatorial auction.Second,this thesis introduces the basic theories and models of mechanism design, and discusses the assets and drawbacks of the various current combinatorial auction mechanisms.Because the current mechanisms have different shortcomings in the combinatorial auctions for complements,we propose the ascending proxy mechanism at last.This mechanism works simple,allows package bid,and effectively solved problems like information exposure problems etc,in the combinatorial auctions for complements.Third,based on the winner determination problem and combined with the features of the online auction,the static online combinatorial auction model is founded using first price sealed auction mechanism and the price-dynamic online combinatorial auction is founded using ascending proxy auction mechanism.Fourth,this thesis also proposes improved extremal optimization algorithm to solve the auction models:uses the embedded Fitting-First heuristic to configure the feasible solutions,and puts the worst packet bid to the end of the whole bids queue instead of directly eliminating it in the extremal optimization iteration procedure. Because the non-balanced feature of the extremal optimization is adapted to solving dynamic optimization problems,this thesis proposes a new extremal optimization algorithm to solve dynamic combinatorial auction problem,and also discusses in what circumstances the dynamic extremal optimization algorithm performs better than the static extremal optimization algorithm.The simulations on real instances indicate that both of the extremal optimization algorithms proposed in this thesis have high efficiency and wide future.