Today I had an experience that I have had many times before, and so, I imagine, has almost everybody (at least if they are old enough to be the kind of person who might conceivably read this blog post). I was in a queue in a chemist (=pharmacy=drugstore), and I knew that my particular item would be quick and easy to deal with. But I had to wait a while because in front of me was someone who had an item that was much more complicated and time-consuming. In this instance the complexity of the items was not due to their sizes, but a more common occurrence of the phenomenon is something that often happens to me in a local grocery: I want to buy just a pint of milk, say, and I find myself behind somebody who has a big basket of things, several of which have to be weighed, some of which don’t have their prices on, etc. etc.
Suppose you were a shopkeeper with just one till and you wanted to devise a good system that would allow people to jump the queue if they were only going to take a very short time. What might you do? And given that I don’t have a good answer to that question, what am I doing posting about it?
The answer is that a few months ago I wrote a post in which I criticized a proposal for an A-level in Use of Mathematics. Amongst the responses I got to that post was an email by Joseph Malkevitch, from the mathematics department at CUNY, drawing my attention to a thought-provoking article he had written. In this article he defends the idea of interesting children in mathematics by showing how it can be used. My instinctive reaction before I read the article was to expect not to like it (except that there was something promising about the tone of his email), but I actually found myself liking it rather a lot, and have meant for some time to mention it.
His basic idea is that there are certain problems that are not phrased as maths problems, that are engaging to just about anyone, and that gently force you (if that’s not too oxymoronic a way of putting it) to think mathematically. I started this post with an example of my own, but it is very much inspired by the kinds of examples he gives.
Returning briefly to my example, let me say slightly more about why it might cause one to think mathematically, since it may not be obvious (though to most mathematicians I think it would be). I think one has to start with some non-mathematical thoughts, just to understand better what the properties would be that one would look for in a good queueing system. For instance, it won’t do to say that whoever is going to take the least time should go next, since then somebody with a big basket could end up never getting served. Perhaps some principle should apply that said that the time you wait should be comparable to the time you will take. But that cannot always apply, since someone with a huge basket will eventually have to be served, and if there is a constant stream of people with single items, then some of them are going to have to wait a long time. So perhaps the system should be that the person who has the greatest time-waited-to-time-needed ratio is the next person to be served. But what would the effect of that be in various situations? Would it do what one wanted? We have now got to the stage where we have a mixture of straight mathematical questions and more nebulous questions about fairness, what would irritate people, etc.
I’m not saying that the usual more formal style of teaching things like algebraic manipulations should be swept away — far from it — but I do think that Joseph Malkevitch’s idea could, in the hands of a good teacher, be a wonderful supplement to a traditional mathematics course, and it shows up the poverty of imagination of those who devised the use-of-mathematics syllabus that was in the news a few months ago.
It would be interesting to try to come up with a list of real-world problems of this kind that forced one to come to grips with specific mathematical techniques, such as matrix multiplication or solving quadratic equations. It’s important that the problems shouldn’t be stupidly artificial: e.g. you’re not allowed to say, “I have a square piece of paper, and I notice to my surprise that the sum of its area and eleven times its side length, when measured in centimetres squared and centimetres, comes to precisely 24. How long is each side?” The problems have to be engaging before they are recognised as mathematical.
Gowers's Weblog 
April 2, 2010 at 1:48 pm |
This queue problem is one I have run up against in my programming work with regard to file locking algorithms inside the Unix kernel. You can ask for a read lock or a write lock on a section of a file and the system either blocks you until it is available or it grants you access. A read lock is blocked only if someone has a write lock on the section you want to read lock. A write lock is blocked if someone has any kind of lock on the section you want to write lock. Read locks are not blocked by other read locks. The analogy to the store queue problem is that the read locks are like the person w/ only 1 or 2 items. The write locks are like the person w/ lots of items. Most Unix kernels use the following algorithm: if you want a write lock you have to wait until there are no locks on the section you want to write lock; if you want a read lock you have to wait until the current write lock is released. The problem with this algorithm is just as you described in your post: it can happen that someone wanting a write lock never gets served. What the user experiences is a program that stops responding to them — it looks to them as if the computer has frozen up on them. What we did to overcome this is to basically put in a rule that says: you can only have so many read lock requests per second and if you cross that threshhold any further read locks are forced to sleep for a second. Back to the store queue, this would mean that after allowing so many folks to jump the queue in say 1 minute there could be no more jumping the queue for 1 minute. Not sure if that would satisfy everyone but it seemed to add a dose of fairness and allows the customer with large items at the head of the queue a chance to get served.
April 2, 2010 at 2:48 pm |
Terry “buzzed” the following comment on gmail a few weeks back, which I discussed with my calculus students (I showed them the video below as they were settling into the lecture hall). I am taking the liberty to just copy Terry’s post here:
>>>
Suppose one needs to accomplish n tasks. These tasks can be done in any order, but each require a unit of time to perform. Also, each task i has an independent failure probability p_i, and if any one of the tasks fail, one has to immediately start over and do all the tasks again. What is the optimal strategy to minimise the amount of time required to accomplish all n tasks?
It is intuitively plausible (and a good exercise to rigorously show) that the optimal strategy is to arrange the tasks in decreasing order of failure, i.e. to do the most risky task first. This is a typical example of a rearrangement inequality, of which Chebyshev’s sum inequality is perhaps the most well-known.
This inequality was used when creating the following Rube Goldberg video below (which required 60 takes over 2 days – but most takes failed after just 30 seconds). [Via Jason Newquist.]
>>>
Admittedly this was completely off-topic for a calculus class, but my philosophy these days is that it matters fairly little what I actually teach, as long as the students leave my class thinking that maths is both intriguing and potentially useful.
April 6, 2010 at 8:37 pm
There is a variation of the problem you raise that a colleague and I have been working on (and only partially solved):
Suppose you have 2 tasks for the performance of which a machine takes times A and B (where B > A) to perform. The machine is subject to random breakdowns; the time between breakdowns is governed by a distribution function F(x). If the machine breaks down in the middle of a task, the machine is returned to as-good-as-new condition in a fixed amount of time T and the interrupted task has to be restarted. Which sequence, AB or BA, minimizes the expected time taken by the machine to successfully complete both tasks?
An interesting variation is when the breakdowns are generated by a non-homogeneous Poisson process.
April 2, 2010 at 3:29 pm |
The multiple server problem is common in supermarkets. There are usually several tills and a small queue forms ahead of each, with the load balancing done by people choosing which queue to join. It may be more efficient to have a single queue feeding all of them, but it seems to be against human nature to do things that way.
April 2, 2010 at 7:55 pm
If I recall correctly, you can change “may be” to “is”: it has been proven that single queues are “optimal”.
By the way, queues at fast food restaurants (for example) often fall into the one-queue-serves-all category. Makes sense, I guess, since minimizing service times is quite important to the business model of such establishments.
November 4, 2012 at 12:01 pm
In response to Greg: single queues may be ‘optimal’, but perhaps not from a customer service point of view:
In a multiple queue situation… if a customer has a strong objection to queueing then they can expertly choose a queue to minimise their queueing time – probably managing to decrease their time compared to the ‘optimal’ case (to the cost of other customers who don’t express such a strong preference) or, at least gaining the illusion of choice.
April 2, 2010 at 3:45 pm |
I often find (sadly, I’m not making this up) that when I sit into the car the gas tank shows empty. That is, there is so little gasoline, that I don’t know how much there is. This requires a very conservative drive to the gas station, and it is very frustrating to have to come to a dead stop at a traffic light at an otherwise empty intersection (being a mathematician, I rarely need to drive during rush periods). So the question is, when I round a corner and see a light, how should I manage my speed to use as little gasoline as possible?
April 2, 2010 at 3:54 pm |
If you have trouble with the link above in looking at my article here is a link for it in pdf form:
Click to access public-perceptions_Malkevitch.pdf
April 2, 2010 at 4:54 pm |
The airport puzzle I posted on my blog at
was remarkably popular (my second most popular post, in fact), and broadly fits your criteria.
The most popular post ever (by a wide margin) was the blue-eyed islanders puzzle,
but I think one can safely classify that one as “artificial”.
April 2, 2010 at 5:22 pm |
Dan Meyer has written extensively about this kind of problem, and even has a grocery queue one:
The idea is to have a problem that anyone can use their mathematical intuition on, and to have the students decide themselves what mathematical framework is needed to solve the problem.
April 2, 2010 at 10:30 pm |
One of the challenges is that the teacher has to have a clear enough grasp of the mathematics involved to explain it to pupils who may be confused – and I think that cannot be taken for granted.
April 3, 2010 at 10:40 am
Unfortunately, it can’t be taken for granted with a traditional mathematics syllabus either …
April 4, 2010 at 9:11 am |
eh so they sell chemicals in drugstores?
April 4, 2010 at 6:18 pm |
[…] Use of mathematics II « Gowers's Weblog […]
April 4, 2010 at 9:41 pm |
Good post.
As for the example, it is a particular problem at train stations. I remember once the person in front of my taking 40 minutes once, and then I only took about 3 minutes myself. Very irritating.
Actually the airport problem by Tao is nice because people disagreed about the solution a lot (although I think this is by interpreting the question in different ways).
April 4, 2010 at 10:52 pm |
I was once in a government office where requests were processed using a stack system rather than a queue system. As a habitual latecomer, this suited me just fine, but I imagine some of the others might have been a little peeved.
April 6, 2010 at 7:29 am |
Why would a shopkeeper with only one till want a system to allow customers to jump the queue (for whatever reason)? He should rather be concerned with his profit and as long as people remain in the queue and complain instead of leaving the shop he is doing alright. On the contrary, he might fear people to leave his shop because of being cheated by people who jump the queue.
That seems more a problem on conventions, emotions, fairness, perception aso. than a mathematical problem.
April 6, 2010 at 9:45 am |
Uwe, a shopkeeper with a “mathematically ideal” queue-jump system could boast fairness and efficiency, attracting more customers. Just a thought to keep the problem motivated. I think it’s interesting on its own.
April 9, 2010 at 4:56 am |
My take on the queue question is like this:
We have to note that the store keeper has no interest in serving you first, neither does anyone else.
1) Quantify the problem. People value their time differently, and we *may* use money as a proxy for the value people place on their time.
2) Figure out the best way for people who want to jump the queue to be able to compensate those in front of them. This is a operational / behavioural problem.
3) Figure out the optimal amount those who jump the queue should pay, given some constraints on how much would actually work in real life.
IMHO, this problem can be more readily classified as a problem in economics.
Economic theory would suggest that prices of “complex” items that take longer to scan, process etc, would already incorporate these additional costs. If this is not so, and the market doesn’t price that in, then we have to have someone step in to correct this mis-pricing. However, I don’t think this is that serious a problem, and society has invented a simpler solution long ago: politely asking if you may go first.
Great post on the teaching of mathematics, btw.
April 9, 2010 at 8:58 am
I take issue with your very first remark. Imagine the following extreme case. In the grocery shop there are regularly people who buy a lot and therefore take a long time in the queue — enough that if you want just a pint of milk there is a significant chance that you’ll take quite a long time buying it. And imagine that just next door there is another shop of a very different kind that happens to sell milk, though at a slightly higher price. If you knew that the keeper of the first shop allowed people to jump the queue if it was obvious that they would take only a few seconds, then you would be more inclined to go there, which would be in the interests of that shop, as long as they didn’t overdo it and put off their customers who bought a lot. So there are at least some circumstances where it could be in the interests of the shop to allow people to jump the queue.
April 9, 2010 at 9:36 am
Your learned objection makes sense. I should have mentioned that I assumed that there was only one store. Just like to make a few points for us to consider:
Assuming perfect competition and taking the analysis further in this two grocery store world, we may assume that the other store which sells milk at a higher price is able to do so since people are more inclined to buy from him (the price reflects convenience for shoppers).
Once the first store starts allowing customers to jump the queue, we can intuitively think of two consequences
1) big buyers are put off, translating to lower prices that the store may charge for the items they buy
2) the other store reduces its prices (whereas previously he could only charge higher prices because he was selling convenience in addition to milk)
As the other store reduces its milk prices (possibly to equality), allowing queue jumpers to jump for free would impose additional costs on existing “big” buyers. We cannot assume that this cost is negligible, since this cost is already quantified in the difference in milk prices (our assumption earlier). The key insight is that someone has to bear to cost of the queue inefficiency, and allowing queue jumpers merely transfers this cost to other people.
Store owners may foresee this and not allow queue jumping (which is the case in real life). A possible separating equilibrium could involve big customers shopping at the first store and smaller milk buyers shopping at the other store.
One theoretical solution would be for queue jumpers who want to jump the queue to compensate those in front. However this only works if they can figure out exactly how much they would have to pay beforehand. This does not work in real life. They then base their decision on whether the cost of waiting is more than the cost of paying off everyone in front. In a queue of n length, I’m not sure if we start from the end or from the start for this to be optimal. I would say from the start. What do you guys think?
April 9, 2010 at 9:53 am
I don’t think the biggest problem with such a system is that it would scare off customers who buy a lot, but that it would discourage the customers that are already in the shop from buying more. Today, you often buy things you don’t really need, or things you could have bought later somewhere else. But if you would have to wait a minute longer, (or worse: Have a 20% chance that you would have to wait 5 minutes longer) if you bought a few extra items, you probably wouldn’t. And the shop earns more and spent less extra time on a customer who buy a few things extra, than on a customer that only buy a pint of milk.
April 10, 2010 at 11:50 pm |
I agree entirely with Joseph Malkevitch; that’s how I organise my own teaching. Our brain evolved to deal with stories, and people can solve many problems better if they are put into some kind of social context. This applies in mathematics too: people are lousy at conditional probability, unless it refers to social problems such as detecting cheating – when they suddenly become rather good. The Wason test established this back in the 1960s.
How much more is there? This could be a research problem for maths teachers. The psychologists have built out from Wason’s work in other directions; for example, it’s one of the results often cited by evolutionary psychologists such as Tooby and Cosmides. But there may be a serious maths direction too!
April 12, 2010 at 11:45 am |
Undoubtedly people are aware of this but “Feynman’s tips on physics”, a (small) problem-solving companion to Feynman Lectures on Physics vol.1, is extremely good at communicating the use of mathematics (low-level) in thinking about the real world. Perhaps the material is a bit more mathematical (eg algebraic manipulations) than what was typically intended in this post (also a interest for physics is more or less required)
April 14, 2010 at 5:33 pm |
http://en.wikipedia.org/wiki/Quality_of_service
There are numerous existing QoS implementations that try to address this exact problem in a networking context.
How do you prevent queue starvation and apply proper prioritization when each packet ‘thinks’ that their payload is the most important?
All packets, er, shoppers would have to subject themselves to a ‘queue marshal’. Either a person or robot that ‘pre-evaluated’ all shoppers, then directed them to the proper queue based on content, urgency, complexity, shopping club membership, time of day, perishability of merchandise, etc.
Would simply having IceCream in your cart allow you to jump the entire line?
April 16, 2010 at 10:11 am |
I was at my local grocery store today and I only had a bottle of juice whereas the lady in front of me had a shopping trolley full of groceries.
She waved me ahead of her and I smiled and told her thank you. 🙂
Mathematically, I suppose I would change my approach to thinking about this problem in the following way.
Instead of having a ‘queue-marshall’ robot-type system that evaluates every person and places them in the correct order, we simply let the person further ahead in the line choose whether to let the person behind them move up in the queue.
People with a lot of other shoppers in front of them would be less inclined to let people ahead, or those that have waited a long time.
And people with big loads who have not been waiting long would be inclined to let people with less ahead of them.
(Given some reasonable expression of the problem, which is sadly beyond me as a biology student)
April 18, 2010 at 8:05 am |
Hi Tim,
Nice post. Two comments:
First, these questions are not typical questions in pure mathematics.
Second, the point that mathematics is connected to the everyday life should not be taken to extreme.
In the following I will try to explain these two points.
I think that many of these kind of questions are not, strictly speaking, pure math questions, but rather question from social sciences, computer science, and engineering. (I personally prefer CS to pure Math exactly because of this, i.e. it is much more connected to the everyday experience of human beings.) Some parts of applied Mathematics are connected to physics and other areas, but a pure mathematician, in my humble opinion, does something completely different. Maybe the original question starts with some connections to the daily life, but when it becomes a theory, the questions turn to things that no one can connect them easily with where came from. As an example, just look at the typical papers in combinatorics (, which is kind of famous as an area that solves questions they invent). Just to clarify, I am not saying this is bad, our ability in predicting which current topic will become a more useful theory in future is very limited so this freedom in pursue of pure theoretical questions is completely justified in my opinion (although I should say that I think some do misuse this freedom.)
Lets return to your question about how to assign resources. I don’t know any pure mathematical paper about this, but there are tones of papers in CS (scheduling, algorithmic game theory, …) and Economics on this.
I think that a person who is not ready to spend her life in pursue of these kind of pure theoretical questions (as a kind of search for truth in the Platonic world of mathematics) would suffer as a pure Mathematician; using applications and questions from daily life to interest young people in Mathematics is good, but it should not go as far as giving them the feeling that this is what pure Mathematics is about.
May 25, 2010 at 12:26 pm |
Have you ever read a book that really changed the way you look at things? What was the book?
June 9, 2010 at 1:14 pm |
I do not like this kind of “real-life problem”, because it presupposes a lot of things.
Firstly, I do not agree that it is obvious that the person with just one item should have a right to skip the queue. People who buy their needs in doses of single items create much more waiting time for the other clients and work for the cashiers, and generate less revenue for the shop, not to mention that the people with the many items are usually parents who normally have less time than the single buyer picking up a pre-cooked meal. If a teacher had forced me to model according to silent assumptions on societal goals that I did not share, my resistance would have been quite great. (Of course, the same would be true for a model which “naturally” privileged parents without discussion.)
Secondly, it supposes that people react rationally. I suggest the book “Predictably irrational” by Dan Ariely on this topic.
Example from the book: In an Israeli pre-school children were sometimes picked up late, so they introduced a token late fee. Result: Parents came late more often, because now they were paying it, so it was socially ok. When they cancelled the late fee, people continued to come late at the higher level.
Mathematical models for human interaction are rarely based on hard data on actual behaviour, but on the cute assumption that people have fixed money values attached to everything (their time, pain, food) and rationally calculate the optimum. Since most humans have an intuitive understanding of human interaction they come away with the impression that “mathematics does not work”, even though, it is the rational model that does not work, but somehow I do not expect the curriculum designers to do better than current average “economics experts”.
August 13, 2010 at 6:20 pm |
This problem is called scheduling and is treated in numerous application domain, some with math flavor, some with engineering. You might want to have a look at this.
Click to access recurrent-scheduling.pdf
September 20, 2010 at 10:40 pm |
One of the greatest ways to develop mathematical and physical intuition is to recognize symmetries, and I think that this could be started very early in a child’s education.
Since combinatorics and discrete problems are good to work through case-by-case, including a healthy introduction to symmetry arguments would be great to reduce the number of cases in problems. These could be started with obvious questions like why things balance, and move on to tilings, and then to permutations. The final algebraic manipulations might be too tough for many early students, but relating good examples of symmetry back into commutativity would be a huge step foreward.
September 20, 2010 at 11:03 pm |
I recently thought of an issue that I think would be a good one for engaging people and getting them to think mathematically. It’s a question that is of considerable political importance in countries like Britain with a state health system. We have an organization called NICE (National Institute for Health and Clinical Excellence) that decides whether to approve new drugs and whether the National Health Service should pay for them. The question is, how should such decisions be made? More generally, given that the NHS has finite resources, and more importantly has not enough money to give the best possible treatment for every single disease, how should these resources be spent? Or rather, how should the decisions be made?
This question splits into various parts, not all of them mathematical. For instance, the question of whether the life of a newborn is more worth saving than the life of a seventy-year-old is a difficult philosophical question. But one could eventually reach some notion of a utility function and argue that all marginal utilities should be the same. And one could discuss the question of whether there is any hope of using statistical methods to estimate the utility functions. And so on. (In general, there are many real-world problems that naturally lead to optimization problems in mathematics, which in turn provide a great motivation for calculus.)
June 8, 2012 at 4:53 pm |
[…] by Malkevitch’s article, I decided to write a second post, in which I was more positive about the idea of teaching people how to use mathematics. I gave an […]
June 13, 2012 at 1:21 am |
I think questions about the political decisions of the day are fairly fascinating. Especially when it comes to questions of what’s good for the individual/what’s good for society at large.
A recent example from the United States: discussion of health care policy. Everybody wants affordable health insurance coverage, but relatively few people have seriously thought about the link between enforcing a large pool of insured people and the feasibility of requiring insurers to cover all applicants. The overwhelming framework for debate is from the viewpoint of the individual.
June 13, 2012 at 12:24 pm |
I think that the queue-jumping problem in a grocery with one till is a bad example. It ignores basic psychology and it ignores a lot of other issues.
Basic psychology:
Humans value fairness in social interaction much more highly than the value time and money. People will go to great financial, temporal and emotional expense to punish someone who they perceive as unfair. So, the idea that it is enough to optimise for time and money without looking into behavioural psychology and local customs is naive.
This is different with other superficially similar problems (like multiple queues) who don’t have this problem that someone actually jumps ahead.
If I buy a lot, I might let people with few things jump ahead, but I will most certainly not do that if they think that they are entitled to it and jump first, ask second. I don’t think that I am alone with this approach.
Other issues:
It is not evident at all that someone who just buys milk *should* jump ahead in a system that optimises ressources for everyone. Not only is he generating less revenue than other customers, he is wasting everyone’s ressources: He is using up the time and place in the shop and his own time in a much more inefficient way than the customers who buy their groceries in one go instead of ten.
It’s hard to see why there is a general interest in encouraging inefficient or forgetful shopping habits by making the waiting time longer for the more efficient customers.
It’s strange to accept that buying 10 toilet paper packages will be cheaper than 10 times one, but to expect that buying just one should give you a shorter waiting time.
June 21, 2012 at 12:09 am
SMY, you make a good point about the person who is forgetful and is in the shop wasting people’s time buying a single bottle of milk. But this is an extreme case, and in the general optimisation question we also want to worry about the people in the middle, buying closer to ‘average’ amounts.
For example, suppose the shop is a fruit shop and therefore anything you buy there lasts only a week. So even if everybody were well-organised and bought all the fruit they need for a week, there would still be those who are single and therefore buying apples for one, whereas a family-man might be buying bananas for six.
Should we punish the single person? Seems unfair.
Also, the question wasn’t ruling out a notion of memory. So maybe these one-plum time-wasters can skip the queue the first time, but the more often they buy small amounts, then the less queue-skipping privileges they get.
That’s what I like about these real-world questions – not constrained by a mathematical model (i.e. “optimise this function”) you can think what other devices (in my idea, memory) you can use to solve the problem. It encourages creativity.
June 21, 2012 at 8:07 am |
The “nebulous component” is what many call a “policy”. So, the exercise could involve policy-making, and methods/algorithms that best fit some policy. I heard you on the BBC radio program where they ask one guest to describe a good idea in one minute. You’re idea was centered on debating on ideas in school. Public policy-making should, I think, involve debate and respectful disagreements. Can we easily get school students interested in queueing “theory”? Maybe. As access to powerful computing devices beacomes easier and cheaper, I think it gives more choices of “best curriculum” in schools. But how much and how to use computers in maths classes isn’t clear.
June 28, 2013 at 7:32 pm |
Reblogged this on Singapore Maths Tuition.