Moving on from simple zero-sum games, there are a bunch of directions in which
we can go. So far, the games we’ve looked at are very restrictive. Beyond the
zero-sum property, they’re built on a set of fundamental properties which ultimately
reduce to the idea that no player ever has an information advantage over any other
player: the complete payoff matrix is known by all players; no player gets
to see the other players strategy before selecting their own; and so on.

Moving on to more interesting games, we can relax those assumptions, and allow information to be hidden. Perhaps each player can see a different part of the
payoff matrix. Perhaps they take turns, so that one player gets to see the others
strategy before selecting his own. Perhaps the game isn’t zero-sum.

Non-zero sum games turn out to be disappointing from a game theory point of
view. Given a suitable set of restrictions, you can convert a non-zero-sum game to a
zero-sum game with an additional player. In the cases where you can’t do that,
you’re pretty much stuck – the mathematical tools that work well for analyzing
zero-sum games often simply don’t work once you relax the zero-sum requirement.

The more interesting ways of exploring different realms of games comes when you
allow things to get more complex. This comes about when you allow a players strategy
selection to alter the game. This general takes place in a turn-taking
game, where each players strategy selection alters the game for the other player. A
simple example of this is the game of tic-tac-toe. The set of strategies of the game
for a given player at any point in time is the set of open squares on the board.
Each time a player makes a move, the game is altered for the other player.

This makes things much more interesting. The easiest way to think of it is
that now, instead of a simple matrix for the game, we end up with a tree. Each move
that a player can make creates a new game for the other player. By making each game position a tree node, and adding children nodes for each position that can follow it, you can build a tree describing the complete set of possible game positions, and thus the complete set of ways that the game could play out.

Continue reading →

Before we move beyond zero-sum games, it’s worth taking a deeper look
at the idea of utilities. As I mentioned before, in a game, the scores in
the matrix are given by something called a utility function.

Utility is an idea for how to mathematically describe preferences in terms
of a game or lottery. For a game to be valid (that is, for a game to have a meaningful analysis and solution), there must be a valid utility function that
describes the players’ preferences.

But what do we have to do to make a valid utility function? It’s
simple, but as usual, we’ll make it all formal and explicit.

Continue reading →

When I last wrote about game theory, we were working up to how to find
the general solution to an iterated two-player zero-sum game. Since it’s been
a while, I’ll take a moment and refresh your memory a bit.

A zero-sum game is described as a matrix. One player picks a row, and one player picks a column. Those selections are called strategies. The intersection
of the strategies in the game matrix describes what one player pays to the other. The
matrix is generally written from the point of view of one player. So if we call
our two players A and B, and the matrix is written from the viewpoint of A, then
an entry of $50 means that B has to pay $50 to A; an entry of $-50 means that A has to pay $50 to B.

In an iterated game, you’re not going to just play once – you’re going to play it repeatedly. To maximize your winnings, you may want to change strategies. It turns out that the optimal strategy is probabilistic – you’ll assign probabilities to your
strategy choices, and use that probability assignment to randomly select your
strategy each iteration. That probability assignment that dictates how you’ll
choose a strategy each iteration is called a grand strategy.

Jon Von Neumann proved that for any two-player zero-sum game, there is an optimal grand strategy based on probability. In a game where both players know exactly what the payoffs/penalties are, the best strategy is based on constrained randomness – because any deliberate system for choosing strategies can be cracked by your opponent, resulting in his countering you. The best outcome comes from assessing potential wins and losses, and developing a probabilistic scheme for optimizing the way that you play.

Once you make that fundamental leap, realizing that it’s a matter
of probability, it’s not particularly difficult to find the grand strategy: it’s just a simple optimization task, solveable via linear programming. The solution is very elegant: once you see it, once you see how to
formulate the game as a linear optimization process, it just seems completely obvious.

Continue reading →

So, I’ve finally had some time to get back to the linear programming
followup. You might want to go back and look at the earlier post to remember what I was talking about.

Continue reading →

The games that we’ve looked at so far are the simplest case of
basic games. In these games, we’ve got a payoff matrix, and both players
can see the whole matrix – the players have equal information,
and nothing is secret. The players move simultaneously – so neither player can wait to see what his opponent does before making his own decision. Finally, the game is played exactly once – there are no repetitions.

The first complication we can add is to make it an iterative game – that is, instead of each player going once, they’ll repeat the game 10 times in sequence. Everything else stays the same: perfect, equal information, simultaneous moves, etc.

This creates an interesting added dimension. Now, we’ve got two layers
of strategy: each iteration, each player selects a strategy; and then there’s an over-arching strategy that they use to select their strategy each iteration. That over-arching strategy is called a grand strategy

In an iterated game, the optimal solution for players can be different than in the single iteration. The goal is to maximize your total utility at the end of a series of iterations. It’s OK if some iterations result in a loss of utility, so long as by the end of the series of iterations, the final
sum of the utility of the series is maximal.

Continue reading →

Last time I wrote about Game Theory, I explained the basic idea of
zero sum games. In their simplest form, a game can be described by a payoff matrix,where each dimension of the matrix is the set of strategies which can be selected by one player, and each entry in the matrix describes the payoffs that result when all players select their strategy. Informally, a game is zero-sum when the total payoff is zero – that is, when any positive payout to one player is balanced by payouts from other players.

We can formalize some of the basic ideas more precisely. What we can say is that each move results in a state; and for each player y, there is a function, u_p, called a utility function, which maps from a state to a utility value. Taking the player utility functions as components, we can define the game’s utility function in terms of tuples: for players 1..n,
the utility function maps from states to tuples of utility values: u(state)=(u₁, …, u_n).

Continue reading →

In game theory, perhaps the most important category of simple games is
something called zero sum games. It’s also one of those mathematical
things that are widely abused by the clueless – you constantly hear
references to the term “zero-sum game” in all sorts of contexts, and they’re
almost always wrong.

A zero-sum game is a game in which the players are competing for resources, and the set of resources is fixed. The fixed resources means that any gain by one player is necessarily offset by a loss by another player. The reason that this is called
zero-sum is because you can take any result of the game, and “add it up” – the losses will always equal the wins, and so the sum of the wins and losses in the result of the game will always be 0.

Continue reading →

As an introduction to a mathematical game, and how you
can use a little bit of math to form a description of the game that
allows you to determine the optimal strategy, I’m going to talk a bit about Nim.

Continue reading →

Lots of people wanted game theory, so game theory it is. The logical first question: what is game theory?

Game theory is typical of math. What mathematicians like to do is reduce
things to fundamental abstract structures or systems, and understand them in
terms of the abstraction. So game theory studies an abstraction of games – and
because of the level of abstraction, it turns out be be applicable to a wide
variety of things besides what you might typically think of as games.

Game theory starts with the fundamental idea of a game. What is
a game?

Continue reading →