Research On Winner Determination Problem With An Ant Colony Optimization Algorithm

Combinatorial auctions are those auctions in which bidders are allowed to bid oncombinations of items. Combinatorial auctions, as a topic of economics, have beenextensively studied in the past two decades. In a combinatorial auction, finding anallocation of items to maximize the revenue, which is called winner determinationproblem, is an NP-Hard combinatorial optimization problem. A lot of scholars havemade a significant contribution to solving the winner determination problem. Butmany of them impose some different restrictions on the winner determinationproblem to reduce the solving difficulty. Examples are restriction of bids, restrictionof combinations on which bidders can bid, and the complementary assumption.In this thesis we assume that there is no restriction on bids or combinations,complementarities or substitutions between different items are unknown, and biddershave resource constraints. Then a winner determination problem model ispresented. To solve this model, an ant colony optimization algorithm is proposed.Some numerical examples are given to test the effectiveness and feasibility of thisalgorithm. Furthermore, sometimes auctioneers have to achieve multiple objectives.Therefore, a bi-objective winner determination problem model which maximizes therevenue and the number of items to sell is presented, and a numerical example isgiven to test the effectiveness of this model.The main innovations of this paper are concluded as follows:1. Under the above assumption, a winner determination problem model ispresented.2. An ant colony optimization algorithm is proposed to solve this model.3. A bi-objective winner determination problem model which maximizes the reve--nue and the number of items to sell is presented.