Living in a Nonlinear World

This past week there have been two big events marking milestones in the lives of major contributors to our understanding of nonlinear phenomena - one very sad and one happy.

I heard the sad news via a tweet by Professor Laura McLay @lauramclay - Professor Harold Kuhn of Princeton University passed away on July 2, 2014 at the age of 88.  The Nobel laureate Al Roth of Stanford wrote this tribute to this co-founder of nonlinear programming and brilliant game theorist, who, interestingly, was a mathematician but had an appointment in Princeton's Economics Department.

Photo above of Harold Kuhn, courtesy of Princeton University

Anyone working, on, researching, or learning about our nonlinear world is aware of the powerful tool of nonlinear programming and the renowned Kuhn-Tucker optimality conditions, now commonly referred to as the Karush-Kuhn-Tucker or KKT Theorem. Dick Cottle of Stanford wrote a wonderful history of these scientific discoveries which can be read here.

Although I never met Karush, Kuhn or Tucker, my first academic interview when I was finishing my PhD in Applied Math at Brown with a specialization in Operations Research, was at SUNY Stony Brook, and I was interviewed by Al Tucker's son, Al Tucker, Jr., so, of course, we talked about his father. Al Tucker passed away in 1995.

This very same week, on July 5, 2014 we celebrated the 90th birthday of Professor Martin Beckmann, the only surviving author of the classic 1956 book, Studies in the Economics of Transportation, who was on my doctoral dissertation committee at Brown University.

I wrote about Beckmann's milestone birthday on this blog and sent his a special card. More information on this classic, including a special festchrift I organized at a previous INFORMS conference in San Francisco can be viewed here.

 The photo above was taken of Beckmann and me at Northwestern University a few years ago.

The massive impact of this book, which formalized what we now commonly refer to as user-optimization and system-optimization to capture different behaviors on congested network systems, with a focus on urban transportation networks, was summarized in our paper, A Retrospective on Beckmann, McGuire and Winsten’s Studies in the Economics of Transportation  David E. Boyce, Hani S. Mahmassani, and Anna Nagurney,  Papers in Regional Science  84: (2005) pp 85-103.

In their book, on page 59, they stated:  “Demand refers to trips and capacity refers to flows on roads. The connecting link is found in the distribution of trips over the network according to the principle that traffic follows shortest routes in terms of average cost. The idea of equilibrium in a network can then be described as follows: ... the existing traffic conditions are such as to call forth the demand that will sustain the flows that create these conditions.” And, as we noted in the paper, That these authors  succeeded to formulate and extensively analyze a nonlinear optimization problem whose optimality conditions correspond to this statement (and related behavioral assumptions) was an enormous advance in the rigorous modeling of network traffic, a result never before achieved for urban traffic, and most unlikely for any complex system involving interactions of human behavior with technology. Moreover, they provided a parallel model and analysis for the case of cost-minimizing (now called system optimum) flows in a congested traffic network.

Boyce published an article in the journal Economics of Transportation last year: "Beckmann's transportation network equilibrium model: Its history and relationship to the Kuhn–Tucker conditions."

Below I depict congestion on a link where the travel time or cost is an increasing function of the flow.

 

Congestion is a huge problem in the US an beyond. As I noted in my TEDX talk at UMass last November:  Congestion costs continue to rise:  the cost of congestion has risen from $24 billion in 1982 to $121 billion in 2011 in the United States. The average commuter spent an extra 38 hours traveling in 2011, up from 16 hours in 1982. In areas with over 3 million persons, commuters experienced an average of 52 hours of delay in 2011. In 2011,  2.9 billion gallons of wasted fuel -- enough to fill 4 New Orleans Superdomes.
 
Congestion is neither a new phenomenon - it even occurred in ancient Roman times during which time of day chariot policies were used to ameliorate congestion.

Information on some of the most congested roads in the US is available here.

More data can be found in the always fascinating Texas Transportation Institute's Urban Mobility report.

Neither is congestion, and associated nonlinearities, limited to urban transportation systems, but they also arise in freight systems, electric power generation and distribution networks, and the Internet!

And, importantly, if the user travel cost on a link is fixed, then, both user-optimizing solutions coincide with system-optimizing ones, so the (in)famous Braess paradox cannot occur!
 
Many, many thanks to Kuhn, Tucker, Karush, and, of course, to Martin Beckmann for providing us with some of the tools to model and better understand our nonlinear world!

A Mathematician Who Never Had an Economics Course Shares the Nobel Prize in Economic Sciences

Being in Sweden is always special and never more so than when the Nobel prizes get announced.

Today, the Nobel prize in Economic Sciences was announced and the recipients are Alvin Roth of Harvard University, who is visiting at Stanford University (although the LA Times says that he actually has accepted a position at Stanford, his alma mater) , and Lloyd Shapley, who is a professor emeritus at UCLA.

We were waiting with bated breath for the announcement at 1PM today and it is great to have game theorists (again) be awarded the Nobel prize.

One of my favorite previous recipients is John Nash, whose work I cite in many of my papers on  oligopoly theory and competitive supply chains.

I found the following quote from Shapley, who learned that he and Roth had won the $1.2 million award from an Associated Press photographer and another journalist who went to his home in Los Angeles early Monday.,  interesting and it was published in the Boston Herald (which has Roth still at Harvard):

"I consider myself a mathematician and the award is for economics," Shapley told AP by telephone. "I never, never in my life took a course in economics."

Shapley did much of the theoretical work behind matching algorithms (from couples to kidneys and humans to other applications), whereas Roth is know for his empirical applications.

The late Elinor Ostrom, was the only female recipient of the Nobel prize in Economic Sciences.

She was a regular visitor to the University of Gothenburg, and according to my colleagues here, was working with one of them in the hospital before her death.