Mean Field Games (MFG) are the infinite-population analogue of symmetric stochastic differential games with interacting players. By considering a limiting model with a continuum of players, the theory of MFG provides a more tractable representation and can effectively approximate a broad class of perfectly symmetric stochastic dynamic games. This thesis studies games with heterogeneous players, the heterogeneity being expressed either through a type parameter or through asymmetric interactions among players, and aims at understanding under which condition the MFG approximation remains valid for such games and, if it fails, to find a substitute model. In many real-life settings, players do not view themselves as exchangeable and accurate models should incorporate this heterogeneity. We first adapt the MFG paradigm to model more heterogeneous agents by introducing a type parameter in a financial problem that has gained huge interest in the recent years: the competitive Merton problem under relative performance criteria. By deriving a closed-form solution for the finitely many player investment-consumption problem, we show how the risk tolerance and competitivity of the investors influence their optimal strategy in equilibrium. Moreover, this thesis contributes to a very recent line of work bridging MFG theory and network games by studying n-player stochastic dynamic games in which interactions are governed by a graph. For games with perfectly symmetric players, the MFG approximation can be rigorously justified under suitable assumptions for two main reasons: On the one hand, the equilibria of n-player games can be shown to converge to the MFG limit. On the other hand, a solution of the continuum model may be used to construct approximate equilibria for the corresponding n-player model. This thesis extends these results in two cases: first, for games on general graph sequences in the setting of a specific yet rich linear-quadratic model and second, for general games on dense graph sequences. For linear-quadratic games, we show that the MFG is the correct limit only in the dense graph case, i.e., when the degrees diverge in a suitable sense. Even though equilibrium strategies are nonlocal, depending on the behavior of all players, we use a correlation decay estimate to prove a propagation of chaos result in both the dense and sparse regimes, with the sparse case owing to the large distances between typical vertices. We show also that the mean field game solution can be used to construct decentralized approximate equilibria on any sufficiently dense graph sequence. Finally, since graphons have been shown to be the correct limit object for converging dense graph sequences, we develop the theory of graphon-based analogues of MFG. We propose a new formulation of graphon games based on a single typical player's label-state distribution. We show how our notion of graphon equilibrium can be used to construct approximate equilibria for large finite games set on any (weighted, directed) graph which converges in cut norm. The lack of players' exchangeability necessitates a careful definition of approximate equilibrium, allowing heterogeneity among the players' approximation errors, and we show how various regularity properties of the model inputs and underlying graphon lead naturally to different strengths of approximation.

The host of a game presents two indistinguishable envelopes to an agent. One of the envelopes is randomly selected and allocated to the agent. The agent is informed that the monetary content of one of the envelopes is twice that of the other. The dilemma is under which conditions it would be beneficial to switch the allocated envelope for the complementary one. The objective of his or her envelope-switching strategy is to determine the benefit of switch- ing the allocated envelope and its content for the expected content of the complementary envelope. The agent, upon revealing the content of the allocated envelope, must consider the events that are likely to have taken place as a result of the host’s activ- ities. The preceding approach is in stark contrast to considering the agent’s reasoning for a particular outcome that seeks to derive a strategy based on the relative contents of the presented envelopes. However, it is the former reasoning that seeks to identify what the initial amounts could have been, as a result of the observed amount, that facilitates the identification of an appropriate switching strategy. Knowledge of the content and allocation process is essential for the agent to derive a successful switching strategy, as is the distribution function from which the host sampled the initial amount that is assigned to the first enve- lope. For every play of the game, once the agent is afforded the opportunity of sight­ing the content of the randomly allocated envelope, he or she can determine the expected benefit of switching. / Research / M. Sc. (Operations Research)

The host of a game presents two indistinguishable envelopes to an agent. One of the envelopes is randomly selected and allocated to the agent. The agent is informed that the monetary content of one of the envelopes is twice that of the other. The dilemma is under which conditions it would be beneficial to switch the allocated envelope for the complementary one. The objective of his or her envelope-switching strategy is to determine the benefit of switch- ing the allocated envelope and its content for the expected content of the complementary envelope. The agent, upon revealing the content of the allocated envelope, must consider the events that are likely to have taken place as a result of the host’s activ- ities. The preceding approach is in stark contrast to considering the agent’s reasoning for a particular outcome that seeks to derive a strategy based on the relative contents of the presented envelopes. However, it is the former reasoning that seeks to identify what the initial amounts could have been, as a result of the observed amount, that facilitates the identification of an appropriate switching strategy. Knowledge of the content and allocation process is essential for the agent to derive a successful switching strategy, as is the distribution function from which the host sampled the initial amount that is assigned to the first enve- lope. For every play of the game, once the agent is afforded the opportunity of sight­ing the content of the randomly allocated envelope, he or she can determine the expected benefit of switching. / Research / M. Sc. (Operations Research)

