Stable two-sided matching of slot allocation in airport collaborative decision making by top trading cycles mechanism

M′rcio Augusto DA SILVA SOUZA,Weigng LI,*,Reinldo Crispinino GARCIA

aTransLab,Department of Computer Science,University of Brasilia,70910-900 Brasilia,DF,Brazil

bDepartment of Production Engineering,University of Brasilia,70910-900 Brasilia,DF,Brazil

1.Introduction

The airport congestion problem is one of the main challenges facing the air transport system.According to the EUROCONTROL(European Organization for the Safety of Air Navigation)forecasts,even after taking into account currently planned infrastructure enhancements in Europe,10%of the demand for air transport will not be accommodated in 2030,due to a shortage of airport capacity.Building more runways and new airport infrastructure is the obvious solution,however,the impact on environment and on land planning is a growing concern besides the current economic crisis,for which the government needs to put the budget balance into a longterm sustainable path.Therefore,more cost-effective solutions have to be found to tackle congestion than relying on expanding hard infrastructure.Any option ensuring a more efficient use of existing capacities allowing a more sustainable aviation system has to be contemplated.

In Air Traffic Management(ATM),slot allocation is one of these options even though it can neither generate additional capacity nor providing the same benefits as additional runway or terminal capacity.What’s more,slot allocation cannot solve the many difficult issues created by a lack of capacity such as providing congested hubs with enhanced connections to all world regions.Nevertheless,slot allocation can be an effective tool for managing scarce capacity.An efficient assignment of slots is then definitely a cost-effective solution to be implemented at the airports.The Game theory and related algorithms can be applied to achieve this efficient assignment of slots.

In recent decades,Game theory has been used as a mathematical approach for modeling and analyzing strategies among multiple players.One of the reasons for its success is the diversity of actual and theoretical scenarios where it can be applied.1–5Furthermore,Game theory has been used to study the relationships between supply and demand of resources in societies.6,7

An application of Game theory includes the Matching approach,which aims to define,analyze and propose solutions to resource allocation problems in specific markets.Matching can be defined as a match among the players not violating the rules of the market.The Matching approach can then be applied to the problem of slot allocation in order to achieve an efficient allocation among the flights and the slots.

Previous studies have obtained an efficient slot allocation based on the preferences either of the airlines.7–9Therefore,this research aims to apply the Top Trading Cycle(TTC)algorithm of Matching theory to the slot allocation problem taking into account the preferences of the two already mentioned entities,the airlines and the airport managers in the Collaborative Decision Making(CDM)process.Once comparing the proposed Top Trading Cycle CDM(TTC-CDM)model to the existing models such as the conventional Compression algorithm in the CDM and,the Trade Cycle.7–9Another research developed a Deferred Acceptance CDM(DA-CDM)model algorithms10in the same process.But this paper applies the implemented model in the air traffic data from the Tancredo International Airport(SBCF)in the city of Belo Horizonte(Brazil).The results show the capabilities of the TTCCDM and DA-CDM to the slot allocation issue including the preferences of the different agents involved such as the airlines and the airport managers.

This paper is structured in the following manner.Section 2 gives the background of this research including a brief introduction of the game and the matching theories.Section 3 provides the theory of the matching for two-sided market applied to the market of slot allocation.Section 4 describes the TTCCDM model developed in this research and the Trade Cycle Schummer algorithm.A theoretical and a practical case study by TTC-CDM are presented in Section 5.The paper ends in Section 6,presenting relevant conclusions and future work.

2.Background

The Matching approach for a two-sided marketis a theory for the market with two distinct user groups providing network benefits.In the management of airports,using the airport runway can be considered asusing a limited resource,where at one time,only one aircraft can use this interval.The use of this intervalis made through the concept of slot,a right granted by the airport owner allowing the slot holder,airlines,to schedule a landing or departure during a specific time period.Therefore,the process of allocating the aircraft to the slots for landing or take off operations can be modeled as a‘market”.1,7–9,11,12

The increase in air traffic may result in congestion either at the airports or at the air sector.The management of the available air resources has been made by the CDM policy.1The CDM includes concepts of property,prioritization,justice and efficiency in resource allocation and aims to improve the exchange of information among the various airport agents such as Air Traffic Control(ATC),airlines and airport managers.Currently,the ATC classical model for slots allocation is based on the CDM,where airlines must provide reliable information in a timely manner to the ATC to achieve a better outcome.

The CDM process initially includes three steps:Ration-By-Schedule(RBS),substitutions/cancellations and compression.In the last step,the compression includes the re-allocation of the free slots after the step of substitutions/cancellations.The Compression algorithm integrates the airlines to fill the vacant slots according to pre-agreed rules of the involved agents.2,13–15

The CDM model seeks to include various interested parties so that the exchange of information results better decisions in the air traffic management.1Nevertheless,the CDM does not consider all stakeholders in the decision-making process related,but only the interests of the ATC agents and the airlines.16In order to solve the slot allocation issue,one can take insights of other applications where this allocation problem is also presented.

Notable market design applications have included the allocation of heterogeneous indivisible objects without monetary transfers,such as assigning pupils to public schools in a school choice program,or re-matching kidney patients with donors when patients have donors with incompatible kidneys.A common feature of such problems is the ranking of individuals needs in apriority order.The TTC approach and its variants emerge as a desirable solution to incorporate such priorities in the allocation process.17,18

