Game Theory in AI

Game Theory in AI 

By Azfar Uzair, Aashay More, Pranav Ratnaparkhi, Swetank Raj, Prathamesh Yadav

Introduction:

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 is some of the games that have been mastered by AI systems using breakthrough technologies. From that viewpoint, the success of AI seems to be tied to the progress of game theory.[1]

While games are the most obvious expression of game theory, they are far from the only domain in which those principles are used. From that viewpoint, the integration of game theory and AI can have an impact on a variety of different domains. Most scenarios involving several "participants" working together or competing to complete a job may be gamified and enhanced utilizing AI approaches.[1]

 

Types of games:

Symmetric vs. Asymmetric.

The symmetry of a game is one of the most basic categories.

A symmetric game is one in which each participant has identical aims and the outcomes are completely determined by the techniques used.

Chess is one of the most well-known symmetric games.

Because participants typically have distinct and even opposing aims, many of the scenarios we witnessed in the actual world lack the mathematical elegance of symmetry.

Business negotiation is an asymmetric game in which each participant has distinct aims and analyses the outcomes from a different viewpoint (ex: winning a contract vs. minimizing an investment).[2]

 

Fig 1. Example of Symmetric: Checkers.

(Image Source: https://images.unsplash.com/photo-1551198581-aec5c1556d7c?ixlib=rb-1.2.1&ixid=MnwxMjA3fDB8MHxzZWFyY2h8Mnx8Y2hlY2tlcnN8ZW58MHx8MHx8&w=1000&q=80)

 

 

Fig 2. Example of Asymmetric: Monopoly.

(Image Source: https://i.vimeocdn.com/video/912647937-dcd7547d62a00baaba5672c506edfa45e2f37c15b325aecc7a4f49ced1207031-d_640x360.jpg)

 

Perfect vs. Imperfect Information

Another key way to categorise games is by the sort of data offered. A perfect information game is one in which each player can observe the moves of the other player. Chess is an example of a perfect information game once again. Many current interactions take place in contexts where each player's moves are hidden from the other players, which game theory describes as incomplete information games. Imperfect information games may be found everywhere, from card games like poker to self-driving automobile scenarios.[2]

 

Fig 3. Example of a Perfect Information game: Chess.

(Image Source: https://images.unsplash.com/photo-1523875194681-bedd468c58bf?ixlib=rb-1.2.1&ixid=MnwxMjA3fDB8MHxzZWFyY2h8MXx8Y2hlc3N8ZW58MHx8MHx8&w=1000&q=80)

 

 Fig 4. Example of Imperfect Information: Poker (blackjack).

(Image Source: https://w0.peakpx.com/wallpaper/240/226/HD-wallpaper-blackjack-card-games-playing-cards-poker.jpg)

 

Cooperative vs. Non-Cooperative

A cooperative gaming setting is one in which the various players can form teams to optimize the outcome. Negotiations are frequently fashioned after cooperative games. Non-cooperative situations are those in which participants are not allowed to establish coalitions. Non-cooperative games are reflected by wars. [2]

 

Fig 5. Example of Cooperative games: Football 

(Image Source: https://cdn.tabletopia.com/static/files/007/807/gbmcnf5xxwcmiigcytodc4.png?maxwidth=1600&maxheight=900&format=jpg&quality=80)

 

 

Fig 6. Example of Non-cooperative game: Battleship board game

(Image Source: https://i.ytimg.com/vi/4gHJlYLomrs/maxresdefault.jpg)

 

Simultaneous vs. Sequential

A sequential game takes place in a setting where each participant is aware of the previous activities of the other players. The majority of board games are sequential. Simultaneous games are settings in which both players can do actions at the same time. Simultaneous games include things like stock trading.[2]

Fig 7. Example of Simultaneous games: Four in a row.

(Image Source: https://is5-ssl.mzstatic.com/image/thumb/Purple118/v4/aa/a5/6b/aaa56bb2-e570-4a5d-01b8-0a6dbf62d57f/pr_source.png/576x768bb.png)

 

Zero-Sum vs. Non-Zero-Sum

A zero-sum game is a situation in which one player's gains always result in losses for the other participants. Zero-sum games include board games, for example. In situations when numerous players might gain from the actions of one player, non-zero-sum games are common. A non-zero-sum game is an economic transaction in which numerous participants work to enhance the size of the market.[2] 

 

Novel Ideas in Game Theory which might be Influencing Machine Learning:

Multi-agent AI systems are one of the maximum charming regions of studies withinside the AI ecosystem. Recent improvements in regions including multi-agent structures are pushing the limits of game concept counting on a number of the maximum state-of-the-art thoughts withinside the field. Here are a few examples of game concept sub-disciplines that might be very found in present-day device learning.

 

Mean Field Games

Mean Field-Games(MFG) is a quite new region in the game theory space. The MFG theory turned into simply evolved in 2006 as a part of a chain of impartial papers posted with the aid of using Minyi Huang, Roland Malhamé, and Peter Caines in Montreal, and with the aid of using Jean-Michel Lasry and Fields medalist Pierre-Louis Lions in Paris. Conceptually, MFG accommodates techniques and strategies to observe differential video games with a huge population of rational players. These marketers have possibilities now no longer best approximately their state (e.g., wealth, capital) however additionally at the distribution of the final people withinside the populace. MFG theory research generalized Nash equilibria for those systems.

A conventional instance of MFG is how organizations of fish in an education swim withinside the identical path and in a coordinated matter. Theoretically, this phenomenon is tough to give an explanation for however it has its roots in the truth that a fish reacts to the conduct of the nearest group. More specifically, every fish does now no longer care approximately every one of the opposite fishes for my part however, rather, it cares approximately how the fishes nearby, as a mass, globally move. If we translate that into mathematical terms, the response of fishes to the mass is defined by the Hamilton-Jacobi-Bellman equation. On the opposite hand, the aggregation of the movements of the fishes which determines the movement of the mass corresponds to the Fokker-Planck-Kolmogorov equation. The mean-discipline game theory is the mixture of those equations.

  

Stochastic Games

Stochastic video games date again to the Fifties and had been delivered with the aid of using Nobel-prize winner economist Lloyd Shapley. Conceptually, stochastic video games are performed with the aid of using a finite wide variety of gamers on a finite country space, and in every country, every participant chooses one in all finitely many movements; the ensuing profile of movements determines praise for every participant and a chance distribution on successor states.

A conventional shape of stochastic video games is the dining philosophers hassle wherein there are n + 1 philosophers (n ≥ 1) sitting at a spherical desk with a bowl of rice withinside the middle. Between any philosophers who take a seat down after every different lie a chopstick, which may be accessed with the aid of using each of them. Since the desk is spherical, there are as many chopsticks as there are philosophers; To consume from the bowl, a logician desires to accumulate each of the chopsticks he has to get entry to. Hence, if one logician eats, then his pals can't consume at an identical time. The lifestyle of a logician is alternatively easy and includes wondering and eating; to survive, a logician desires to suppose and consume once more and once more. The project is to lay out a protocol that lets all the philosophers survive.

 

Fig 8. Dining philosophers problem.

(Image Source: https://www.thecrazyprogrammer.com/wp-content/uploads/2017/06/Dining-Philosophers-Problem.png)

 

Inverse Game Theory

In many circumstances, the issue is not to maximise a game participant's strategy, but to construct a game around logical participant behaviour. This is where inverse game theory comes in. Auctions are one of the most common applications of inverse game theory.

The rise of AI and multi-agent systems has sparked a boom in game theory. The ideas of game theory, which were developed by computer science giants such as Alan Turing and John Von Neumann, are now at the heart of some of the world's most intelligent systems, and current advances in AI are also helping to progress game theory research.[2]

Evolutionary Games

The Darwinian idea of evolution is the basis for Evolutionary Game Theory (EGT). The formalisation of competitions studied as strategies and the mathematical criteria that may be used to forecast the results of competing strategies by John Maynard Smith and George R. Price date back to 1973. EGT is the application of game theory principles to situations in which a population of agents with different strategies interact over time to generate a stable solution through a selection and duplication process.[3]

The central idea of EGT is that many behaviours require the interaction of numerous individuals in a population, and the success of any one of these individuals is determined by how its strategy interacts with the strategies of others. While the traditional game theory has focused on static tactics or methods that do not vary over time, the evolutionary game theory focuses on how strategies develop over time and which types of dynamic strategies are most effective in this evolutionary process.[3]

The Hawk Dove Game, which models a fight between a hawk and a dove over a shared resource, is a famous example of EGT. Each competitor in the game uses one of the two techniques listed below:

• Hawk: Start acting aggressively and don't stop until you're hurt or your opponent backs down.
• Dove: If an opponent engages in hostile behaviour, retreat quickly.

 

If we suppose that (1) anytime two individuals engage in aggressive behaviour, conflict occurs, and both persons are equally likely to be wounded, and (2) the cost of the conflict decreases individual fitness by a constant amount, The fitness payoffs for the Hawk-Dove game can be summarised as follows: C, (3) when a Hawk meets a Dove, the Dove immediately retreats and the Hawk obtains the resource, and (4) when two Doves meet, the resource is shared equally between them, the fitness payoffs for the Hawk-Dove game can be summarised as in fig 10:

Fig 10. Hawk-Dove Game.

References:

1. A. R. Karlin and Y. Peres, Game theory, alive. Providence, RI: American Mathematical Society, 2017.

2. M. D. Davis and O. Morgenstern, Game theory: A nontechnical introduction. Mineola (New York): Dover, 2013.

 3. N. Nisan, Algorithmic game theory. Cambridge: Cambridge Univ. Press, 2013.

4. A crash course in game theory for Machine Learning: Classic and new ideas. KDnuggets. (n.d.). Retrieved January 7, 2022, from https://www.kdnuggets.com/2020/03/crash-course-game-theory-machine-learning.html