Algorithmic mechanism design for egalitarian and congestion-aware airport slot allocation

We propose a game-theoretic model and a mechanism design solution to allocate slots fairly at congested airports. This mechanism: (a) ensures that the slots are allocated according to the true valuations of airlines, (b) provides fair opportunities for flights connecting remote cities to large airports, and (c) controls the number of flights in each slot to minimize congestion. Drawing inspiration from economic theory, this mechanism allocates the slots based on an affine maximizer allocation rule and charges payments to the airlines to incentivize them to participate in the allocation process and reveal their actual valuations. The allocation also optimizes the occupancy of each slot to keep them as uncongested as possible. The formulation solves an optimal integral solution in strongly polynomial time. We conduct experiments on the data collected from two primary airports in India. We also compare our results with existing allocations and an allocation based on the International Air Transport Association (IATA) guidelines. The computational results show that our mechanism is more egalitarian and generates 20%−30% higher social utility than the IATA based state-of-the-art approach and current allocations.