IBM Israel Research Seminars

Many interactions in complex environments (e.g., games like chess) are affected by computational limitations. An extreme example is the "factoring game," where the first player chooses a large number and sends it to the second player who then attempts to factor it. Ignoring computational considerations, the second player can factor any number and always win, but with computational considerations the game seems to favor the first player.

This well-known issue in game-theory falls under the term "bounded rationality," yet there is no general model of playing games with computational limitations. We propose an extremely simple model of a game with additional costs (computational or otherwise) for each strategy. We discuss equilibrium properties of these games and show that natural learning dynamics converge to equilibrium in zero-sum and potential games with these additional costs. We also give economic applications, in some cases where a weaker company has an advantage of a stronger one.

Joint work with Eli Ben-Sasson and Ehud Kalai.

About the Speaker
Adam Tauman Kalai will be starting as an Assistant Professor at Georgia Tech next fall. He is currently a visitor at the Weizmann Institute and will soon be visiting Microsoft Research in Redmond. Kalai received his B.A. from Harvard in 1996, Ph.D. from CMU in 2001, followed by years at MIT and three years at the Toyota Technological Institute in Chicago. His interests include Machine Learning, Game Theory, and Online/Randomized Algorithms.