ITR: Networks of Strategic Agents: Theory and Algorithms

Cornell University, Ithaca NY

Investigators

Abstract

Networks of interacting agents play a fundamental role in many domains, ranging from physical communication networks such as the Internet to social networks arising from relationships between people. These networks grow and evolve through interactions of large numbers of participants, yielding complex global structure and dynamics. Often this leads to systems that function efficiently and reliably; but in other, seemingly similar settings, networks can exhibit latent inefficiency or cascading failures. Such failures occur not only in physical networks but also in social ones, as illustrated by recent financial crises which propagated through networks of relationships and trust. Despite considerable interest in these topics, the research community is only beginning to understand the behavior of networks such as these; small variations in the incentives, information, and computational power possessed by the agents in a network can have profound effects on network behavior, yet the principles underlying these effects remain elusive. This project develops theoretical and algorithmic underpinnings of networks that arise from the interaction of strategic agents. By combining game-theoretic approaches with computational models of interacting agents, the work develops models that are richer and more informative than either those that consider strategic agents in the absence of interaction networks or those that consider network structure in the absence of game-theoretic models of the agents. Networks of strategic agents are investigated at several different levels, extending from questions of structure to those of function and behavior. One of the project's central goals is to examine the inter-relationships between these three levels. In contrast, most current techniques are tuned to a single level in isolation, with work in computer science and mathematics focusing primarily on structure and work in economics emphasizing strategic behavior. The project's inter-disciplinary nature exposes similarities between questions in communication networks, including the Internet, and those arising in social networks, such as trust in markets. Beyond analyzing questions arising from these networks in general, a particular goal is to better understand the networks of interactions underlying electronic markets. Indeed, while it was widely predicted that such marketplaces would revolutionize trading of goods and services, very few have survived. The project participants contribute expertise from several perspectives. They have made some of the fundamental contributions to algorithmic game theory, computational and economic analysis of interacting agents, and models for complex networks, as well as to the understanding of market microstructure and the design of electronic markets. Further, the investigators have been key participants in the new Information Science program at Cornell. This program seeks to broaden the reach of computational ideas by attracting students from non-technical backgrounds, and incorporating notions of computation as a human-centered activity that is intrinsically embedded in social, legal, and economic contexts. The scientific results of the project support the intellectual underpinnings of this program at both the graduate and undergraduate levels. Many of the models involved in the research have an immediate intuitive appeal, and are well suited to interactive graphical demonstrations. These demonstrations can be used to broaden general understanding of the nature of strategic interaction and its networked character, and can be made broadly available through the National Science Digital Library (NSDL) where appropriate to pre-collegiate educational levels. The Internet is but the newest of many networks of strategic agents. However, it has served to change the structure and function of other networks, as it enables instantaneous, always-on, global communication. Understanding the theoretical underpinnings of these changes can provide important societal benefits in terms of more secure, stable communication and economic systems.