The TTC algorithm in a two-sided matching environment has been an important method for achieving efficient outcomes as in school choice problems.18The TTC mechanism takes another perspective on how priorities must be treated.When applying the TTC to the school choice problem,each student points to his/her most favorite school and each school points to her top ranked student.When the cycles form,the students are matched with their favorite schools which then will be removed from the problem,and the algorithm continues with the remaining students and schools.This TTC mechanism allows students to trade their priorities through a very well structured process.

When schools are considered like objects having a unit capacity,it was shown that an assignment mechanism was strategy-proof,Pareto efficient,and recursively respects top priorities if and only if it is a TTC mechanism.19,20Moreover,the TTC mechanism includes the axiom of top priorities stating that,for instance,if a student is admitted to a school,then the top ranked at this school must have been admitted to a weakly better school.

Later studies have generalized the TTC algorithm to theoretical situations of the real estate market where some agents have no initial appropriations.21,22Rules have been applied to shield the TTC to the manipulation of preferences.It must be said that the TTC mechanism is a direct mechanism where there is a matching among all reported priorities and preferences.However,the matching selected by the TTC algorithm is not a stable one,in contrast to another algorithm in use,the Deferred Acceptance(DA)algorithm.17The DA algorithm has been also applied lately to the assignment of students to schools.

The mechanisms of TTC and the DA were proved to be strategy proof,but the TTC is Pareto efficient and not necessarily stable,and the DA is a stable algorithm,but not necessarily efficient.All these algorithms can be used to solve the allocation problems with the application of the concept of Matching.

3.Matching in game theory

Game theory can be defined as the theory of mathematical models to evaluate the choice of optimal decisions under conditions of con flict.23–25The set of players are the basic element in a game.It is assumed that each player has a set of strategies.When applying Matching approach,the preferences of each player on available resources are the strategies to be evaluated by the allocation mechanism.

The player preferences are formalized through lists where each player gives their priorities.The matching concepts assume the agents to be rational ones in a market,setting their preferences according to their interests and properly acting to achieve goals.If no agent finds a way to get a better result than the result proposed by the matching process,the result is said to be a stable one.

Definition 1.Formal Definition—There are two disjoint and finite sets of agents,one called S,with n agents,another called M with k agents.Each si∈ S（i=1，2，···，n）,has a strict preference,and is completely transitive on the elements of the other set.23

This preference can then be represented by an ordered list in the set M ∪ ｛si｝.Denote also the sias an element to form the preferred list by P（si）.Therefore,one possible preference list is P（si）=m1，m2，m3，m4，s1，m5.The notation m1?P（si）m2means that siprefers strictly m1to m2.Moreover,s1?P（si）m5also means that siprefers to be allocated to m5rather than not to be allocated.An agent m is an accept able partnership,or just acceptable to the agent s,if and only if m?P（si）s.Similarly,each agent mjin M,for j=1，2，···，k，has a strict preference,complete and transitive in the set S ∪ ｛mj｝.It can be represented by an ordered list of preferences and denoted by P（mj）.It is also said that s is acceptable to m,if and only if s?P（m）m.Finally,the notation PS= ｛P（s1），P（s2），···，P（sn）｝and PM= ｛P（m1），P（m2）···，P（mk）｝or,P= （PS，PM）denotes the preference lists of all agents in this market.

Each agent in S can be assigned to at most one set of agents in M,and each element mjof M can admit up to q（mj）agents.The number of elements in mjis then represented by q（mj）,or specifically by the set｛q（m1），q（m2），···，q（mk）｝.The market is denoted simply by H=({S,M,PS,PM,q})and the objective of the H function is to find the best way of partnering among the agents.A set of such partnerships is called matching.Formally,a problem of matching is then represented by the 5-tuple just described:

The incorporation of another element called r has been proposed in this 5-tuple,where r represents a constraint on the allocation:

The following definitions are given in order to understand the theory applied in this research.

Definition 2.A matching μ is a function from the set M∪S into the set of all subsets of M ∪ S such that:(A)|μ（s）|=1 for all s ∈ S such that if μ（s）? M then μ（s）=s;(B)|μ（m）|=q（m）for all m,and if the number of elements in μ（m）,say r,is such that r ＜ q（m）,then μ（m）contains q（m）-r copies of m;(C)μ（s）=m,if and only if s∈ μ（m）.23

Definition 3.A matching μ is individually rational if every pair（m，s）such that μ（s）=m,m is acceptable to s,and s is acceptable to m.In other words,the matching μ is individually rational if no agent is matched to an unacceptable mate.23

A special type of matching is the stable matching.Then these stable matchings are subsets of all possible matchings of a market.

Definition 4.A matching μ is stable in pairs and individually rational,if there is no s and m associated by this matching,m?P（s）μ（s）and s?P（m）s′such that for some s′∈ μ（m）.23

If there is a pair （m，s）then we say that this destabilizes the matching μ,because it can be improved if they form a partnership with each other.A matching μ is said to be unstable by sets,if there are another matching μ′and a coalition A?M?S.

