## Thursday, January 18, 2007

### Doing Lines, Part 2

A couple of weeks ago, I promised a couple of new ideas for increasing the blog’s level of activity. Here is one of them: more half-baked posts! This post’s topic is one I’ve been wrestling with for a couple of days, and it’s turned out to be surprisingly difficult to wrap my head around. I’m not sure at all I’ve reached the right conclusion, but I’m posting it anyway to see if my readers (especially the mathematically and economically inclined) can confirm or correct my thinking.

As I stood in line to buy popcorn at the movie theater on Saturday, I noticed that the young couple in front of me had split between two lines: the girl stood in my line, the boy in the next line over. When it became clear that the boy’s line was moving faster, she joined him. This is a strategy that I often use myself when I have a companion. I have a vague impression, however, that there’s a mild social stigma against it. No one will actually call you out for it, but they might give you the stink-eye. When I do it, I generally try to be subtle – no words, just gestures.

But as I stood in line Saturday, I began to think the stigma is unjustified. The line-splitting strategy does not just help those who employ it; it also performs a useful social service. The line-splitters improve the efficiency of the system by allocating more customers to the faster checkers, thereby lowering the average waiting time. They also tend to equalize the waiting time across lines, much as they would if they knew in advance which checker was fastest and simply chose that line – yet the effect occurs without their actually possessing such knowledge.

Or at least, that was my logic while standing in line. I later formalized my logic like so. Suppose there is one fast lane and one slow lane. The lines are currently equal in length because customers don’t know which lane is faster. Just arriving at the lines is one couple (C), followed by two singles (S1 and S2). Assume the singles will not switch lines after joining, perhaps because new customers fill in behind them. Are S1 and S2 better off when splitting is allowed or banned? The key insight is that regardless of the policy, someone, either S1 or S2, will have to wait behind C to get served. If the policy allows splitting, C will always end up getting served in the fast lane, so either S1 or S2 (whoever joined the fast lane) will have to wait through one more fast transaction. If the policy bans splitting, then about half the time C will choose the fast lane by pure luck, and the result be just as if they had split between lines. But the rest of the time C will unluckily choose the slow lane, and that means either S1 or S2 (whoever joined the slow lane) will have to wait through one more slow transaction.

More simply: Someone has to wait for the couple to get served. But how much time it takes for them to get served depends on where they get served, and splitting assures that they get served in the fast lane. Therefore the expected waiting time for whoever’s behind them goes down.

Now, however, I think this logic is incomplete. Why? Because it doesn’t extend easily to the case in which lots more customers fill in the lines behind C, S1, and S2. If the new arrivals simply filled in the lines in equal numbers, then the analysis would clearly apply. In fact, it would be strengthened, because more people would share in the benefit of assuring the couple gets served in the faster lane. But if one lane is faster than the other, then it will get shorter more quickly, and thus more new arrivals will join that lane (without even knowing that it’s faster). That means a larger number of people will end up waiting behind the couple in the fast lane, while a smaller number will benefit from not having to wait behind the couple in the slow lane. It turns out that this effect cancels out the efficiency gain I showed above. For instance, if the fast line is twice as fast, it will serve twice as many customers. Moving a couple from the slow lane to the fast lane will save each slow-lane customer twice as much time as each fast-lane customer loses (this is why it appeared, in the two-singles case above, that switching allowed an overall gain in efficiency). But twice as many fast-lane customers suffer the loss, so the scale balances.

And now I may have an explanation for the taboo. Line-splitting, while having no efficiency effect, does have a distributional impact. The couple assures itself of getting served in the fast lane. As the single customers fill in the lines behind, they will be just slightly more likely to end up in the slow lane than they would have otherwise, because that’s necessary to balance the ratios. So the couple’s gain comes at the singles’ expense, although on average waiting time does not change.

Then again... Well, let me stop here. I think there’s still a flaw in my analysis, but I can’t quite put a finger on it, so I’ll leave that part to you. Bonus points if you see the analogy with insider trading.

Lauren S said...

Dont the people behind split C also gain when one moves out of their line to join with the other. Their line time is shorted from what it was when part of C were infront of them?

Glen Whitman said...

