A little pre-exam reflection

Colliding Pedestrians' Puzzle

We’ve all been in that awkward position of walking towards a person coming in our direction, having to decide between keeping a steady course and deviating either left or right to avoid an uncomfortable collision or one of those dances. It happens over and over again. One should think that a street with a width of five meters should be able to accommodate two individuals with an average size of 60 centimetres, so that we might avoid this unpleasant decision-making that usually ends up in annoyance; “Why the hell did you also turn to that side?! I specifically swerved leftwards to make it easy for you.” For centuries pedestrians have been troubled by this puzzle: Why do oncoming persons find it so hard to “collectively agree” in the streets, thereby avoiding front-to-front crashes? Let’s put this Gordian Knot under the scope.

On the oceans and in the air, there are well-defined rules on which direction to take in the case of an oncoming vessel. Size (and thus navigability) of the vessel sometimes has an impact, at other times both units are simply “obliged to turn right” – a clause which usually resolves the whole issue. On the highways, vehicles on wheels will seldom have to play the “chicken’s game” by sticking to separated lanes, unambiguously associated with one driving direction. The costs involved in yielding airplanes, ships or cars the unwanted choice of deviation would simply be too great. From time to time motor driven vehicles do collide but mainly not due to an imprecise framework but due to human or mechanical error. That’s a whole different story.

Pedestrians, on the other hand, are not guided by some universally accepted rules for these situations. In a battle of wits we try to avoid making the same choice as the other party – the wrong one! It’s entirely psychological; we try to unravel the train of thought of our “competitor” by picking up on small facial gestures, gazes, hand movements, and simultaneously convey our own master plan. Because in this game, I win only when you win, and when we lose we always do so together. Essentially, the pedestrians are playing a cooperative game in which the preferred outcome is making strictly different choices. We can call it equilibrium when they succeed: Both are satisfied with the decision they made (that is, the path they took) given the decision of the other one. In other words, they would not strictly prefer to have deviated in light of the oncoming pedestrian’s final choice.

Back to the core – why do we so often find ourselves in an awkward dance with a stranger (no reference intended)? The intuitive thing to do approaching someone on a street is making a quick decision about your path. However, whenever both of you choose “the same path” problems arise. Soon enough, you will both catch up the signal from the other individual and most likely you will continue that path with slightly more determination. But alas, both will also catch up this signal, getting cold feet and opting for the other path (that will be swaying left for one, right for the other). Also this signal will be perceived and, most likely, both will miserably try to outsmart the other one by turning again. And before you know it you stand face to face with the opponent, wishing you had opted otherwise. Two losers – the least favoured outcome. Where is the flaw, the little misjudgement that leads to the inevitable collision? Answer: Letting your decision on whether and where to deviate be influenced by the decision of the other party. When both players follow this strategy we have an undetermined game in which there is no telling of the outcome. Sometimes we stray clear of the other, other times we don’t – governed as if by the flip of a coin.

Let’s be a tad more sophisticated. We consider two pedestrians, F and G, sauntering in opposite directions on a straight road of some positive length. There are no other objects or individuals on the road and no well-defined lanes which to follow. Both F and G have some aversion of colliding and strictly prefer be allowed to walk unobstructed to the far end of the street. At some point in time, these two pedestrians observe the other party and immediately start considering their strategy as to how to avoid collision. This contemplation can be modelled in terms of mathematics by saying that F and G are also the name of two functions, namely the final choice concerning which path to take for pedestrian F and G, respectively. Allowing only two alternative paths, left and right (luckily we are not so constrained in politics), each one would like to take the opposite path when they knew the other party’s choice. In mathematical terms, F is a “function of G” and G is a “function of F”, ergo F(G) and G(F). It simply means you care about the choice of the other, creating interdependency in the strategies. So far, so good! But what happens if we insert the expression for the G-function into the F-function? We get F(G(F)), which to many of you simply look comical and is far from illuminating. Follow me for a couple more steps. F(G(F)) tells us that F’s choice of path depends on which path G chooses, which in turn is a decision dependent on the choice of pedestrian F. And we can go further: F(G(F(G))). Naturally, because (like we said) F still cares about the choice of G. Moreover: F(G(F(G(F)))), reminding me of a Christopher Nolan film. What is going on with all these parentheses? The surprisingly simple explanation is this: Each pedestrian’s choice is a function of (or response to) the other pedestrian’s choice (or rather: his expected choice). But his choice again, is a response to the expected choice of the other. Basically, this is an unsolvable problem in mathematical sense: F and G are reciprocal functions and they yield no intelligible outcome. F(G(F(G(F…)))) indicates an endless series of “bluff and double bluff” – who has thought the furthest? If you want some more numerical meat on the bone, you can specify the F-function to be F(G) = –G and the G-function to be G(F) = –F if we remember to allow only two values for F and G, –1 (being the choice of going left, or “up” to remove the ambiguity) and 1 (being the choice of going right or “down”). When G has the value –1, pedestrian G has chosen to go “up” and the best response for F is to choose –1*(–1) = 1, that is going “down”. But since no-one can decide, neither theoretically nor in practice, we’re back at the flip of a coin and a occasional collision.

So what comes of our Gordian knot? Eureka, we simply define the F-function to be 1. Then G(F) will automatically be –1*(1) = –1, and we have reached equilibrium of our little game, meaning that the two are taking distinct paths. Put differently, if we manage not to let our decision on where to veer be affected by the choice of the oncoming guy, we always avoid disaster. We take a decision from the very beginning, say “up”, and we stick to this decision with the firmest confidence, like a cold mathematical truth, and ignore completely what the erratic other one might do. It’s a sure success – safer than the bank – but it requires some guts and a little confidence in the simplest of all mathematical functions: F = –1.

Or one can simply yell out “I’m choosing my left!”