What is Game theory in AI? Nash Equilibrium

Game theory and Artificial Intelligence have the origin from similar roots, they have provided a broad area of research in different directions from the past few years.

 

In recent research, a deep connection between these two fields is noticed with a great range of applications especially, within that framework, researchers emphasize the various issues coming in filing the bridge between them[source]. 

 

The game theory has a concrete impact while to configure and plan in designing an AI model. In reality, when the linear machine learning deeply deals with a one-dimensional variable, the significant energy in AI models released with various facets and applications of game theory.

 

To understand how game theory promotes power to AI models, it is very essential to understand the basic and working methodology of game theory, and same we will discuss in the blog.

 

 

Topics Covered

 

• What is game theory?

• Types of Games theory

• Nash-Equilibrium

• Illustration of Nash Equilibrium 

• AI with Game Theory

• Limitations with Games Theory

 

 

What is Game Theory?

 

Game theory is the science of strategy that determines suitable actions that players should take  mathematically and logically in order to secure the best-favorable results for themselves in a wide arena of games.

 

Game theory was initially produced by John Von Neumann and Oskar Morgenstern in 1944 as a mathematical theory, Neumann published “ The Theory of Games and Economic Behaviour “ in which Morgenstern is the co-author.

 

But in originality, the famous economists named John Nash, John Harsanyi, and Reinhard Selten received the Nobel Prize in 1994 for Economics as they further developed game theory related to economics.

 

“When you strip away the genre differences and the technological complexities, all games share four defining traits: a goal, rules, a feedback system, and voluntary participation.” ― Jane McGonigal,

 

In layman terms, a Game theory is the scientific study of imperative and interdependent decision making, a framework in which players understand the social situation in the form of competition. The game theory aims at serving as a model of interactive conditions within rational players.

 

The term “rational” signifies here that each player thinks another player as rational and has the same level of knowledge and understanding as to the first player poses. According to rationality, each individual player always gives preference to higher reward/payoff.

 

All games have the metrics :

• Rules, to monitor the conduct of the players

• Pay-offs, such as win, lose or draw

• Strategies that affect the process of decision making.

 

For example, the business objective of game theory to assist/guide organizations when they face several strategic choices that authorize their capability to obtain desired pay-off, such as decisions to take 

• On price and output in terms of raise, lower and hold.

• On products, if to keep existing products, or develop new ones

• On promoting products whether to spend more over advertising, spend less, or keep spending constant, and many more. 

 

(Recommend blog: What is Group Theory?) 

---

Applications of the Game Theory in various domain

---

Game theory has a spacious area of applications that include psychology, biology, politics, economics, business, science, etc. Instead of many such advances and applications, game theory is still developing science and open wide bandwidth for researchers.

 

 

Types of Games theory

 

The game theory includes a wide bandwidth of the games depending upon the players and their actions, some are most relevant and well-known covers some of them as; Single-move Game including an example of stock purchasing, Repeated Games having a classical example of Prisoner’s dilemma, Sequential Game such as Chess and Go.

 

Let’s plunge more deeply into these terms with further division of game types;

 

1. Cooperative and Non-cooperative Games: In cooperative games, participants can secure connections e.g. Negotiations for maximizing the chances to win in the game, whereas, in non-cooperative games, participants can’t prefer supports and agreement(e.g. War).

 

2. Symmetric and Asymmetric Games: In symmetric games, a goal is fixed for all the participants, but their planning, strategies and implement actions for achieving goals, can only determine who is going to win the game(e.g Chess), in opposite to that, Asymmetric games are having the participants who consider different goals and  incompatible strategies in order to accomplish goals. 

 

3. Perfect and Imperfect Information Games: In perfect information games, a participant can see the actions or decisions of other participants (e.g Chess), instead, in imperfect information games, one participant can’t see other’s moves, others’ actions are hidden (e.g. Poker).

 

4. Simultaneous and Sequential Games: In simultaneous games, every player can make moves at the same time, rather, in sequential games, the individual player is conscious of the other players’ prior move (e.g. Board games).  

 

5. Zero-sum and Non-Zero sum Games: In zero-sum games, a player’s gain may cause the loss to other players, alternatively, in non-zero sum games, the gain to one player gives benefits to all the players. 

 

(Must check: Big data Applications in Sport Industry)

 

 

What is the Nash-Equilibrium?

 

Nash equilibrium is that outcome where no player can increase his payoff by changing his decisions, i.e. the player wouldn’t want to change his decision or action once taken if he changed his action from Nash Equilibrium, then it is reflected that he is not playing ideally.

 

It is also states as the action of “no regrets” in the sense that once the decision has taken, the player will have no regret after accounting the consequence of the decision. Not in all the conditions, the Nash equilibrium is reached, but over time, once it is reached, it won’t get deflected. 

 

After we learn how to get the Nash Equilibrium, can you guess any single move would affect the situation?

 

Well, it doesn’t, this is why the Nash Equilibrium is also referred to as “no regret “ condition. There can be more than one state of nash equilibrium in the game. This state generally arises in the matter of more complex variables inside a game than the two decisions made by two players.

 

With the reference of types of games discussed in the above section, in simultaneous games that get reproduced by time, after some trial and error state of multiple equilibria is reached.

 

For example, when two firms are deciding prices for huge replaceable products, the same scenario of multiple decisions came most of the time in the business world before reaching the final decision, like ticket fare, eatable product.

 

 

