In his seminal paper, Barrett (1994) argues that international environmental agreements (IEAs) are typically not successful, which he coined "the paradox of cooperation". If the potential gains from full cooperation would be large, self-enforcing IEAs have low participation and, therefore, cannot achieve much, or, if the potential gains are small, agreements are not important, even though IEAs may enjoy large participation. This message has been reiterated by several subsequent papers. Even though these papers explain the driving forces of the paradox, the analysis of membership in stable agreements and the actual and potential gains from cooperation are still mainly based on simulations. In this paper, we provide a full analytical characterization of all items on which the paradox of cooperation is based.