Date: Thu, 21 Jan 1999 15:27:18 -0700 (MST)
From: "Samuel B. Johnson" <sjohnson@mail.sjcsf.edu>
Subject: categories: Inquiry - Manhattan Street Problem

Inquiry to: categories list-serve subscribers
 
In the mid- to late 70s there were meetings at Columbia University in New
York of mathematicians interested in topos theory, which meetings I
attended as a student of Peter Freyd. 
 
At one such meeting, someone proposed and solved the following problem,
which I have since named The Manhattan Street Problem.  (Note: it was NOT
so named at the time.) 
 
    Consider a large number of commuters, all traveling from
    south to north along two parallel highways.  Connecting the
    two north-south highways are one (or more?) east-west linking
    streets, all of which are one way from west to east.  The
    speed at which a commuter moves along any highway or street
    is a function of the number of users on that (part of that)
    highway or street, e.g., as more commuters who are initially
    on the western of the two north-south highways choose to
    leave and go over to the eastern of the two north-south
    highways, the speed of traffic on the western highway
    increases and the speed on the eastern highway decreases. The
    functions relating speed to number of users are not
    (necessarily) the same for each highway or street.  (I think,
    however, that the most elegant solution would have a single
    function applicable to both highways and (all) street(s).)
    Each commuter chooses whether (and when, if there's more than
    one cross over street) to go over to the eastern highway in
    an attempt to minimize individual total travel time.
 
    Problem:  Specify the speed controlling function(s), the
    number of crossing east-west roads and, if necessary, the
    distances, e.g., distance between eastern and western
    highways as a fraction of total north-south distance, or
    distance between various east-west roads, again presumably as
    a fraction of total north-south distance, such that:  the
    system stabilizes, i.e., individual commuters cannot improve
    their time by changing their route, BUT the total travel time
    summed over all travelers is NOT a minimum.  Thus, if such a
    solution is found, an omniscient, big brother traffic
    controller, by (randomly?) requiring some commuters to take a
    route slower than what he/she would individually choose,
    could thereby decrease (minimize?) travel time (hence air
    pollution?) for the whole commuting community.
 
Plausibility argument that this might be possible:  That the
situation stabilizes seems intuitively plausible to me.  That the
stable situation might not minimize total travel time is
suggested by the following:  If the big brother traffic
controller moves an individual from a too heavily traveled
highway, the benefit flows to a large number of commuters left
behind on that highway, which flows faster, even though the moved
individual may be shunted over to a route slower for that
individual.
 
If anyone:  a) remembers who presented and solved this problem at
Columbia, or b) remembers the solution, or c) can point me toward
where this might be solved in the literature, or d) can provide
any other help, I would be extremely grateful.
 
Samuel Johnson  (sjohnson@mail.sjcsf.edu)
 
Postscript:  A solution would have (obvious?) implications for
those who have great faith in the general applicability of free
market mechanisms and Adam Smith's invisible hand for solving
problems or finding best strategies from a society's point of
view.