DIMACS 2004 - 2008 Special Focus on Computation and the Socio-Economic Sciences: Overview

Partnerships between mathematicians and social scientists have existed for a long time, but partnerships between computer scientists and social scientists are relatively new. In the past five years, they have begun to sprout and several important new fields of research are already thriving as a result. The topic of game theory and mechanism design has involved many leading computer scientists with economists and, as a result, for the first time many computer scientists are taking serious note of both the problems and the methods of economics. Analysis of the analogies between the growth of social networks and the development of the Internet have led to important insights about both areas and serious interactions between computer scientists and sociologists. Problems of metasearch have engaged computer scientists with political scientists and economists working on voting and social choice. We believe that the time is ripe to build on these early and exciting connections.

Partnerships between computer scientists and biologists are somewhat of a model for what we have in mind. These partnerships have flourished in the past 15 years. They have played a critical role in the human genome project, have led to a major emphasis on information processing in the biological organism, have spawned intriguing new areas of research in computer science such as DNA computing, and have contributed to major developments in tree reconstruction and pattern matching algorithms in computer science. In short, they have had a profound effect on both biology and computer science. There may not be a specific "big science'' challenge such as the human genome project in the case of computer science and the social sciences, but the opportunities for real and significant progress both in the computing and social sciences as a result of new interdisciplinary partnerships are upon us. In fact, the interaction between computer science and the social sciences is changing in dramatic ways that can be expected to have lasting impacts on both disciplines. Many applications in computer science and information technology (IT) involve issues and problems that social scientists (economists, political scientists, sociologists, psychologists and others) have addressed for years, issues of preference, utility, decision making, conflict and cooperation, incentives, auctions, bidding, consensus, social choice, and measurement; and the methods social scientists have developed for dealing with these issues and problems form an impressive toolkit. At the same time, with the widespread availability of today's powerful computers and new and exciting data sets, work in economics, political science, sociology and psychology that was only a theoretical possibility a few years ago is becoming a reality. Applying methods of social science to CS/IT problems requires new computational tools and the development of new variants of these methods. Applying computational methods to the solution of modern social science problems requires the development of new data structures, algorithms, and other tools that are in the domain of the computer scientist.

We have begun to see the use of methods developed by social scientists in a variety of IT applications. The requirements associated with these applications place great strain on the social science methods because of the sheer size of the problems addressed, issues involving computational power of agents, limitations on information possessed by players, and the sequential nature of repeated applications. Hence, there is a great need to develop a new generation of methods to satisfy these CS/IT requirements. In turn, these new methods will provide powerful new tools for social scientists. At the same time, great progress is being made on the problems traditionally of interest to social scientists through the use of new methods for finding patterns in data, searching through databases, computing solutions, and testing models.

This Special Focus seeks to develop the new "social-science-based" CS methodologies and to investigate their application to problems of information technology and to problems of the social sciences of fundamental importance to modern society. It also seeks to investigate computer science tools that are especially relevant to emerging problems of the socio-economic sciences. Research into issues of the type we envision requires new interdisciplinary partnerships among computer scientists, mathematicians, operations researchers, economists, experts in business applications, political scientists, psychologists, sociologists, and researchers specializing in the handling of information. We will build on the extensive interdisciplinary experience at DIMACS to bring together such interdisciplinary groups in the course of this special focus. DIMACS special foci on Mathematical Support for Molecular Biology (1994-2000) and Computational Molecular Biology (2000-2004) have played an important role in bringing computer and biological scientists together. This special focus is aimed at doing a similar thing.

Several major research themes span the Special Focus. They include:

• Computational Tractability/Intractability. Limits on what can be efficiently computed are very important in social-science-based CS applications and applications of CS methods to the social sciences.
  • Can our understanding of computational complexity help us to buld computational tools that will enlarge the set of social science models that can be analyzed and to adapt social-scientific concepts to solve problems of information technology?
  • How can we characterize situations where intractability is a good thing, as for example when we use it to protect privacy or make it difficult to manipulate the outcome of an election?