Stability is an important concept from both theoretical and empirical point of view.Nevertheless,safety is the maximum requirement in ATM for the whole system.2,13,14,16For the slot allocation in DA-CDM approach,the stable solution is an important issue and models have been developed modifying the Compression step of the algorithm.8–10,26

4.TTC-CDM model

The TTC-CDM model has been developed based on TTC allocation mechanism and mainly in the CDM one.8,9This research is motivated by the maturity of this model and its application in a wide range of scenarios.TTC-CDM can be seen as a problem of resource allocation in a two-sided market represented by airlines(the flights)and airport managers(the slots).Implementing a TTC approach aims then to assign flights to slots based on a one-to-one relationship respecting the allocation preferences of airlines and airport managers.

4.1.Market of slot allocation

The slots allocation process is a fundamental task that takes place on the runways of airports.To define which aircraft will land or take off,as well as their order,is one of the basic processes performed daily for the flight schedule generation of runway operation.

A slot is a small time window for using the full range of airport infrastructure at a coordinated airport.That is,the term slot refers to a time band and relates to a certain space that an airline uses so that its aircraft,on a given route,can perform the landing and take-off procedures at an airport.

Since the runways at an airport can be considered as limited resources of the aeronautical and airport infrastructure,with supply and demand for their use.The models of two-sided matching markets can be associated with air traffic flow management processes.Therefore,the slot allocation process,whether for takeoff or landing operations,can be modeled as a ‘market”.12

As GDP can be seen as a resource allocation problem,this environment can be characterized as a ‘slots market”.

The problem of slots market consists of the following elements:(A)A finite set of flights F= （f1，f2，···，fn）;(B)A finite set of slots S= （s1，s2，···，sm）;(C)An array of capabilities q= （qs1，qs2，···，qsm）,where qsis a positive integer indicating the maximum number of flights that can be allocated;(D)A list of preferences Pf= （Pf1，Pf2，···，Pfn）,where Pfis the relationship of flight preferences f related to the slots including the option not to be allocated,S∪?;(E)A list of preferences of slots in relation to flights (individually)PS= （Ps1，Ps2，···，Psm）where PSis the slot’s preferences s related to the flights including the option to keep the position open,F∪?;(F)A restriction to the timetables of flights ef(the Earliest Possible Arrival Time(EPAT)),where ef≤si,i.e.any flight can be allocated a time slot that is less than the original flight schedule.

The matching can then be represented by the elements described above as μ = （S，F(xiàn)，Pf，Ps，q，ef）which can be written as:

The objective is to obtain this matching μ allocating the flights to the available slots.The slot allocation is referred to as a matching and can be defined as:

Definition 5.A matching is a function μ:F→S∪?satisfying|μ-1（s）|≤ qsfor all s∈ S.27

The first property of a matching is then refused by the flights and the slots to the proposed matching.Therefore,consider a matching μ and a pair （f，s）such that μ（f）=s.The pair is considered not mutually acceptable if s is not acceptable by f and f is not acceptable by s and then it is said the proposed matching μ is blocked unsatis fied by side.In this work,different types of agents will be assumed to be the decision partners and able to refuse the matchings.

4.2.Agent selection

The CDM process has already been applied in air traffic management.26Three types of agents as decision partners are considered in this research:

Air Traffic Control(ATC).a single agent responsible for detecting congestion in advance by predicting aircraft occupancy in the air scenario,using data available from the flight schedule.Its goal is to control and optimize air traffic flow.

Airline.agents having flights being operated during a given day.Each agent’s goal is to control its aircraft with regard to planned times of take-off and landing,reporting possible schedule changes due to technical and/or mechanical problems,or cancellations that may interfere in the original flight schedule.

Airport.airport managers of origin and destination,defined in the flight schedule.Their goal is to maintain the appropriate flow of take-off and landing in their runways,adapting to the operational security restrictions specified by the ATC agent.

ATC agent represents a centralized agent in the market and has no preferences over allocations.The airline and airport agents are the decision-makers to achieve the new schedule for the airport runways use.In order to obtain the best matching of the slot allocation taking into account the airlines and airport managers preferences,this research applies a different number of algorithms.

In other developed countries,such as USA,airport management is included in CDM procedures at the operational level.Since 2012,several international airports in Brazil are being privatized and,therefore,having their own economic interests.Due to this privatization,the efficiency and quality of airport management services in Brazil have been signi ficantly improved in the ATFM aspect,making airports an important player in the CDM process.

With this background,the initiative of this research is to develop a new framework of CDM,including the activities of decision of ATC services,airlines and airport management services.Within this framework,the three major decision makers mutually collaborate to allocate the slots and decide the sequencing of the aircraft,having strategic preferences in the allocation process.

In the slot allocation market,the goals of each agent may be different and even contradictory.For airlines,it may be important to reduce the total delay of their flights,and then to reduce the costs associated with such delays.For airport concessionaires,perhaps the goal is to optimize the flow of aircraft in the yard for a higher exit rate for passengers.

In this paper,the preferences of airlines are based on a strategy to focus on the operational pro fit of each aircraft belonging to the set of flights.

The preferences of the airport manager are based on the following three strategies:(A)to reduce the aircraft delay time;(B)to prioritize the flights according to the number of passengers;(C)to reduce the stress of the crew and passengers of each flight.

It is also important to mention that,according to the proposed structure,there is no direct relationship between the priority given to the flight by the airport manager and that by the airlines.

