Game Theory and Artificial Intelligence
Continuing our series of articles about the different foundational aspects of artificial intelligence(AI), today I would like to focus on game theory. Games have been one of the most visible areas of progress in the AI space in the last few years. Chess, Jeopardy, GO and, very recently, Poker are some of the games that have been mastered by AI systems using break through technologies. From that viewpoint, the success of AI seems to be really tied to the progress on game theory.
While games are, obviously, the most visible materialization of game theory, is far from being the only space on which those concepts are applied. From that perspective, there are many other areas that can be influenced by the combination of game theory and AI. The fact us that most scenarios that involve multiple “participants” collaborating or competing to accomplish a task can be gamified and improved using AI techniques. even though the previous statement is a generationazation, I hope it conveys the point that game theory and AI is a way to think and model software systems rather than a specific technique.
From a conceptual standpoint, there are several aspects of game theory that could help better understand AI systems. Let’s explore a few of those concepts.
AI systems that could be improved using game theory require more than one participant which narrows the field quite a bit. For instance, a sale forecast optimization AI systems such as Salesforce Einstein is not an ideal candidate for applying game theory principles. However, in a multi-participant environment, game theory can be incredibly efficient. In those settings, game theory can serve two fundamental roles:
— Participant Design: Game theory can be used to optimize the decision of a participant in order to obtain the maximum utility.
— Mechanism Design: Inverse game theory focus on designing a game for a group of intelligent participant. Auctions are a classic example of mechanism design.
There are many other goals of game theory but they can all be seen as variations of the ones listed above.
Types of Games
Game theory covers a large spectrum of games. Some of the most relevant and well-known include:
— Single-Move Games: This type of game is based on each player taking a single action without knowing the action of any other participant. Stock purchasing is a classic example of single move games.
— Repeated Games: This type of game faces players with the same choice multiple times but, each time, each player has knowledge about the previous decision of the other players. Many repeated games are variations of single move games with repetitions.
— Sequential Games: As you might have guessed, sequential games model the environment as a series of turn which can produce new and different states. Chess, GO are examples of sequential games.
Remember John Nash’s story famously depicted on “A Wonderful Mind” ? Well Nash’s contributions have been at the center of game theory for decades. Specifically, the Nash Equilibrium theory proves that every game can achieve a point on which no player can benefit from switching strategy assuming than the other players stay with their current strategy. That state is known as Equilibrium. Nash theory has become an essential element o game modeling.
Inversed Game Theory
In many cases, the problem is not to optimize the participant’s strategy on a game but to design a game around the behavior of rational participants. this is the role of inversed game theory. Auctions are considered one of the main examples of inverse game theory.
I will cover other aspects of game theory on future posts. I hope this content can give you an idea of the influence of game theory artifacts in the AI space.