What Is the Algorithmic Game Theory? Explained With Examples

# What Is the Algorithmic Game Theory? Explained With Examples

Last updated:
1st Oct, 2020
Views
8 Mins
View All

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.

## 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.

## Explore our Popular Data Science Courses

 Executive Post Graduate Programme in Data Science from IIITB Professional Certificate Program in Data Science for Business Decision Making Master of Science in Data Science from University of Arizona Advanced Certificate Programme in Data Science from IIITB Professional Certificate Program in Data Science and Business Analytics from University of Maryland Data Science Courses

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.

## Top Data Science Skills to Learn

 SL. No Top Data Science Skills to Learn 1 Data Analysis Programs Inferential Statistics Programs 2 Hypothesis Testing Programs Logistic Regression Programs 3 Linear Regression Programs Linear Algebra for Analysis Programs

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

## Read our popular Data Science Articles

 Data Science Career Path: A Comprehensive Career Guide Data Science Career Growth: The Future of Work is here Why is Data Science Important? 8 Ways Data Science Brings Value to the Business Relevance of Data Science for Managers The Ultimate Data Science Cheat Sheet Every Data Scientists Should Have Top 6 Reasons Why You Should Become a Data Scientist A Day in the Life of Data Scientist: What do they do? Myth Busted: Data Science doesn’t need Coding Business Intelligence vs Data Science: What are the differences?

upGrad’s Exclusive Data Science Webinar for you –

## 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.

#### Rohit Sharma

Blog Author
Rohit Sharma is the Program Director for the UpGrad-IIIT Bangalore, PG Diploma Data Analytics Program.
Get Free Consultation

Select Course
Select
By clicking 'Submit' you Agree to

#### Data Science Skills to Master

1What is the significance of game theory?

Game theory revolutionized economics by overcoming major problems in prior quantitative economic models. Economists commonly utilize game theory to better understand the behavior of oligopolistic businesses. When firms engage in certain actions, such as price fixing and collusion, it can help predict the likely outcomes.

2In game theory, what is pure strategy?

Game theory is the study of interactive decision-making in which each participant's or player's fate is determined by the actions of all. When deciding your course of action or 'strategy' as a player in such a game, you must consider the decisions of others. A comprehensive specification of how a player will play a game is provided by a pure strategy. Pure strategy may be regarded as a plan that is based on the observations made throughout the game. It, in particular, influences how a player will respond in any given circumstance.

3What is game theory, and why does it matter to economists?

Game theory is a tool used by economists to analyze, predict, and explain human behavior. It's been used to research auctions, bargaining, merger pricing, oligopolies, and a variety of other topics. It has progressed to multiplayer, positive-sum games, in which all participants may benefit from 'gains through trade' (exchange) between individuals.

## Suggested Blogs

20771
Attending a PySpark interview and wondering what are all the questions and discussions you will go through? Before attending a PySpark interview, it’s

05 Mar 2024

5056
Data science is an important part of many industries today. Having worked as a data scientist for several years, I have witnessed the massive amounts

by Harish K

28 Feb 2024

5145
Data science training is one of the most hyped skills in today’s world. Based on my experience as a data scientist, it’s evident that we are in

by Harish K

28 Feb 2024

5071
A data science course syllabus covers several basic and advanced concepts of statistics, data analytics, machine learning, and programming languages.

by Harish K

28 Feb 2024

17536
Python is one of the most popular programming languages. Despite a transition full of ups and downs from the Python 2 version to Python 3, the Object-

27 Feb 2024

10736
Introduction Data mining is the process in which information that was previously unknown, which could be potentially very useful, is extracted from a

27 Feb 2024

80454
What is a Data Analytics Lifecycle? Data is crucial in today’s digital world. As it gets created, consumed, tested, processed, and reused, data goes

19 Feb 2024

138814
The arrangement of data in a preferred order is called sorting in the data structure. By sorting data, it is easier to search through it quickly and e