Could reserving a hotel room potentially lead to a suboptimal allocation of rooms?

Question

Suppose you have a standard hotel with a set of rooms. If you have booked a room for a fixed period of time, would allocating a specific room in advance potentially cause a conflict when trying to allocate rooms for other bookings in the future?

I have thought about this and can not think of an example where allocating in advance would make any difference, given the rooms are all interchangeable within their class (single/double etc.). Assuming that every booking has to be assigned a room eventually, there must be a solution so that every booking is associated with a matching room. Which specific room within the set of matching rooms should be irrelevant, hence a pre-allocation of a specific room should make no difference.

Is this in fact the case or am I missing something? I would like to have an example of where pre-allocation would cause an issue.

Background: I was told at checkin that my requested room could not be allocated because I would have been blocking it for other guests.

Answer 1

I respond to your question, assuming you are interested in "types of constraints that can restrict a pre-allocation or assignment of a room to a person in advance."

Since there is a time aspect in that problem, think of these assignments as scheduling jobs on machines (so a pre-allocation is assignment without the complete knowledge of all the other jobs). For example:

1) A group of jobs needs to be processed together on a machine. Think of a group of people traveling and would like their rooms to be next to each other during their time in the hotel. Pre-assignment of rooms may avoid that to happen because:

• Some of the rooms are pre-assigned and not available.
• The rooms next to each other can be available but only for a portion of the time (they want it for a whole week but only two days those rooms are available)

2) Extending on point 1, there are cases that there is uncertainty in the processing time of a job on a machine. i.e. a regular businesswoman staying at the hotel and historically, she may require several extra days beyond what she reserves for. As the manager, I prefer to keep her current room available for a few extra days (beyond what she has reserved) rather than pre-assigning it to someone, in case she likes to stay a few more days!

3) And now extending on point 2, I like to take into account the uncertainty of job assignment, i.e. the person may show up or cancel the reservation (of course, unless you are willing to reserve the room and pay the non-refundable price in advance, which in that case, it falls under the 1st point again)

Answer 2

In case the number of reservations for any of the days does not exceed the number of available rooms, by applying Dilworth's theorem one can show that there always exists an allocation of rooms to reservations in such a way that none of the guests has to switch rooms during their stay. When a single room is pre-allocated, this indeed will still always be possible as the rooms are interchangeable. However, when two rooms are pre-allocated, conflicts may occur as the following example shows:

• Guest 1 books day 1
• Guest 2 books day 2 and day 3
• Guest 3 books day 1 and day 2
• Guest 4 books day 3

Clearly, assigning guests 1 and 2 to the same room and guests 3 and 4 to the same room requires only two rooms. However, if guests 1 and 4 are pre-allocated to the same room, three rooms are required.

Finally, note that a reason for such a seemingly shortsighted assignment (besides the ones that @EhsanK mentions) is that in reality often not all rooms are interchangeable. For example, guests 1 and 4 could both have requested a quiet room at the backside of the hotel.