Constant-Factor Algorithms for Revenue Management with Consecutive Stays

Imagine you are the manager of a bustling train station or a popular hotel chain. Every day, thousands of people show up, each wanting to book a seat or a room for a specific stretch of time. Some want the whole journey; others just want a few stops. The catch? You have a limited number of seats or rooms, and once you give one away, it's gone for that specific time slot. This is the heart of Network Revenue Management: the art of deciding who to say "yes" to and who to say "no" to, so you make the most money without running out of inventory for the big spenders who might arrive later.

In the world of math and computer science, this is a classic puzzle. Usually, the best way to solve it is to look at the entire future, know exactly who will arrive and when, and then plan the perfect schedule. But in the real world, you can't see the future. You have to make decisions on the fly, one customer at a time, not knowing who is coming next. This is called an "online" problem. For years, mathematicians have struggled to find a simple, fast rule that guarantees you'll make a decent amount of money, even without knowing the future. The big question has been: Can we find a strategy that is guaranteed to be "good enough" (a constant fraction of the best possible outcome) no matter how long the bookings are or how tricky the customers are?

This paper by Ming Hu and Tongwen Wu tackles that exact question. They look at two different ways customers might behave. In the first scenario, it's like a train ticket: you either accept the passenger and assign them a specific seat, or you reject them. In the second, more complex scenario, it's like a boutique hotel or Airbnb: you show the customer a menu of available rooms, and they get to pick the one they like best based on their own preferences. The authors developed new, fast computer algorithms to handle these situations. They proved that their methods are mathematically guaranteed to earn at least 63.2% of the money the "perfect" future-knowing planner would make in the simple train-ticket case. When customers get to choose from a menu, the guarantee drops to 27.1%. Even when the length of the stay is random and unpredictable, their algorithms still manage to secure a solid chunk of the potential revenue, proving that you don't need to be a psychic to run a profitable business—you just need the right math.

The Puzzle of the Missing Seats

Think of the problem like a giant, shifting jigsaw puzzle where the pieces keep changing shape. In the "Accept-or-Reject" world (like the train example), every time a passenger asks for a seat from Station A to Station F, you have to decide instantly: "Do I give them Seat 101? Or do I save it for someone who might want it later?" If you give it away too early, you might miss out on a big group booking. If you hold on too tight, you might leave the seat empty forever.

The authors realized that instead of trying to predict the future, you can use a clever trick called a "fluid relaxation." Imagine the seats aren't solid blocks but a flowing liquid. You calculate how much of that "liquid" seat should be reserved for different types of travelers based on probabilities. Then, they built a "Proposal-Discarding" algorithm. Here's how it works in plain English:

Before a customer even walks up to the counter, the computer simulates a "what-if" scenario. It asks every available seat, "If a customer of this type showed up, would you be willing to take them?" Each seat flips a coin based on the math to decide if it raises its hand. If multiple seats raise their hands, the computer picks the one that would make the most money. If no one raises their hand, the customer is politely turned away.

But here's the magic twist: even if a seat didn't get picked for the real customer, the computer pretends it did get used. It marks that seat as "busy" in its internal simulation. This keeps the math honest and prevents the system from getting too greedy. This "virtual busy" status ensures that the algorithm doesn't accidentally double-book a seat in its calculations, keeping the probabilities independent and the math solvable.

When Customers Get to Choose

The second part of the paper is even more fun because it adds human choice. Imagine a hotel where you don't just assign a room; you show the guest a list of three available rooms: one with a view, one with a balcony, and one that's cheaper. The guest then picks the one they like best. This is the "BAM-based" scenario (Basic Attraction Model).

This is harder because the guest's choice depends on the whole list you show them. If you show them a fancy room, they might pick it. If you show them a fancy room and a cheap room, they might pick the cheap one. The authors had to invent a new way to link the computer's "virtual" choices with the guest's real choices. They used a technique called "randomized coupling." Think of it like a magician's trick: the computer generates a random list of rooms to offer, but it does so in a way that mathematically guarantees the guest's choice will align with the computer's plan, even though the guest is making a free choice.

They found that while this choice adds complexity, their algorithm still works. In the "menu" scenario, they proved their policy earns at least 27.1% of the optimal revenue. If the length of the stay is also random (like a guest saying, "I might stay 2 days, or maybe 5"), the guarantee drops a bit more, but it stays positive: 17.1% for the menu scenario and 39.9% for the simple train scenario.

Why This Matters

Before this paper, the best guarantees for these kinds of problems were very weak. They depended on how long the bookings were. If people booked for very long trips, the guarantee would shrink to almost nothing. It was like saying, "Our strategy is great, unless you stay for a month, then it's useless."

The authors showed that this isn't true. They proved that you can have a "constant-factor" guarantee. This means no matter how long the stays are, no matter how many resources you have, your strategy will always capture a fixed, healthy percentage of the best possible money. They also showed that you can't do much better than 63.2% for the simple case (proving it's "hard" to get closer to 100%), which means their solution is actually very close to the best possible answer we can hope for.

In short, they took a messy, unpredictable real-world problem and gave it a solid mathematical backbone. They showed that with the right algorithm, you don't need to be perfect to be profitable; you just need to be smart enough to know when to say "yes," when to say "no," and how to let customers choose without losing your shirt.