- Kewler - http://blog.icyball.com -
Puzzles that required computer solutions
Posted By admin On 20. October 2010 @ 14:07 In Programming Code Help, Managing Business | 1 Comment
Long-time Dr . Dobb’s readers may remember
“Dr. Ecco’s Omniheurist Corner”
where Professor Dennis Shasha posed
puzzles that required computer solutions.
Dennis is returning to Dr. Dobb’s, but with
a new twist on puzzles. The idea is to take
inspiration from the challenging apps that
readers have faced and to turn those into
puzzles.
If you have written an application that
required extensive use of heuristics
(because no algorithm would solve it) or
that is otherwise algorithmically interesting,
please send mail to Dennis at
shasha@cs.nyu.edu. Put “Tough Apps” in the
subject line. If Dennis likes it, he will contact
you. Then he will try to understand what you’ve
done and create a puzzle explaining the algorithmic
core. You will write a little blurb about yourself
and the problem if you want.
An empty hotel room represents a lost opportunity
to the hotel owner. The marginal cost of
cleaning a room is minimal compared to the fixed
cost of the personnel, rent, and so on. So, the
hotel has every interest in filling all its rooms.
Clever travellers and entrepreneurs can take
advantage of this by waiting until the last minute
to buy cheap rooms. Of course, they run the risk
that they may not sleep anywhere. The result is a
game. Let’s work up to the game in stages. It will
lead us to strange and amoral places, I promise.
Suppose you have the only hotel
in town. You have three rooms free for tonight.
You know from history that there will be one visitor
who is willing to spend $300 per night,
another at $200 per night, and one at $100 per
night. We’ll abbreviate this demand profile to 1 @
$300, 1 @ $200, 1 @ $100. If you have to give the
same price to all comers, what should you set
your price to be?
$200 — you get
$400 and leave one room empty. A recurrent
theme in this puzzle is that charging the same
price to everyone in the service of fairness results
in empty hotel rooms and roomless travellers.
Suppose there are two hotels next to one
another of the same quality and the demand is
twice that before, i.e. 2 @ $300, 2 @ $200, 2 @
$100. Now if your hotel sets the price at $200, the
other hotel can set the price at, say, $180 and get
three guests out of the four. You get only $200.
If you don’t know how much the
other hotel will charge, then what can you guarantee
to obtain?
Solution to Warm-Up 2: If your hotel charges
$133 and the other charges more, then you will
fill your three rooms and get $399. On the other
hand, if the other hotel also charges less but more
than $100, then you will get only $133. So, if you
charge $100, you will guarantee an income of
$300. If the other hotel reasons the same way,
then there will be six rooms for six travellers,
each costing $100 per night. Note how much better
this is for consumers.
Warm-Up 3: The hotel owners approach anagent to set room prices for both of them. They
agree to give the agent a portion of any extra profit they would
make beyond the $300 they can already get.
Solution to Warm-Up 3: If the agent sets prices at $200 per
room instead of $100, then each hotel’s profits will increase to
$400 (less the agent’s commission) while leaving two travelers
without rooms. This is why a single agent (whether online or not)
can be as bad for consumers as a hotel monopoly.
Now It’s Your Turn
1. Suppose you have the only hotel in town and it has six rooms.
The general problem is, given a demand profile and a certain number
of rooms, try to find the price per room that will maximize
hotel profits if you control all the rooms in a town. If the demand
profile is x @ $300, y @ $200, and z @ $100, for which positive
values of x, y, and z would you set the price for your six rooms at
$300, for which positive values would you set the price at $200,
and for which at $100?
2. If you control all the rooms in town, is there ever any profitmaximization
reason to charge $250, given the above demand profile?
Why or why not?
3. Suppose there are two virtually identical hotels on the same
block each having three rooms, but you control the rooms of only
one and the demand profile is again x @ $300, y @ $200, and z @
$100. For which x, y, and z values would you charge $200 to guarantee
as much revenue as possible? For which x, y, z would you
charge $300?
4. Staying in the two hotel scenario, for which x, y, z would you
charge something strictly between $200 and $300 in your hotel
(assuming you don’t know what the other hotel charges)? What if
you did know the other hotel’s prices and customers would always
compare prices before taking a room?
5. Loyalty programs and other perks may direct customers your
way. Suppose that your perks program can convince all travelers to
come to your hotel first. Each traveler will take a room in your
hotel if you charge what he or she is willing to pay. As usual, there
are six travelers altogether, where x travelers will be willing to pay
$300, y @ $200, and z @ $100. How should you set your prices as
a function of x, y, and z? How should your competitor set prices?
6. As you can see, the pricing power of the hotel owner depends as
much on consumer behavior (whether consumers compare prices)
as on monopoly power, either gained directly or through an agent.
Do you see any general pattern?
Solutions
1. If x >= 3 and y <= 4, then setting the price at $300 is best for the
hotels, though only x people will get rooms. Otherwise, if x + y >=
3, then charge $200 to get $800 for the two hotels. Otherwise, set
the hotel prices to $100.
2. No. You capture no more customers than if you set the price to
$300 and receive less revenue.
3. We already saw in the Warm-Ups that you would charge $100 if
x = y = z = 2 to guarantee at least $300 in revenue. Any other price
would give a lesser guarantee (though the possibility of more). If x
>= 5, then each hotel may as well charge $300 as each will get at
least two customers at that price. If x <= 4 and x + y >= 5, then
$200 is the best price (because charging $300 would guarantee you
only one customer and charging $200 gurantees at least two).
4. There are no x, y, z for which it is worthwhile to charge something
between $200 and $300 unless you know the prices of the
other. If, on the other hand, you knew the other hotel was charging
$300 and x = 3 and y = 5, then you could charge say $280 and
get all the $300 customers.
5. If x >= 3, then a price of $300 will guaranteee $900. If x + y >=
2, then $200 will guarantee $600. Your competitor can’t charge
even $200 unless x + y >= 5.
6. With monopoly power, you know all customers will come to
you, so you can set the price through direct calculation. In a competitive
market, you have to assume the worst case. If you can convince
customers to come to you first, then you can charge the most
per room.
Article printed from Kewler: http://blog.icyball.com
URL to article: http://blog.icyball.com/2010/10/20/43/
Click here to print.