How would game theory improve the allocation of seats on an airplane?

The following paper was developed by co-authors Muath Khlifawi, MSc and Jason Kraus, MSc for John Korsak's game theory class at Babson College:

Introduction
While the purpose of taking an airplane was originally getting from point a to point b, this concept has been evolving over the past couple of decades to encompass an above and beyond experience. Today, airlines pride themselves in not only transporting passengers, but also in providing an in-flight experience that is unmatchable. Competition is high and differentiation occurs through the creation of multiple classes that appeal to flyers from different socioeconomic backgrounds and by differentiating existing classes from their competitors. The differentiation
process occurs through free meals, snacks, and always-friendlier staff. One aspect that greatly affects a flyer’s experience is the location of their seat and to whom they sit next to. While airlines have tried to address the first issue by allowing passengers to select their seats online, the current systems fail to address the second issue.
For example, though John may have intentionally selected a specific seat, his experience on his latest flight from Hawaii to Boston was a negative one. This is attributed to whom he was sitting next to; John usually prefers some quiet time on his journey to allow him to engage in deep self-reflection.Unfortunately for him however, his neighbor kept initiating conversations with him for the entirety of the trip. Sadly, both concluded their journeys with a negative experience as the situation was not ideal for either party. One is tempted to dismiss this issue as beyond the airline’s control, but this paper proposes a new method for finding the ultimate seating solution. While passengers today have the ability to select their seats, there is still a clear lack of information about whom will be sitting next to them. If John knew about his talkative neighbor (and vice versa), they would have chosen different seats. What if the the new age of traveling was free of surprises and included optimal seating arrangements?

Role of game theory in seat selection in the airline industry
This paper is proposing a new system to address the issue of sea. Passengers share their preferences prior to the flight with the airlines for two key things: 1) seat location and 2) what kind of neighbors they would appreciate/like to avoid. The airlines’ system analyzes all of the inputs provided by the passengers and assigns seating based on the highest payoff possible to each passenger individually and collectively. By allowing passengers to prioritize preferences, they may not always get their number one preference, but they are somewhat guaranteed to avoid
their worst nightmare. 
For instance, Kyle may have two preferences: having a window seat and enjoying a quiet journey. However, he values his quiet time more than he does his window seat. Therefore, he is content with a middle seat (the least preferred seat on an airplane) so long he is guaranteed his quiet time. If the system is unable to provide him with both preferences, it automatically defaults to his most valued one. As a result, Kyle gets to enjoy his flight even though he did not get to sit in his favorite seat.By obtaining more information about the preferences passengers have, the airline is able to make more prudent decisions that enhance their passengers’ experience. What once was very similar to shooting in the dark, now becomes a thoroughly calculated process that increases overall utility at practically very little cost.
A game will be constructed to demonstrate the effectiveness of this system compared to the existing one. Nonetheless, because it can get extremely complicated very easily, the game will only cover a small section of the airplane and four passengers’ profiles. Once the validity of the model is proven, more player types and larger sections of airplanes can be covered.