Lauren -- yes, but that's actually already included in the analysis. Moving C from the slow lane to the fast lane saves time for whichever single is in the slow lane (say, S1) and loses time for whichever single is in the fast lane (S2). You are referring to S1. The reason the overall effect is a reduction in waiting time is that it's better to have a short delay to S2 than a longer delay to S1.

Also, remember that to be accurate, we have to measure gains and losses relative to the other regime (no splitting allowed), not relative to the situation after splitting but before rejoining.

Kevin B. O'Reilly said...

Hmm ... this post seems to be *about* something. What happened to all those great posts about what you were or weren't goin to post about? Those were great!

Anonymous said...

Neal says: I think the slight stigma might be because of the uneasy feeling people in line get that maybe the person who just joined you is not really an "item" with you, and that it's like you just inviting your buddies to join you in line and cut in front of the others. Of course, it makes no difference if you're going to buy the same amount of refreshments or tickets in any case, and people might keep their mouth shut because they realize that. But they have to look at you a bit to figure out if you're really a couple or a family, or just two friends who happened to see each other at the theatre, or maybe two platonic friends who are going to see the movie together, but in that case, hey? Why does one get to let the other cut in? Well, I guess I'd buy my friend's refreshments, too, if I were out with a friend... But still, only one of them had better pay for the whole order. If I see them placing separate orders, I'm gonna be pissed, man!

Gil said...

Glen, I think you're confused.

When the couple is getting served (and thereby making people wait), there will be the same number of people behind them whether they are in the fast lane or the slow lane (because new people will join the currently-shorter line).

Yes, more of them will be new arrivals if they're in the faster lane, but why should you care more about new arrivals than "old" arrivals? It's the same number of people.

I think your original analysis is correct. Splitting will not only save the couple time, but it will reduce the overall expected wait time for others as well.

I think the stigma is just because of envy (or stupidity).

Gil said...

And another thing...

If it were true that there were more people in the faster line, by the same factor as the line is faster, then the splitting would be neither a benefit nor a cost to the overall expected wait.

And, if the line lengths differed by an even greater factor than the speed advantage, it wouldn't just be an indictment of the splitters, but against everybody who got into the faster line (they're causing more wait time for others). And, they'd be stupid because they'd have to wait longer than the people in the slow line.

But, in real life, I don't think everybody joining a line knows how much faster one is than another. Most people will get into the shorter line, and will be unlikely to switch once they've committed.

The best system is when everybody stands in one line and gets served as soon as a new spot opens for service. Then, everybody takes advantage of the faster servers equally, and nobody gets stuck waiting for the slow ones.

Glen Whitman said...

"When the couple is getting served (and thereby making people wait), there will be the same number of people behind them whether they are in the fast lane or the slow lane (because new people will join the currently-shorter line)."

There will be the same number of people visibly standing in each line. But there will be more total people served in the fast lane, because that lane gets filled in more quickly. All of them are affected by the addition of one more transaction in front of them.

"Yes, more of them will be new arrivals if they're in the faster lane, but why should you care more about new arrivals than "old" arrivals? It's the same number of people."

I don't care about them more, I'm counting them the same as anyone else.

"If it were true that there were more people in the faster line, by the same factor as the line is faster, then the splitting would be neither a benefit nor a cost to the overall expected wait."

Right, that's what I meant when I said there was no efficiency effect.

"And, if the line lengths differed by an even greater factor than the speed advantage, it wouldn't just be an indictment of the splitters, but against everybody who got into the faster line (they're causing more wait time for others)."

True, but we wouldn't expect that to happen. To have the line lengths differ by a greater factor than the speed difference, we'd need to have some people who deliberately got in the longer line even though they had no reason to think it's faster.

"But, in real life, I don't think everybody joining a line knows how much faster one is than another. Most people will get into the shorter line, and will be unlikely to switch once they've committed."

I agree, and those are the assumptions I used. The reason more people will get in the faster lane is because spaces open up there more quickly, so it is more often the shorter line.

"The best system is when everybody stands in one line and gets served as soon as a new spot opens for service. Then, everybody takes advantage of the faster servers equally, and nobody gets stuck waiting for the slow ones."

I agree, and it's a mystery to me why some establishments don't use that policy. Space constraints can matter; for instance, it might be hard to have all the carts lined up in a single grocery line. But a single line works just fine at a concession stand, so I'm baffled by the fact that some theaters don't use that system. Maybe having multiple lines makes it easier to track the productivity of workers and identify shirking?

