Bringing the United States and major developing countries to control their greenhouse gas emissions will be the key challenge for the international climate regime beyond the Kyoto Protocol. But in the current quantity-based coordination, large uncertainties surrounding future emissions and future abatement opportunities make the costs of any commitment very difficult to assess ex ante, hence a strong risk that the negotiation will be stalled. The authors use a partial equilibrium model of the international allowance market to quantify the economic consequences of the main post-Kyoto quota allocation rules proposed in the literature and to assess how robust these consequences are to uncertainty on future population, economic, and emissions growth. They confirm that, regardless of the rule selected, the prices of allowances and the net costs of climate mitigation for all parties are very sensitive to uncertainty, and in some scenarios very large. This constitutes a strong barrier against adopting any of these schemes if no additional mechanism is introduced to limit the uncertainty on costs. On the other hand, parties' preferred (least-cost) rules are essentially robust to uncertainty. And although these preferences differ across countries, the authors' analysis suggest some bargaining is possible if developing countries make a commitment and join the allowance market earlier in exchange for tighter quotas in the North. This underscores the importance of the rules governing the entry of new parties into the coordination. But the magnitude of the win-win potential strongly depends on how different abatement costs are assumed to be between industrial and developing countries, and on how long that gap is assumed to persist.