Research On Modeling And Optimization Methods Of Reverse Combinatorial Auctions For E-procurement

Auction is an efficient mechanism for allocating items or tasks. With the rapid development of electronic commerce (e-commerce), online auctions, as an important component of e-commerce, quickly become one of the most successful applications of electronic commerce. Due to the flexibility of the e-commerce environment, online auction theory, auction mechanism design, and other related issues have drawn extensive attention. Economists and management workers have been taking increasing interests in developing advanced forms of online auction.Auction mechanism and bidding strategy are the core issues in the auction theory. For the auctioneer it is necessary to decide that what kind of bidders should be allowed to participate in bidding, how to design auction rules will bring more benefit for themselves, and what kind of bid would be accepted, etc.. While for the bidders, it is necessary to determine the bidding strategies that how to bid, when to bid, and how much to bid, so as to bring more benefit for themselves.The traditional auction theory and mechanism will face great challenges in the environment of e-commerce. For example, trading forms of the combinatorial auction, multiple attribute auction and double-side auction, which exhibit some new properties in online auction, are widely concerned in the e-commerce.In an attempt to saved procurement costs, the reverse combinatorial auctions are usually applied to the centralized E-procurements of governments and large enterprise groups. This dissertation focuses on the mechanism design and winner determination problems of several different forms of reverse combinatorial auction.(1) This dissertation surveys the relevant research dynamic on auction theory, online reverse combinatorial auction, and winners determination problem of combinatorial auction. Firstly, we summarize the traditional auction theory, including the basic features, the basic model and the main research contents. After that, the current research achievement of the online auction designing is introduced, the characteristics between reverse combinatorial auction and the positive auction are analyzed. Finally, we emphatically summarize the main progress and achievements of three important contents of the combinatorial auction, i.e. bidding languages, winner determination problem (WDP), and variou auction mechanisms designing.(2) A practical auction process is designed for the reverse combinatorial auction in E-procurement. By setting reasonable bidding scale and the quota restraint of supplier in the design process of auction mechanism, the generation of feasible solution and competitiveness of the auction is guaranteed. It is proved that the average number of feasible solutions reduces with the increase of the number of items, and increase with the increase of the number of participants. It is also proved that quota restraint has great influence on the average feasible solution numbers.(3) For solving the winner determination problem of reverse combinatorial auction, a model is formulated and PRIM (preprocessing rules-based improved MMAS) algorithm and RCAGA (genetic algorithm for reverse combinatorial auction) algorithm is proposed Simulation results with different bidding scales show that the PRIM algorithm achieves good performance through applying the three preprocessing rules. The first preprocessing rule can eliminate dominant noncompetitive bidding. The second preprocessing rule which can eliminate recessive noncompetitive bidding to preprocess the search space. The third preprocessing rule effectively avoids unnecessary trials as early as possible. The preprocessing rules greatly improve the searching speed. Besides, the computational results show that RCAGA has a good search characteristic and the convergence property even for the large-scale problem, and the optimality of the solution is high.(4) Reverse combinatorial auction with XOR-bids allows bidders expressing their preference with different mix of resources more exactly. In this dissertation, a common model is formulated for the winner determination problem of the reverse combinatorial auction with XOR-bids. Three improved preprocessing rules are proposed and an improved PRIM algorithm is developed for solving this problem. Simulation results show that the search space is reduced by avoiding unnecessary trials using the proposed preprocessing rules as early as possible. Compared with other algorithms, the developed PRIM is feasible and efficient in solving the winner determination problem of reverse combinatorial auction with XOR-bids and performs better performance.(5) We design a reduction preference-based single-round discriminatory auction mechanism concerned with the problem of low efficiency of distribution in multiple-unit and multiple-item reverse combinatorial auction in which buyer purchases variety, large number of items. Reduction rules, the appropriate method of the setting of the reduction price and two kinds of effective reduction calculation method are proposed. The analysis results show that the special behavior of the supplier, those who utilizes this mechanism in their attempts to obtain more benefit, will not bring economic loss to the buyer. In addition, an genetic algorithm for winner determination problems is designed under this auction mechanism. Simulation results show the effectiveness of the mechanism and the algorithm.(6) In combinatorial auction, some of high quality bid can not win the auction for that these bid can not create feasible solution with the bid of other bidders, or the feasible solutions with this bid contain some low quality bid. In order to solve this problem, a multi-round bidding mechanism is designed to allowed incompletely bidding. Based on this mechanism, a common model is formulated and a PRIM algorithm with phantom bid is developed for solving the winner determination problem of reverse combinatorial auction in every round. The calculation results show that, allowing incompletely auction mechanism increase the the winning probability of the bid with high quality and much more procurement cost can be saved evidently. In addition, the bidding price of the phantom bidder in the bid-evaluation process is the reservation price, which can guarantee the purchasing costs are not higher than the reservation price of items.