As the impact of climate change becomes increasingly urgent, conflicts over transboundary water resources have become more complex, particularly in light of the role of water in shaping socioeconomic and regional power dynamics. The challenge of optimizing objectives and strategic behavior across multiple stakeholders simultaneously makes it difficult to arrive at policies that can enhance long-term transboundary water management in a harmonious manner. In the Eastern Nile Basin (ENB), tensions have risen between upstream Ethiopia and downstream Egypt and Sudan due to the development of the Grand Ethiopian Renaissance Dam (GERD), making successful negotiations for water allocation critical. Ideally, such negotiations should produce agreements with high-stability policies, meaning that no actor has an appealing unilateral gain in utility that would cause them to defect from an agreement. Several water allocation simulations have been developed in the ENB using both linear and nonlinear programs to aid decision-making, but only two studies have previously examined measures of stability for these optimization results, and neither has been done since the completion of the GERD. Moreover, as simulation complexity has increased, there is a gap in knowledge regarding the measurement of stability using optimization results from closed-loop, multi-objective adaptive simulations. To address this gap, this research reexamines the stability of policy candidates for water allocations in the ENB using three different solution concepts from cooperative game theory—the Nash-Harsanyi solution, the Shapley value, and the nucleolus. The stability of each policy candidate is assessed using three different stability metrics—the Euclidean distance, the Loehman Power Index, and the propensity to disrupt—to determine their relative stability. The approach yields similar objective trade-offs and utility behaviors for the Nash-Harsanyi and Shapley Values. The most stable policies, when ranked by Euclidean distance, prioritize Ethiopia’s utility, while policies become more unstable with the rapid growth of Egypt’s utility. Furthermore, propensities to disrupt and power indices between Egypt and Ethiopia or Sudan show converging and diverging behaviors, respectively, which explain the negotiation potentials between the players. Our results indicate that Egypt’s willingness to engage in collaboration is directly related to its level of utility; however, at these levels, Ethiopia and Sudan’s benefits from utility are at levels that prompt higher likelihoods of defections from a potential coalition. The results also showed stable policies characterized with high policy efficiencies in instances of basin-wide cooperation, which increases benefits to all nations. Given the different assumptions and characteristics of each stability concept, the insights on the stability of different policies provide general guidelines for incorporating stability into the optimization formulation itself. The results have larger implications for policy planners in the ENB and the difficulties they may face when finding acceptable solutions in multi-stakeholder decision arenas. Furthermore, the methodological contribution of this study could allow for easy application of this method to other water allocation conflicts to help guide policy planners detect opportunities for utility optimization or risk mitigation in a cooperative setting.