First of all, a word of explanation about the title:

1. Decentralized – By this word, I mean the absence of an all wise and all knowing supreme being which governs everything that go around in an idealized world for the best of all possible purposes. In this real world, events take place via the interactions of individuals, organizations, and countries each pursuing their own agenda and interest.

2. Control and Optimization – By these two words which I use in the colloquial sense to mean that human civilization always strive for “improvement” though not always successfully. This is a fundamental desire.

#1 and #2 certainly reflect the situation in the real world. .

 

Now I want to explain conceptually why this is hard, very hard, to do. In the process I hope to explain using very simple terms as to the “what” and “why" that constitute an impossibility theorem.  In my earlier blogs you may have read my mention of the so-called “Witsenhausen Problem”. This is a problem made famous by Hans Witsenhausen, a Bell Laboratory researcher in 1968 to illustrate the difficulty with information and coordination (the issue of who know what when and dynamic team theory. If you google or bing it you will get over 1000 reference to this problem). It is a problem of the SIMPLEST kind with all the right mathematical assumptions such as linearity, convexity, Gaussian noise, etc. involving only two decision variables. You have a constant (which is a sample of a gaussian random variable) to eliminate or cancel. The first decision maker, DM1, knows exactly the value of this constant, but his action is costly. Thus, it costs something for him to eliminate the constant (reduce it to zero). The second decision maker, DM2,  who acts after the first decision maker incurs no cost to act, but he does not know what DM1 knows. He only has a noisy observation of the resultant value of the unknown (to him) constant value plus any effort on the part of DM1’s attempt to cancel this constant. Thus he cannot cancel what remains exactly if he uses the noisy observation. The un-canceled leftover will incur a cost. The problem is what should the two decision maker jointly do so that resultant performance (cost to cancel in part or in whole by DM1 plus the leftover un-canceled portion due to uncertainty and the action of DM2) is at a minimum . Note the problem will be trivial not even qualify to be an exercise in an undergraduate control/optimization course if the two decisions are under the control of one decision maker – the centralized case (we can even let the first decision’s information be noisy also. The optimal solution is well known to every student in such courses). But this simple change of different decision maker having different and non-inclusive information made all the difference. Witsnehausen did not solve the problem he thus posed. But showed a number of surprising things. Among them:

What everyone expect to be the answer – a linear proportional solution- is not optimal

A much better nonlinear solution, though still not optimal, exists. This is highly surprising at the time.

 

In the ensuing 40+ years (1968-2009), a large number of people, including myself spend enormous number of hours using rather advanced technical theory trying to advance the solution to this so-called W-problem resulting in many published papers on different aspects of this simplest problem. In 2002, my student and I finally published a numerical solution of the Witsenhausen problem with a conceptual explanation that captures the essence of the problem. We claimed that we have exhausted all the ideas associated this problem and any further improvement can only be numerical (for example using more significant number of digits in computation, or a better search algorithm). Since 2002, several other people have worked on this problem (including someone just last month) but no one has invalidated our claim. Thus, you can say that the last word probably has been said on it. But why such an apparently simple problem took 40+ years and many scholars’ time?

 

Now let me explain the essence of this simple problem in an even simpler way without any advanced mathematics. Once understood, readers will begin to appreciate why decentralized control and optimization (in plain language – coordinate actions to work for the common good)  is very hard in the best of circumstances. Once you add in human frailties, politics, and other vices, a perfect world is impossible for all practical purposes.

 

Think back to the W-problem.as described above. It is clear unilateral action by either decision maker (for DM1 to simply cancel out the constant regardless of the cost or for DM2 to treat the noisy observation as true value and cancel accordingly) is not going to be the best course of action. Thus, they need to cooperate and each does a bit of work. The expected linear solution simply does a proportional compromise which is better than unilateral action by either one. But you can do better. The following are clear:

For DM1 you wish to use as small an effort as possible in changing (canceling in whole or in part) the value of the constant since it is costly for him to act. If the constant is either one of two possible known values separated far apart comparing to the size of the noise, then canceling by the DM2 should be easy. Because even with noise, you can be very certain which one of the two values the constant has and cancel with no cost accordingly.

From these two considerations, a nonlinear scheme emerges. Let DM1 observe the constant exactly and then proceed to change (cancel) the value of the constant to either one of two pre-agreed-on positive or negative value, say +or – C. DM2 then observes with noise either plus or minus C and can be pretty certain even under noise which one it is and cancel it out completely. Now of course when the particular noise sample is very large, mistake in cancellation can still occur. Similarly, when the value of the constant is very different from + or – C, the cost of moving to these values can be high. But the probability of these rare event happening are very small. Thus, on expected value basis, this nonlinear scheme works better than any sort of compromise using linear proportional methods. In effect, DM1 is signaling to DM2 (Nobel economics prize 2002 to Michael Spence on market signaling is based on similar idea). Finally, once you can use one pair of pre-agreed-on values, there is nothing wrong and every thing to gain by considering more than one pair of pre-agree-on values. More values will enable DM1 to choose the nearest value in order to minimize the cost moving the value of the constant. However, more pre-agreed-on values will complicate the problem for the DM2. He will have more chance of making mistakes because of observation noise when trying to guess which one of the many possible values DM1 has move the constant value to. Thus, there is a limit and tradeoff on the number and value of these pre-agreed-on points. For any given numerical example, we can perform a brute force search to solve the problem which is still computational intensive but doable (Note 1). This was what we did in 2002. It took 30-40 years before we realized the simple insight in this paragraph .

 

Anyway, the above discussion points out the complexity of coordination even in the simplest problem between two decision makers. When you come to the real world where there are many interacting decision makers and vairables, much more complex dynamics and uncertainties, the resultant exponential growths adds MANY MORE ORDERS of difficulty and complexity.

Thus, the popular slogan of think globally and act locally is much easily said than done.

So far our discussion of complexity and difficulty is purely technical. We have not brought in other non-quantifiable and softer issues such as human frailty, emotion, nationalism, and politics that always intrude in the real world. What we generally do instead is iteratively tries to improve locally in the short term, and hope for the best globally and for the long term. You can also say that throughout history human beings by way of different types of government and systems try to solve or improve on the solution to this basically impossible dream. It is actually relatively amazing we do as well as we have done so far. But can our luck hold forever? Don’t you sometime wish for an all wise and benevolent dictator to decide everything?

 

 

(Note 1. Actually because of the quadratic nature of the formula used to measure cost, there is an additional bit of extra that can be squeezed out of the problem by introducing a very small perturbation on the various pre-agreed-on points. But this is conceptually a detail dependent on the particular criterion used and not central to the major points of the discussion. Mathematically, however, such issues confused the research in earlier years which emphasized analytics of rather than the physical insight of the problem as explained above)