Two of the most recent and exciting examinations of game theory and economics have been on its computational and behavioral aspects. This working group will engage in one of the first efforts at exploring the intersection between these rich and rapidly developing fields.
Over the past several years, computer scientists have developed a rich toolbox and theory both for tackling computational issues arising in traditional game theory and economics, and for applying game-theoretic analyses and design to classical CS problems, such as resource allocation and networking. The computational tools include improved algorithms for computing equilibria in large games that make use of the most advanced algorithmic techniques, sampling methods, recent developments in mathematical programming, and sophisticated learning algorithms. Of equal importance has been the development of rich new representations for complex games, permitting the specification of network structures of communication in games, and specialized but natural payoff functions [Kearns, Littman and Singh (2001), Kearns and Mansour (2002)].
At the same time it has been developing models and algorithms for game-theoretic computations, the CS community has also been using game theory as a formalism and design principle for many kinds of distributed algorithms [Feigenbaum, Papadimitriou and Shenker (2000), Roughgarden and Tardos (2000)]. Rather than the traditional view of each node in a distributed protocol or system "behaving'' or being "malicious,'' these analyses assume that nodes are simply "rational,'' for some appropriate notion of self-interest. This line of thought has led to an insightful sequence of analyses and solutions for problems such as routing, multicast transmission, and load balancing.
On the other hand, for some time now a growing group of economists and game theorists have been challenging and revising the basic assumptions of rationality in humans and organizations [Camerer (2003)]. The considerable body of controlled experimental work in behavioral economics has repeatedly shown not only that human subjects will frequently deviate from traditionally assumed notions of self-interest and greed, but will do so in ways that are predictable, repeatable, and amenable to mathematical modeling and analysis. Notions such as altruism, revenge, and envy have been quantified and fruitfully measured, examined in many such studies, and have shed new light on both human behavior and the foundations of economic thought. (For some interesting relevant work, see [Camerer, Ho and Chong (2003), Costa Gomes, Crawford and Broseta (2001), Erev and Barron (2001), Stahl and Wilson (1995)].
One of the primary difficulties of applications of computational game theory to resource allocation problems has been (as is often the case) the specification of appropriate payoff or utility functions, where by "appropriate'' we mean not only resulting in the desired mathematical solution (equilibrium), but also one that the players (often nodes in a network) "care'' about. Typically, an assumption comparable to that of classical game theory --- namely, that there is some abstract "currency'' with respect to which players will act entirely greedily --- is made. Currencies may be things like negative network latency for routing, execution time for load balancing, or actual cash compensation. The lessons of behavioral game theory suggest that the consideration of broader notions of utility may be both more realistic and more effective.
In the opposite direction, the revised models of rationality proposed in the behavioral game theory literature present a slew of interesting and challenging computational issues that have received little consideration to date. Computer scientists now have a fairly clear understanding of the algorithmic challenges presented by Nash equilibria and related classical notions, but no deep computational thought has been given to how things change when mathematically formal notions of altruism and fairness are considered.
The purpose of this working group is to gather some of the most influential figures in both behavioral and computational game theory for the first time, in the hopes of articulating common interests and differences, and fostering collaborative research.
Camerer, C.F., Ho, T.H., and Chong, K., "Models of thinking, learning and teaching in games,'' American Econ. Review Papers and Proceedings, 2003.
Costa Gomes, M., Crawford, V., and Broseta, B., "Experimental studies of strategic sophistiction and cognition in normal-form games,'' Econometrica, 69, 2001, 1193-1235.
Erev, I., and Barron, G., "On adaptation, maximization and reinforcement learning among cognitive strategies,'' Technion working paper, 2001.
Feigenbaum, J., Papadimitriou, C., and Shenker, S., "Sharing the cost of multicast transmission,'' J. of Computer and System Sciences, 2000.
Kearns, M., Littman, M., and Singh, S., "Graphical models for game theory,'' Proceedings of UAI 2001.
Kearns, M., and Mansour, Y., "Efficient Nash computation in large population games with bounded influence,'' Proceedings of UAI 2002.
Roughgarden, T., and Tardos, E., "How bad is selfish routing?'', Proceedings of IEEE Foundations of Computer Science, 2000.
Stahl, D., and Wilson, P., "On players' models of other players -- theory and experimental evidence,'' Games and Economic Behavior, 10, 1995, 213-154.
Next: Call for Participation
Workshop Index
DIMACS Homepage