turns out to contain concepts closely
related to fundamental principles of
statistical thermodynamics, so that
knowledge gained by physicists has influenced how computer scientists understand some types of computation.
economics and Game theory
Early on, computer scientists appreciated game theory and economic modeling. That connection dates to at least
the 1940s and the pioneering work of
John von Neumann, but has grown
much deeper in recent decades. Economists talk of Pareto optimums, in which
no participant in a system can perform
better without making another participant worse off, and of Nash equilibria,
in which no participant can make a unilateral change of strategy that will bring
an advantage, and they have proved theorems showing that, under certain assumptions, Pareto optimums and Nash
equilibria must exist. But the existence
of such a state is no guarantee that a
realistic system can actually attain it.
For example, computer scientists have
shown that Nash equilibria are computationally intractable problems, meaning not only that mathematical models
of economic markets are hard to solve,
but that the extent to which human behavior can move a market toward a Nash
equilibrium becomes questionable.
Moreover, Pareto optimality and
Nash equilibria do not necessarily
connote social or political desirability.
Nash equilibrium represents the best
that participants in a market can do by
pursuing a wholly selfish strategy. Papadimitriou has coined the term “price
of anarchy” for the fact that Nash equilibrium often gives participants a poorer
outcome than the best they could have
obtained through collaboration, while
work by other computer scientists not
only shows how to calculate this price,
in certain models, but also indicates
that the price may not be too high.
There are challenges, however, in
getting academic disciplines to collabo-
rate, says Lance Fortnow, a professor of
electrical engineering and computer sci-
ence at Northwestern University. “Com-
puter scientists want to impress other
computer scientists,” Fortnow says, and
economists possess the same attitude.
But cooperation between the two fields
is growing, and an increasing number of
economists see computer science as of-
fering ideas they can draw from, not only
in the technical matter of making mathe-
matical models work efficiently, but also
as a source of insight into the behavior
and properties of those models.
Further Reading
Otto, S.P.
The evolutionary enigma of sex, The
American Naturalist 174, S1, July 2009.
Lenski, R.E., Ofria, C., Pennock, R. T.,
and Adami, C.
The evolutionary origin of complex features,
nature 423, 139, May 8, 2003.
Yedidia, J., Freeman, W. T., and Weiss, Y.
Understanding belief propagation and
its generalizations, Exploring Artificial
Intelligence in the New Millennium,
Lakemeyer, G., nebel, B. (eds), Morgan
Kaufmann Publishers, San Francisco, CA,
2003.
Fortnow, L. and Gasarch, B.
Computational Complexity blog
http://blog.computationalcomplexity.org/
Kalai, E., Jackson, M.O., Lehrer, E., Palfrey, T.R.,
and Parkes, D.C. (eds.)
Games and Economic Behavior
http://www.elsevier.com/wps/locate/geb
David Lindley is a freelance science writer in Alexandria, VA.
© 2010 ACM 0001-0782/10/0700 $10.00
Milestones
SIGSOFT
Awards
The aCM special interest
Group on software engineering
(siGsoFT) recently presented
its highest awards to several
computer scientists whose
contributions in research,
education, and service have
shaped the development of
software engineering and
its ability to solve complex
computational problems.
eric Gamma, richard
helm, ralph Johnson, and
(posthumously) John Vlissides
received the 2010 siGsoFT
outstanding research award
for contributions to the practice
of software engineering. Their
landmark book Design Patterns
explored the capabilities and
pitfalls of object-oriented
programming and catalogued
23 specific solutions to common
design problems. Gamma
is technical director of the
software Technology Center of
object Technology international
in Zurich, switzerland. helm is a
partner and managing director
of the boston Consulting Group
in sydney, australia. Johnson is
on the faculty of the University
of illinois Urbana-Champaign
department of computer
science. Vlissides, a researcher
at ibM T.J. watson research
Center, passed away in 2005.
The 2010 siGsoFT
influential educator award was
presented to Leon osterweil, a
computer science professor at
the University of Massachusetts
amherst, for pioneering work
in graduate-level education
in software engineering. he
launched the New software
engineering Faculty symposium
in 1991 at the international
Conference on software
engineering to encourage new
software engineering faculty
early in their careers.
Mary Lou soffa, who chairs
the department of computer
science at the University of
Virginia, received the 2010
siGsoF T distinguished
service award for her extensive
service in the software
engineering community and her
commitment to strengthening
ties with her colleagues across
the programming languages
community. soffa has served
on the community’s leading
editorial boards, advisory and
steering committees, and
conferences.
