Algorithmic Game Theory

… a core concept used in Managing New Technologies and Atlas112M

Concept description

In their book The Ethical Algorithm (reference below), Michael Kearns and Aaron Roth, define algorithmic game theory as “a new field that … blends ideas and methods from classic game theory and microeconomics with modern algorithm design, computational complexity, and machine learning, with the goal of developing efficient algorithmic solutions to complex strategic interactions between very large numbers of players.”

They describe its application to navigation apps such as Google Maps and Waze (page 101):

“To illustrate how the scale and power of modern technology have made algorithmic game theory relevant, let’s consider an activity that many people engage in every day but may never have thought about as a “game” before: driving a car. Suppose you live in a busy metropolitan area with congested roads, and each day you must drive from your house in the suburbs to your workplace downtown. There is a complex network of freeways, highways, streets, thoroughfares, and back roads you must navigate, and the number of plausible routes you could take might be very large indeed. …

“If you think about it, on a moderately long commute in a busy city the number of distinct routes you might take or at least try over time could be in the dozens or even hundreds. Of course, these different routes might overlap to varying degrees – maybe many of them use the freeway, and if you live on a cul-de-sac, they will always start by getting off your street – but each route is a distinct path through your local network of roads. In game theory terminology, your “strategy space” – the possible actions you might choose – is much larger than in simple games like Rock-Paper-Scissors, where by definition you only have three actions available. So you have a lot of choices; but what makes this a “game”? It’s the fact that if you’re like most commuters, your goal or objective is to minimize your driving time. But the driving time on each of your many possible routes depends not just on which one you choose but also on the choices of all the other commuters. How crowded each route is determines your driving time as much or more than the length of the roads, their traffic lights, speed limits, and other fixed aspects. The more drivers who choose a given road, the longer the driving time for all routes that use that road, making them less attractive to you. Similarly, the fewer drivers there are on a road, the more you might want to choose a route that uses it (as long as the other segments on the route aren’t too busy).

“The combination of your hundreds of possible routes with the choices made by the tens of thousands of other commuters presents you with a well-defined, if mind-boggling, optimization problem: pick the route with the lowest total driving time, given the choices of all the other drivers. This is your “best response” in the commuting game. …

“Note that while the complexity of this game is much greater than something like Rock-Paper-Scissors, the fundamental commonality is that the payoff or cost of any individual player’s choice of action depends on the action choices of all the players. There are important differences as well. In Rock-Paper-Scissors the two players have the same payoff structure, whereas if you and I live and work in different places, our cost structures will differ (even though we still both want to minimize driving time for our own commute). And if you and I commute at different times of day, we aren’t really even in the same round of the game. But these differences don’t alter the fundamental view of commuting as just another (albeit very complex) game. And this means that as with Rock-Paper-Scissors …, it makes sense – from both qualitative and algorithmic perspectives – to discuss its equilibrium, whether it is “good” or “bad,” and whether there might be a better outcome.”

Kearns and Roth go on to describe other applications (pages 126-127):

“[W]e have deliberately chosen to illustrate the interplay between individual preferences, collective welfare, game theory, and algorithms through examples with which most of us have daily experience, such as driving, shopping, or reading news. But there are many more specialized settings in which algorithmic game theory has long played a central role in highly consequential decisions.

“One such setting is broadly known as matching markets in economics. While this phrase may bring to mind dating apps …, matching markets are usually found in much more formal scenarios in which we want to pair up individuals with each other, or individuals with institutions. One long-standing application area is medical residency hiring, in which the approach we’ll describe is implemented as the National Resident Matching Program …” (NRMP, affectionately known as “The Match”).

Atlas topic, subject, and course

Managing New Technologies (core topic) in Information and Technology Management and Atlas112M Management of Human, Information, and Technology Resources.

Sources

Michael Kearns and Arron Roth (2019, The ethical algorithm: the science of socially aware algorithm design, New York: Oxford University Press.

Page created by: Ian Clark, last modified 2 March 2021.

Image: Michael Kearns and Arron Roth (2019, The ethical algorithm: the science of socially aware algorithm design, New York: Oxford University Press., page 104, accessed 2 March 2021.