Kick out your passengers fairly

The Problem

At Coders Co. we make the world a better place by helping airlines to kick out their passengers in a fair way.

We all heard that using bad algorithms generates a very wrong kind of buzz on social media. Fortunately, it doesn’t have to be the case. In the following lines, we provide a solution and allow you to kick out your passengers truly randomly giving all the people the same chance to be thrown out. There is more the algorithm can take into account exceptional cases — a wealthy client that just bought the ticket, a 150-kilo athlete that might not be too easy to drag — you only need to know where people that you make exceptions for sit.

We start with Figure 1 that shows a scheme of a typical plane with seats and rows. We assume you know the allocation of people. We first solve a couple of fairly simple cases to build up intuition and then present a more general solution. For now, we assume there are no exceptions and we will cover other cases later.

Figure 1. Typical plane scheme
Only individuals

Assume, that we checked in N people and we need to kick out k of them. The simplest case is if all our clients travel on their own. In that case, we can randomly pick k of them, and that will be fair. For example, we can write down all the names of people and put them into a hat to draw similar to Figure 2.

 

Figure 2. Draw from a hat like this
Individuals and couples

Now suppose we also have some couples that travel together. For simplicity, assume that the total amount of checked-in passengers N=5 among them we have 3 individual travellers: A, B, and C; and a couple D E. Suppose, we need to kick out k=2 persons. We assume that we only want to kick out D and E together since they are travelling together and we want to treat our customers well.

We can pick 2 persons from the individuals, and there are 3 possible combinations: AB, AC and BC. Alternatively, we can kick the only natural couple we have DE. Now it is the time to write the possible pairs on a piece of paper and put it in the hat. The only thing is to make sure every person has the same chance to be picked we need to put the pair DE to the hat twice. The reason is anyone except for DE is a member of two possible combinations and will be in the hat on two pieces of paper. Therefore, the hat pieces of paper composition is as follows: AB \times 1, AC \times 1, BC \times 1, DE \times 2.

Now, suppose there are N passengers that we checked-in, p couples and we need to kick 3 people. We can use a similar logic to solve this case. If we only pick from individuals, each of them can be a member of (N-p\times2-1)\times (N-p\times2-2) tripletons. On top of that, he can join one of the p couples to form a tripleton. As far as members of couples are concerned, they can make a tripleton with one of the (N-p\times2-1) individuals. Now, to make sure everybody has the same chance to be selected we need to balance the number of times tripletons are build from individuals with the number of times they are made of individuals and couples.

Suppose that each triplet constructed from individuals only is there once and the tripletons constructed from individuals and couples are there W times. Then, each individual is there

    \begin{equation*} (N-p\times2-1)\times (N-p\times2-2)+p\times W \:\: \text{times.} \end{equation*}

Whereas, each member of a couple is there

    \begin{equation*} N-p\times2-1\times W \:\: \text{times.} \end{equation*}

Now, to ensure that everybody has the same chance of being selected those two numbers should be the same. So we get

    \begin{equation*} (N-p\times2-1)\times W=(N-p\times2-1)\times (N-p\times2-2)+p\times W. \end{equation*}

putting things that contain W to the left-hand-side and the rest to the right-hand-side we obtain

    \begin{equation*} (N-p\times2-2)\times W = (N-p\times2-1)\times (N-p\times2-2) . \end{equation*}

Solving for W yields

    \begin{equation*} W = \frac{(N-p\times2-1)\times (N-p\times2-2)}{(N-p\times2-2) } . \end{equation*}

Concluding Remarks

In general, if we have N checked-in passengers, p couples and k people to kick we can use similar logic. There are only N-p\times2 individuals and each can be a part of N-p\times2-1 different pairs (he can make a pair with any other individual). Having said that, we also can consider cases 4 people travelling together (families with kids).

If you or your company struggle with a similar problem, contact me or us at Coders Co. We might not help you kicking out your passengers, but we can develop software that picks them randomly in a fair way.