Solving the Auction-Based Task Allocation Problem in an Open Environment

Abstract

In this paper we analyze the process of allocating tasks to self-interested agents in uncertain changing open environments. The allocator in our model is responsible for the performance of dynamically arriving tasks using a second price reverse auction as the allocation protocol. Since the agents are self-interested (i.e. each agent attempts to maximize its own revenue), previous models concerning cooperative agents aiming for a joint goal are not applicable. Thus the main challenge is to identify a set of equilibrium strategies- a stable solution where no agent can benefit from changing its strategy given the other agents ’ strategies- for any specific environmental settings. We formulate the model and discuss the difficulty in extracting the agents ’ equilibrium strategies directly from the model’s equations. Consequently we propose an efficient algorithm to accurately approximate the agents ’ equilibrium strategies. A comparative illustration through simulation of the system performance in a closed and open environments is given, emphasizing the advantage of the allocator operating in the latter environment, reaching results close to those obtained by a central enforceable allocation.