• Limitations on Computational Power/Information. Increasingly, economic decisions have to be made in situations where there are many "actors'' each having partial information or where there are limits to computation that prevent actors from obtaining needed information. Limitations include:
  • informational asymmetries
  • computational limits to extracting information that is available (perhaps in large data sets)
  • cognitive limitations on the part of agents.

• The Impact on New Methodologies of the Sheer Size of CS/IT Applications. The sheer size of CS/IT applications requires new methods/protocols where efficiency is a central focus and where issues of scalability and robustness with respect to errors in data are prominent.

• Learning through Repetition. Issues of learning, taking advantage of repeated games or auctions or through combining repeated inputs, arise in CS/IT applications in fascinating ways. Some tasks may be delegated to software agents and one needs to understand how they should be designed to "learn'' user preferences and how to bid and trade.

• Security, Privacy, Cryptography. The need for secure communication and privacy sparks the need for cryptographic methods in the analysis and design of voting procedures, games, and decision processes. Such issues arise in areas like electronic commerce and electronic voting, and many will be discussed in detail in a parallel special focus program on "Communication Security and Information Privacy'' at DIMACS. (For more detail about the planned program, and in particular a list of planned workshops and working groups, see http://dimacs.rutgers.edu/archive/SpecialYears/2003_CSIP/.)

• Game-theoretic Solution Concepts. As we consider larger and larger games in modern economic applications, Nash equilibria, solution concepts in cooperative games, and other game-theoretic solution concepts applied in a variety of settings become harder and harder to compute.

• Markets as Information Sources. Increasingly individuals and firms are using markets to learn about their competitors' preferences and to aggregate and combine information, for example through the generation of prices. These developments can benefit from methods of distributed computing and combinatorial exchange.

• Implementation of Auctions. While dramatic changes in availability of information technology have allowed us to expedite increasingly complex business transactions, for example complex auctions, the ability to implement such transactions often puts a strain on existing computational methods.

• Designing Markets. How do we design markets for the exchange of complicated assets like spectrum, stock portfolios, landing rights, and airline routes? The problems involved are different from those of traditional auctions, as there are multiple owners whose assets interact in complex ways.

• Dynamic Markets. Ever-more-powerful computers make it increasingly possible to develop sophisticated algorithms that allow actors to adjust prices, bandwidth, etc. in a dynamic way, as well as adjust schedules and allocations in response to changing market conditions or unforeseen events.

• Computing Utilities. Utility functions, which have been studied for a long time by economists and psychologists, are increasingly important in considerations of interest to computer scientists. For both groups, there is the need to compute utilities in larger and larger environments and under conditions of distributed information. These call for new models, tools, and algorithms such as the use of polyhedral combinatorial methods which are so central to computer science.

Now would be an ideal time for this special focus. Leading computer scientists are seeking to learn and modify methods of the social sciences and are interacting with social scientists in increasingly sophisticated ways, while social scientists are more and more aware of the kinds of issues that are of central importance in computer science. Attendance at the early meetings organized around this kind of interface both at DIMACS and elsewhere has been large and enthusiastic and we are starting to see very serious research coming out of this interdisciplinary field. This should just be the beginning.

Opportunities to Participate: The Special Focus will include:

• Workshops: A variety of workshops and mini-workshops are being planned

• Working Groups: Interdisciplinary "working groups" will explore special focus research topics.

• Tutorial: A tutorial will provide background knowledge to those who wish to participate in the special focus or just get an introduction to some of the fundamental issues in the field.

• Seminar Series: There will be a mix of research talks and practitioner presentations.

• Visitor Programs: Applications for research and graduate student visits to the center are invited. Some funds are available for travel and local support.

• Postdoctoral Positions: There is a possibility postdoctoral positions will be offered in this area

• Graduate Student Support: Funds will be set aside for graduate students interested in attending workshops. Students interested in visiting DIMACS during the special focus are encouraged to apply to the special focus organizers.

• Publications: We anticipate that a variety of publications, including AMS-DIMACS volumes, technical reports, abstracts and notes on the WWW, and DIMACS modules will result from the special focus.

Index of Special Focus on Computation and the Socio-Economic Sciences

DIMACS Homepage