In this dissertation, I present three theoretical results with real-world applications related to scheduling and distributionally-robust games, important fields in discrete optimization, and computer science. The first chapter provides simple, technology-free interventions to manage elevator queues in high-rise buildings when passenger demand far exceeds the capacity of the elevator system. The problem was motivated by the need to manage passengers safely in light of reduced elevator capacities during the COVID-19 pandemic. We use mathematical modeling, epidemiological expertise, and simulation to design and evaluate our algorithmic solutions. The key idea is to explicitly or implicitly group passengers that are going to the same floor into the same elevator as much as possible, substantiated theoretically using a technique from queuing theory known as stability analysis. This chapter is joint work with Charles Branas, Adam Elmachtoub, Clifford Stein, and Yeqing Zhou, directly in collaboration with the New York City Mayor’s Office of the Chief Technology Officer and the Department of Citywide Administrative Services. The second chapter proposes new algorithms for recomputing passenger itineraries for airlines during major disruptions when carefully planned schedules are thrown into disarray. An airline network is a massive temporal graph, often with tight regulatory and operational constraints. When disruptions propagate through an airline network, the objective is to \textit{recover} within a given time frame from a disruption, meaning we replan schedules affected by the disruption such that the new schedules have to match the originally planned schedules after the time frame. We aim to solve the large-scale airline recovery problem with quick, user-independent, consistent, and near-optimal algorithms. We provide new algorithms to solve the passenger recovery problem, given recovered flight and crew solutions. We build a preprocessing step and construct an Integer Program as well as a network-based approach based on solving multiple-label shortest path problems. Experiments show the tractability of our proposed algorithms on airline data sets with heavy flight disruptions. This chapter is joint work with Clifford Stein, stemming from an internship and collaboration with the Machine Learning team (Artificial Intelligence organization) of GE Global Research, Niskayuna, New York. The third chapter is about computing distributionally-robust strategies for a popular game theory model called Stackelberg games, where one player, called the leader, is able to commit to a strategy first, assuming the other player(s), called follower(s) would best respond to the strategy. In many of the real-world applications of Stackelberg games, parameters such as payoffs of the follower(s) are not known with certainty. Distributionally-robust optimization allows a distribution over possible model parameters, where this distribution comes from a set of possible distributions. The goal for the leader is to maximize their expected utility with respect to the worst-case distribution from the set. We initiate the study of distributionally-robust models for Stackelberg games, show that a distributionally-robust Stackelberg equilibrium always exists across a wide array of uncertainty models, and provide tractable algorithms for some general settings with experimental results. This chapter is joint work with Christian Kroer.

Algorithms for repeated (or “online”) decision-making are predominantly studied under the assumption that feedback is either statistical (determined by fixed probability distributions) or adversarial (changing over time in a potentially worst-case manner). Both of these assumptions ignore a phenomenon commonly present in repeated interactions with other agents, in which the space of our possible future outcomes is shaped in a structured and potentially predictable manner by our history of prior decisions. In this thesis, we consider online decision problems where the feedback model is adaptive rather than purely statistical or adversarial. One such example is a repeated game played against an opponent who uses a learning algorithm of their own; here, we give a characterization of possible outcome spaces which unifies disparate equilibrium notions, and serves as a basis for designing new algorithms. We then consider the task of providing recommendations to an agent whose preferences adapt based on the recommendation history, where we explore algorithmic tradeoffs in terms of the structure of this adaptivity pattern. We conclude by offering a general framework and algorithmic toolkit for approaching adaptive problems of this form.

One of the major mysteries in science is the remarkable success of machine learning. While its empirical achievements have captivated the field, our theoretical comprehension lags significantly behind. This thesis seeks for advancing our theoretical understanding of learning and intelligence from a computational perspective. By studying fundamental learning, optimization and decision making tasks, we aspire to shed lights on the impact of computation for artificial intelligence. The first part of this thesis concerns the space resource needed for learning. By studying the fundamental role of memory for continual learning, online decision making and convex optimization, we find both continual learning and efficient convex optimization require a lot of memory; while for decision making, exponential savings are possible. More concretely, (1) We prove there is no memory deduction in continual learning, unless the continual learner takes multiple passes over the sequence of environments; (2) We prove in order to optimize a convex function in the most iteration efficient way, an algorithm must use a quadratic amount of space; (3) We show polylogarithmic space is sufficient for making near optimal decisions in an oblivious adversary environment; in a sharp contrast, a quadratic saving is both sufficient and necessary to achieve vanishing regret in an adaptive adversarial environment. The second part of this thesis uses learning as a tool, and resolves a series of long-standing open questions in algorithmic game theory. By giving an exponential faster no-swap-regret learning algorithm, we obtain algorithms that achieve near-optimal computation/communication/iteration complexity for computing an approximate correlated equilibrium in a normal-form game, and we give the first polynomial-time algorithm for computing approximate normal-form correlated equilibria in imperfect information games (including Bayesian and extensive-form games).