Choosing What Game to Play without Selecting Equilibria: Inferring Safe (Pareto) Improvements in Binary Constraint Structures

We consider a setting in which a principal gets to choose which game from some given set is played by a group of agents. The principal would like to choose a game that favors one of the players, the social preferences of the players, or the principal's own preferences. Unfortunately, given the potential multiplicity of equilibria, it is conceptually unclear how to tell which of even any two games is better. Oesterheld et al. (2022) propose that we use assumptions about outcome correspondence -- i.e., about how the outcomes of different games relate -- to allow comparisons in some cases. For example, it seems reasonable to assume that isomorphic games are played isomorphically. From such assumptions we can sometimes deduce that the outcome of one game G' is guaranteed to be better than the outcome of another game G, even if we do not have beliefs about how each of G and G' will be played individually. Following Oesterheld et al., we then call G' a safe improvement on G. In this paper, we study how to derive safe improvement relations. We first show that if we are given a set of games and arbitrary assumptions about outcome correspondence between these games, deriving safe improvement relations is co-NP-complete. We then study the (in)completeness of a natural set of inference rules for outcome correspondence. We show that in general the inference rules are incomplete. However, we also show that under natural, generally applicable assumptions about outcome correspondence the rules are complete.