Anonymous Hedonic Game for Task Allocation in a Large-Scale Multiple Agent System
This addresses task allocation for self-interested agents in dynamic environments, but it is incremental as it builds on existing game-theoretic methods.
The paper tackles task allocation for large-scale multi-agent systems by proposing a decentralized game-theoretic framework that guarantees convergence to a Nash stable partition in polynomial time, with numerical experiments showing scalability, adaptability, and robustness.
This paper proposes a novel game-theoretical autonomous decision-making framework to address a task allocation problem for a swarm of multiple agents. We consider cooperation of self-interested agents, and show that our proposed decentralized algorithm guarantees convergence of agents with social inhibition to a Nash stable partition (i.e., social agreement) within polynomial time. The algorithm is simple and executable based on local interactions with neighbor agents under a strongly-connected communication network and even in asynchronous environments. We analytically present a mathematical formulation for computing the lower bound of suboptimality of the solution, and additionally show that 50% of suboptimality can be at least guaranteed if social utilities are non-decreasing functions with respect to the number of co-working agents. The results of numerical experiments confirm that the proposed framework is scalable, fast adaptable against dynamical environments, and robust even in a realistic situation.