Inefficiency of Self-Interested Behaviour in Markov Games: State-Dependent Price of Anarchy

Multi-agent systems are present in many real-world applications, making the development of autonomous agents that can solve complex tasks an active area of research. We focus on scenarios where a set of self-interested agents interact with each other and their environment in a manner that affects some social or system-level outcome. Given such scenarios, our goal is to measure and understand how self-interested behaviours affect the desired social outcome. We address this problem by introducing a state-dependent price of anarchy (PoA) metric within the context of a sequential decision-making problem formalized as a Markov game. We then outline a computational approach for estimating this metric and understanding observed trends from empirical experiments. We demonstrate our approach in a multi-agent wildfire fighting task and show the importance of considering state dependence in this problem.