A decentralized algorithm for the preferred assignment problem in multi-agent systems

In this paper, we consider a task-allocation problem where N agents are to be assigned N distinct tasks without a central coordinator. The agents communicate over a connected network and we assume that each agent has a preference for a distinct unique task, i.e., without loss of generality, agent i prefers task i and is unhappy with any other task (≠ i). With the assumption that each agent starts by picking an arbitrary random task, we can divide the preferred task-allocation problem into two phases: (i) to reach the set of N! unique assignments from the set of NN total configurations-presented elsewhere; and (ii) to reach the single preferred assignment from the set of N! unique configurations. In this paper, we consider the phase (ii) of this preferred assignment problem, i.e., we assume that the network is already in one of the N! unique configurations. In particular, we assume that each agent has a unique task that may not be preferred and each agent does not know its preference until it sees the task and evaluates its cost. Under mild conditions on the network connectivity, we propose a swap-stick algorithm and show that this algorithm reaches the preferred assignment in finite-time (a.s.) using Markov-chain arguments. The analysis in this paper is further extendable to show the convergence of the phase (i) assignment problem.