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!”