# Anonymous Hedonic Game for Task Allocation in a Large-Scale Multiple Agent System

**Authors:** Inmo Jang, Hyo-Sang Shin, Antonios Tsourdos  
**arXiv:** [1711.06871](https://arxiv.org/abs/1711.06871)  
**Date:** 2017-11-18  
**Summary page:** https://www.summarizepaper.com/en/paper/1711.06871v2/

## Key points

- Authors propose a novel game-theoretical autonomous decision-making framework for task allocation in a large-scale multiple agent system
- Focus on cooperation among self-interested agents
- Decentralized algorithm ensures convergence of agents to Nash stable partition or social agreement within polynomial time
- Algorithm operates through simple local interactions with neighboring agents in a strongly-connected communication network, even in asynchronous environments
- Analytical formulation provided for computing lower bound of suboptimality of the solution
- At least 50% suboptimality guaranteed if social utilities exhibit non-decreasing functions regarding number of co-working agents
- Numerical experiments validate scalability, adaptability to dynamical environments, and robustness in realistic scenarios

## Summary

In their paper titled "Anonymous Hedonic Game for Task Allocation in a Large-Scale Multiple Agent System," authors Inmo Jang, Hyo-Sang Shin, and Antonios Tsourdos propose a novel game-theoretical autonomous decision-making framework to tackle the task allocation problem for a swarm of multiple agents. The focus is on cooperation among self-interested agents. The authors demonstrate that their decentralized algorithm ensures the convergence of agents with social inhibition to a Nash stable partition or social agreement within polynomial time. This algorithm operates through simple and executable local interactions with neighboring agents within a strongly-connected communication network, even in asynchronous environments. Furthermore, the authors provide an analytical formulation for computing the lower bound of suboptimality of the solution. They also establish that at least 50% of suboptimality can be guaranteed if social utilities exhibit non-decreasing functions concerning the number of co-working agents. Numerical experiments conducted by the authors validate that their proposed framework is scalable, swiftly adaptable to dynamical environments, and robust even in realistic scenarios. The research was accepted by IEEE Transactions on Robotics and published in 2018. The findings contribute significantly to understanding how autonomous decision-making frameworks can effectively address complex task allocation challenges within large-scale multiple agent systems.