Assumed players in the game
In order to make the application of the model as replicable as possible, four main personas were developed in order to capture user preferences on location and neighbor. When selecting seat assignments, each passenger can be grouped into one of these personas to determine their payoffs for different locations and the game’s optimal result. The personas were constructed using research from several studies. Correspondingly, the payoffs were calculated as a composite of location preference (aisle, middle, or window) and neighbor preference (talkative or quiet).
Additionally, since people in the middle seat have two neighbors, they are assumed to be affected by both of these neighbors equally.The resulting personas are:
1. Tech Traveler (T)
This is the airline passenger that spends their time on the plane using their electronic devices. They have headphones in during the flight as they listen to music or watch videos. The headphones drown out the sound of their neighbors, so these are quiet passengers that are also indifferent to the talking of their neighbors. Because the tech travelers are using laptops, tablets, phones, iPods or other devices, these individuals prefer seats with the most space around them. Their top choice is sitting in the aisle, followed by a window seat and then a middle seat (Livewell Collaborative).
2. Nature Lover (N)
The cloud move wistfully by above the scenic vista of the cities and sprawling
landscapes below. This traveler wants to take full advantage of the scenic view with a window seat. If this is not an option, they will settle for the comfort of an aisle seat and a good conversation. The nature lover loves conversing and as such prefers sitting next to talkative individuals, especially other nature lovers. However, they do not like starting a conversation with no response, so will be disappointed sitting next to a quiet traveler (Patterson, Thom).
3. Sleeping Beauty (S)
Whether they had a long day of layovers before this or have a long night ahead of them, this individual just wants to spend the majority of the flight sleeping. They prefer curling up and resting their head on the window and want peace and quiet on the flight while they sleep (International Business Times).
4. Running Faucet (R)
That spicy food and large soda before the flight is coming back to haunt them. And the bladder problem doesn’t help as well.The running faucet is the person on your flight that constantly gets up to go to the bathroom. They want to sit as close to the aisle as possible in order to get easy access when they need to get up. As they are not falling asleep on the flight, they would like to sit next to someone that they can have a conversation with (International Business Times).
Based on the developed personas, the following payoffs were assigned to each and every one of them. The payoffs are in utility units. Further, the table below showcases how different passengers payoffs are affected by sitting next to each other:

Note: An extended list of the payoffs resulting from each set of neighbors and locations can be found in Appendix 1.
How airlines and passengers play the game (today’s game)
The current model of airplane seat selection represents a sequential selection process with imperfect information. In this analysis, it is assumed that the order of selection is randomly chosen by nature as the next person to sign on and book a flight could be any of the four personas. Additionally, an equal number of each persona is participating in this game as they try to book twelve seats in four-row section of an airplane. A random generator was used to choose the order of selection and the results from two different orderings were compared. Below are the results:

The seat selections could be made using a game tree. There are 12! outcomes to the game tree. Player 1 has 12 choices, player 2 can choose from any of the remaining 11 seats and so forth. So instead, a diagram of the plane model is shown below. Seats are selected based on location preferences, and it is assumed that a quiet individual will pick their preferred seat with the fewest people in the row, while the talkative individuals will do the opposite. This yields the following:

As shown in Exhibit 1, the game is played by each player selecting their preferred seat when they sign up to book their tickets, a phenomena the researchers in this study chose to call ‘The Airplane Dilemma’. At this point in the game, every player had selected their best available seat in terms of location and only middle seats remain as they are deemed the least favorable. Player 9 is a nature lover and as such would prefer to sit next talkative individuals, especially other nature lovers. The payoff resulting from a middle seat in between a sleeping beauty and tech
traveler is -1, while the payoff resulting from a middle seat in between a nature lover and a tech traveler or sleeping beauty is +2. In an ideal situation, player 9 would select to sit in row 1 or 2 in order to receive the higher payout. However, in this situation the player has imperfect information and has no idea who any of the other players are or where they are sitting. As such, in this situation player 9 has a 50% chance of sitting between a sleeping beauty and a tech traveler, receiving the lower payoff, which is essentially a coin toss between the two outcomes.The row was randomly selected as row 3. The game is continued in Exhibit 2 below with
resulting payoffs above the seats:

As the airline wants the best seating arrangement for the plane as a whole, the outcome of the game is viewed as the sum of all payoffs, or +25. This will be compared to the alternative ordering as well as the ideal seating arrangements in the proposed method. Now, using a different ordering of the players (randomized), Exhibit 3 displays a different result:

In the second ordering, the resulting overall payoff is now 27. This shows that the order of selection does indeed matter for the overall payoffs of the game as it determines the remaining options for the other players. Because different orderings result in different payoffs, there must be an order that maximizes the total payoffs of everyone on the plane. Furthermore, if the airline had had perfect information on each passenger, they would have been in a position to develop an ideal seating chart that maximizes overall utility on the flight as demonstrated in the next section.

