Video summary
In his discussion of markets and collective outcomes, Michael Kearns highlights how game theory serves as a mathematical framework for analyzing systems where individual interactions shape overall results. While originating in economics, this field has evolved into algorithmic game theory over the past two decades, particularly within computer science. A foundational concept here is Nash's work establishing that competitive equilibria exist under very general circumstances; however, Kearns clarifies that mere existence does not guarantee stability through natural iterative behavior. He uses the classic prisoner's dilemma to illustrate how individuals pursuing self-interest can lead to a collective outcome worse than what cooperation might achieve, noting that such cooperative states are often not equilibrium points in these scenarios. The intersection of game theory and machine learning represents perhaps the most significant technical contribution to algorithmic game theory according to Kearns. This connection is deeply rooted in "no regret" learning, which provides a general framework explaining how multiple players acting selfishly can actually reach an equilibrium relatively quickly. In practical terms, this dynamic is evident in modern navigation apps like Google Maps and Waze. These platforms utilize data from all users on the network to calculate routes that minimize individual driving time based on current traffic conditions created by everyone else's movements. Essentially, these algorithms compute a selfish best response for each user, effectively nudging them toward a Nash equilibrium of the complex game played across the entire transportation network. Despite the efficiency gains in specific metrics like distance or route availability compared to older methods, Kearns points out that reaching this competitive equilibrium is not inherently beneficial for everyone. Both theoretical models and limited studies on actual traffic data suggest that when all drivers optimize their own paths selfishly via these apps, collective driving time can become significantly higher than under alternative solutions. This phenomenon extends beyond transportation; similar algorithms operate on social media platforms like Facebook or news feeds, as well as e-commerce sites like Amazon. These systems use machine learning to predict user preferences and product interests, optimizing content delivery in a way that drives users toward their own equilibrium points without necessarily considering whether the collective outcome is optimal for society at large. Ultimately, Kearns emphasizes a crucial lesson from game theory: being at an equilibrium does not mean it is impossible or undesirable to find solutions where some or even all participants could be better off. The algorithms driving these platforms rely heavily on machine learning techniques—predicting traffic patterns, product likes, and newsfeed satisfaction—to optimize outcomes for individual users based on the actions of others. However, this optimization often locks systems into stable states that may not represent the best possible collective welfare. By understanding the link between no-regret learning mechanisms in machine learning and game-theoretic equilibria, we can better recognize how platforms influence human behavior and explore ways to design interventions that move beyond simple self-optimization toward more beneficial systemic outcomes.
Read the full video transcript
speaking of markets a lot of fascinating
aspects of this world arise not from
individual humans but from the
interaction of human beings you've done
a lot of work in game theory first can
you say what is game theory and how does
help us model and study yeah game theory
of course let us give credit where it's
due they don't comes from the economist
first and foremost but as I'd mentioned
before like you know computer scientists
never hesitate to wander into other
people's turf and so there is now this
20 year old field called algorithmic
game theory but you know game game
theory first and foremost is a
mathematical framework for reasoning
about collective outcomes in systems of
interacting individuals you know so you
need at least two people to get started
in game theory and many people are
probably familiar with prisoner's
dilemma as kind of a classic example of
game theory and a classic example where
everybody looking out for their own
individual interests leads to a
collective outcome that's kind of worse
for everybody then what might be
possible if they cooperate it for
example but cooperation is not an
equilibrium in prisoner's dilemma and so
my work and the field of algorithmic
game theory more generally in these
areas kind of looks at settings in which
the number of actors is potentially
extraordinarily large and their
incentives might be quite complicated
and kind of hard to model directly but
you still want kind of algorithmic ways
of kind of predicting what will happen
or influencing what will happen in the
design of platforms so what to you is
the most beautiful idea that you've
encountered in game theory there's a lot
of them I'm a big fan of the field I
mean you know I mean technical answers
to that of course would include Nash's
work just establishing that you know
there there's a competitive equilibrium
under very very general circumstance
which in many ways kind of put the field
on a firm conceptual footing because if
you don't have equilibria it's kind of
hard to ever reason about what might
happen since you know there's just no
stability so just the idea that
stability can emerge when there's
multiple who or that it means not that
it will necessarily emerge just that
it's possible right it's like the
existence of equilibrium doesn't mean
that sort of natural iterative behavior
will necessarily lead to it in the real
world yeah maybe answering a slightly
less personally than you asked the
question I think within the field of
algorithmic game theory perhaps the
single most important kind of technical
contribution that's been made is the
real the the realization between close
connections between machine learning and
game theory and in particular between
game theory and the branch of machine
learning that's known as no regret
learning and and this sort of provides a
freight a very general framework in
which a bunch of players interacting in
a game or a system each one kind of
doing something that's in their
self-interest will actually kind of
reach an equilibrium and actually reach
an equilibrium in a you know a pretty
you know a rather you know short amount
of steps so you kind of mentioned acting
greedily can somehow end up pretty good
for everybody or pretty bad or pretty
bad it will end up stable yeah right and
you know stability or equilibrium by
itself is not that is not necessarily
either a good thing or a bad thing so
what's the connection between machine
learning and the ideas well if we kind
of talked about these ideas already in
in kind of a non-technical way which is
maybe the more interesting way of
understanding them first which is you
know we have many systems platforms and
apps these days that work really hard to
use our data and the data of everybody
else on the platform to selfishly
optimize on behalf of each user okay so
you know let me let me give what the
cleanest example
which is just driving apps navigation
apps like you know Google Maps and ways
where you know miraculously compared to
when I was growing up at least you know
the objective would be the same when you
wanted to drive from point A to point B
spend the least time driving not
necessarily minimize the distance but
minimize the time right and when I was
growing up like the only resources you
had to do that were like maps in the car
which literally just told you what roads
were available and then you might have
like half hourly traffic reports just
about the major freeways but not about
side roads so you were pretty much on
your own and now we've got these apps
you pull it out and you say I want to go
from point A to point B and in response
kind of to what everybody else is doing
if you like what all the other players
in this game are doing right now here's
the the you know the the route that
minimizes your driving time so it is
really kind of computing a selfish best
response for each of us in response to
what all of the rest of us are doing at
any given moment and so you know I think
it's quite fair to think of these apps
as driving or nudging us all towards the
competitive or Nash equilibrium of that
game now you might ask like well that
sounds great why is that a bad thing
well you know it's it's known both in
theory and with some limited studies
from actual like traffic data that all
of us being in this competitive
equilibrium might cause our collective
driving time to be higher may be
significantly higher than it would be
under other solutions and then you have
to talk about what those other solutions
might be and what what the algorithms to
implement them are which we do discuss
in the kind of game theory chapter of
the book but but similarly you know on
social media platforms or on Amazon you
know all these algorithms that are
essentially trying to optimize our
behalf they're driving us in a
colloquial sense towards some kind of
competitive equilibrium and you know one
of the most important lessons of game
theory is that just because we're at
equilibrium doesn't mean that
there's not a solution in which some or
maybe even all of us might be better off
and then the connection to machine
learning of course is that in all these
platforms I've mentioned the
optimization that they're doing on our
behalf is driven by machine learning you
know like predicting where the traffic
will be predicting what products I'm
gonna like predicting what would make me
happy in my newsfeed
you