When the scheduled demand at an airport exceeds the forecast capacity, the available capacity needs to be allocated among airlines in an efficient and equitable manner. The first stage of this two-step allocation process is a centralized optimization to determine the initial allocation among airlines. In the second stage, airlines cancel flights or modify their schedules based on flight-specific delay costs, which they hold private. The overall objective is to increase efficiency (that is, reduce total delay costs) to the extent possible. This paper demonstrates an inherent trade-off between the ability of the first-stage optimization to dynamically adapt to updates of the capacity forecast, and the flexibility available to airlines in the second stage. A new stochastic optimization model that balances this tradeoff is proposed. In addition to increasing the flexibility available to the airlines and the resultant delay reduction, the proposed formulation is shown to have attractive computational properties.