Skip to main content

Mathematical Economics and Game Theory

Mechanism design is the problem of designing a game so as to guarantee that players playing rationally will produce outcomes that are desirable from the point of view of the mechanism designer.

Auctions can be viewed as instances of mechanisms. We may be interested in designing auctions that, for example, maximize the revenue of a seller or encourage truthful behavior on the part of buyers. Computer scientists have become interested in algorithmic mechanism design, where the focus is on designing mechanisms with good properties that can be implemented in polynomial time. More recently, there has been work designing extremely simple mechanisms, that may not be optimal but perform well (in some appropriate sense) in equilibrium.

Combining learning theory with game theory: Online learning theory provides powerful models (such as the famous multi-armed bandit problem) for reasoning about processes that adapt their behavior based on past observations. New research questions emerge when one places online learning in a game-theoretic context. For example, what can be said about the dynamics of systems composed of multiple learners interacting in either a competitive or a cooperative environment? If the learner's observations depend partly on data provided by selfish users, can we design learning algorithms whose behavior is aligned with the users' incentives, and what impact does this have on convergence rates? How should one design algorithms for settings where the learner cannot take actions directly, but instead depends on myopic agents who can be encouraged via incentive payments to explore the space of alternatives, as when an online retailer attempts to learn the quality of products by eliciting consumer ratings?

Adding computation and language issues to game theory: We consider models of game theory that explicitly charge for computation and take seriously the language used by agents. This turns out to have a major impact on solution concepts like Nash equilibrium. The approach seems to capture 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 insights and new approaches in security.