
Price of anarchy quantifies the degradation of social welfare in games due to
the lack of a centralized authority that can enforce the optimal outcome. At
its antipodes, mechanism design studies how to ameliorate these effects by
incentivizing socially desirable behavior and implementing the optimal state as
equilibrium. In practice, the responsiveness to such measures depends on the
wealth of each individual. This leads to a natural, but largely unexplored,
question. Does optimal mechanism design entrench, or maybe even exacerbate,
social inequality?
We study this question in nonatomic congestion games, arguably one of the
most thoroughly studied settings from the perspectives of price of anarchy as
well as mechanism design. We introduce a new model that incorporates the wealth
distribution of the population and captures the income elasticity of travel
time. This allows us to argue about the equality of wealth distribution both
before and after employing a mechanism. We start our analysis by establishing a
broad qualitative result, showing that tolls always increase inequality in
symmetric congestion games under any reasonable metric of inequality, e.g., the
Gini index. Next, we introduce the iniquity index, a novel measure for
quantifying the magnitude of these forces towards a more unbalanced wealth
distribution and show it has good normative properties (robustness to scaling
of income, noregret learning). We analyze iniquity both in theoretical
settings (Pigou's network under various wealth distributions) as well as
experimental ones (based on a large scale field experiment in Singapore).
Finally, we provide an algorithm for computing optimal tolls for any point of
the tradeoff of relative importance of efficiency and equality. We conclude
with a discussion of our findings in the context of theories of justice as
developed in contemporary social sciences.

We establish that firstorder methods avoid saddle points for almost all
initializations. Our results apply to a wide variety of firstorder methods,
including gradient descent, block coordinate descent, mirror descent and
variants thereof. The connecting thread is that such algorithms can be studied
from a dynamical systems perspective in which appropriate instantiations of the
Stable Manifold Theorem allow for a global stability analysis. Thus, neither
access to secondorder derivative information nor randomness beyond
initialization is necessary to provably avoid saddle points.

Regularized learning is a fundamental technique in online optimization,
machine learning and many other fields of computer science. A natural question
that arises in these settings is how regularized learning algorithms behave
when faced against each other. We study a natural formulation of this problem
by coupling regularized learning dynamics in zerosum games. We show that the
system's behavior is Poincar\'e recurrent, implying that almost every
trajectory revisits any (arbitrarily small) neighborhood of its starting point
infinitely often. This cycling behavior is robust to the agents' choice of
regularization mechanism (each agent could be using a different regularizer),
to positiveaffine transformations of the agents' utilities, and it also
persists in the case of networked competition, i.e., for zerosum polymatrix
games.

Routing games are amongst the most well studied domains of game theory. How
relevant are these penandpaper calculations to understanding the reality of
everyday traffic routing? We focus on a semantically rich dataset that captures
detailed information about the daily behavior of thousands of Singaporean
commuters and examine the following basic questions: (i) Does the traffic
equilibrate? (ii) Is the system behavior consistent with latency minimizing
agents? (iii) Is the resulting system efficient? In order to capture the
efficiency of the traffic network in a way that agrees with our everyday
intuition we introduce a new metric, the stress of catastrophe, which reflects
the combined inefficiencies of both tragedy of the commons as well as price of
anarchy effects.

The YouTube8M video classification challenge requires teams to classify 0.7
million videos into one or more of 4,716 classes. In this Kaggle competition,
we placed in the top 3% out of 650 participants using released video and audio
features. Beyond that, we extend the original competition by including text
information in the classification, making this a truly multimodal approach
with vision, audio and text. The newly introduced text data is termed as
YouTube8MText. We present a classification framework for the joint use of
text, visual and audio features, and conduct an extensive set of experiments to
quantify the benefit that this additional mode brings. The inclusion of text
yields stateoftheart results, e.g. 86.7% GAP on the YouTube8MText
validation dataset.

BlackScholes (BS) is the standard mathematical model for option pricing in
financial markets. Option prices are calculated using an analytical formula
whose main inputs are strike (at which price to exercise) and volatility. The
BS framework assumes that volatility remains constant across all strikes,
however, in practice it varies. How do traders come to learn these parameters?
We introduce natural models of learning agents, in which they update their
beliefs about the true implied volatility based on the opinions of other
traders. We prove convergence of these opinion dynamics using techniques from
control theory and leaderfollower models, thus providing a resolution between
theory and market practices. We allow for two different models, one with
feedback and one with an unknown leader.

Small changes to the parameters of a system can lead to abrupt qualitative
changes of its behavior, a phenomenon known as bifurcation. Such instabilities
are typically considered problematic, however, we show that their power can be
leveraged to design novel types of mechanisms. Hysteresis mechanisms use
transient changes of system parameters to induce a permanent improvement to its
performance via optimal equilibrium selection. Optimal control mechanisms
induce convergence to states whose performance is better than even the best
equilibrium. We apply these mechanisms in two different settings that
illustrate the versatility of bifurcation mechanism design. In the first one we
explore how introducing flat taxation can improve social welfare, despite
decreasing agent "rationality", by destabilizing inefficient equilibria. From
there we move on to consider a well known game of tumor metabolism and use our
approach to derive novel cancer treatment strategies.

Routing games are one of the most successful domains of application of game
theory. It is well understood that simple dynamics converge to equilibria,
whose performance is nearly optimal regardless of the size of the network or
the number of agents. These strong theoretical assertions prompt a natural
question: How well do these penandpaper calculations agree with the reality
of everyday traffic routing? We focus on a semantically rich dataset from
Singapore's National Science Experiment that captures detailed information
about the daily behavior of thousands of Singaporean students. Using this
dataset, we can identify the routes as well as the modes of transportation used
by the students, e.g. car (driving or being driven to school) versus bus or
metro, estimate source and sink destinations (homeschool) and trip duration,
as well as their modedependent available routes. We quantify both the system
and individual optimality. Our estimate of the Empirical Price of Anarchy lies
between 1.11 and 1.22. Individually, the typical behavior is consistent from
day to day and nearly optimal, with low regret for not deviating to alternative
paths.

The Multiplicative Weights Update (MWU) method is a ubiquitous metaalgorithm
that works as follows: A distribution is maintained on a certain set, and at
each step the probability assigned to element $\gamma$ is multiplied by $(1
\epsilon C(\gamma))>0$ where $C(\gamma)$ is the "cost" of element $\gamma$ and
then rescaled to ensure that the new values form a distribution. We analyze MWU
in congestion games where agents use \textit{arbitrary admissible constants} as
learning rates $\epsilon$ and prove convergence to \textit{exact Nash
equilibria}. Our proof leverages a novel connection between MWU and the
BaumWelch algorithm, the standard instantiation of the
ExpectationMaximization (EM) algorithm for hidden Markov models (HMM).
Interestingly, this convergence result does not carry over to the nearly
homologous MWU variant where at each step the probability assigned to element
$\gamma$ is multiplied by $(1 \epsilon)^{C(\gamma)}$ even for the most
innocuous case of twoagent, twostrategy load balancing games, where such
dynamics can provably lead to limit cycles or even chaotic behavior.

What does it mean to fully understand the behavior of a network of adaptive
agents? The golden standard typically is the behavior of learning dynamics in
potential games, where many evolutionary dynamics, e.g., replicator, are known
to converge to sets of equilibria. Even in such classic settings many critical
questions remain unanswered. We examine issues such as:
Pointwise convergence: Does the system actually equilibrate even in the
presence of continuums of equilibria?
Computing regions of attraction: Given pointwise convergence can we compute
the region of asymptotic stability of each equilibrium (e.g., estimate its
volume, geometry)?
System invariants: Invariant functions remain constant along every system
trajectory. This notion is orthogonal to the game theoretic concept of a
potential function, which always strictly increases/decreases along system
trajectories. Do dynamics in potential games exhibit invariant functions? If
so, how many? How do these functions look like?
Based on these geometric characterizations, we propose a novel quantitative
framework for analyzing the efficiency of potential games with many equilibria.
The predictions of different equilibria are weighted by their probability to
arise under evolutionary dynamics given uniformly random initial conditions.
This average case analysis is shown to offer novel insights in classic game
theoretic challenges, including quantifying the risk dominance in staghunt
games and allowing for more nuanced performance analysis in networked
coordination and congestion games with large gaps between price of stability
and price of anarchy.

Given a nonconvex twice differentiable cost function f, we prove that the
set of initial conditions so that gradient descent converges to saddle points
where \nabla^2 f has at least one strictly negative eigenvalue has (Lebesgue)
measure zero, even for cost functions f with nonisolated critical points,
answering an open question in [Lee, Simchowitz, Jordan, Recht, COLT2016].
Moreover, this result extends to forwardinvariant convex subspaces, allowing
for weak (nonglobally Lipschitz) smoothness assumptions. Finally, we produce
an upper bound on the allowable stepsize.

A new approach to understanding evolution [Val09], namely viewing it through
the lens of computation, has already started yielding new insights, e.g.,
natural selection under sexual reproduction can be interpreted as the
Multiplicative Weight Update (MWU) Algorithm in coordination games played among
genes [CLPV14]. Using this machinery, we study the role of mutation in changing
environments in the presence of sexual reproduction. Following [WVA05], we
model changing environments via a Markov chain, with the states representing
environments, each with its own fitness matrix. In this setting, we show that
in the absence of mutation, the population goes extinct, but in the presence of
mutation, the population survives with positive probability. On the way to
proving the above theorem, we need to establish some facts about dynamics in
games. We provide the first, to our knowledge, polynomial convergence bound for
noisy MWU in a coordination game. Finally, we also show that in static
environments, sexual evolution with mutation converges, for any level of
mutation.

We develop a quasipolynomial time Las Vegas algorithm for approximating Nash
equilibria in polymatrix games over trees, under a mild renormalizing
assumption. Our result, in particular, leads to an expected polynomialtime
algorithm for computing approximate Nash equilibria of tree polymatrix games in
which the number of actions per player is a fixed constant. Further, for trees
with constant degree, the running time of the algorithm matches the best known
upper bound for approximating Nash equilibria in bimatrix games (Lipton,
Markakis, and Mehta 2003).
Notably, this work closely complements the hardness result of Rubinstein
(2015), which establishes the inapproximability of Nash equilibria in
polymatrix games over constantdegree bipartite graphs with two actions per
player.

A key question in biological systems is whether genetic diversity persists in
the long run under evolutionary competition or whether a single dominant
genotype emerges. Classic work by Kalmus in 1945 has established that even in
simple diploid species (species with two chromosomes) diversity can be
guaranteed as long as the heterozygote individuals enjoy a selective advantage.
Despite the classic nature of the problem, as we move towards increasingly
polymorphic traits (e.g. human blood types) predicting diversity and
understanding its implications is still not fully understood. Our key
contribution is to establish complexity theoretic hardness results implying
that even in the textbook case of single locus diploid models predicting
whether diversity survives or not given its fitness landscape is
algorithmically intractable. We complement our results by establishing that
under randomly chosen fitness landscapes diversity survives with significant
probability. Our results are structurally robust along several dimensions
(e.g., choice of parameter distribution, different definitions of
stability/persistence, restriction to typical subclasses of fitness
landscapes). Technically, our results exploit connections between game theory,
nonlinear dynamical systems, complexity theory and biology and establish
hardness results for predicting the evolution of a deterministic variant of the
well known multiplicative weights update algorithm in symmetric coordination
games which could be of independent interest.

In a recent series of papers a surprisingly strong connection was discovered
between standard models of evolution in mathematical biology and Multiplicative
Weights Updates Algorithm, a ubiquitous model of online learning and
optimization. These papers establish that mathematical models of biological
evolution are tantamount to applying discrete Multiplicative Weights Updates
Algorithm, a close variant of MWUA, on coordination games. This connection
allows for introducing insights from the study of game theoretic dynamics into
the field of mathematical biology. Using these results as a stepping stone, we
show that mathematical models of haploid evolution imply the extinction of
genetic diversity in the long term limit, a widely believed conjecture in
genetics. In game theoretic terms we show that in the case of coordination
games, under minimal genericity assumptions, discrete MWUA converges to pure
Nash equilibria for all but a zero measure of initial conditions. This result
holds despite the fact that mixed Nash equilibria can be exponentially (or even
uncountably) many, completely dominating in number the set of pure Nash
equilibria. Thus, in haploid organisms the long term preservation of genetic
diversity needs to be safeguarded by other evolutionary mechanisms such as
mutations and speciation.

We present a new class of vertex cover and set cover games. The price of
anarchy bounds match the best known constant factor approximation guarantees
for the centralized optimization problems for linear and also for submodular
costs  in contrast to all previously studied covering games, where the price
of anarchy cannot be bounded by a constant (e.g. [6, 7, 11, 5, 2]). In
particular, we describe a vertex cover game with a price of anarchy of 2. The
rules of the games capture the structure of the linear programming relaxations
of the underlying optimization problems, and our bounds are established by
analyzing these relaxations. Furthermore, for linear costs we exhibit linear
time best response dynamics that converge to these almost optimal Nash
equilibria. These dynamics mimic the classical greedy approximation algorithm
of BarYehuda and Even [3].

Covering and packing problems can be modeled as games to encapsulate
interesting social and engineering settings. These games have a high Price of
Anarchy in their natural formulation. However, existing research applicable to
specific instances of these games has only been able to prove fast convergence
to arbitrary equilibria. This paper studies general classes of covering and
packing games with learning dynamics models that incorporate a central
authority who broadcasts weak, socially beneficial signals to agents that
otherwise only use local information in their decisionmaking. Rather than
illustrating convergence to an arbitrary equilibrium that may have very high
social cost, we show that these systems quickly achieve nearoptimal
performance.
In particular, we show that in the public service advertising model, reaching
a small constant fraction of the agents is enough to bring the system to a
state within a log n factor of optimal in a broad class of set cover and set
packing games or a constant factor of optimal in the special cases of vertex
cover and maximum independent set, circumventing social inefficiency of bad
local equilibria that could arise without a central authority. We extend these
results to the learnthendecide model, in which agents use any of a broad
class of learning algorithms to decide in a given round whether to behave
according to locally optimal behavior or the behavior prescribed by the
broadcast signal. The new techniques we use for analyzing these games could be
of broader interest for analyzing more general classic optimization problems in
a distributed fashion.