Graph-Based Representations for Decision Analysis

Special Issue of the Journal of Decision Analysis

Access pdf of editorials for volume 1 and volume 2.

Editorial for Volume 1

Graphical representations of beliefs and preferences have played a central role in decision analysis. For at least as far back as the time of Blaise Pascal, decision analysts have represented actions, uncertainties, and preferences with branching trees capturing paths through a conceived space of outcomes. Although decision trees remain popular, more general graphical representations have come to the fore. Today, decision analysts and computer scientists have access to a variety of directed and undirected graphical representations for encoding relevance, independence, and sequence, including influence diagrams, Bayesian networks, dependency networks, Markov networks, and CP-nets. Graphical models have proven to be valuable for eliciting influences, beliefs, and preferences in a natural and comfortable manner, and for providing a computational substrate for efficient inference.

The introduction of influence diagrams by Ronald Howard and James Matheson in the late-1970s was a landmark contribution, providing a general graphical representation for decision analysis. Influence diagrams were forged amidst pressures to solve increasingly complex decision problems and the growing availability of computers that could represent and propagate assertions about relationships among variables of a decision basis. Howard, Matheson, and colleagues on their team, recognized that computers could be harnessed to free decision analysts from tedious bookkeeping, while providing both professionals and lay people with a more human-oriented graphical language for specifying, refining, and interacting with representations of decision problems.

It is said often that decision analysis is more about generating insights than about simply identifying actions with maximum expected utility. Influence diagrams shine most brightly in the communication channel they open for non-expert principal agents, engaging them, reducing the burden of assessment, and, ultimately, in providing insights via an intuitive, yet rigorous method for encoding and reflecting about decision challenges.

Beyond their use in decision analysis, influence diagrams have proven valuable in other ways, including their use as a tool for crisp communication among collaborating experts, for expressing and solving technical decision-analytic challenges in a graph-theoretic manner, and for serving both as a clarifying lens and as an explicit computational representation in artificial intelligence research. On the latter, influence diagrams are well-known within the artificial intelligence community and have been used in theoretical studies, such as efforts pursuing an understanding of causation and causal reasoning, and in engineering efforts focused on building and fielding automated decision-making systems.

Howard and Matheson’s initial article on influence diagrams expressed with atypical clarity the utility and beauty of the representation. Unfortunately, the manuscript was never published in the archival literature. Those interested in seeing the original work have had to expend varying amounts of effort to track down the 1981 technical report.

We decided to publish Howard and Matheson’s original article in archival form, along with a retrospective by the authors, to anchor a two-volume special issue of the journal on graph-based representations for decision analysis. Beyond the article and retrospective, this first volume includes two new articles. In the next volume of Decision Analysis, we will publish two additional articles and several shorter perspective pieces on the influences of influence diagrams, composed by leaders from several disciplines.

On the new articles in this volume, David Pennock and Michael Wellman explore the value of using graphical models to probe belief aggregation and risk sharing—two fundamental problems that come under the herald of group coordination. Research on forming consensus beliefs and preferences by combining the beliefs and preferences of groups of people has been fraught with negative results that come in the form of paradoxes and impossibility theorems. Pennock and Wellman make progress in this difficult space, harnessing graphical models to represent the aggregate probability distribution for a group of individuals. Although their analysis highlights new limitations and impossibility results, they also show how graphical models can be used to identify restrictive conditions that allow for consistent aggregations. The paper provides interesting background on group coordination problems and shows how graphical models can be used to build insights and generate results.

The article by David Matheson and James Matheson might be characterized as “the Heisenberg uncertainty principle meets decision analysis.” Motivated by their experiences with decision-analysis consultations, the authors investigate challenges with modeling situations where observational or control actions may have unintended, and typically unmodeled, influences on multiple aspects of the decision basis. They introduce the concept of purity of interventions and describe extensions to basic influence diagrams that account for side effects of interventions. Then, they provide an approach to estimating the value of interventions in advance of expending the effort to extend decision models to incorporate the side effects.

It has been an honor to serve as the Guest Editor of these volumes. I hope that the collection of articles and commentary will serve to appropriately honor the original work on influence diagrams, highlight current research, and ultimately stimulate new research efforts. I thank the many insightful reviewers who diligently read submissions and revisions and provided valuable comments to the authors and editors. I would like to also thank the Editors in Chief of Decision Analysis, Robert Clemen and Don Kleinmuntz, for their enthusiastic support. I want to especially recognize Bob, who put a great deal of effort into the special issue as a collaborator on the project.

Eric Horvitz, Guest Editor
October 2005

Editorial for Volume 2

