Introduction to Overbooking
Overbooking is the sale of goods or services more than actual capacity.
Understand Overbooking
Assume, airlines earn their revenue from passengers only if it equals the ticket price. It maximises their profits just by ensuring their flight is full of passengers. If the seat is empty, no revenue generated from the ticket sales. Hence to alleviate this problem of hoping it flies full always, airlines tend to overbook their flights.
Why Overbooking?
Full Flight = Maximum Revenue
Maximum Revenue = Total Seats \({\times}\) Ticket Price
Empty Seat = No Revenue
Handle Overbooking
Overbooking raises another concern what if more passengers show up than the total capacity.
It generally is compensated in the form of expensive vouchers, and revenue takes a hit. We need to find a number that maximises the profits with overbooking.
All customers show up?
Bumping Customers = Revenue Hit
Mathematical Modelling
Let us consider an airline is selling its tickets for $100 each for a plane with total six seats and cost of bumping a customer is $120. Suppose seven persons want the ticket. Each ticket holder has a probability of 15% not showing up for the flight.
The probability is calculated based on historical data for this particular flight as Bernoulli random variable.
Ticket Cost = $100
Bumping Cost = $120
Total Seats = 6
Seats with Overbooking = 7
Probability (Customer showing up) = .85 (85%)
Let's model the Success that customer shows up after purchasing the ticket.
We define Random Variable N as Number of Success or number of customer shows up after purchasing the ticket. We see that the above trial is Bernoulli Trial since it is finite, independent, two outcomes customer shows up or not, and probability remains same (0.85).
\begin{align}
Success & = \text{Number of customers showing up} \newline
\text{Random Variable} \space N & = \text{Number of Success (or number of customers showing up)}
\end{align}
We can define Probability of success of getting k customers showing up given n number of events in the trial as
\begin{align} & P(N=kn) = {n\choose k} (p)^k (1p)^{nk} \\ &\space \text{for }\textit{k}\text{ number of success, where} \\ & N = \text{Number of Success}\\ &n = \text{number of events in the trial}\\ &p = \text{probability of customer showing up}\\ \end{align} Here the term \({(p)^k (1p)^{nk}}\) is the probability of a specific sequence k out of n, where as the term \({n\choose k}\) gives the number of combinations of such sequences.
Note: Please refer my previous post on Bernoulli Trials for an overview on probability distribution. blog.vcillusion.co.in/bernoullitrialsyesorno/.
Let's model the Revenue Function for the aircraft which is directly dependent on number of passengers showup against number of seats.
\begin{equation} r(k) = \begin{cases} 0 \space & \forall \space k \ni k \leqslant 0 \\ cost \times k \space & \forall \space k \ni 1 \leqslant k < n \\ cost \times n  bCost(kn) \space & \forall \space k \ni k \geqslant n \\ \end{cases} \\ \begin{array}\\ where,& \\ n =& \text{Number of seats} & \text{= 6} &\\ k =& \text{Number of passengers showup} & &\\ r(k) =& \text{Revenue function for k passengers} & &\\ cost =& \text{Cost of Seat in the flight} & \text{= \$100} &\\ bCost =& \text{Bumped Cost born per passenger} & \text{= \$120} &\\ \end{array} \\ \end{equation}
Let's put in the values and calculate for flitght with 6 seats with the ticket of $100 and bumped ticket of $120.\begin{equation} r(k) = \begin{cases} 0 \space & \forall \space k \ni k \leqslant 0 \\ \$100 \times k \space & \forall \space k \ni 1 \leqslant k < 6 \\ $100 \times 6  $120(k6) \space & \forall \space k \ni k \geqslant 6 \\ \end{cases} \\ \end{equation} \begin{align} where, \\ n =& \space\text{Number of seats in the flight = 6} & \\ k =& \space\text{Number of passengers showup} & \\ r(k) =& \space\text{Revenue function for k passengers} & \\ cost =& \space\text{Cost of Seat in the flight} & \text{= \$100} \\ bCost =& \space\text{Bumped Cost born per passenger} & \text{= \$120} \\ \end{align}
Let's use the expected value of revenue given ns passengers are invited can be defined as:
\begin{align} E(rn)=& \sum_{k=0}^{n} P(N=kn) \space r(k)\\ where,& \newline n =& \space \text{number of passengers invited} \newline r =& \space \text{revenue function} \newline P =& \space \text{probability of k passengers showing up} \newline E (rn) =& \space \text{expected value of revenue after inviting n number of passengers} \newline \end{align}
The airline has two strategies:

Normal Booking
Let us consider a usual scenario for sixseater aircraft. We are selling six tickets against six seats.
Expectation without revenue:
One shortterm approach can be to find passengers showing up based on probability and seats alone.
Expectation of number of customer showing up for selling six tickets against six seats with probability of customer showing up as .85 can be defined as
$$E(N) = 6 \times p = 6 \times 0.85 = 5.1$$Note: This approach is short sighted without the revenue. We expect 5.1 customers to show up, when 6 customers are expected with 0.85 probability.

Expectation with revenue:
We can define expected value of revenue given six passengers are invited for six seats as below.

\begin{align} E(r6)=\space & \sum_{k=0}^{6} P(N=k6) r(k) \\ \\ E(r6)= \space &P(N=06)\space r(0) \space + P(N=16)\space r(1) \space + \\ &P(N=26)\space r(2) \space + P(N=36)\space r(3) \space + \\ &P(N=46)\space r(4) \space + P(N=56)\space r(5) \space + \\ &P(N=66)\space r(6) \\ \\ E(r6)= \space &{6\choose 0} (0.85)^0 (0.15)^{6} \times 0 \space + {6\choose 1} (0.85)^1 (0.15)^{5} \times 100 \space + \\ &{6\choose 2} (0.85)^2 (0.15)^{4} \times 200 \space + {6\choose 3} (0.85)^3 (0.15)^{3} \times 300 \space + \\ &{6\choose 4} (0.85)^4 (0.15)^{2} \times 400 \space + {6\choose 5} (0.85)^5 (0.15)^{1} \times 500 \space + \\ &{6\choose 6} (0.85)^6 (0.15)^{0} \times 600 \space + \\ \\ E(r6)= \space &0 \space + 0.038728125 \space + \\ &1.097296875 \space + 12.43603125 \space + \\ &70.47084375 \space + 199.667390625 \space + \\ &226.289709375 \space \\ \\ E(r6)=\space &510 &\\ \end{align}
Note: We can observe that two values obtained using without revenue and with revenue coincides because of linear revenue function. Moreover, we can use the approach without revenue and multiply it by revenue when the passengers show up is less than the number of seats.
 Overbooking:
Selling seven tickets against six seats
 Expectation with revenue:
We can define expected value of revenue for seven invited passengers for six seats as below.
\begin{align} E(r7)=\space & \sum_{k=0}^{7} P(N=k7) r(k) \\ \\ E(r7)=\space &P(N=07)\space r(0) \space + P(N=17)\space r(1) \space + \\ &P(N=27)\space r(2) \space + P(N=37)\space r(3) \space + \\ &P(N=47)\space r(4) \space + P(N=57)\space r(5) \space + \\ &P(N=67)\space r(6) \space + P(N=77)\space r(7) \space \space \space \space \\ \\ E(r7)= \space &{7\choose 0} (0.85)^0 (0.15)^{7} \times 0 \space + {7\choose 1} (0.85)^1 (0.15)^{6} \times 100 \space + \\ &{7\choose 2} (0.85)^2 (0.15)^{5} \times 200 \space + {7\choose 3} (0.85)^3 (0.15)^{4} \times 300 \space + \\ &{7\choose 4} (0.85)^4 (0.15)^{3} \times 400 \space + {7\choose 5} (0.85)^5 (0.15)^{2} \times 500 \space + \\ &{7\choose 6} (0.85)^6 (0.15)^{1} \times 600 \space + {7\choose 7} (0.85)^7 (0.15)^{0} \times \big(700 120(76)\big) \space \\ \\ E(r7)= \space &0 \space + 0.006777421875 \space + \\ &0.23043234375 \space + 3.264458203125 \space + \\ &24.6647953125 \space + 104.825380078125 \space + \\ &237.60419484375 \space + 185.934711203125 \space \\ \\ E(r7)=\space &556.53\\ \end{align}
Hence, we can say that for a given bumping of passenger the cost is $120 and the probability of passenger showing up as 0.85 for a 6 seater aircraft is profitable for overbooking to 7 tickets.
NOTE: If we increase the bumping cost from $120 to $150, we see \(E(r7)=\space 466.77\). Hence, result in an expected loss regarding revenue.
 Finding Maximum Profit:
Selling x tickets more to six seats for maximum profit. We have understood the concept of overbooking by covering a simple scenario of booking an additional ticket, now let's try to find x more tickets airlines should book for maximum profits.
\begin{align} E(r6+x)=\space & \sum_{k=0}^{6+x} P(N=k6+x) r(k) \\ \end{align}
We can find the values of above equation to see revenue as a function of x.
Note: Ideally, we need to pay extra attention to various other external factors involved in bumping passengers like a hotel room, next flight, customer loyalty.