Source-linked AI summary
Dynamic Auction Mechanisms in a Closed-Credit Economy: Sequential Slot Reallocation in Air Traffic Management
Jihun Kim, Pan-Yang Su, Maria G. Mendoza, Victoria Marie Tuck, Chinmay Maheshwari, S. Shankar Sastry
TL;DR
When capacity reductions make preallocated resource rights infeasible, exchange is complicated by existing endowments, uncertain capacities, and restricted monetary transfers. The paper proposes a subgroup-based ascending auction using reusable credits. It preserves individual rationality and weak nontrader neutrality, with conditional efficiency and an incentive guarantee under stated conditions.
Problem
Sequential reallocation is difficult because agents hold existing resource endowments, capacities are uncertain, and monetary transfers may be restricted.
Source: §I · p. 1Method
The mechanism partitions agents into subgroups for ascending price discovery and uses the minimum subgroup price as a common transaction price.
Source: §I · p. 1Results
The mechanism preserves individual rationality and weak nontrader neutrality, provides conditional Pareto efficiency when G = 1, and bounds manipulation gains by the probability of changing the common price.
Source: §I · p. 1Takeaways & Limitations
The impossibility result means a closed-credit economy cannot generally achieve efficiency, incentive compatibility, individual rationality, and weak nontrader neutrality together.
Source: B. An Impossibility Result · pp. 5–6
Abstract
from arXiv · showhide
Indivisible resources allocated in advance may need to be reallocated when capacity reductions make existing assignments infeasible, yet monetary compensation is often impractical or undesirable. We develop a sequential resource reallocation scheme using reusable artificial credits, where agents hold pre-existing resource rights and have heterogeneous marginal valuations over time blocks. Capacity reductions produce fractional endowments, which our closed-credit scheme resolves into indivisible final allocations. We model agents' intertemporal preferences through a predicted-value-to-go function and characterize conditions ensuring that their optimal demand is non-increasing in price. We propose an ascending-auction mechanism that partitions agents into subgroups and uses the minimum subgroup market-clearing price as a common transaction price. We show that the mechanism preserves non-myopic individual rationality and weak nontrader neutrality. Moreover, we establish Pareto efficiency under optimal-demand clearing in the unified market and bound the expected gain from misreporting by the probability that an agent changes the common price. Simulations of airport slot reallocation demonstrate reductions in total modeled delay and cancellation costs relative to a ground-delay baseline.
I. INTRODUCTION
The paper studies sequential exchange of preallocated resource rights when capacity is uncertain and monetary transfers are restricted. It establishes a limit on jointly attainable market properties, then proposes a credit-based auction and applies it to airport slot reallocation.
I. INTRODUCTION
- The setting involves long-lived agents with existing resource endowments, uncertain capacities, and restricted monetary transfers, so reallocation requires exchange of previously assigned rights.The paper identifies transportation capacity and advance reservations as examples.Source: §I · p. 1
- Theorem 1 shows that Pareto efficiency, incentive compatibility, individual rationality, and weak nontrader neutrality cannot generally be achieved simultaneously.The result embeds bilateral trade as a special case and applies the Myerson–Satterthwaite impossibility theorem [3].Source: §I · p. 1
- The proposed ascending auction preserves individual rationality and weak nontrader neutrality, with conditional Pareto efficiency in the unified market and manipulation gains bounded by the chance of changing the common price.It splits agents into subgroups for price discovery and sets a common transaction price at the minimum subgroup price.Source: §I · p. 1
II. RELATED WORK
- Unlike related artificial-currency and airspace approaches, this work uses credits to exchange preallocated capacity rights without real-money transfers.Prior airspace approaches either rely on real money or lack an alternative currency for exchange.Source: §II · p. 2
III. MODEL
- After capacity reductions, endowments are scaled proportionally and treated as accounting entitlements, while final allocations remain indivisible.Agents receiving fewer items than their scaled entitlements receive credits, while those receiving more pay credits; balances carry forward across blocks.Source: §III · p. 2, A. Preliminaries · p. 3
A. Preliminaries
- Agents trade relative to scaled endowments using reusable credits, with unallocated demand and unused credits carried into subsequent blocks.The application models airlines as agents and flight slots as items.Source: Figure 1 · p. 3, A. Preliminaries · p. 3
B. Predicted Non-myopic Value
The paper models an agent’s value across blocks by combining current item values with the predicted future value of its remaining credits. Under stated conditions, an optimal demand can be characterized by a marginal-value test.
B. Predicted Non-myopic Value
- The predicted-value-to-go function represents expected future utility from the next block as a function of credit balance, while credits derive value from future allocation opportunities.The function is an approximation with other state variables held fixed and need not equal the true value-to-go.Source: B. Predicted Non-myopic Value · p. 3
- The value maximization accounts for how current purchases reduce next-block credits and releases increase them.An agent choosing K items with endowment e and balance w enters the next block with balance w − (K − e)p.Source: B. Predicted Non-myopic Value · p. 3
- With nonincreasing marginal valuations and a concave predicted-value-to-go function, the largest feasible quantity satisfying the marginal test is an optimal demand.The test balances the current item’s marginal value against the opportunity cost of the credits spent, subject to budget feasibility.Source: B. Predicted Non-myopic Value · pp. 3–4
C. Price Monotonicity of Optimal Demand
The paper characterizes conditions under which agents’ marginal gains and optimal demands decline with price, supporting ascending price discovery. It also frames mechanism design as mapping model primitives to feasible allocation-price pairs.
C. Price Monotonicity of Optimal Demand
- Concavity of the predicted-value-to-go function and a nondecreasing wealth-weighted right derivative are necessary and sufficient for marginal gains to be nondecreasing in wealth on every feasible price interval.Under these conditions, marginal gain is nonincreasing in price.Source: C. Price Monotonicity of Optimal Demand · p. 4
- When marginal valuation is nonincreasing in quantity and the continuation function belongs to the characterized class, the largest optimal demand is nonincreasing in price.This price monotonicity is a foundation for the mechanism design.Source: C. Price Monotonicity of Optimal Demand · p. 4
IV. PROBLEM FORMULATION
- A mechanism maps the model’s primitives to a feasible allocation-price pair.Source: §IV · p. 4
A. Normative Properties
The normative properties compare participation against an administrative allocation and protect nontraders’ relative credit balances. In the stated condition, weak nontrader neutrality is equivalent to weak budget balance.
A. Normative Properties
- Non-myopic individual rationality requires every agent’s utility, including predicted value-to-go, to be at least its administrative baseline.The baseline rounds fractional scaled entitlements down; the fractional residual is settled at the clearing price.Source: A. Normative Properties · p. 4
- In a closed-credit economy, deficit-financing credit creation can dilute nontraders’ relative purchasing power, which may affect future block outcomes.Source: A. Normative Properties · p. 5
- Weak nontrader neutrality preserves a nontrader’s relative credit balance, so its share of total credits does not decrease after settlement.Source: A. Normative Properties · p. 5
- With at least one nontrader holding positive credits, weak nontrader neutrality holds if and only if weak budget balance holds.Source: A. Normative Properties · p. 5
B. An Impossibility Result
The paper shows that efficiency, incentive compatibility, individual rationality, and weak nontrader neutrality cannot generally be achieved together. It responds by proposing a subgroup-based ascending auction that prioritizes individual rationality and weak nontrader neutrality.
B. An Impossibility Result
- With a buyer, seller, and positive-balance nontrader, overlapping independent valuation supports rule out any mechanism satisfying NIR, WNN, NPE, and NIC simultaneously.The result is a closed-credit analogue of the Myerson–Satterthwaite impossibility.Source: B. An Impossibility Result · pp. 5–6
V. MECHANISM DESIGN
- The proposed subgroup-based ascending auction prioritizes non-myopic individual rationality and weak nontrader neutrality, then analyzes its efficiency and incentive guarantees.Source: §V · p. 6
A. Proposed Mechanism
- The mechanism has three stages: splitting groups, running subgroup ascending auctions, and aggregating allocations.Source: A. Proposed Mechanism · p. 6
1) Group Splitting Procedure:
- Agents are sorted by scaled endowment, assigned sequentially to the subgroup with the lowest aggregate endowment, and subgroup capacities are rounded using largest remainders.Source: 1) Group Splitting Procedure · p. 6
2) Subgroup-Based Ascending Auction:
- Subgroup price discovery raises price under excess demand, returns a price at exact capacity, and steps back one increment when demand falls below capacity.Source: 2) Subgroup-Based Ascending Auction · p. 6
3) Aggregate Allocation:
The aggregate allocation uses the minimum subgroup discovery price as a common transaction price, then allocates demanded quantities or rations oversubscribed capacity. Unmet demand may be carried into the next block.
3) Aggregate Allocation:
- The common transaction price is the minimum subgroup discovery price, and demands at that price have already been encountered in the ascending procedures.Source: 3) Aggregate Allocation · p. 6
- At the common price, a subgroup within capacity receives its demanded allocation; an oversubscribed subgroup first gives agents up to their integer scaled endowments, subject to demand, then rations remaining capacity randomly among excess demands.Source: 3) Aggregate Allocation · pp. 6–7
4) Block Transitions:
- An agent’s unmet demand may be withdrawn or carried forward, and carried demand is combined with its initial endowment to set its next-block maximum resource requirement.Source: 4) Block Transitions · p. 7
B. Theoretical Analysis
The analysis establishes feasibility and market clearance, then characterizes the mechanism’s individual-rationality, nontrader-protection, efficiency, and approximate incentive guarantees. Those guarantees are conditional: Pareto efficiency is shown only in a unified market under optimal-demand clearing, and incentive improvement with more subgroups depends on how often reports change the common price.
1) Feasibility and Market Clearance:
- When the equilibrium block price is positive, Algorithm 1 produces a feasible allocation-price pair and leaves no capacity unallocated.These are the feasibility and market-clearance properties established for the mechanism.Source: 1) Feasibility and Market Clearance · p. 7
2) Individual Rationality, Nontrader Protection, and Efficiency:
- The mechanism satisfies non-myopic individual rationality and weak nontrader neutrality for every subgroup count; Pareto efficiency is guaranteed under optimal-demand clearing only when G = 1 and the stated conditions hold.The efficiency result requires truthful reports and that every agent receive its reported demand at the market-clearing price.Source: 2) Individual Rationality, Nontrader… · p. 7
3) Approximate Incentive Compatibility:
- The expected gain from misreporting is bounded in terms of the probability that a report changes the common price; for a fixed market, M_b is independent of G.When q_b^G ≤ c/G, the mechanism is (M_b c/G)-NIC.Source: 3) Approximate Incentive Compatibility · p. 7
- If price-grid jumps require rationing, individual optimality and Pareto efficiency need not be preserved; efficiency-preserving rationing is left for future work.The stated efficiency condition is met when reported demands are fully allocated at a price-grid point.Source: 3) Approximate Incentive Compatibility · p. 7
- More subgroups can improve the incentive guarantee when q_b^G ≤ c/G, but smaller groups may be more sensitive to individual reports, so the improvement is not assured.The common price is the minimum subgroup price, and balancing endowments alone does not ensure that q_b^G decreases with G.Source: 3) Approximate Incentive Compatibility · p. 7
VI. EXPERIMENTS
SFO simulations compare sequential slot reallocation with ground delay across two capacity-reduction scenarios and four credit initializations. The results show lower modeled costs in the reported comparisons, alongside checks of market properties and allocation feasibility.
VI. EXPERIMENTS
- The SFO simulation uses the published schedule of 591 arrivals across 52 airlines and tests mild and severe capacity reductions against nominal capacity of 52 arrivals per hour.The modeled flight cost includes arrival delay and delay propagated to the next departure; cancellations occur beyond three hours of delay and are valued as passenger refunds.Source: §VI · pp. 7–8
- Airline slot values are modeled as avoided delay costs, and initial credit budgets are tested using equal, exposure, seats, and flights weights.Exposure weights reflect the cost of delaying an airline’s flights by one block; the other weights use equal shares, seats, or flight counts.Source: §VI · p. 8
- In S1, exposure initialization yields total cost 64% below GD; in S2, the mechanism lowers total cost by 7–18% under every initialization but cancels at least as many flights as GD.Source: §VI · p. 8
- In S2, exposure, seats, and flights produce 31–34 cancellations versus GD’s 30, while equal produces the lowest total cost with 51 cancellations.Exposure and seats cancel fewer passengers than GD (3.3k and 2.7k versus 4.0k); equal reduces propagated delays and delays beyond 15 minutes by about 18%. Whether the cancellation trade-off is desirable depends on airline cancellation costs, which the simulation models only as passenger refunds.Source: §VI · p. 8
- Dark nontrading periods do not reduce airlines’ relative budget shares, while the reported allocations respect pending-flight, capacity, and budget constraints.The reported minimum gain net of the rebate for partial units is zero, validating NIR; allocation fractions remain at or below one and stay within capacity.Source: §VI · pp. 8–9, Figure 2 · p. 8, Figure 3 · p. 9
VII. CONCLUSION
- The conclusion reports an impossibility of jointly achieving NIR, WNN, NPE, and NIC, and presents a group-splitting ascending auction with conditional efficiency and approximate incentive guarantees.Future work is identified in subgroup selection, budget allocation, and sharper efficiency and incentive guarantees.Source: §VII · p. 9
APPENDIX
The appendix develops the optimal-demand argument and proves conditions for price monotonicity. Its proof tracks the required properties of the value function and extends monotonicity across feasible price boundaries.
A. Proof of Proposition 1
- The Proposition 1 argument uses a nonincreasing marginal surplus in slot quantity to characterize optimal demand.The passage ties this result to concavity of the predicted-value-to-go function and a nondecreasing credit opportunity cost.Source: A. Proof of Proposition 1 · p. 10
B. Proof of Proposition 2
- The Proposition 2 proof establishes that J is nondecreasing, continuous, and concave, and uses nondecreasing zJ′(z) in its sufficiency argument.The proof separately establishes continuity on positive values and concavity on the nonnegative domain.Source: B. Proof of Proposition 2 · p. 10
- The sufficiency proof checks boundary cases to extend monotonicity across the entire feasible price interval.It distinguishes cases by initial balance w and parameter a, including whether the feasible interval has a finite upper endpoint.Source: B. Proof of Proposition 2 · p. 11
C. Proof of Proposition 3
The appendix proves that selected optimal demand is nonincreasing in price, then establishes feasibility properties of the subgroup-priced auction. The theorem’s proof checks price, domain, budget, and capacity constraints.
C. Proof of Proposition 3
- For Proposition 3, demand selected at a higher price remains budget-feasible at a lower price when the agent is a net seller, supporting nonincreasing demand.The proof uses the largest optimal demand and the budget-feasibility condition at the lower price.Source: C. Proof of Proposition 3 · p. 11
D. Proof of Theorem 2
- Theorem 2’s proof verifies nonnegative clearing prices and the allocation’s domain, budget, and capacity constraints.The algorithm and subgroup capacity bounds supply the stated feasibility checks.Source: D. Proof of Theorem 2 · p. 11
- Theorem 2’s subgroup rule allocates each subgroup’s cleared demand up to its capacity, using random ordering when demand exceeds capacity.When demand does not exceed capacity, the subgroup’s demand is allocated in full.Source: D. Proof of Theorem 2 · p. 11
E. Proof of Theorem 3
The proof establishes non-myopic individual rationality and weak nontrader neutrality, and proves Pareto efficiency for the unified-market case. Its efficiency argument rules out a feasible Pareto-dominating alternative.
E. Proof of Theorem 3
- The proof establishes NIR by showing the relevant participation gain net of payment is nonnegative.The proof treats cases based on demand and the agent’s endowment.Source: E. Proof of Theorem 3 · p. 11
- The proof establishes WNN through its equivalence with WBB in the stated setting.It invokes the earlier lemma relating weak nontrader neutrality and weak budget balance.Source: E. Proof of Theorem 3 · p. 11
- For G = 1, the proof establishes NPE by ruling out a feasible Pareto-dominating allocation-price alternative.The argument uses feasibility and market clearing; any strict improvement for an agent would make the auctioneer strictly worse off.Source: E. Proof of Theorem 3 · p. 12
F. Proof of Theorem 4
The proof separates deviations that leave the common price unchanged from those that change it. Truthful reporting is no worse in the first case, while the gain in the second is bounded.
F. Proof of Theorem 4
- The subgroup partition and capacities are independent of agents’ reports, and the proof compares reports using the same opponents’ types and random ordering.It defines the event that a deviation changes the common price.Source: F. Proof of Theorem 4 · p. 12
- When a deviation leaves the common price unchanged, truthful reporting weakly maximizes utility over feasible quantities up to the report-independent allocation cap.The proof uses Proposition 1’s nonincreasing marginal gains and writes the allocation as min{d, Ki}.Source: F. Proof of Theorem 4 · p. 12
- When a deviation changes the common price, its utility gain is bounded by M_i; the proof then takes the supremum over agents, types, and admissible deviations.Source: F. Proof of Theorem 4 · p. 12