With this second volume, we complete the special issue of Decision Analysis on “Graph-Based Representations for Decision Analysis.” In the first volume, we published Howard and Matheson’s original article on influence diagrams, along with a retrospective by the authors, and two new manuscripts. The current volume includes two additional articles followed by several shorter invited perspectives on the influence of graphical models.

In the first article, Ali Abbas and Ronald Howard present a class of utility models that they refer to as attribute dominance utility functions. They describe how methods for assessing joint probability distributions can be used to assess these utility functions and demonstrate the generality of their approach by showing how any utility function can be reformulated as an attribute dominance utility function. The authors introduce an intriguing graphical representation of attribute dominance utility functions, named utility diagrams, and present a “utility inference” procedure that is analogous to probabilistic inference.

The second paper, by Apiruk Detwarasiti and Ross Shachter, moves beyond traditional decision analyses—which consider the beliefs and preferences of a single principle agent—to tackle team decision-making challenges. The authors use graphical models to represent decisions that involve groups of people, such as actions that are taken by decision makers who are not collocated. They examine the class of team decision problems where team members are assumed to have common beliefs and preferences but cannot explicitly share information, and map such team decision making problems to actions by a single person with imperfect recall. They introduce influence-diagram representations of the team decision problems and show how the graphical models can elucidate opportunities for simplification and optimization.

The constellation of short perspectives following the longer contributions serves as an interesting ensemble of reflections on the history and influences of probabilistic and decision-theoretic graphical models. The authors of the perspectives share their thoughts on how graphical representations have shaped scholarship and practice in several realms, including insights about accomplishments to date and challenges ahead.

Graphical probabilistic models, including influence diagrams and Bayesian networks, have played a central role in the evolution of research in artificial intelligence (AI), where investigators have explored theoretical and practical problems with the automation of learning and reasoning. Historical analyses and reviews of the current state of research on graphical models in AI, statistics, and decision analysis reveal complementary cross-discipline efforts and interactions, with both shared and distinct goals and motivations.

Craig Boutilier reflects about the impact of influence diagrams in AI. He reviews how graphical models, and decision-theoretic concepts more broadly, have sculpted in a very significant manner research directions and approaches in the AI community. Judea Pearl shares personal reflections about the relationships between his work on Bayesian networks and the preceding work on graphical models in the Decision Analysis community. Readers will likely find interesting Pearl’s recollections of his early meeting with Howard, Matheson, and colleagues. His comments underscore how differences in fundamental passions, goals, and curiosity led to different stresses and priorities in work on graphical models. Pearl, and others in the AI community who have pursued the dream of understanding intelligence and of building automated reasoning systems, investigated graphical probabilistic models as a promising representational fabric for automated learning and inference. These goals motivated such efforts as the derivation of graph-theoretical results about the specification of independence and the formulation and testing of several exact and approximate algorithms for propagating beliefs in graphical models containing large numbers of variables. In earlier work, Howard, Matheson, and colleagues in the Decision Analysis community, pursued influence diagrams as a means for enhancing the practice of decision analysis, with a focus on easing assessment and entailment. Pearl noticed with interest, and some surprise, the differences in thrusts and goals in the initial meeting he had with Howard and Matheson on graphical models.

Over the last two decades, influence diagrams have been used by practitioners of decision analysis for tackling hard problems in numerous domains. Dennis Buede shares his personal experiences with using influence diagrams for tackling challenging decision problems that he has encountered in the course of his work as a professional decision analyst. He reports on the value of using influence diagrams consultations he has performed in working with government agencies, including challenges defined within the intelligence community.

Stephen Pauker and John Wong share their thoughts on the role of influence diagrams in medical decision making. Decision analysis has played a starring role in evidence-based medicine, providing insights to clinicians, patients, and policy makers about challenging, real-world healthcare decision problems. A thriving community of Medical Decision Making (MDM) researchers came into existence over twenty-five years ago, and assembles each year for the annual MDM meeting. Pauker and Wong describe the continuing dominance of decision trees in medical decision making and reflect about the relatively poor penetration of influence diagrams in their community. The authors’ reflections are relevant for professional decision analysis in domains beyond healthcare, and their insights highlight challenges and frame opportunities for future innovation.

The special issues of the Journal of Decision Analysis have provided a venue for recognizing formative work on influence diagrams and for communicating new results at the frontier of research. They have also provided a place for sharing reflections from several communities about progress and directions on graphical representations in decision making. Given the growing density of research on graphical probabilistic and decision-theoretic representations—and the expected stream of future publications on graph-based methods—I suspect that people will one day look back upon our decision to prepare “special” volumes on graph-based methods with interest and curiosity.

It has been an honor to serve as guest editor of the two volumes.

Eric Horvitz, Guest Editor
December 2005