Inducing Coordination in Multi-Agent Repeated Game through Hierarchical Gifting Policies

Coordination, i.e., multiple autonomous agents in a system to achieve a common goal, is critical for distributed systems since it can increase the overall reward among all agents. However, The dynamic environment and selfish agents pose challenges to learning coordination behavior from historical interaction data in a long-term interaction environment. Previous works mostly focus on one-shot or short-term distributed agent interaction environments, which often leads to selfish or lazy behavior in long-term interaction environments, i.e., prioritizing individual optimal strategies over cooperative strategies. This behavior is mainly due to the lack of historical memory or incomplete use of historical interaction data to guide the current interaction strategy. In this paper, we propose a hierarchical peer-rewarding mechanism, hierarchical gifting, that allows each agent to dynamically assign some of their rewards to other agents based on historical interaction data and guide the agents towards more coordinated behavior while ensuring that agents remain selfish and decentralized. Specifically, we first propose an auxiliary opponent modeling task so that agents can infer opponents' types through historical interaction trajectories. In addition, we design a hierarchical gifting strategy that dynamically changes during execution based on known opponents' types. We employ a theoretical framework that captures the benefit of hierarchical gifting in converging to the coordinated behavior by characterizing the equilibria's basins of attraction in a dynamical system. With hierarchical gifting, we demonstrate increased coordinated behavior of different risk, general-sum coordination games to the prosocial equilibrium both via numerical analysis and experiments.