« Calorie counts on the menu | Main | New constitutional amendments? »
Group Theory in the Bedroom
I had never thought of this:
In a sense, base 3 is the best of the integer bases because 3 is the integer closest to e...Suppose you are creating one of those dreaded telephone menu systems -- press 1 to be inconvenienced, press 2 to be condescended to, and so forth. If there are many choices, what is the best way to organize them? Should you build a deep hierarchy with lots of little menus that each offer just a few options? Or is it better to flatten teh structure into a few long menus? In this situation a reasonable goal is to minimize the number of options that the wretched caller must listen to before finally reaching his or her destination. The problem is analogous to that of representing an integer in positional notation: the number of items per menu corresponds to the radix r, and the number of menus is analogous to the width w. The average number of choices to be endured is minimized when there are three items per menu.
I have no idea if it is correct. It is from the often quite interesting Group Theory in the Bedroom, and Other Mathematical Diversions, by Brian Hayes.
Posted by Tyler Cowen on July 24, 2008 at 05:14 AM in Science | Permalink
Comments
My guess is that it's true only if all choices are equally likely.
Posted by: John S. at Jul 24, 2008 5:48:37 AM
1. I agree with John S. If one of the first three choices is chosen 5% of the time, then it should not be there and two choices would be efficient.
2. If someone can key the number before hearing all the options, things change and order also matters.
3. There is a final consideration regarding how people usually categorize options. We have a mental model of how a hierarchical menu works and that affect our expectations and hence the ease of use of the menu. These mental models should matter when designing the menu.
Posted by: londenio at Jul 24, 2008 6:15:58 AM
Mmmm. Interesting.
As John S said, it shouldn't be a symmetrical tree, but depend on frequency of choices, with infrequent choices further down the tree. However, this does NOT effect whether then span should be 3 at each level, ceteris paribus. At any given level, all choices (through their summed descendents) should have similar probabilities.
The objective function should be to minimise user time, not choices. In practise, dimensionally alike options will have to be put together, and complex parsing may have to be split apart. Was there a time cost for answering?
Overall, individual system variance will be so large that I suspect this finding is true but irrelevant.
Posted by: Alistair Morley at Jul 24, 2008 6:33:30 AM
I don't see how the menu selection problem is analogous to selecting the base of your numbering system. Reading a number isn't a particularly sequential operation, for most numbers in everyday use. More important is the expressivity of the base. That's why 12 has to be the best. A large number of fractions (based on 1/3, 1/4, 1/6) become much easier to write.
Posted by: A L at Jul 24, 2008 6:34:48 AM
The proof is easy. Maximize x^y (number of possible destinations) subject to (x*y) being some constant C (number of choices). This is equivalent to the problem of minimizing x*y subject to x^y fixed -- the math works out the same either way.
Okay, so y=C/x. Maximize x^(C/x). First order condition: x^(C/x) * (C/x^2 - log (x) C/x^2) = 0. In other words, log(x)=1; x=e.
Posted by: Alex F at Jul 24, 2008 6:57:02 AM
An organization that wants to minimize the number of phone calls that came through to a live person will have a more complicated menu structure.
An alternative is that you never get through to a live person but are asked to leave a message because the operators are so busy "serving" others.
For some companies, the customer who needs to talk with a human being rather than ordering online, looking at the company's web site for information, and submitting any questions via email or web form, is an unwanted and undesirable customer, a too expensive customer.
It is expensive to have a person answering a phone to take orders, answering questions, etc.
Posted by: chug at Jul 24, 2008 7:15:35 AM
Mmmmm... Huffman coding applied to lists...
Posted by: Jody at Jul 24, 2008 7:24:03 AM
Jody beat me to it. Huffman coding. Nothing to do with three or e, unless they are all equally probable options. Alex F: - lovely proof notwithstanding - wrong problem.
Posted by: Gef at Jul 24, 2008 8:09:32 AM
Alternate way of reaching of Alex F's result:
Define the cost function C(r,k) to be the number of items listened to, when there are k total items and r items per menu. Then C(r,k) = r * log_r k. and setting its derivative equal to zero, after a bunch of rearranging, gives (ln k / ln r)(1 - 1/ln r) = 0, to which r = e is the only solution.
(I assume that callers listen to every option on each menu they reach; if you relax that assumption and let them push a button as soon as they hear the one they want, it introduces a constant factor of 1/2 to C(r,k), and the minimizing value of r is unchanged.
Posted by: James Grimmelmann at Jul 24, 2008 8:21:15 AM
The easy way to see that the "Huffman coding" huffers are on to something is that if you had one option 99% likely, and 10 more options each 0.1% likely, you'd definitely want an unbalanced tree (you first ask if they want the most likely thing, and if they do the tree ends, if they don't it continues with more options).
What I don't get is how to construct the tree in general. I remember that information-based encoding selects the most likely option as having the least cost, and so on.
Could you construct a properly huffman-coded tree in a greedy fashion? By picking the most likely option first, for a tree of size one, and then increasing the size incrementally as you add less and less frequent options?
Posted by: mk at Jul 24, 2008 8:30:28 AM
A few corrections:
1) Arithmetic coding is more efficient than Huffman coding. They converge to the same thing if all your probabilities are powers of two.
2) Alex F's proof has a mistake. He's forgotten to add options for additional menu options. To take the extreme view, put two options at each level. Option 1 is do A. Option 2 is hear more options.
Posted by: EnlightenedDuck at Jul 24, 2008 9:55:23 AM
I have no fancy shmancy data to back it up, but I think each time the user has to press a button, beyond maybe... 3 times, their anger starts to increase exponentially. You probably have to strike a balance between efficiency and what people are willing to deal with.
Sure, when you want to determine the nature of truth, the Socratic method is fine and good -- but when you want to get an RMA for a broken router you're going to run and find some Hemlock.
Posted by: jay barnes at Jul 24, 2008 10:04:20 AM
I've got a ways to go before I get to thinking about that.
I'm still pondering why I have to press 1 for English. And no, I don't think 1 should be for Spanish or Chinese.
Posted by: Andrew at Jul 24, 2008 10:15:50 AM
Why not just use base e?
Posted by: aaron at Jul 24, 2008 10:21:08 AM
"Why not just use base e"
Well, it's fine if you don't mind expressing integers with infinite non-repeating 'e'-themal expansions...
Posted by: MattF at Jul 24, 2008 10:53:27 AM
A guiding principle among some professional game designers is to present to each player, on his turn, at least three but no more than four good choices.
Posted by: Allen Varney at Jul 24, 2008 11:27:41 AM
Gef -- I didn't mean to make any sort of normative statement about how to set up menus, or to defend the relevance of the math to the actual real-world problem. You can take this up with Brian Hayes. But Brian says "e" is the answer to a question, so I figured I'd state a mathematical version of the question and show why "e" is the answer. (I haven't read the book, but I assume the argument behind Brian's result is essentially the one that James and I made.)
I agree that the problem as I've stated it is really about minimizing the maximum number of choices to endure rather than the average number, and that these are only interchangeable under very specific assumptions -- again, take this up with Brian Hayes.
Posted by: Alex F at Jul 24, 2008 11:49:17 AM
Pretty sophisticated group of commentators. Myself, when I read about group theory in the bedroom, all I think is "J'aime bien faire l'amour surtout a trois."
Posted by: y81 at Jul 24, 2008 12:10:50 PM
Lester Telser had an article in which he argued that the denominations of currency and coinage ought to be at multiples of 3: 1,3,9,27,81,...
The reasoning is analogous to the above. However, Van Hove argues for the "Principle of Least Effort", i.e., base 2.
Telser, L.G. 1995. Optimal denominations of coins and currency. Economics Letters 49, 425-427.
Van Hove, L. 2001. Optimal denominations for coins and bank notes: in defense of the principle of least effort. Journal of Money, Credit, and Banking 33 (4), 1015-1021.
Posted by: Acad Ronin at Jul 24, 2008 12:15:16 PM
MK, yes you actually do build a Huffman tree with a greedy algorithm, but it works in reverse, ie from the least likely choices up.
Enlightened Duck, good point about Arithmetic coding being more efficient, but we don't really want the code. We want the tree that gives us the Huffman code, and I didn't think you get anything comparable with Arithmetic coding. (Been a long time though, I could be wrong.) Maybe you can reconstruct a similar tree given the coding scheme though...
The interesting question is how to adapt Huffman (or similar) methods to non-binary alphabets. I don't see why you couldn't modify the Huffman algorithm to do ternary coding without much trouble. Or even variable coding -- why force yourself to use the same number of symbols/same number of options at each position in the code/at each point in the phone call? That seems like what we really want, actually.
Posted by: SB7 at Jul 24, 2008 12:25:35 PM
SB7, thanks for the clarification.
I thought the standard Huffman tree would not suit our needs, but it could. We'd have to assume that the tree is binary: i.e., you always hear options of the form: "If blah blah blah, press 1, otherwise press 2."
If we want to relax this assumption we run into trouble. As you say, ternary or quaternary coding is not a big deal (just pick the three, or four, least frequent subtrees in the recursive step, instead of picking two).
But with variable branch factors it is trickier.
We can't assume that the greedy property still holds. Suppose we did assume this: we would be left with the following (wrong) recursive step:
Recursive step: With S subtrees remaining, try all values of n from n=2 up to S. Calculate the "loss" from placing the final 'n' subtrees underneath a new node. Keep track of the step with the least loss.
This doesn't work, since you want the lowest total loss, not the lowest loss at each step. The proposed algorithm is biased against values of n>2.
You may be able to do this using dynamic programming, where the state of the dynamic program is the number of remaining subtrees. I haven't checked, but that may work.
Posted by: mk at Jul 24, 2008 1:42:36 PM
To clarify: "Loss" here is not in terms of "lossy encoding", since this is not a lossy scheme. Instead loss is defined as let's say "expected number of options listened to" or something similar.
Maybe the problem could be viewed as starting with a terrible options tree (everything on one level) and making a sequence of repairs using dynamic programming, to optimize the "loss" or, if you like, "cost."
Posted by: mk at Jul 24, 2008 1:49:57 PM
mk, you're absolutely right. Getting a greedy method working with variable branching wouldn't be easy (and may not be possible). I had some heuristics in mind when I suggested it, but nothing close to provable optimal.
Posted by: SB7 at Jul 24, 2008 4:32:09 PM
So this is why Herbert Quain used the threefold structure in April March?
Posted by: Alejandro at Jul 24, 2008 5:16:34 PM
I really expected to see something about a threesome here.
Posted by: Dave at Jul 24, 2008 5:37:57 PM