For specific strategies not addressed in this model,the players can work with the importance given to the flights based on specific goals,such as the priority treatment required for military flights,government flights,or among others.

In this work,all the modeling was carried out using only the airlines and airport managers as the stakeholders in the games,and different agents could be incorporated in future work.

4.3.Compression Algorithm(CA)

The Compression Algorithm(CA),currently used by the Federal Aviation Administration(FAA)during the Reassignment step of the Ground Delay Program(GDP),is a significant improvement over previous methods for allocating slots.The main advantage of this algorithm is the rewarding of the airlines when they give up slots that they cannot use.16When an airline gives up an earlier slot considered useless,it trades the slot for a later one,usually owned by the airline that eventually takes the possession of the earlier slot.

In the compression algorithm,an airline has a flight f with the earliest feasible arrival time of efand,e′frepresents its real arrival time as it is known by the airline.It may then be possible for the airline to falsely announce it to be e′f=ef,in an attempt to achieve a better outcome under the algorithm.The iterative scheme set out by the CA is described step by step in the following algorithm:

Algorithm 1.Compression Algorithm(CA).

Input.Initialize the current assignment as Φ = ΦI,Π = ΠI.Let V=S ΠI（F）denote the set of vacant slots,where Π is a Landing Schedule formalized as a feasible assignment of flights to the slots.Specifically,it is a function Π :F → S mapping flights to slots such that distinct flights get distinct slots,and flights are assigned to feasible slots.A slot ownership function,which is a function Φ :S → A that satis fies consistency with some Π:for all f∈ F,f∈ FAimplies Φ（Π（f））=A where A is the set of airlines,and each airline A∈A has a set of flights FA.Step 1.If V= ?,the algorithm ends at the assignment（Π，Φ）.Otherwise,it picks the earliest vacant slot s∈V to declare it active.Step 2.Let A= Φ（s）denote the airline that owns s.Check whether airline A has a flight f∈FAthat both:(A)occupies a later slot Π（f）＞ s;(B)could feasibly use slot s（ef ≤ s）.If so,let f be the earliest such flight according to Π,denote its slot t= Π（f）,and go to Step 4.Otherwise go to Step 3.Step 3.Check whether any airline has a flight f that both:(A)occupies a later slot Π（f）＞ s;(B)could feasibly use slot s（ef ≤ s）.If so,let f be the earliest such flight according to Π,denote its slot t= Π（f）,and go to Step 4.Otherwise remove slot s from V and return to Step 1.Step 4.Move flight f from slot t to slot s:set Π（f）=s and set Π（s）equal to the airline of flight f.Set Φ（t）=A.Remove s from V and add t to V.Return to Step 2,using t as the new active slot s.One of the important features of the CA is given by property 1.8

Property 1.The CA cannot be manipulated by misreporting the feasible arrival time of its flights.

Even though the CA satis fies Property 1,it can return a landing schedule that is not in the core.In Game theory,thecore is the set of feasible allocations that cannot be improved upon by a subset(a coalition)of the market.

4.4.Trade Cycle(TC)Schummer algorithm

A previous work of Schummer and Vohra8,9related to the Assignment of Arrival Slots contains a Game theory approach based on the airlines.Their work defines new proposals on Matching theory to the problem of waiting on the ground.

The first contribution of Schumer and Vohra study was to formalize and analyze attributes such as encouragement that the airlines have to send delay and cancellation information on their flights in a timely manner.A mechanism was then proposed to satisfy some formal attributes,called Trade Cycle.This mechanism is a generalization of the TTC algorithm published in previous research.3,6,21,28Therefore,the new attribute included in the Trade Cycle(TC)algorithm is a formalized incentive according to the Matching theory,motivating airlines immediately to release any of their unusable slots.

The new TC mechanism,although based on TTC variants as proposed by Balikrishnan,29has a different implementation.Schummer and Vohra8assume airlines to be the market participants responsible for making strategic decisions and rather than the aircraft.It is then showed that the FAA Compression algorithm cannot guarantee the concept of slots property rights for airlines even though that fact was the motivation for the introduction of Compression more than a decade ago.Nevertheless,the existing mechanisms do not avoid a possible manipulation by the airlines,as they do not need necessarily inform cancellations,enabling them to retain their landing slots.

In summary,the Compression algorithm cannot always obtain stable results and therefore a satisfactory core set.The TC algorithm by Schummer and Vohra8,9solves the waiting problem on the ground(GDP,i.e.,ground problem)obtaining a viable solution based on the CDM algorithm.This research describes the TC algorithm obtaining an allocation set in the core.It iteratively adjusts the original landing schedule until any remaining vacant slots are unusable by the present flights.The iterative scheme set out by the applied TC algorithm is described next:

Algorithm 2.TC algorithm.

Input Initial assignment （f，s）declaring all slots and flights to be‘active”.Step 1.If the set of active flights is empty,the algorithm ends.Otherwise,construct a graph as follows:(1)Introduce a node for each active slot and each active flight.(2)From each flight f,draw a directed edge to the earliest active slotthat f can occupy.(3)From each occupied slot,draw a directed edge to the flight that occupies it.From each vacant slot owned by any airline A,draw a directed

