A brief mention of "wicked" problems....

What is the computational structure of social change? Or social persistence, for that matter? These might seem like strange questions, mainly because they are not asked too often. True, people have tried to understand the phenomenon of social dynamics using a variety of techniques spanning from agent-based models to economic models and even discourse analysis. However, these approaches have not provided a predictive framework suitable for the onset and management of large-scale events that define social changes. These include disruptions and upheavels such as stock market crashes, ethnic conflicts, and disease outbreaks. Because their computational representations feature complexity beyond NP (non-polynomial) [1], they are called "wicked" problems [2].

Figure 1. Nested set of solution spaces for different degrees of problem hardness.

As a formal concept, wicked problems were first identified in late 1960s and early 1970s [3]. Wicked problems are highly complex and nonlinear, with dynamic, spatial, and parallel process components. Some components of these problems many not be predictable [4]. In fact, this may not be true of any single component. In the literature [5], there are four features that distinguish "wicked problems" from relatively easier ones (such as chess, network reconstruction, or pattern recognition):

Figure 2. Is this a wicked problem? Is this how it should be set up?

1) ill-defined problem space: In a recent workshop (HTDE 2012), I discussed the attributes of "hard-to-define" problems. While not all hard-to-define problems are wicked, wicked problems do not feature a closed or even finite set of possible solutions. Whether they can truly be treated using an algorithmic framework is not clear.

2) all solutions are heuristic: due to the limitations of the first feature, any given wicked problem has no exact solution. The problem space will be characterized by many different solutions, likely context-dependent (the word "contingent" [6] can also be used).

3) there is no "stopping rule" for wicked problems. In conventional computing, the is an end point to a simulation of program that can be defined either deterministically (program-dependent) or stochastically (a Turing machine). With wicked problems, there is no natural stopping point, as the problem has no natural end-point [7].

4) so-called "messes" [8] define interactions between subdomains of the problem. In this case, a problem's subdomains form a dense, fully-connected network which cannot be decomposed to reveal clear causal or associative relationships. Instead of being merely massively parallel, such problems are at least massively interactive and are often exhibit parallelism as well. Furthermore, such messes often transcend formal system-level boundaries, and from a phenomenological standpoint implicate several loosely-related systems.

Figure 3. Two first-pass approximations at wicked problems? LEFT: M.C. Escher's Mobius Strip, RIGHT: SimCity.

How is this perspective useful for computing and solving complex scientific problems? Well, it is not so much useful as it is a challenge. There is much work to be done here. So what a challenge it is [9]!

NOTES:
[1] Papadimitriou, G.H.   Computational Complexity. Addison-Wesley, Boston (1994).

[2] Brown, V.A., Harris, J.A., and Russell, J.Y.   Tackling Wicked Problems: Through the Transdisciplinary Imagination. Earthscan, London (2010).

[3] According to Wikipedia, C. West Churchman introduced the term in 1967, which was expanded upon in the following paper:

Rittel, H.W.J. and Webber, M.M.   Dilemmas in a General Theory of Planning. Policy Sciences, 4, 155-169 (1973).

[4] Mandelbrot, B. and Hudson, R.L.   The (mis)Behavior of Markets: a fractal view of risk, ruin, and reward. Basic Books, New York (2004).

[5] Wicked problems have been discussed extensively in the business and operations research literature as a mans to solve social policy problems. Please see the following example:

Lazarus, R.J.   Super Wicked Problems and Climate Change: Restraining the Present to Liberate the Future. Cornell Law Review, 94(5), Georgetown Public Law Research No. 1302623 (2009).

However, the things that define a wicked problem apply to a much larger class of problems. Formal methods are needed.

[6] Levin, K., Cashore, B., Bernstein, S., and Auld, G.   Playing it forward: Path dependency, progressive incrementalism, and the "Super Wicked" problem of global climate change. IOP Conference Series: Earth and Environmental Science, 50(6) (2009).

[7] an example might be cultural or biological evolution, which do not "end" until some major catastrophe wipes out the entire system. In these examples, it is interesting to note that you can observe an artificially-determined endpoint, but it does not always reveal a definitive solution (e.g. natural selection and the evolution of "maximally adaptive" traits).

[8] According to Wikipedia, this term was originally coined by Russell Ackoff. Please see the following reference:

Ackoff, R.   Systems, Messes, and Interactive Planning. In "Redesigning the Future". Wiley, New York (1974).

[9] I have no prize to offer for anyone who proposes reasonable-sounding solutions or formal methods. It's just a call-to-arms.