This article critically examines the dispute between realists and institutionalists on the conditions facilitating or hindering international cooperation and suggests a new solution. Realists base their scepticism about the possibility of cooperation in the international arena on the desire of the states to prevent a decrease of their relative power vis-à-vis other states, assuming that they are willing to forgo substantial absolute gains in order to avoid this outcome. In this article, the authors use two-person non-cooperative game theory to show that the "problem of relative gains" is ultimately an instance of the general problem of agreement instability. The problem can be solved if and when the conditions specified by institutionalist theory are present. A better understanding of "the logic of absolute gains" is also necessary because it helps to understand why cooperation can be difficult or absent even in those situations when, according to "the logic of relative gains", it is necessary, i.e. when two or more states face a common threat to their security.