Hi there, I am doing an online course - Introduction to Game Theory and Mechanism Design. The inspiration behind this series of posts is my assignment's due date (tomorrow). These posts are intended to serve as notes for the past, present, and future me. Albeit, if you do like them, I would be really glad! :)

What is Game Theory?

We come across "games" all the time in our lives - sports, business deals, wars, negotiations with your sibling on who gets the last slice of pizza, etc). Game theory deals with multi-agent decision-making and the outcome(s) of any game. The participants are called players or agents and they may potentially have conflicting objectives. Their decision affects your outcome.

Objective of Game Theory & Mechanism Design

Given a game, game theory helps to find the most probable outcome or payoffs of the game and utilities (result) for each player. It is an analysis and predictive approach. There is another branch called Mechanism Design which deals with building a game that will yield a desirable outcome. It is a synthesis and prescriptive approach. We will discuss mechanism design later, let's focus on game theory for now.

Neighboring Kingdom's Dilemma

Let's say there are two neighboring kingdoms creatively named Kingdom A and Kingdom B. Both have to take a decision on where to invest their wealth. They have two options:

1. Farming 🌽: Will help feed their people
2. War ⚔️: Ransack the other kingdom and capture their wealth while defending yourself

[Assume that these are the only two options available to both kingdoms and they cannot choose both options. Of course, there are other possibilities but we will discuss them later. ]

Outcomes dependent on every player's action

Now, if you're one of the kingdoms it is important to note that the outcome of this scenario or game cannot be determined by your own actions alone. For e.g. if you decide to invest in agriculture, you cannot be sure what will be your payoff (outcome) because if the other kingdom comes to fight, you are doomed (since you didn't invest in warfare and would not be able to defend yourself).

Thus, the outcome depends not only on the actions picked by one of the players but on the action profile i.e. actions picked by both the agents.

Utility Matrix

Let's represent this more succinctly in the form of a utility matrix:

The utility matrix represents payoffs for different scenarios based on the actions of two players viz. Kingdom A and Kingdom B. Numbers in each cell are representative of the payoff (1st number is the utility of A and 2nd number is the utility of B). The 2 rows represent the available actions to Kingdom A and similarly, the 2 columns represent the available actions to Kingdom B.

If both the kingdoms decide to invest in agriculture then the utility of each player would be 5. Nobody attacks the other, both are prosperous. When both kingdoms are at war with each other, they would try to defend themselves as they would've invested in warfare. Thus, both will get some amount of payoff and not lose everything. The utilities will be 1 for each of the players in this case.

But imagine if A decides war and B decides agriculture, A would get all of B's wealth so the utility will be higher than if A went for agriculture. B will lose everything since it would not be able to defend itself. Thus, A gets a utility of 6 and B gets a utility of 0 in this case. Symmetrically, if the roles are reversed A will have a utility of 0, and B will have a utility of 6 for the Agriculture x War scenario.

What is a "reasonable" outcome?

Let's say agent A is trying to select the optimal strategy. It checks what are its utilities if agent B chooses either of her actions. So, if B chooses agriculture, A gets a utility of 5 (highlighted in light green) should it choose agriculture too albeit it gets a utility of 6 (highlighted in dark green) if it goes to war. Hence, war is a better option for A given that B selects agriculture.

Similarly, if B chooses war, it is prudent for A to go to war as well since it gets a utility of 0 should it choose agriculture and a utility of 1 if it fights the war.

We can extrapolate a similar conclusion for B and its optimal choice as war if A was choosing agriculture as B's utility goes from 5 -> 6.

...and if A chooses war, it's still war for B i.e. utility 0 -> 1.

This is SPARTAAAA

Thus, you can conclude that War x War is the most predictable outcome no matter what the other player chooses. Note that it is not the most optimal outcome which is (5,5) i.e. Agriculture x Agriculture. But personal greed and no communication between the agents is leading to a worse outcome for this kind of game.

If you were familiar with game theory earlier, you must've observed that the above example is similar to a more famous example of Prisoner's Dilemma.

Definitions

Game: A game is a formal representation of the strategic interaction between multiple agents called players.

Actions: The choices that are available to the players are called actions. (For e.g. agriculture & war in the Neighboring Kingdom's Dilemma example)

Strategy: The mapping from the state of the game -> to the set of actions.

Representation: Depending on the context, games can be represented in many ways: Normal Form, Extensive Form, Repeated, Stochastic, etc.

Game theory: The formal study of strategic interaction between players that are rational and intelligent.

A player is rational if she picks actions to achieve her most desired outcome. For e.g. maximizing her payoff (like we did in the example earlier).

A player is intelligent if she knows the rules of the game perfectly and picks action considering that there are other rational and intelligent players in the game.

Intelligence implies that the player has sufficient computational ability to find the "optimal" action (against other players). This will be important when we discuss Equilibrium later.

That's all for now, hopefully, this gives you an idea about what game theory is and how we go about it. We will discuss more in detail representation, common knowledge, and its implications in the next post.