Considerate Behaviour in Multi-Agent Non-Cooperative Settings

Abstract

In many multi-agent systems, it is impractical to assume that agents always make decisions without considering social relationships among them. Indeed, in many situations an agent might reject a protable action if a neighbouring agent ends up worse o. In this paper, the social context is captured by the notion of consideration - an approach proposed by Hoefer et al. Considerate Equilibrium (CE) allows for stable outcomes in non-cooperative games, in particular, where a pure strategy Nash equilibrium does not exist. In particular, we demonstrate that few social connections are sucient to provide stability in classic examples of player-specic congestion games without pure strategy equilibria. We then apply the notion of consideration to stabilise desirable outcomes. Specically, we seek a minimal (in terms of the number of connections) social context that guarantees stability of any Pareto ecient prole. In this work, two greedy algorithms are established, a general algorithm to stabilise any strategic game and a specialised algorithm to stabilise the roommate problem - a game studying one-sided matchings. In addition, we build on previous research to dene necessary and sucient conditions for Pareto eciency in the roommate problem of k-roommates.