edge to(A)the earliest active flight airline A,if one exists;(B)the earliest active flight in F.Step 2.Within any(directed)cycle in the graph:Assign each flight to the slot it points to in the cycle;declare the flight and its assigned slot an inactive.Unassigned slots within a cycle become vacant(and remain active).Return to Step 1.

Comparing the TC algorithm with the Compression algorithm,a notable distinction is that the flights are moved to new slots in each round and the inactive flights in the TC algorithm are removed.In Step 2,the two types of obtained cycles are either the one containing at least one vacant slot,or the other one containing only a flight and the slot it occupies.Nevertheless,the flights in such cycles are allocated to their favorite active slot having no chance to further improve their position.Therefore,TC corresponds,at least algorithmically,to an element of the class of Fixed Endowment Hierarchical Exchange(FEHE)rules described by.6,30

4.5.TTC-CDM allocation model

The TTC-CDM model has been designed for the compression step after substitutions and cancellations step in the CDM.The model consists of two algorithms including a preprocessing and an allocation process.

The pre-processing process aims to create the preference list of flights and slots by agents,using the pay off functions for the agent of airlines and the agent of airport managers.10The approach is based on a strategy focused on operational pro fit of each aircraft belonging to the set of flights of a given airline.

The algorithm for allocation process is developed to achieve a stable matching,considering the preference of each of the market participants.The algorithm ensures correct processing in case of inconsistencies in the preference ordering of flights and slots represented by?Fand?S.

The algorithm must always follow the preference ordering of all allocable elements in the model.Therefore,each flight is definitely allocated to the slot it has been associated with in the last step of the algorithm.The next section describes the TTC algorithm applied in this research.

4.6.TTC algorithm

TTC algorithm has been applied to many problems including the dynamic housing market situation.In this subsection,the TTC algorithm is introduced with some generalizations and properties.For better description of the TTC,it is necessary to establish the definition of a cycle,as well as auto-cycle.

Definition 6.A cycle is an ordered list of two disjoint finite sets called agents of the form （f1，s1，f2，s2，···，fk，sk，fk+1）,where f1=fk+1,more,f1prefers s1,s1prefer f2,···，fkprefers skand skprefers f1.In addition,each agent can be part of a cycle.19

The cycle is represented by Fig.1.where flight f1prefers to be allocated to slot s1, flight f2to slot s2and so on.

Fig.1 Graphic representation of a cycle.

Definition 7.Anauto-cycle is an ordered list of two disjoint if nite sets called agents of the form （f1，s1，f1）,where f1prefers s1and s1prefer f1.Mathematically:Let fi∈F and si∈S,then for any i,an auto-cycle is:（fi，si，fi）.

Once a cycle is defined,TTC algorithm can then be defined as follows:

Definition 8.(TTC Algorithm)Every flight points to its most preferred slot.There will be at least one cycle,and the flights on any such cycle(including self-loops)receive the slot to which they point.These flights are then removed from the system,and each remaining flight points to its most preferred remaining slot.The procedure continues till there is no flight to be allocated.3The following are the main steps of TTC algorithm.

Algorithm 3.Top Trading Cycle(TTC)algorithm.

Input.(1)The flight preferences by the slots.(2)The slots ranking preferences by the flights.(3)The flights are allocated according to their announced preferences and the preferences of the slots.The preferences list is programmed in the pre-processing by CDM.First round.Step 1.It is assumed that each flight has a preferred slot,and vice versa.Designate a counter for each slot(stating the amount of flights related to the slots).Its initial value is called the ability of the slot.Step 2.Each flight ‘points”to its favorite slot and each slot‘points” to its favorite flight.There is at least one cycle.Each flight in a cycle is assigned to a vacancy on the slot‘pointed” and removed from the process.The counter of each slot in a cycle is reduced by one,and if this counter becomes zero,the slot is also removed from the process.Counters of other slots remain unchanged.k-th round Step 1.Flights(slots)who do not wish any of the slots( flights)remaining are systematically removed from the process,keeping theiroutsideoptionsorkeeping theremaining vacancies unoccupied until each flight(slot)wants some remaining slots( flights).Step 2.Each remaining flight ‘points” to its favorite slot among the remaining slots and each remaining slot ‘points” to its favorite among the remaining flight.There is at least one cycle,where the remaining slots( flights)are exactly the desired slots(continued on next page)

It is observed that the TTC algorithm is similar to the Gale-Shapley algorithm proposed.The TTC algorithm terminates when all flights are allocated to a slot.A cycle is an ordered list that merges slots and flights.A slot in the system points to a flight that points to a slot.Whenever an element is repeated in this chain,a cycle is closed and the algorithm terminates a step,removing the participants bending to the cycle.The algorithm continues while the slots and flights remain.

Proposition 1.The mechanism TTC is not stable.19

Proof.Assuming that the matching is not stable,there is a set（f，s）;blocking μ,and then i.e.fP（s）μ（s）and sP（f）μ（f）.Observe that f is acceptable to s and vice versa.As μ（f）=f,so,f is allocated to itself.sP（f）μ（f）means that,at some step of the algorithm,slot s made a proposition to flight f and as μ（s）=f,the proposal is accepted by f.Therefore,fP（s）μ（s）=sP（f）μ（f）.So,the matching is not a stable one. □

