A Local Search Algorithm For The Winner Determination Problem

Auction is a process of buying and selling by bidding.A traditional auction is to transfer a specific item or property right to the bidder who offers the highest price.Different from the traditional one,the combinatorial auction allows the bidder to bid on a set of goods instead of disclaiming the price of each.The winner determination problem is one of the most important problems in combinatorial auction,which is significantly valuable in both theory and practice.However,the winner determination problem has been proved to be a NP hard problem in theory,there is no exact polynomial time algorithm for it at present.Despite that the exact algorithm can prove the optimality of the solution,with the expansion of the problem scale,the solving time grows exponentially,which makes a large instance be solved in acceptable time hardly.This kind of NP problem usually needs to rely on heuristic algorithm for approximate solution,in order to be used in practical application.As one of the important heuristic algorithms,local search has the characteristics of simplicity and high efficiency.Local search algorithm has excellent performance in solving a variety of NP problems.It is not able to give the optimal solution and prove its optimality as the exact algorithm does,but on a large scale instance,the local search algorithm can usually give a high quality approximate solution in shorter time.The winner determination problem is important in practice and attracts a lot of attention.In this paper,we design and implement a local search algorithm for the winner determination problem,which can be used to solve large scale instances in a short time and improve the solution quality as much as possible.The algorithm designed in this paper is named WDPLS.WDPLS is based on an efficient and concise local search framework,it is equipped with three techniques,i.e.,the configuration checking,free bid and pseudo tie techniques.Configuration checking is a very efficient strategy to block revisiting in the search process.The free bid may exist in searching,which is special compared to the other losing bids.WDPLS picks free bids preferentially to improve the solution quality quickly.In addition,there may be some losing bids with similar quality(score)in an iteration.For these bids,the pseudo tie technique prevents the algorithm from excessively greedy selecting the highest score bid,thus providing the possibility to other good quality bids to be selected,enhancing the diversity.A large number of experiments on the LG benchmark show that the WDPLS is superior to the state-of-the-art algorithms in solving quality and running time.In particular,although WDPLS has been implemented as a single thread program in this paper,it has obvious advantages in comparison with the multi thread algorithm CARA and the commercial solver CPLEX.The experiments also show that the three main technologies have positive effects on the performance of WDPLS,which proves the effectiveness of the technologies.