We were on I-80 Eastbound somewhere around Nebraska. It had just gotten dark. The large semi-trucks on the road – usually the highway’s peaceful, lumbering mammoths – seemed to be turning aggressive.
I moved to the left lane, preparing to pass a slower semi truck looming ahead on my right. Suddenly the red and yellow lights of a large truck appeared in my rearview. The truck was approaching behind me, at high speed, and pressuring me into the right lane.
Not one for confrontation – and, let’s face it, this was a Ford Taurus – I acquiesced, laying on the brakes and ducking behind the first truck, almost as if for cover. The newcomer blew past both of us.
“Man,” I said to Josh, shaking my head. It was clear to us that the speeding truck’s behavior had been unfriendly. But it wasn’t quite clear why.
Driving across the country – Josh and I just made the trip from Portland to Baltimore – one has time to think about many things. The above event, along with countless others, got us pondering how highway passing works. Passing behavior on the interstate, in fact, follows predictable and consistent patterns, and these patterns are somewhat complex. We concocted a game-theoretic account of passing behavior.
We didn’t spend our time just reading Amadis of Gaul — an absolutely epic 14th-century chivalric romance of the sort mocked in Don Quixote — with surprisingly effectively imitated knightly voices, or singing in harmony obscure 1700s choral music by Johann Sebastian Bach (or paying attention to the road). We did much more. Let’s begin.
The anecdote given above will be quite illustrative. Let’s take a closer look. Suppose that among three drivers on a road, each has a natural speed, and that, further, the cars are situated in a cluster in such a way that the slowest resides in front and the fastest resides in back. We can depict the situation with the following diagram:
Here, we’ve labeled each car with the ordinal ranking of its desired, or natural, speed. For example, 3, the slowest driver, begins in front.
Each driver wishes to drive unencumbered by those slower drivers ahead of him, if they exist. What are the incentives facing each driver?
Car 3, slowest and in front, has no desire to leave the right lane. Between cars 2 and 1, though, an interesting conflict arises. 2 would like to pass 3, and 1 would like to pass 2. (To simplify notation, we’ll abbreviate these moves as 2 passes and 1 passes, respectively.) These desires conflict with each other, though, in the sense that neither can occur if the other does. Indeed, if 2 tries to pass, by moving into the left lane he blocks 1 from passing, and if 1 tries to pass, he does so at the expense of 2 passing.
Of course, either 1 or 2 can make a move at any time, assuming that no collision is possible. (I’ll leave aside details of the game implicit here between 1 and 2, which probably resembles chicken in one of its various forms.) This state is stable, though, in the sense that there exists a mutually recognized conflict of desires. (Otherwise I’ll call it free.) The state can only be overcome if one party transgresses and the other party yields.
Now let’s modify our game only a tiny bit, by shifting car 2 left. Consider the new diagram:
In this situation, no conflict exists. Indeed, car 3 doesn’t desire to pass anyone and car 1 can’t pass anyone; car 2, now at the head of the left file, can’t disrupt anyone’s desires. 2 can pass freely, and this state is free.
In this latter state, 2 passes at will, and ultimately drifts away ahead of the new cluster, which consists, now, of only 3 and 1. 1 can now pass 3, and eventually also 2, freely, and all three drivers soon become extricated with no conflict.
We’ll explore the game in more detail and generality below. I’ll briefly stop now, though, to hint at the solution to the question I posed at the beginning. Why was the truck’s behavior objectionable? Though both passing patterns — 1-pass-first and 2-pass-first — eventually separate the vehicles, the former occurs despite conflict and the latter occurs without it. The truck transgressed, and I yielded.
These two situations will form the the building blocks for our general game.
Imagine a cluster of n cars in a k-lane road. The goal of our game is for these cars to extricate themselves, or to separate themselves into an arrangement in which they’re naturally sorted by speed so that each driver can proceed unencumbered by slower drivers ahead. We’d also like for this to happen through free passes alone.
Let’s suppose, in fact, that the cars in a cluster are physically arranged in such a way that for each i = 1, …, n, the ith-fastest car is in the ith position (counting from the back). We also label the cars in such a way that for each i = 1, …, n, car i is the ith fastest. (The slowest car, n, is in front.) We now select k particular cars c1 < c2 < … < ck-1 < ck = n (the final car must be n) and partition the set of n total cars into k subsets in such a way that for each j = 1, …, k, the car cj is the foremost member in the jth subset. Finally, suppose that the cars are arranged in such a way that for each j = 1, …, k, the jth subset resides in the jth lane (counting from the left). Thus we achieve a cluster of cars in what we’ll call echelon formation. An example is illustrated in the following diagram:
I claim that this sort of cluster — consisting of cars in echelon formation — exhausts the library of possible road states that are interesting to us. Why? In short, this represents the most general situation involving cars whose desires to pass mutually influence each other.
I’ll argue now that we can reduce the general case to the echelon formation case.
It’s clear first that a given car desires to pass only cars which are slower than it. If a cluster of cars contains a pair of adjacent cars with the property that the frontmost car is the faster, then the backmost car will never pass the frontmost car. We might as well draw a virtual bar between these two cars and consider the cars in front of and behind this bar as, respectively, members of separate clusters. We then analyze these, say, virtual clusters separately. Of course, a car faster than both might pass the rearmost car. Then what? After passing the rearmost car, it will naturally transition from the rearmost virtual cluster to the foremost one. Further, in the course of this transition no passes will occur. Allowing that transitions from and to virtual clusters can occur, it suffices to understand passing behavior within a given one. Drawing bars as described, we find only virtual clusters in reverse-speed-sorted order.
Likewise, it suffices to consider virtual clusters in echelon formation. Suppose that in a cluster of cars in reverse-speed-sorted order, there exists a car in front of and to the left of another car. The rearmost among these two cars now has two options. (We always assume that no cars pass on the right!) On the one hand, it can shift left, reintroducing echelon formation and leaving us with nothing to argue. If it declines to shift left, on the other hand, then we can, as before, draw a virtual bar between this car and the car in front of it, and consider the cars ahead of and behind this bar as members, respectively, of separate virtual clusters. Why? Any car behind this rearmost car, observing that this rearmost car has declined to shift left, now understands that this car has no desire (or ability) to pass that car in front of it and to its left, and thus may pass it freely as if it were the frontmost car in its file (in a way, it is.). In short, the behavior of those cars including and behind our rearmost car is exactly as it would be were those cars the only cars on the road. Of course, as before, between passes, transitions between (virtual) clusters can occur; these themselves don’t involve passes. This isn’t a problem as we seek only to understand passing behavior. Drawing all such bars, we produce only echelon-formation clusters.
Transitions between clusters, again, do not involve passes. We must only stipulate, then, that virtual clusters in echelon formation may be modified occasionally by the augmentation of slow cars to the back or the removal of fast cars from the front. Thus it suffices to consider a single cluster in echelon formation. We should also remember that virtual clusters can separate physically once enough extrication has occurred. This, after all, is what happens when a single car becomes free!
Of course, once a pass has occurred, a cluster no longer maintains its reverse-sorted order. This is fine. We re-partition the cluster as appropriate, and begin analysis again (twice). Thus a description of echelon behavior alone is sufficient for a complete account of passing behavior.
When is a cluster in echelon formation locked up in stability? It depends on the particularities of the formation — or, that is, of the partition. Recall again the example diagram, reproduced here:
Between the jth and the j+1th files, we see a free situation: Because car cj+1 is the only car in its file, it does not desire to use the jth lane to pass — and car cj may pass at will. Between the j’th and the j’+1th files, on the other hand, the situation is stable. Cars cj’ and cj’+1 both fear passing the respective cars in front of them, because these two actions are mutually opposing. A pattern emerges:
Claim 1: Juncture stability condition. Consider a road state consisting of n cars in k lanes (assume n, k > 1) in echelon formation, partitioned along the representatives c1 < c2 < … < ck-1 < ck = n. For each j = 1, …, k-1, the juncture between cars cj and cj+1 is free if and only if cj+1 is the only car in its file — that is, if cj+1 = cj+1.
This merely summarizes observations we’ve already made. When any car is the lone car in its file, the foremost car in the file to the left of this car’s file can pass this car freely. If the car has cars in front of it, then those cars to its left cannot freely pass.
From this we deduce a description of optimal group play behavior. Individual optimal behavior is not especially interesting to us. In principle, a greedy fast car could simply pass everyone in front of it, squelching tension as it proceeded. But how can groups of cars operate to minimize tension-laden passes?
In fact, any cluster of cars can rearrange itself in such a way to completely extricate all cars with no tension. The idea is as follows (recall that we count lanes starting from the left):
Claim 2: Group play strategy. Consider a road state consisting of n cars in k lanes (assume n, k > 1) in echelon formation, partitioned along the representatives c1 < c2 < … < ck-1 < ck = n. To facilitate extrication, cars should operate by the following rules:
- Consider a subset consisting of consecutive representatives cj’ < cj’+1 < … < cj’’ (where j’ < j’’ are some numbers 1, …, k) with the property that for each i = j’, …, j’’-1, we have ci+1 = ci+1. (Such a subset could be said to be in pure echelon formation.) Any member ci of this subset, for i = j’, …, j’’-1, should pass at will.
- Let j be a lane containing more than one car, i.e., some number j such that cj-1 ≠ cj-1. Then cj-1 should yield to permit cj-1+1 to shift left into the j-1th lane.
Cars operating by these rules will extricate completely and freely.
In short, there are two rules: when in pure echelon formation, always pass; when on the other hand the file in front of you has multiple cars, let that file’s rearmost car move in front of you. These latter movements tend to either create or extend pure echelons. Cars leading the flank feel free to break away.
Note that the use of strict inequalities between the ci precludes the existence of empty lanes or degenerate partitions.
Cars shifting left who create pure echelons further ahead may do so at the expense of ones further back. Indeed, pure echelons away from the front of the cluster may come in and out of existence as cars shift left in a cascading manner. Precise behavior depends on whether cars tend to “shift first or pass first”, or whether, in other words, rule 1 or 2 among those above takes precedence. In the end, these are empirical questions which are not particularly important to us. At stake is merely the order in which the cars extricate.
These two rules lead to complete and tension-free extrications. Though a “proof” is quite unnecessary, I’ll make a few small observations to this effect. It’s clear that all passes condoned under these rules are indeed free. It suffices to show that the cluster will completely extricate. For this it suffices, by induction, to show that a single pass will be made. But after enough cars shift left, the rightmost car will be the only car in its file; when this happens, the foremost car in the second-to-rightmost lane (here we use k > 1) will pass it without hindrance.
It’s worthwhile to examine the special case of 2 lanes. In this case, all those cars in the right lane (except the first) will shift, in a one-by-one manner beginning from the back, into the left lane. Once the right lane consists only of a single car, the members of the left lane will, again in a one-by-one manner and now beginning from the front, pass the right-hand car and into freedom. The cluster of cars will, albeit after a series of future interactions each involving only two cars, extricate itself without confrontational passes.
If only it worked that way in real life!
By the time we realized all this, we were halfway through Iowa, and each a venti coffee deep. There was no one else on the road.