Proposition 2.The mechanism TTC is Pareto efficient.19

Proof.(Induction).Consider the TTC algorithm,any flight leaving the process in Step 1 was assigned to the slot of its choice and,therefore,we cannot propose another better allocation.Each flight leaving the system in Step 2 is assigned to the slot of its choice between those remained vacant and,as the preferences are strict,it is not possible to do the flights to improve their positions in Step 2 without harming the flights already allocated in Step 1 which have their best possible allocation.Proceeding in a similar manner by induction,no flight could be improved without harming any other flight of a previous step.Therefore,it is proved that the mechanism is Pareto efficient.□

Lemma 1.Fix the announced preferences of all flights except f in R-f= （Ri）i∈F｛f｝.Suppose that in TTC,the flight f is removed at Step T under Rfand in Step T*under R*f.Suppose T≤T*,then the remaining flights and slots at the start of the Step T are the same whether flight f announces Rfor R*f.19

Proof.As the flight f did not participate in a cycle prior to Step T,the same cycles are formed and so the same flights and slots are removed in the previous steps to the Step T. □

Proposition 3.The mechanism TTC cannot be manipulated.19

Proof.Consider a flight f with true preferences Pf,and to fix an announced preferences pro file R-f= （Ri）i∈F｛f｝,the objective is to show that advertising their true preferences Pfthe flight f gets allocation at least as preferable to the allocation obtained through any other Rf.Let T be the step at which flight f leaves under the Rf,（s，f1，s1，···，sk，f）be the arbitrary cycle it joins,and thus slot s be its assignment.Let T*be the step which flight f is removed under the Pf.We want to show that the allocation obtained at f under the Pfis at least as preferred as the slot s.Two cases have to be considered. □

Case 1:T≤T*

Suppose the flight f advertises their true preferences Pf.Consider the Step T.By Lemma 1,the flights and slots remaining at the beginning of this step are the same as the flight f advertise Rfor Pf.So in Step T,slot s points to the flight f1,the flight f1points to the slot s1,...,the slot skpoints to the flight f.Moreover,they continue doing this until the flight f be allocated in some slot.As the flight f under Pftruly points to its best choice among the slots remnants of each step,it is assigned to a slot better than its current position s or eventually joins the cycle （s，f1，s1，···，sk，f）and is appointed to a vacancy on the slot s.

Case 2:T＞T*

By Lemma 1 in the TTC algorithm,the slots remnants at the beginning from Step T*are the same which want flight to advertise Rfor Pf.Moreover,the flight f chooses its best option among the slots remaining in step T*under Pf.In this case,their allocation under the real preferences is at least as preferable as the slot s.

The proposed algorithm is in the tactical operation level for the Compression in the last step of CDM.We assume that all necessary information in this step is made available for related agents.This information is the result considering the conditions of weather change and other random influence.

The next sections present the applications of the algorithm proposed in this research.First,a theoretical example related to the assignment of flights and slots is presented,applying not only the algorithm proposed in this research but also the Compression and the TTC algorithms.To our knowledge,it is the first time that one example of slots allocation is presented using the Compression and the TTC algorithms.Afterwards,a practical example is given applying the TTC-CDM algorithm here proposed.

In practical example,the preference lists were based on payoff functions built from specific goals defined for each player.For airlines,their goal is to maximize the pro fit,and for the airport manager,to prioritize the delayed aircraft with large number of passengers.10

5.Case study

The TTC-CDM algorithm aims to better allocate the flights to the available slots taking into account the preferences of the airlines and the airport managers.The other algorithms proposed in previous research can also be applied to find the best assignment of slots and flights,but they take into account only the preferences of one of these agents,either the airlines or the airport managers.In order to show the differences among these algorithms,a detailed theoretical example is given applying these algorithms.

5.1.Assignment of slots and flights—theoretical example

A hypothetical example of Ground Delay Program(GDP)including six slots and five flights is given in this section.After running the Ration-By-Schedule(RBS)Algorithm and the substitutions and cancellations step,performed by the airlines,the beginning stage of the third stage consists of the setting of the information presented in Table 1.

5.1.1.Compression and the TTC-Schummer algorithms

The Compression algorithm is applied to the initial data set presented in Table 1.As has already been described in Step 1 of the Compression algorithm,one tries to allocate the first available slot to the first available flight with the first preference.The implementation of the algorithm for this example is presented in detail in Table 2.

The TTC-Schummer algorithm is also applied to the assignment of the slots and the airlines having the same input data set given in Table 1.As can be observed,the final results when applying the Compression algorithm and the TTC-Schummer algorithm are the same,as can be seen in Step 3 of Tables 2 and 3,respectively.

5.1.2.TTC-CDM algorithm

In order to show the feasibility of the TTC-CDM algorithm proposed in this work,the algorithm is also applied to the initial data set presented in Table 1.As mentioned before,in thefirst two steps of TTC-CDM algorithm,it is assumed that each flight has a preferred slot,and vice versa.In other word,each flight points to its favorite slot and each slot points to its favorite flight.The algorithm is presented in detail in Table 4.

The scenario just described shows the implementation of the three algorithms.It is important to note that in the TTCCDM algorithm,the airlines B and C were neither rewarded nor punished during the assignment of the slots.The allocations were made respecting the preferences not only of the airlines but also of the airport management.

