ML Wiki
Machine Learning Wiki - A collection of ML concepts, algorithms, and resources.

Game Theory

Game Theory

In Game Theory the decision of a decision maker and its consequences are based on somebody else’s decisions

Game

A ‘‘game’’ is a ‘‘strategic interaction’’ (in economics, social studies, networking, etc) between two or more ‘‘self-interested agents’’

Each agent has his/her own opinions and preferences

The ‘‘outcome’’ of a game depends on what all agents do

  • what actions a game player takes?
  • all users act in the same way?
  • is there a global behavior pattern?
  • if players can communicate, what effect it will have?
  • repetitions?
  • does it matter if opponents are rational?

Example:

  • Suppose we have two airline companies $P_1$ and $P_2$
  • They are both thinking about about opening a new destination
  • Both consider two options: either make tickets cheap or make them expensive
  • Clearly if $p_1$ decides to sell cheap tickets while $p_2$ - to sell expensive tickets, everybody will buy from $p_1$

So we can depict it with the following pay-off matrix

  • a cell represents consequences of the decision that both players take

| $p_2 \leftarrow$
$p_1 \downarrow$ | 500 | 200 | 500 | (50, 100) | (-100, 200) || 200 | (150, -200) | (-10, -10) | We see that:

  • if both agree on cheap tickets - both will have profits
  • if $p_2$ sells expensive tickets and $p_1$ cheap ones, all go to $p_1$ and $p_2$ will have losses
  • the same with $p_1$ and $p_1$
  • if both decide on expensive tickets - nobody will buy them and they both will experience losses

This is a variation of the Prisoner’s Dilemma, an example of Normal Form Game

Types of Games

There are many types of games:

Rationality

It is often assumed that agents behave rationally:

Examples

Paradoxes

Pure Competition Games

Cooperation Games

General Games

Other

Sources