What Is the Algorithmic Game Theory? Explained With Examples

In 1999, when Nisan and Ronen contributed their ideas to a paper, the world witnessed a new Algorithmic Mechanism Design concept. It attempts to negate The Price of Anarchy, where self-interest always results in a degraded system. 

Their paper proved that multiple self-interested parties could establish a productive system at equilibrium. So, instead of looking at a degrading economy, we would look at social-welfare and revenue maximization. 

Algorithmic Game Theory (AGT) is based on the understanding of Algorithmic Mechanism Design (AMD). 

While AMD describes that self-interest could lead to a good system, AGT aims to analyze and design a strategic set-up that describes the self-interested participants’ actions. 

Before we look at how AGT works in the strategic environment, let’s look at how Game theory works!

Check out our data science training to upskill yourself

Let’s Understand Game Theory With The Help Of An Example

In a perfect world, where every move is a calculated endeavor, Game Theory would not make so much sense as it does today. 

The idea of calculating the next move of intelligent, rational citizens is both thrilling and fearsome. 

Game theory dictates that in any given social situation, the competing parties can make rational-decisions by evaluating the validity of the possibilities and estimating the competitor’s net move.

While it may seem like a gamble, theorists have reinstated an explainable strategy that uproots the belief that it is a gamble. 

The most commonly referred example is the Prisoner’s Dilemma.

Learn: Top 8 Projects Every Developer Should Try Without Fail

Prisoner’s Dilemma Explained

The premise is simple – when the police caught two convicts and questioned them about the crime, neither would break their silence. 

So, the DA decided to make this simpler by laying down three conditions in front of them, as they sit adjacently. 

• Condition 1: If neither of them confesses to the crime, they go to prison for six years.
• Condition 2: If either one rats out the other, the whistle-blower gets to roam freely while the other one goes in for ten years.
• Condition 3: If both of them confess, they go to prison for one year. 

Immediately after listening to the conditions, they are taken to a separate room to make their decisions. 

We can transfer this data in the form of a matrix, as such; 

Source

The solution to this problem is straightforward;

Each prisoner will consider telling the truth about the crime. Neither of the two can strictly say that the other one will stay quiet. So, giving in to the probability, both of them decide to confess to the crime and only go to prison for one year. 

Game theory is a potent weapon in the hands of who wields it. We can decipher even the most complex situations by understanding the nature of numbers and the social set-up placement. 

Our learners also read: Free Online Python Course for Beginners

Algorithmic Game Theory 

Now, consider a Venn diagram of Game Theory and Computer Science. Imagine a drastic increase in the level of accuracy why charting the probability of achieving answers. 

And this is what the Algorithmic Game Theory(AGT) does! 

It attempts to solve modern-day problems by striking a perfect balance between computer algorithms and game theory. 

In further simpler words, Algorithmic Game Theory attempts to define the socio-economic balance between performing a task. It also uses the principles of the Nash Equilibrium; it states that once the participants find a strategy that works for them, they will not wish to deviate from it until it stops working in their benefit. 

Let’s take a small example to understand the working of Algorithmic Game Theory.

Let’s travel back to school when we played games like Kho-Kho, Ice & Water, Chain-Cut, etc. Each of these games has a beautiful design and mechanism to play. 

Let’s consider Ice & Water, for example; 

• There are several players and one catcher. The catcher is supposed to turn everybody into ice. 
• The other players have the power to turn somebody back to water upon touching. 
• There are free-zones where the players can rest for 30 seconds.

Now, if you look carefully, you’ll see that each of these rules makes up the game’s mechanism and defines its design. 

• The players may play this game for as long as they find it interesting. Here, The Nash Equilibria describes that as long as the players find their strategy working and the game interesting, they shall play. 
• A player’s ration is not to get caught. And she acts on that ration by understanding the set-up. She implements an objective-first approach, where she wins the game by not getting caught. And this is popularly known as Mechanism Design or Reverse Game Theory. 
• Now, in case each player only considers one motive – “Of not getting caught” – and doesn’t consider the second part of it – “of saving the other players,” then this concept is called the Price Of Anarchy. It explains how the efficiency of any system will degrade due to the selfish behaviors of the players. 

Now, a plethora of more concepts emerge from the three concepts mentioned above. While they are all wholly or moderately related to game theory, they create a functional basis for algorithmic game theory. 

Checkout: 42 Exciting Python Project Ideas & Topics for Beginners

Now, the question arises: “How do we represent a strategic environment in terms of Algorithms?”

Let’s now look at how we can use Python to define a strategic environment and understand the implementation of Nashpy for a given situation. 

Imagine you’re playing a game of rock-paper-scissors with one of your friends. Each of you has either of the three options; 

• Rock
• Paper
• Scissors 

And the rubric to win the game is 

• Rock crushes scissors
• Scissors cuts papers
• Paper covers rock

And this means that if both the players present rock, it accounts for do-overs. 

We can represent this in the form of a 3×3 matrix where Aij is;

Source

Note: Here, i and j are the turns played by the two players. 

Here, 

• Zero represent that both of you played the same object (rock-rock; or paper-paper) 
• One represents that one of you trumped the other (like rock-scissors) 
• Minus One represents that either of you lost because the other one trumped you (like rock-paper) 

Now, to represent this on Nashpy, you’ll write a code that looks something like this;

Source

upGrad’s Exclusive Data Science Webinar for you –

ODE Thought Leadership Presentation

Final Thoughts

Algorithmic Game Theory is a perfect principle in the current world where competition stems out of self-interest, and the victory is the accomplishment of the self-interest. 

So, as modern-day managers, teachers, CXOs, or businessperson, if you understand the dominance of Algorithmic Game Theory, then allows me to alter the quote by Severus Snape from Harry Potter; 

“Algorithmic Game Theory can teach you how to bottle fame, brew glory, even put a stopper on losses.” 

Understanding Algorithmic Game Theory can help you deal with numbers more decisively than ever. In the current era, where we decide things to the last details to develop a sustainable plan, AGT proves to be a transformational aspect. 

We already know that Data Science can transform businesses into a lucrative arena, but AGT has the power to raise the threshold. 

Suppose you’re still skeptical about Game theory and how data science is the most lucrative and competitive profession today. 

If you are curious to learn about data science, check out IIIT-B & upGrad’s PG Diploma in Data Science which is created for working professionals and offers 10+ case studies & projects, practical hands-on workshops, mentorship with industry experts, 1-on-1 with industry mentors, 400+ hours of learning and job assistance with top firms.