Table 5 Final result by three algorithms shows the final results obtained by using three algorithms:(A)conventional Compression algorithm;(B)The TC-Schummer algorithm8,9;(C)TTC-CDM algorithm.

5.2.Assignment of slots and flights—TTC-CDM real case study

This case study uses the air movements of arrival of Tancredo International Airport(SBCF)in the city of Belo Horizonte(the state of Minas Gerais in Brazil).The SBCF airport has a large number of daily usages of various national and international flights,having a capacity of 10.2 million passengers per year.10

Table 1 Initial scenario( flights schedule)and initial set(preferences).

Table 2 Application of Compression algorithm.

Table 3 Application of TTC-Schummer algorithm.

Table 4 Application of the TTC-CDM algorithm.

The SBCF airport has only one runway and the original schedule of flights is usually adapted allowing arrivals and departures.This feature allows then to test the settings of the airlines on the possible arrival time ef.The proposed modelallows then the airlines to strategically advance or delay their flights,since they obey the airport operating restrictions.

Table 5 Final results by three algorithms.

Therefore,airlines can prioritize some flights over other ones.10The data set used is from the Civil Aviation National Agency(CANA),the Brazilian Enterprise of Aeronautics(INFRAERO),and the airlines TAP from Portugal and AZUL and GOL airlines from Brazil.The applied data set is given in Table 6.

