关键词: 多属性逆向拍卖, 获胜者确定问题, Choquet积分, 偏好揭示

Abstract: Winner determination problem (WDP) is one of the most important research issues in multi-attribute reverse auctions. Presently, the additive value function is commonly used as the scoring rule to solve WDP, which ignores the interactions among the attributes in reality. To deal with the interacting effects, the Choquet integral defined on 2-order additive fuzzy measures is used in this paper to represent an auctioneer's preference, where the n+C_n² parameters are inferred by a set of indirect preference information in accordance with the preference aggregation-disaggregation paradigm. Generally, the scoring functions which could restore the auctioneer's preference are not unique. A two stage winner determination model is then proposed, which aimes at utilizing all the compatible scoring functions to determine the winner. In each round of an iterative auction, all the potential winning bids are first selected via a linear programming model. Then, a mixed integer linear programming model is developed to determine a ranking which is most close to the evaluations of all the compatible scoring functions. The bid with the highest score in this ranking will be the robust winning bid, which will be recommended to the auctioneer. The auctioneer's final decision will generate a feedback information to further refine the elicitation. Finally, a simulation experiment is conducted to evince the practical applicability of the method. The simulation results show that in general a large amount of bids are impossible to win, and the percentage increases with the number of bids in each round, which illustrates the necessity of choosing the potential winning bids in the first stage. The comparison with an existing approach verifies the validity and efficiency of the method. According to the simulation, the proposed method can identify all the outranked bids determined by the existing approach as losing bids. Moreover, unlike the existing method which will generate a set of "unknown bids", the proposed one can distinguish the potential winning bids from the offers. In computation efficiency, the running time of the proposed method is always less than the existing one in the same auction setting. Although both two methods will cost more time with larger rounds or more bids, the running time of the existing method increases more sharply, which proves the advantage of the proposed method in computation efficiency.

Key words: multi-attribute reverse auctions, winner determination problem, Choquet integral, preference elicitation