نظریه بازی ها از نگاه دانشمند کامپیوتر

I consider issues in distributed computation that should be of relevance to game theory. In particular, I focus on (a) representing knowledge and uncertainty, (b) dealing with failures, and (c) specification of mechanisms.

There are many areas of overlap between computer science and game theory. The influence of computer science has been felt perhaps most strongly through complexity theory. Complexity theory has been viewed as a tool to help capture bounded rationality, going back to the work of Neyman (1985) and Rubinstein (1986). In addition, it is well understood that complexity-theoretic notions like NP-completeness help categorize the intrinsic difficulty of a problem. Thus, for example, a result showing that, even in simple settings, the problem of optimizing social welfare is NP-hard (Kfir-Dahav et al., 2000) shows that the standard procedure of applying Clarke’s mechanism, despite its many benefits, is not going to work in large systems. Perhaps less obvious is the interplay between game theory and work in distributed computing. At the surface, both areas are interested in much the same problems: dealing with systemswhere there are many agents, facing uncertainty, and having possibly different goals. In practice, however, there has been significant difference in emphasis in the two areas. In distributed computing, the focus has been on problems such as fault tolerance, scalability, and proving correctness of algorithms; in game theory, the focus has been on strategic concerns (that is, playing so as to optimize returns, in light of the preferences of other agents). In this paper, I hope to make the case that each area has much to learn from the other. I focus on three particular topics: • the representation of games (and, in particular, the knowledge and uncertainty of players in a game), • strategic concerns vs. fault tolerance, and • specification of mechanisms. The following sections deal with each of these topics in turn.

I have focused on one set of issues at the interface of computer science and game theory here, which arise from work in distributed computing. As I hope this discussion has made clear, I think that game theorists need to take more seriously issues like fault tolerance, asynchrony, the representation of knowledge and uncertainty, the difficult in the design and analysis of largemechanisms and games, and problems of specification. On the other hand, I think computer scientists need to take strategic concerns more seriously in the design and analysis of distributed protocols. These issues are not just of theoretical interest. They arise, for example, when we consider the design of Internet agents.We will certainly need to take into account failures, and no company would want to claim to support software for agents that bid in auctions that has not been carefully specified.7 The specification of the agents will, in turn, depend on a careful specification of the mechanism in which they will be participating. These issues represent only part of the commonality in interests that I see between computer science and game theory. I have already hinted at another important area of commonality: that of finding compact representations of games. Other issues of common interest include learning, mental-level modeling of beliefs (Brafman and Tennenholtz, 1997), qualitative decision theory (see the bibliography of over 290 papers at http://www. medg.lcs.mit.edu/qdt/bib/unsorted.bib). With the growing awareness of the commonality between computer science and game theory, I look forward to a great deal of fruitful interaction between the fields in the coming years.