We present a modeling approach for generating robust predictions about how changes in institutional, economic, and political considerations will influence the outcome of political negotiations over complex water-ecosystem policy debates. Evaluating the political viability of proposed policies is challenging for researchers in these complex natural and political environments; there is limited information with which to map policies to outcomes to utilities or to represent the political process adequately. Our analysis evaluates the viability of policy options using a probabilistic political viability criterion that explicitly recognizes the existence of modeling uncertainty. The approach is used to conduct a detailed case study of the future of California's Sacramento-San Joaquin Delta. Several other possible applications of the approach are briefly discussed.