It is intuitively clear that, in many situations, agents (in the sense of game theory) do not make a best response because determining what the best response should be would require a great deal of effort. This does not make agents irrational; chess players are not being irrational when they fail to play optimally. Indeed, their response could be viewed as perfectly rational, given their computational limitations. Standard solution concepts such as Nash equilibrium do not explicitly take computation into account.
The importance of considering computational issues in game theory has been recognized since at least the work of Simon. The PIs have developed a general framework for taking computation into account. A player is viewed as choosing a Turing machine (TM). With each TM M and input is associated a complexity. The complexity can represent the running time of or space used by M on that input; it can also be used to capture the complexity of M itself (e.g., the number of states) or to model the cost of searching for a new strategy to replace one that the player already has. The approach captures important intuitions, and can deal with a number of well-known problematic examples. Moreover, there are deep connections between this approach and cryptographic protocol security. Thus, thinking in terms of computational games can lead to new insights and new approaches in security.
The goal of this project is to investigate the implications of adding computational cost to game theory more broadly. This is expected to involve issues of language, awareness, and cryptography. Topics to be addressed include the following: - The extent to which this approach can capture important notions of secure computation and suggest new notions will be studied. - In the model, it is implicitly assumed that agents "understand" the costs associated with each TM and "understand" what the best response is. Thus, if the complexity is taken to be running time, agents know (or at least have subjective beliefs about) the running time of each TM. But where are these beliefs coming from? Clearly they, too, must be computed. Thus, the model will be extended so that it takes into account the cost of computing beliefs and best responses. Doing this will force consideration of issues of language in a serious way. - The earlier model considered only normal-form games. In extensive-form games, computation becomes an explicit part of the game. Intuitively, as the agent does computation, his understanding of the game improves, and he may become aware of more options. Thus, there should be deep connections between computation in extensive-form games and awareness, a topic that has attracted a great deal of recent attention in game theory and computer science; these will be explored. - To further understand the role of language, the interplay between the choice of language, computational cost, and rationality will be considered.
Progress in this area could have broad impact on theoretical models in game theory and computer science, and on applications of game theory both to the social sciences and to more practical work in security and networks, where game-theoretic models are becoming more and more prevalent.