Gil said...

Glen,

"There will be the same number of people visibly standing in each line. But there will be more total people served in the fast lane, because that lane gets filled in more quickly. All of them are affected by the addition of one more transaction in front of them."

It's irrelevant that the line fills more quickly. What counts is how many people you're delaying, and that number is the same. Don't confuse the rate with the quantity. I think you're letting the fact that people join the line more frequently make you believe that there are more people being delayed. There aren't. It's the same number of people as if you were delaying people in the other line. They've just spent less time in line.

Gil said...

And, I think modern Point-Of-Sale registers can generate good stats to let management know which servers are more efficient.

I wonder why more places don't use the single line, as well.

Perhaps they've found that many people are psychologically less likely to stand in a long line, even if their expected wait is shorter.

People are strange.

Gil—standing in the faster line delays more people, because it delays people who aren't there yet. Assume (for simplicity) that the lines never manage to actually go to zero, that there's always some finite queue in each line. Then if you add one person to the back of a line, he's going to delay the time for everyone else who gets in that line after he does (because if he hadn't gotten in line, the next person would have gotten served when he actually got served).

So if the fast line moves twice as fast, it will over the course of the day serve twice as many additional people, each for half the length of time. Each future person to join the line loses half as much time, but there are twice as many of them. The fact that some people are already in line has no bearing on the efficiency results, except insofar as it guarantees that locally the queue is full.

I contend that there is no non-self-harming strategy that can reduce efficiency. No matter what line you get in, the future people who arrive after you will move into lines so that service happens at the same rate. (You can, of course, reduce efficiency by doing things like being deliberately slow, but that's not really what we're talking about). The only effects you can have are distributional, and that's what cutting in line—of all sorts of different forms, including this one—causes. The couple decreases its expected wait time, and since total expected wait time is constant, it must be decreasing someone else's (or many someones'). Hence the hostility.

Ran said...

You seem to be assuming that the slowness of a line is solely due to the inefficiency of the worker manning it; but it seems to me to have more to do with the indecisiveness and gluttony of the customers in the line. This completely changes the analysis, as no one except the couple benefits from the couple's identification of the faster line (since the couple doesn't take less time when it's in the faster line, and the line won't necessarily remain faster anyway).

Regardless, I think the taboo is because the split-up-and-reunite approach is an attempt to game an established social system that everyone accepts even though no one likes waiting. Keep in mind that even if the couple is somehow producing a net efficiency benefit to the rest of society, that's not the couple's goal; selfishness is nearly always taboo, even when it's not actually at others' expense.

Gil said...

That's a good explanation, but I don't buy it.

I don't think that if I was in a line then, even if it never empties, everyone who gets in that line later on will face a line with one more person in it because of me.

I think that some time shortly after I got in line somebody who would otherwise have joined my line will join the other one because I made my line a little longer.

That will cancel out my effect on the line.

Gil, it'll remove the effect of you being in that line only by transferring it to some other line. There's still a line with one more person in it, it's just a different one. If we assume that your line moves twice as fast as the other, on average out of every three people two get in your line and the third gets in the other. When you get in your line that means we'll get to the person who goes to the other line sooner, but then back to the person who gets in your line sooner as well.

Or, in other words—when you get in line it means that someone who would have gotten in your line gets into the other line instead. So when he gets into that line, doesn't he cause someone who would have gotten in that line to get in your line instead?

Glen Whitman said...

I just want to add that Gil and Jadagul's debate is doing a good job of showing why I found this topic surprisingly difficult.

Gil said...

Glen...true!

Ok, I'm still not happy with the original explanation, but now I think that regardless of which line I get in, I'll have the same effect on future expected wait times.

Because the system of lines processes n customers/hr and I'm adding 1 customer to the system. The waits will get distributed among the lines in proportion to their speed.

So, getting in the fast line (instead of a slower one) will help yourself, and not help or hurt the average customer that comes later.

I still don't see a reason for others to resent this. It's just as if a couple was a customer who somehow knew which line was faster.

In fact, if everybody had this knowledge it would equalize waits; line lengths would vary in proportion to their speed, and nobody would suffer because their line is slower.

So, the effect is not to reduce wait times, but it is to increase wait time equity (just like the single-line/multiple servers model).