Illustration of Nash Equilibrium With the Example of a Prisoner’s Dilemma

 

One of the best classical examples of the Nash Equilibrium is the Prisoner’s Dilemma,

 

Let’s assume two culprits, Henry and Dave, get arrested for a crime, they are now in confinement and don’t have any scope to communicate with each other. Below is the picture in which the flash of the conditions they both are facing when asked to confess the crime. 

---

A picture of the Prisoner’s dilemma 

---

 

Flashback, they are arrested, both have two choices either remain silent or confess the crime, so there would be four outcomes, such as

• [silent, silent],
• [confess, silent],
• [silent, confess], and
• [confess, confess].

 

Above, these four outcomes become the game matrix which I have highlighted in the picture. It is a clear presentation of what they are thinking and how much payoff they get. 

Making it more clear; in this scenario, the payoff is reflected in Henry and Dave’s payoff, along with the row, actions of Henry are presented and along the column, the actions of Dave are presented.

 

Have you noticed payoffs have negative representation? yes, you are right somewhere, they did a crime, so their actions tie them with a predetermined number of years of imprisonments if likely.

 

"In general, If either one of the prisoners confesses, then the other prisoner gets imprisonment of 15 years while confessor sets free, if both of them confess the crime, they get imprisonment of 10 years, and if both don’t confess, then both of them get imprisonment for a year. "

 

However, this is the outcome of the present situation of prisoners, also which is clearly be observed in the picture. As neither of the prisoners is aware of others’ actions, so the dilemma for prisoners comes into the picture. 

 

Now let’s talk about the what is Nash Equilibrium here, it is very obvious to think if they would help each other and stay silent. But then, they might be in the process of thinking to minimize the imprisonment they receive as not aware of each other actions. This is actually what is happening in Henry’s mind, 

 

“ if Dave confesses and I confess, I would get 10 years of imprisonment which is better than 15 years of imprisonment, if Dave doesn’t confess and I confess, it is better for me to walk free than to spend a year in jail.”

 

Henry finds in both the conditions “whether dave confess or not” if he confesses he can get a minimum year of prisonments. On the other hand, Dave is also thinking the same somewhere.

 

“Their behavior is based on your own, just as your behavior is being influenced by theirs.”― Brian Christian, Tom Griffiths

 

And the thinking process of both to them makes a perfect sense if both take a decision to confess, and the condition of “Nash Equilibrium” gets achieved where they no “no regret” on their decisions. As a result, [confess, confess] comes out to be the best strategy for them.

 

 

AI With Game Theory

 

A variety of games like poker, solitaire, chess, ludo, etc. are quite popular games amongst the games that are playing digitally on laptops, phones, tablets, etc. All the games have a clear set of rules and instructions, one has to play with rules to win the game.

 

To make these games digitally, one has to develop some algorithms that consider the number of players and rules, hence the game theory gets deployed.

 

Majority of popular games which we play digitally are developed with the help of Artificial Intelligence and Game theory, game theory is not just confined to games, it also has huge applications of AI like Generative Adversarial Networks (GANs), machine learning algorithms, manipulation-resistant system, multi-agent AI system, imitation and reinforcement learning, etc.

 

Any problem can be considered into two parts, first one is when a single person is trying to do a job, and the second one is when many people are trying to do the same job like in a game when the decision of one person affects the other one. The concept of game theory is required to solve numerous dynamic problems. 

 

 

How is Game Theory helping AI?

 

In Multi-agent Reinforcement Learning, game theory helps in improving the traffic flow of an area by using AI-governed Self-Driving cars. Each of the cars has perfect interaction with the external environment, now think, what if cars think as a group, things get more complicated.

 

Consider a car may get conflict with the other car because to follow a specific route might be convenient for them for traveling. This state can easily be modeled with game theory.

 

In terms of game theory, cars act as players and Nash Equilibrium is the point of collaboration among different cars. 

 

---

AI-models as robots in human-environment

---

Reinforcement learning intends to make an agent learn by having interaction with the environment either real or virtual, or augmented reality

 

Suppose an agent is interacting with a random environment and learn a policy through a reward or a punishment, but if multiple agents are put up in the same environment, this is no longer possible. It is because now interaction is taken place between multiple agents and the environment.

 

Thereby, modeling of a system with multiple agents is a difficult task, an increase in a number of agents may result in increasing the possible paths exponentially that agents use to interact with each other, this issue can be fixed with game theory. 

 

 

Limitations of Games Theory

 

Games theory has many applications based on its functionality but each invention also has some drawback, if you talk about the issues with the games theory, 

• It counts the hypothesis that agents are rationals that are self-centered, self-interested, and large profit-makers.

 

We are kind of social-beings who believe in cooperation and caring about the others, either at own expense.

• Games theory cannot value the fact that we may fall into Nush Equilibrium sometimes and other times not, it totally depends upon the social situation and other agents. 

 

 

Conclusion

 

At last, you must enjoy reading the blog, I assume you have got the fundamentals of the game theory. We have covered the essential topics of game theory and its connection and utilization with AI.

 

Game theory also has various applications in machine learning that impacts everyday life and real-world implementations. There are many real-life cases for surmising the basic thought of game theory. We are uniformly in the game of our life that reshaped by the actions and decisions made by others.