Solving combinatorial auctions with temporal constraints in economic agents.

详细信息   

• 作者：Collins ; John Edgar.
• 学历：Doctor
• 年：2002
• 导师：Gini, Maria L.
• 毕业院校：University of Minnesota
• 专业：Computer Science.;Economics, Commerce-Business.
• ISBN：0493712054
• CBH：3056308
• Country：USA
• 语种：English
• FileSize：7799629
• Pages：182

文摘

We consider the problem of self-interested economic agents who must negotiate with each other to carry out their plans. Customer agents express plans in the form of task networks, which they offer in a marketplace in a request for quotations (RFQ). The market runs a combinatorial reverse auction, in which supplier agents submit bids that specify prices for combinations of tasks, along with time windows and duration data that the customer uses to compose a work schedule. The presence of temporal and precedence constraints among the items at auction requires extensions to the standard winner-determination procedures for combinatorial auctions, and the use of the enhanced winner-determination procedure in real-time negotiation requires that we predict its runtime when planning the negotiation process.;We describe the high-level design of an agent that can act as a customer in this environment, and describe the decision behaviors such an agent must implement to maximize its utility. One of the primary decisions such an agent must make is to determine the winners of its auctions. Methods for the determination of auction winners are explored in detail, and three different algorithms are presented. One is an Integer Programming (IP) model, the second is a queue-based Simulated Annealing (SA) design, and the third is an extension of the bidtree-based Iterative-Deepening A* (IDA*) formulation proposed by Sandholm.;The winner-determination algorithm must be run in the context of a real-time negotiation, and the time available to run it must be published to suppliers as part of a request for quotations. This is because suppliers need to know when they may expire their bids, and because shorter bid-expiration times are expected to lead to lower prices and higher willingness to bid on the part of suppliers. The result is that we must be able to predict the runtime of these NP -complete algorithms based on information that can be measured or estimated before bids are available. We report on a series of experiments that provide us with runtime probability distributions across a range of problem size parameters.