The Airport Problem Revisted
Today’s blog is one that nobody asked for and likely few will read. But that’s OK. I’m going to explore some different solutions to the Airport problem I walked through in my previous blog on Is Uber fare splitting fair? I’m also (hopefully) going to continue improving my writing skills.
The Airline Problem: Quick Summary
Imagine we had the following scenario (as provided by the Wikipedia article on the Airport Problem): There are 4 airlines considering building an airport runway: Alpha, Bravo, Charlie, and Delta (no relation to Delta Airlines):
Each airline operates planes that require different lengths of runway. For example, the local carrier Alpha only needs a short runway (Runway A) for its smaller planes, while the regional carrier Bravo would require a runway extension for its larger planes. Each airlines’ runway needs are shown below along with the cost of the runway section.
How should the airlines divide the $18 total cost?
Shapley’s Solution
One “fair” solution discussed in my last blog post was proposed by game theoretician Lloyd Shapley who won a Nobel Prize in Economics for his efforts. For linear problems (like this), his solution essentially becomes: if an airline uses a section of runway, it should split the costs for using that section of runway.
Thus, the Shapely solution looks like this:
Which means that each airline would end up paying the following:
This solution works for a couple reasons. Each airline is better off than if it tried to build its runway needs on its own. Alpha contributes $2 to the construction of Runway A in Shapley’s collective solution instead of paying $8 if it chose to build the runway itself. Likewise, Delta pays $9 in the collective solution versus paying $18 to build Runways A, B, C, and D on its own. No airline is better off reneging from this agreement. The solution also feels “fair” — you pay for what you use.
An Alternate Solution
Shapley seems like a smart guy. He won the Nobel Prize after all. Shouldn’t we consider the issue closed? My wife tells me we should. But I kept thinking about this problem, and something didn’t feel quite right… So I started asking myself some additional questions and trying to think of new solutions.
Do all the airlines consider the runway sections equal? If I knew that another airline cared more about a section than my airline, would that change how much we each should pay? Would an airline build a national hub if there wasn’t already a local airline service to the surrounding area? Could the larger airline ask the other airlines to build more of the runway before they committed to building section?
So I started messing around with some different thought experiments and solutions.
Relative Need Splitting Solution
The first experiment started with this idea: 100% of Alpha’s airline needs depend on Runway A. It is the sole section required for this airline. However, Runway A is only 50% of Bravo’s needs. Bravo also requires Extension B to operate its planes. In Bravo’s eyes, the runways are equally important — it can’t operate without either. And so on for Charlie and Delta.
If we take this perspective, each airlines values the runway sections in the following way:
If we weighted those needs against the needs of airlines, we’d get an idea of how much each airline cares about a section of runway relative to the other airlines. For example, for Runway A we’d say the airlines care about this section in the following way:
- Alpha =100% of runway needs = 1/1 = 12/12
- Bravo = 50% of runway needs = 1/2 = 6/12
- Charlie = 33% of runway needs = 1/3 = 4/12
- Delta = 25% of runway needs = 1/4 = 3/12
If compare the ratios of how much each airline cares, we can develop an idea of how much each airline cares about Runway A. This admittedly requires a little bit of mathematical gymnastics, but it works like this: If every airline rated Runway A’s importance to their needs on a scale of 12, Alpha would rate 12. The others would mark 6 (Bravo), 4 (Charlie), and 3 (Delta). Of the 25 overall “ratings” from all airlines, Alpha’s 12 represents 48% of this total. If we repeated this for each section, we van start to see how much each airline cares about each section of runway relative to the other airlines:
This makes intuitive sense to me. For example, even though Extension D is only 25% of Delta’s needs, it is the only airline that needs this section. The relative value to Delta versus any other airline is 100%. Likewise, Charlie disproportionately needs runway Extension C relative to the other airlines. The same is true for Runway A for Alpha and Extension B for Bravo.
If we then multiply the cost of the runway by how much each airline needs that section of runway relative to the other airlines, we get the following:
Summing the runway splits up, the $18 runway project costs are allocated in the following way:
This is slightly different than the values Shapley came up with, but all airlines still benefit from splitting costs collectively. I’m going to call it the Relative Need Splitting Solution (particularly since my best man roasted me at my wedding about naming a mathematical law after myself — Sullivan’s Law). While Alpha ends up paying more, this kind of makes sense since the expensive Runway A section is relatively more important to it than the other airlines. You can play this strategy out and see that it isn’t rationale for anyone to renege under this structure either.
Relative Costs Splitting Solution
Since we know that runway sections have different costs and each airline values a section of runway differently too, can we combine these two ideas?
In this version of the solution, instead of thinking about whether a runway was needed in an airline’s overall strategy (a binary “Yes” or “No”) and treating all sections as equally important to an airline (e.g. Bravo valued Runway A and Extension B equally important at 50% of its overall needs), I instead looked at the cost of each section of runway to an airline’s overall needs.
Let’s look at Delta, which needs to build the longest runway. If Delta builds the entire runway on its own, it would pay $18 broken down as: $8 (Runway A) + $3 (Extension B) + $2 (Extension C) + $5 (Extension D). Therefore Runway A represents 44% of Delta’s required costs ($8 / $18). Instead of treating Runway A as 25% of Delta’s relative need like the last example, the 44% make more sense since Runway A is the most expensive section to be completed. We can expand this idea to see that Runway A represents 100% of Alpha’s costs, 73% of Bravo’s costs, and 62% of Charlie’s cost.
If we look at the costs of each runway relative to each airline’s overall cost requirements, we will see the following:
Using the same mathematical gymnastics as before to compare the relative costs of each runway section to each airline’s overall cost needs, we could make the following split (note the Least Common Multiple of 8, 11, 13, and 18 is 10,296):
- Alpha =100% of runway costs = $8/$8 = 10,296 / 10,296
- Bravo = 72.7% of runway needs = $8/$11 = 7,488 / 10,296
- Charlie = 61.5% of runway needs = $8/$13 = 6,336 / 10,296
- Delta = 44.4% of runway needs = $8/$18 = 4,576 / 10,296
In this case, Alpha would account for 10,296 of the 28,696 “cost ” importance ratings for Runway A, or 35.9%. Across all runways, costs would be allocated in the following proportions:
If we multiple the cost of each runway by the proportion each airline should pay we get the following split outcome:
We can once again sum up the allocated cost of each runway to see how the $18 project will be split across airlines:
I kind of like this solution because it recognizes the relative importance of each runway stretch to each airline while also considering the cost of that section of runway. When comparing the solutions, this one (unsurprisingly) nets out as a middle solution for 3 out of the 4 airlines.
Is there room in the game theory pantheon for the Relative Costs Splitting solution?
The Relative Costs Splitting solution potentially reduces the bias within the simplification of both the Shapley Value and Relative Need Splitting outcomes. The Shapley Value finds a solution where everyone splits what they use evenly, even if runway sections have different relative importance to each airline. The Relative Need Splitting solution only considers whether an airline needs a section of runway or not as a basis for its relative evaluation. The Relative Costs splitting solution looks to incorporate ideas from both of these solutions and adjusts for cost.
One way I decided to check for “fairness” was by looking at how much each airline would pay in the 3 different collective strategies versus building their own runways (the “go-it-alone” strategy). In the Shapley scenario, Alpha would pay $2 instead of the $8 it costs to build Runway A itself. This strategy yields paying only 25% of the go-it-alone total. I did the same comparison for all airlines across all strategies as shown below.
Looking across the three strategies, it kind of looks like my conjectures were well founded. The Shapley and Relative Need Splitting strategies yield results with greater variability. I (intuitively) think the Shapley Value reduces Alpha’s % payments the most, because it’s the runway section that is most shared and therefore most beneficial to the others participating in a collective agreement. Why shouldn’t it get more of the savings? That’s kind of “fair” in a way.
The Relative Costs Splitting approach, however, keeps the airlines in a tighter % savings range. It has the lowest variance across the group when comparing % savings rates — which also feels kind of “fair”-ish. I wonder if there’s a way to find the point at which the % savings range reaches a minimum across strategies, and what results that would yield. Sadly, I don’t have the math skills at present for that. If any mathematician is bored, feel free to tease this out further and hit me up ;) Here’s whay I imagine it would look like:
Hopefully some of my nerdy friends enjoyed this unsolicited deep dive. In any case, I enjoyed thinking through this problem again and getting a little more writing practice under my belt. If you want to think about other problems like these in an approachable way, I recommend Dr. Haim Shapira’s highly entertaining book Gladiators, Pirates and Games of Trust: How Game Theory, Strategy and Probability Rule Our Lives.
Until our next mental flight together!