GAME THEORY

This week I read about Game Theory in Morton D. Davis’ book Game Theory: A Nontechnical Introduction. I stumbled upon this book in the City Library while I was looking for a novel to read during the holidays.

What I found really interesting about Game Theory is the relationship between comprehensible strategy games and complex real-life dynamics: it has many applications in several fields including Economics, Political Science, Biology… not to mention Artificial Intelligence.

There are many cool examples in the book and no prior knowledge is really necessary to be able to (at least) grasp the basic concepts. In fact, many decisions in everyday life are taken using intuitive theoretical game models (also know as common sense).

The field of Game Theory was born in 1928 when a twenty-four-year-old John von Neumann, a Hungarian-American scientist, proved the minimax theorem in his paper Zur Theorie der Gesellschaftsspiele (Theory of Board Games). The idea behind minimax is that each player tries to maximise his minimum gain and minimise his maximum loss. This is used in two-persons zero-sum games to make decisions. In a minimax setting:

  1. Each player tries to maximise his score, V.
    • The strategy of each player guarantees him a gain of at least V.
  2. Each player tries to minimise his loss.
    • The strategy of each player guarantees him a loss of at most V.
  3. The sign of the value of the game, V, represents the outcome.

Since it is a zero-sum game, the above is the same as saying that each player tries to minimise the maximum gain of the other player. And this is exactly what Game Theory is about: analysing the goals and consequences of actions and making decisions accordingly. Game Theory provides some tools to reach the best possible solution even with some unpredictable (random) circumstances. In Game Theory:

  • A game is a situation that can be modelled as a Game Theory problem.
  • A player is an agent or set of agents that have the same goal in the game: a chess player, a football team, a company, or a country, to name a few.
  • A strategy is a decision or set of decisions made by a player: his action plan.
    • Strategies are not necessarily good strategies.
    • Random strategies might be really useful.
    • Decisions translate into actions.
  • A reward or penalty is the payoff of the game for a player.

As an example, a strategy for tic tac toe (the only game I mastered so far) would be: “Place a cross in cell A; if the adversary places a circle in cell B, then place a cross in cell D; if he places a circle on C, instead, place a cross in cell E. Then, if he does F, answer with G…”.

ezgif-com-5333cab391
Figure 1. A strategy can be represented as a tree graph where nodes are actions taken by both players alternatively. Leafs nodes are terminal states that might represent a win, a loss or a draw. Note that, we are implicitly representing the state of the board in the path to the goal.

Of course, real strategy games are very different from one another; they can be too complicated to explicitly write a strategy, rewards might be conditioned by unknown variables, actions can be non-deterministic, players might choose to cooperate or compete or even try to surprise the adversary, etc. All games, though, have one thing in common: while the players act on their environment to achieve their goals, other players are also changing the very same environment.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s