Solving the Winner Determination Problem by a distributed genetic algorithm

In this paper we present a distributed system that is capable of solving the Winner Determination Problem (WDP) for combinatorial auctions by use of a genetic algorithm. Combinatorial auctions are simple, allowing agents to bid on combination of items rather than making several individual bids. These types of auctions lead to more economical efficient allocations of goods in situations where the agents´ have preference over bundles of goods. However, determining the winner(s) has been shown to be a NP-complete problem. This means that there is no simple way to solving the WDP. Our approach is to use a distributed system that solves the WDP using a genetic algorithm that is being distributed. In this way we are able to take advantage of the benefits that distributed systems offer. The results obtained from the system are compared to IBM´s algorithm, known as CPLEX.