Autonomy with structural task allocation games: from inefficiency to optimality

A common belief is that decentralized systems often suffer from inefficiencies due to self-interested decision making by autonomous agents, leading to suboptimal outcomes. These inefficiencies, typically measured by the Price of Anarchy (PoA), are expected to worsen as competition intensifies. However, this is not always the case. Contrary to this belief, our observations reveal that, in specific domains, as the number of agents increases, the system’s efficiency can converge toward more optimal outcomes, and the PoA approaches 1, a phenomenon that we refer to as the Power of Autonomy. To explore this, we introduce Structural Task Allocation Games (STAGs), a non-cooperative framework in which agents autonomously select paths in a directed graph, each representing a sequence of interdependent tasks, to maximize their utility. By deriving a tight upper bound on the PoA for this class of games, we show that social welfare in the worst-case Nash equilibrium is at most twice that of the social optimum. These results were further validated experimentally.