Computer Science

This short course will review recent advances in econometric theory for datasets that stem from the strategic interaction of participants in a game theoretic scenario. The course will cover basics of identification and estimation strategies for structural parameters of game theoretic models in settings like market entry games, dynamic games and auctions. In the first part, I will review basic econometric theory and in particular large sample asymptotic theory of generalized method of moment estimators and M-estimators, which forms the basis of many estimation and identification strategies proposed for game theoretic settings. I will then give an application of this theory to entry games of incomplete information. I will finish with an overview of how this approach extends to dynamic games of incomplete information. In the second part, I will analyze games of complete information and focus on the problem arising from the multiplicity of equilibria in these games, due to the unobserved heterogeneity of the participants. The latter leads to partial identification of the parameters of interest and set estimation. Finally, I will focus on econometrics of auction games and in particular estimation of the private value distribution in simple single item auctions. I will finish with a brief description of recent progress at the intersection of algorithmic game theory and econometrics.

This short course will review recent advances in econometric theory for datasets that stem from the strategic interaction of participants in a game theoretic scenario. The course will cover basics of identification and estimation strategies for structural parameters of game theoretic models in settings like market entry games, dynamic games and auctions. In the first part, I will review basic econometric theory and in particular large sample asymptotic theory of generalized method of moment estimators and M-estimators, which forms the basis of many estimation and identification strategies proposed for game theoretic settings. I will then give an application of this theory to entry games of incomplete information. I will finish with an overview of how this approach extends to dynamic games of incomplete information. In the second part, I will analyze games of complete information and focus on the problem arising from the multiplicity of equilibria in these games, due to the unobserved heterogeneity of the participants. The latter leads to partial identification of the parameters of interest and set estimation. Finally, I will focus on econometrics of auction games and in particular estimation of the private value distribution in simple single item auctions. I will finish with a brief description of recent progress at the intersection of algorithmic game theory and econometrics.

Classically, the outcome of a learning algorithm is considered in isolation from the effects that it may have on the process that generates the data or the party who is interested in learning. In today's world, increasingly more people and organizations interact with learning systems, making it necessary to consider these effects. This tutorial will cover the mathematical foundation for addressing learning and learnability in the presence of economic and social forces. We will cover recent advances in the theory of machine learning and algorithmic economics. In the first half of this tutorial, we will consider strategic and adversarial interactions between learning algorithms and those affected by algorithmic actions. What makes these interactions especially powerful is that they often occur over a long-term basis and can corrupt data patterns that are essential for machine learning. In this part of the talk, we work with online decision processes (such as no-regret learning) and solution concepts (such as stackelberg and minmax equilibria) to discuss statistical and computational aspects of  learning and learnability in the presence of such interactions. In the second half of the tutorial, we will consider collaborative interactions in machine learning. What makes these interactions especially beneficial is their ability to learn across multiple stakeholders' tasks. In this part of the talk, we see how online algorithms act as a medium for effective collaborations. We also discuss challenges involved in designing efficient data sharing mechanisms that fully account for learner's incentives.

Classically, the outcome of a learning algorithm is considered in isolation from the effects that it may have on the process that generates the data or the party who is interested in learning. In today's world, increasingly more people and organizations interact with learning systems, making it necessary to consider these effects. This tutorial will cover the mathematical foundation for addressing learning and learnability in the presence of economic and social forces. We will cover recent advances in the theory of machine learning and algorithmic economics. In the first half of this tutorial, we will consider strategic and adversarial interactions between learning algorithms and those affected by algorithmic actions. What makes these interactions especially powerful is that they often occur over a long-term basis and can corrupt data patterns that are essential for machine learning. In this part of the talk, we work with online decision processes (such as no-regret learning) and solution concepts (such as stackelberg and minmax equilibria) to discuss statistical and computational aspects of  learning and learnability in the presence of such interactions. In the second half of the tutorial, we will consider collaborative interactions in machine learning. What makes these interactions especially beneficial is their ability to learn across multiple stakeholders' tasks. In this part of the talk, we see how online algorithms act as a medium for effective collaborations. We also discuss challenges involved in designing efficient data sharing mechanisms that fully account for learner's incentives.

We examine questions in game theory and online learning from a dynamical systems perspective. Specifically, the goal of the tutorial is to establish links between typically distinct tools such as optimization theory (regret analysis), chaos theory, topology of dynamical systems and more traditional game theoretic ideas such as different classes of equilibria and Price of Anarchy. We will use these connections to elucidate recent results in the area as well as pose open questions.

We examine questions in game theory and online learning from a dynamical systems perspective. Specifically, the goal of the tutorial is to establish links between typically distinct tools such as optimization theory (regret analysis), chaos theory, topology of dynamical systems and more traditional game theoretic ideas such as different classes of equilibria and Price of Anarchy. We will use these connections to elucidate recent results in the area as well as pose open questions.

We examine questions in game theory and online learning from a dynamical systems perspective. Specifically, the goal of the tutorial is to establish links between typically distinct tools such as optimization theory (regret analysis), chaos theory, topology of dynamical systems and more traditional game theoretic ideas such as different classes of equilibria and Price of Anarchy. We will use these connections to elucidate recent results in the area as well as pose open questions.

We examine questions in game theory and online learning from a dynamical systems perspective. Specifically, the goal of the tutorial is to establish links between typically distinct tools such as optimization theory (regret analysis), chaos theory, topology of dynamical systems and more traditional game theoretic ideas such as different classes of equilibria and Price of Anarchy. We will use these connections to elucidate recent results in the area as well as pose open questions.

In over the last two decades we have developed good understanding how to quantify the impact of strategic user behavior on overall performance in many games (including traffic routing as well as online auctions). Early work focused on evaluating the quality of Nash equilibria. However, it turns out that the resulting bounds extend to learning out comes in repeated games under pretty general assumptions. In this talk we will review these results, which mostly assume that learners satisfy versions of the no-regret property after a long enough play. We will also discuss pros and cons of no-regret as a behavioral assumption on learning outcomes, as well as limitations of assuming no-regret as the main condition players achieve as they are learning.

In over the last two decades we have developed good understanding how to quantify the impact of strategic user behavior on overall performance in many games (including traffic routing as well as online auctions). Early work focused on evaluating the quality of Nash equilibria. However, it turns out that the resulting bounds extend to learning out comes in repeated games under pretty general assumptions. In this talk we will review these results, which mostly assume that learners satisfy versions of the no-regret property after a long enough play. We will also discuss pros and cons of no-regret as a behavioral assumption on learning outcomes, as well as limitations of assuming no-regret as the main condition players achieve as they are learning.