Study On Winner Determination Problem And Its Application

With the development of electronic commerce and the actual needs of auctioning multi-unit items, many of the traditional auction theory and assumptions are no longer suited for the new economic environment. People began to design and use some complex auction formats. Experiments show that, when goods have a strong synergy (complementary or alternative) in a multi-item auction, simultaneously ascending auction is superior to sequential auctions, and combinatorial auction is superior to the formers. Therefore, in the Nineties of twentieth century, multi-unit items combinatorial auction becomes to a research focus area of the auction. However, the application of combinatorial auction design has been greatly curtailed as the number and variety of goods sold increases, the auction quickly becomes much more complex, since many bids are for a combination of overlapping items, thus it is difficult to calculation who is the winner, this issue has become a hot issue in computer science. The problem of complexity of Winner decided is not just to make the decision into the plight of the auction side, but also makes people very difficult to forecast their own auction tender result, as well as difficult to judge on whether the auction of honest auction. Therefore, the winner decided to issue a serious impediment to the application of combinatorial auction theory and development. In the course of the study used a proof of concept experiments show that a comparative analysis and other methods.At present, winner determination problem on the issue of research scholars in the field is mostly computer algorithms to improve the issue, but from the economic and applied research in the field to win by decision of how to solve the problem is rare. This article focuses on approaches to winner determination problem and its application in related fields. Firstly, describing the disadvantages of sequential and parallel auction, for example, the inefficient allocation, winner curse. But, combinatorial auction can solve these problems. Secondly, from the positive, reverse and double combinatorial auctions to systematically demonstrate the complexity of winner determination problem. Its findings were: positive and double combinatorial auction's winner determi-nation problem is NP-hard and hard to approximate; reverse combinatorial auction's winner determination problem is NP-hard, Next, it discusses the approaches of combinatorial auction's winner determination problem, and treatment methods are divided into three main categories:tractable cases for winner determination problem, improved algorithm for winner determination problem and improved mechanisms for winner determination problem. According to the characteristics of three types of analysis of three approaches, its complexity is increasing basing the order.Lastly, this paper describes the main application areas of the combinatorial auction:spectrum auctions, electricity and energy auction, the aircraft parking auctions, bus line auctions, trucking auctions and procurement auctions. This article divided these six areas into three categories, namely: network-structure items positive auctions, no-network-structure reverse auctions and no-network-structure reverse auctions, compare these three type of approaches, and analyze how to use approaches well, Through auction theory, analysis, design and implementation of a series of computer simulation experiments, the experimental results, using descriptive statistics and inference statistical analysis in the three types of comparative analysis of the different combinatorial auction winner decided to deal with the problem of different accounting methods. For items being auctioned can be divided into those who decided to tackle the problems to win the auction side define optimal combinations and to submit bids at the same time optimizing the use and choice of two ways, one way of comparison, the computing time will not be significantly reduced. For the indivisible goods being auctioned winner decided to tackle the problems, the definition of optimized combination of auction and bidding parties to submit two ways to optimize the use of more alone should also be a way to significantly reduce computing time. For sub-items can not be reverse auction winner decided to tackle the problems, the definition of optimized combination of auction and bidding parties to submit optimized combination of both methods should also use more methods used alone can significantly reduce the computational time and reverse auctions limit your search to the an approach would significantly reduce the computation time.