Proposed Model (new game)
In an ideal scenario, as the one displayed in Appendix 1, the airline has perfect information about each encounter between the passengers. By analyzing the utility data available on each passenger, the airline is now able to assign seats to its passengers versus selecting on their own with imperfect information. This model yields the following result in Exhibit 4:

As seen in Exhibit 4, by allowing the airline to select seats on behalf of its passengers, the total payoff moves from an average of 26 to 42; a utility increase of 61.5%. It is important to note here that the players’ role in the game is dramatically changing as they are no longer making a choice. They are shifting their position from active players in a sequential game with imperfect information to passive ones in a non-participatory simultaneous game. Yet, by giving up their roles, they end up with a significantly higher payoff. Consequently, the airline is now also doing better. Increased utility on their airplanes translate to happier customers which correlates to brand association with positive experiences.

It is worthy to note that the numbers were not tinkered in any manner to produce this outcome. The first two experiments in Exhibits 1 and 2 were completely randomized and the payoffs of the players were not changed at any point during the study. Granted, no airplane has four personas with an equal distribution. In fact, this game can get fairly complicated very easily. For example, a further exploration would be to dive into the kinds of conversations passengers enjoy
delving into. In this study, it is assumed that all conversations are linear. Again, these simple assumptions were in place for the purposes of simplicity and model validation. Taking the model any further would require sophisticated computational efforts.

Nonetheless, what this paper successfully concludes is that there are inefficiencies in place due to lack of information all around. This was a simple demonstration. In such scenarios, even when interests are conflicted (i.e. two players preferring the same seat), disclosing more information is better than less. This goes against common wisdom as giving out more information is deemed a strategical error. Nevertheless, this paper attests that by negating conflicted interests (i.e. airline
has no incentive to make players worse off, but has an incentive to maximize utility), revealing as much information as possible improves the situation for every player on his/her own as well as the collective population as a whole.

Synthesis
The same concept can taken and applied to all sorts of situations in which a group of people is
broken down to smaller subgroups that will have no choice for a given amount of time, but to allocate that time together. Internal projects at companies or university group projects are great examples where this model could be utilized. In fact, companies like McKinsey & Co considers the Myers-Briggs exam thoroughly for its assignment of consultants on a given project (Cunningham, Lillian). This is because obviously the company deems to establish synergies between team members, but also intend to create a pleasant experience for it employees and,
thereby, retain them. In this scenario, the interests of both consultants and the company are to maximize utility on working teams. Hence, the consultants have an incentive to provide as much information as possible about their working styles and be truthful on the Myers-Briggs exam. Through the modeling of the airplane dilemma, it is evident that game theory can be a helpful tool in solving real world problems. As demonstrated by shifting the game from a sequential one
where players have imperfect information to a non-participatory simultaneous game with perfect information, higher utilities can be achieved and all players end up with better payoffs. By putting the principles of game theory into action, airlines that usually spend extravagantly on improving their passengers’ experiences, now can benefit greatly from improving their passengers’ utility score at a relatively minimal cost. This goes to attest that game theory can be used to solve complex problems through cost-efficient manners.

Appendix 1: Modeled Payoffs for Every Player Based on Location and Neighbors

Works Cited

Cunningham, Lillian. "Myers-Briggs: Does It Pay to Know Your Type?" Washington      Post.The Washington Post, 14 Dec. 2012. Web. 30 Apr. 2015.                    <https://www.washingtonpost.com/national/on-leadership/myers-briggs-does-it-pay-     toknow-your-type/2012/12/14/eaed51ae-3fcc-11e2-bca3-aadc9b7e29c5_story.html>.
"Identifying the Future Traveler." Livewell Collaborative (2012): n. pag. Http://
     livewellcollaborative.org/. 2012. Web. 30 Apr. 2015. Patterson, Thom.
"Are You a Window Flier or Aisle Seater?" CNN. Cable News Network,n.d. Web.         30 Apr. 2015.
"The Most Popular Seat On A Plane Is?" International Business Times. N.p., 24         Apr. 2012.Web. 30 Apr. 2015.