The goal is to allocate all flights to the available slots,respecting the minimum allowed arrival time and the preferences of the agents.The initial setting of the allocation process is presented in Table 7 Sets of flights preferences(?F），slots preferences(? s）,and original owners of the slots(O),showing not only the preferences of the sets of the flights and of the slots but also the slots owners.10

The allocation process starts with an offer and acceptance step.First,f1proposes to its most preferred option,s1.All other flights follow the same step,such as f2and f3proposing to s2,f4and f7proposing to s4,f6to s5and finally f8to s6.As s1is empty,it accepts f1making the pair(s1,f1).The slot s2prefers f3instead of f2,and makes a pair with f3rejecting f2,and so on.The detailed implementation of this TTC-CDM algorithm is presented in Table 8.

Table 9 shows the results from DA-CDM process and the TTC-CDM process.All slots were allocated respecting to the preferences of both airlines and airport managers.Due to the cancelation,the original sequence with the vacancies of a few slots were maintained until the initial of the execution of TTC-CDM algorithm.It must be added that the two models obtained the same results showing not only the correctness of the implemented model but also its importance,since it applies a new approach to the important slot allocation problem.

The slots were allocated to guarantee the property concepts,prioritization,fairness and efficiency in resource allocation,which are defined premises in the philosophy of collaborative decision making,and above all sense of stability.

An important discussion is the trade-off between choosing the DA-CDM algorithm and the TTC-CDM algorithm.The DA-CDM algorithm guarantees stability because no more allocated slots and flights prefer to be allocated again to others.However,the DA-CDM algorithm does not guarantee that the result is Pareto efficient.

On the other hand,the TTC-CDM algorithm necessarily reaches a Pareto efficient result for both sides,but will not necessarily be stable.

Table 6 Air movements of arrival and Information of flights from(SBCF airport).

Table 7 Sets of flights preferences(? F）,slots preferences （? s),and original owners of the slots(O).

Table 8 Detailed implementation of TTC-CDM algorithm.

Table 9 Final results of DA-CDM and TTC-CDM algorithms.

Table10 Comparison of DA-CDM and TTC-CDM algorithms.

Another aspect of matchings theories is that there is an important trade-off bet ween these choices stability and efficiency.

Table 10 presents the idea linked to this trade-off,the DA-CDM algorithm leads to a necessarily stable result(no blocking pairs),but it only guarantees to be weak Pareto optimum for the side to make the proposal.The TTC-CDM algorithm does not guarantee stability,but guarantees a Pareto result for both sides.

For a good allocation system,the more the agents feel and participants engaged in the selection process,the better the system will become.

6.Conclusions

CDM is an important approach to improve the efficiency of the airport traffic flow management.Based on this concept,this paper reformulated the TTC-CDM model to show a stable manipulation of the mechanism in the compression step of the slot allocation.Therefore,the proposed model allows the user to include the preferences of airport managers besides ATC units and airlines.

The TTC-CDM model was applied to a theoretical and a real case study.In the theoretical case,its results agreed with the ones obtained by other algorithms currently used to the slot allocation problem.In the real case study,the application of TTC-CDM algorithm showed its capabilities to be applied for real world problems.

Future work intends to modify the TTC-CDM model to include other factors and/or stakeholders in order to maintain the model manipulation-proof.For example,the new agents maybe the Tower of Control,Approach Control(APP),Soil Control,and other ATM services.It is also possible to define different payoff functions for each set of players and to reflect the specific objectives of each group.

In this way,optimized scenarios will also be modeled,to allow the initial treatment of multi-tracking in airports,and later multi-station multi-tracking.

Nevertheless,applying the TTC-CDM model allows one to evaluate the aircraft allocation problem under different scenarios including to avoid the manipulation.

In the case of airlines still deciding to manipulate the system,the TTC-CDM model can guide airport managers to take the appropriate actions.Moreover,as the preferences of different agents are taken into account,any disagreements in the allocation of slots can be really mitigated in order to make the system more efficient.

This research is partially supported by the Brazilian National Council for Scientific and Technological Development(CNPq Grant No.304903/2013-2).

1.Ball MO,Hoffman RL,Knorr D,Wetherly J,Wambsganss M,Smith RH.Assessing the benefits of collaborative decision making in air traffic management.Prog Astronaut Aeronaut 2000;239–52.

2.Brinton C,Lent S,Provan C,Prevost T,Passmore S.Collaborative departure queue management an example of airport collaborative decision making in the united states.Ninth USA/Europe air traffic management research and development seminar(ATM2011);2011 Jun 17;Berlin,Germany.New York:ATM;2011.p.1–9.

3.Shapley L,Scarf H.On cores and indivisibility.J Math Econ 1974;1(1):23–37.

4.Ball MO,Hoffman R,Mukherjee A.Ground delay program planning under uncertainty based on the ration-by-distance principle.Transp Sci 2010;44(1):1–14.

5.Sun X,Wandelt S.Robustness analysis metrics for worldwide airport network:a comprehensive study.Chinese J Aeronaut 2017;30(2):500–12.

6.Roth AE.The economist as engineer:game theory,experimentation,and computation as tools for design economics.Econometrica 2002;70(4):1341–78.

7.Almeida CRF,Weigang L,Meinerz GV,Li L.Satisfying game approach to collaborative decision making including airport management. IEEE Trans Intell Transp Syst 2016;17(8):2262–71.

8.Schummer J,Vohra RV.Assignment of arrival slots.Am Econ J Microecon 1999;5(2):164–85.

9.Schummer J,Vohra RV.Assignment of arrival slots.Am Econ J Microeconom 2013;5(2):164–85.

10.Arruda AC,Li WG,Milea V.A new airport collaborative decision making algorithm based on deferred acceptance in a two-sided market.Expert Syst Appl 2015;42(7):3539–50.

11.Hoffman RL.Integer programming models for ground-holding in air traffic flow management[dissertation].Berkeley(CA):University of California;1998.

12.Castelli L,Pesenti R,Ranieri A.The design of a market mechanism to allocate air traffic flow management slots.Transp Res Part C Emerg Technol 2011;19(5):931–43.

13.Cruciol LBV,Arruda AC,Li WG,Li L,Crespo AMF.Reward functions for learning to control in air traffic flow management.Transp Res Part C Emerg Technol 2013;35(10):141–55.

14.Crespo AMF,Li WG,Barros AG.Reinforcement learning agents to tactical air traffic flow management.Int J Aviat Manage 2012;1(3):145–61.

15.Li WG,Dib MVP,Alves DP,Crespo AMF.Intelligent computing methods in air traffic flow management.Transp Res Part C Emergy Technol 2010;18(5):781–93.

16.Vossen T,Ball M.Optimization and mediated bartering models for ground delay programs.Nav Res Logist 2006;53(1):75–90.

17.Gale D,Shapley LS.College admissions and the stability of marriage.Am Math Mon 1962;69(1):9–15.

18.S?nmez T,Utku üM,Benhabib J,Bisin A,Jacksonv M.Matching,allocation,and exchange of discrete resources,2011;(1):781–852.

19.Abdulkadiro?lu A,S?nmez T.School choice:a mechanism design approach.Am Econ Rev 2003;93(3):727–47.

20.Abdulkadiro?lu A,Parag AP,Alvin ER,Tayfun S.The Boston public school match.Am Econ Rev 2005;95(2):368–71.

21.Abdulkadiro?lu A,S?nmez T.House allocation with existing tenants.J Econ Theory 1999;88(2):233–60.

22.Abdulkadiro?lo A,Pathak PA,Alvin ER.The new york city high school match.Am Econ Rev 2005;95(2):364–7.

23.Roth AE,Sotomayor MAO.Two-sided matching:a study in gametheoretic modeling and analysis.Cambridge:University Press;1992.

24.Roth EA,Shapley LS.Stable matching:theory,evidence,and practical design.The sveriges riksbank prize in economic sciences in memory of alfred nobel 2012.Stockholm:Kungl Vetenskapsakademien;2012.p.1–5.

25.Fiani R.Game theory:with applications in economics,administration and social sciences.Amsterdam:Elsevier;2009.

26.Arruda AC,Leite AF,Almeida CRF,Crespo AMF,Li WG.Fairness analysis with cost impact for Brasilia’s flight information region using reinforcement learning approach.13th international IEEE conference on intelligent transportation systems;2010 Sep 19–22;Funchal,Portugal.Piscataway:IEEE Press;2010.p.539–44.

27.Balinski M,S?nmez T.A Tale of two mechanisms:student placement.J Econ Theory 1999;84(1):73–94.

28.Papai S.Strategyproof assignment by hierarchical exchange.Econometrica 2000;68(6):1403–33.

29.Balakrishnan H.Techniques for reallocating airport resources during adverse weather.2007 46th IEEE conference on decision and control;2007 Dec 12–14;New Orleans,LA,USA.Piscataway:IEEE Press;2007.p.2949–56.

30.Hylland A,Zeckhauser R.The efficient allocation of individuals to positions.Source J Polit Econ 1979;87(2):293–314.