Monday, November 30, 2009

The Game Theory of Overbooking

Posted by Mike Dorf

Having just completed a bit of holiday travel, I'm thinking about the game theory of overbooking, which, I discovered upon googling " 'game theory' & overbooking' " has produced a rather substantial literature.  Here's what happened on my latest flight, which presents a nicely simple case:  About 45 minutes before the scheduled departure, the gate agent announced that the flight was overbooked by one passenger and so the airline was offering the first volunteer a seat on a later flight plus $250 to give up his or her seat on this one.  There were apparently no takers, and so 20 minutes later, the offer was upped to $450, whereupon a volunteer came forward.

Was this the best deal the airline could get?  Quite possibly not.  If the volunteer was willing to take the later flight for $450, perhaps he would have been willing to take the later flight for $300, or even for LESS than $250.  True, someone whose break-even point is under $250--let's say $200 for simplicity--risks getting stuck on his scheduled flight (and thus giving up a $50 surplus from his perspective) by turning down the $250 offer in the event that another passenger comes forward and volunteers to take the $250.  But he also knows that everyone else knows that the airline will make a better offer if everyone turns down the $250, and that everyone else knows that everyone else knows that, and so on.

The airline is clearly counting on the collective action problem of the passengers.  If we could organize, we could hold out for a still-higher payout, and then split the surplus among us, but this is very complicated.  Some of us (e.g., I) were traveling in a group or had important deadlines to meet and thus would have required MUCH more money than the airline was likely to offer, and so in fairness, we shouldn't be required to be bought off at all--but the other passengers didn't know that, and so we could unfairly claim a share in the surplus.  In addition, we're strangers, and the airline personnel would likely witness us collaborating, whereupon they'd resort to some other approach.

According to data I downloaded from the Aviation Consumer Protection Division of the Department of Transportation (here), in the last quarter, about 15,000 confirmed passengers were involuntarily "bumped" from their flights, while over 175,000 voluntarily accepted an inducement to take a later flight.  Not having read the small print on my airline ticket, I assume that I have agreed to be bumped if necessary whenever I fly, but I count on the very low involuntary bump rate (just over 1 in 10,000, according to this short informative piece on overbooking) to ensure that this won't happen to me.  However, I would guess that the odds might go up if the gate personnel were to see the passengers organizing a holdout.

But let's go back to the case where there are enough passengers willing to accept an inducement the airline is willing to offer.  The procedure used for my flight and for every other flight I've been on when this issue has arisen is in many respects a prisoner's dilemma: the players (passengers) would do best by cooperating, at least to get the airline's bid up, but they are effectively isolated, and so they adopt a competitive strategy.  As noted above, this isn't a bad strategy from the airline's perspective but the game theory literature I came across suggests that it's not the airline's optimal strategy.  An alternative procedure that might work better for the airline would be to have passengers submit sealed bids indicating the LOWEST figure they'd each be willing to accept to take the later flight.  Then the lowest bidder wins (or lowest bidders, if the flight is multiply overbooked).

But that approach is tough for the airline for two reasons.  First, many of the passengers wouldn't submit bids at all, and other passengers, seeing this, might therefore write down a higher figure than the lowest they would really be willing to take.  Second, and in my view more importantly, the sealed bid approach and others like it would render too obvious what is really going on: Namely, that the airline is trying to conduct a reverse auction among its passengers.  That would likely have harmful effects on the passengers' good will towards the airline--already at something of a low among air travelers.  Sure, the actual procedure used is also more or less a reverse auction, but it creates the appearance of the airline giving something away--which in fact it is doing: The passenger who took the $450 really did value the difference between arriving on his original schedule and arriving later at less than $450.

So, much as I hate to admit it, this really was win-win.