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.
For example, if you play poker with a group of friends, you're playing a
zero-sum game. In each hand, what you can win is the money in the pot - and that
money was put there by you and the other players. There's nothing for you to win
that wasn't put there by another player. If you win something, it's because at least one of the other players lost something.
The simplest kind of zero sum game is one where you've got two
non-communicating players, a fixed payoff matrix, and the
players move simultaneously.
A payoff matrix is a tool for describing a certain kind of simple game. The idea is that if you've got two players, and each player has a fixed set of possible moves, then you can describe the game by a matrix. One dimension of the
matrix is a list of moves for one player; the other is the set of moves for the other player. Each cell contains a payoff: cell x,y contains the result if
player one makes move x, and player 2 makes move y. For clarity, we often label one dimension with numbers and the other with letters, so that player 1's move is always a letter, and player 2 is a number. For example, here's
a simple payoff matrix:
| A | B | C | |
|---|---|---|---|
| 1 | 10 | -5 | -5 |
| 2 | 20 | -15 | -5 |
| 3 | -10 | 10 | -2 |
In this matrix, positive cell values indicate that player 1 pays
player 2; negative cell values indicate that player 2 pays player 1. So, if
player 1 picks move "B", and player 2 picks move 3, then player 1 pays 10 to
player 2.
The strategies in this kind of game are pretty simple. Since
the players don't get to communicate, there's no way of doing any
kind of deal-making. So each player simply looks at the cost-benefit
tradeoffs. For player 1, if they make move "A", they could win or lose 10,
or they could lose 20. That's two bad outcomes, one good one - and the good
outcome is small. If they pick "B", they've got two good outcomes - one small, one large, and one bad outcome. And if they pick "C", all of the outcomes are
good, but small. So for player 1, C guarantees that they'll come out
ahead. Other choices have potentially larger payoffs, but with larger risks.
The best outcome comes from finding a way to maximize the potential wins while minimizing the potential losses. In this case, the potential wins aren't that much larger for moves other than "C", so player 1 would probably be wisest to pick "C".
On the other hand, look at it from player 2's perspective. He can see that player 1 is likely to pick "C". So assuming that, his best choice would be "3". But player 1 knows that player 2 would like to minimize his losses by picking
"3". So player 1 could pick "A", taking a risk in the hopes of winning 10 instead of 2.
You can see that even for a simple game, this can get complicated. It gets even worse if you consider multiple rounds.
It turns out that there is a relative simple linear-programming based
trick that allows you to define a probabilistic optimal strategy for
a zero-sum game. But before we get to that, we'll need to define what
we mean by a strategy in mathematical terms - and to get to that, we need to
define what it means to solve a game by finding its equilibria.
This kind of zero-sum game comes up in a lot of real world situations, many of
which aren't what we intuitively think of as games. For example, an election can
be modelled as a zero-sum game. If you think of the set of people who will vote as
the resources, then each candidate can only gain votes by taking votes away from
other candidates.
This is, of course, an oversimplification, and a typical example of how the
idea of zero-sum games is commonly misused. An election isn't really a
zero-sum game, because the pool of people who vote isn't fixed. The current
primary election cycle in the US is a great example of this: one of the
interesting things that's been going on is that people who haven't voted before
in primaries are registering and voting. Barack Obama has been the main
beneficiary of this, and he has gotten more votes without taking any votes
away from Hillary Clinton by getting votes from new voters.
The key thing that defines a zero sum game is the fixed pool of resources. If
there's any possible input that increases the resource pool, then it's not a
zero-sum game. Elections aren't zero-sum, because the pool of voters isn't a
specific fixed quantity: the number of people who vote can increase or decrease - so a candidate can gain votes without taking away from the set of voters voting for another candidate; and a candidate can lose votes without adding to the
set of people voting for another candidate.
We also frequently hear about zero-sum games in the context of economics
and financial markets. There are many things that can be
represented as zero-sum games in economics. But very frequently, when you
hear someone talking about something as a zero-sum game, they're wrong: the economy as a whole can shrink and grow. In a shrinking economy, wealth
can be lost by many people without being gained by anyone - it can, effectively,
disappear. In a growing economy, money can be made by many people without taking
it away from anyone - wealth can be created. It's not zero-sum: the pool of
resources (wealth) is not constant.
- Log in to post comments
I think elections still qualify as a zero sum game, since the payout for candidates isn't votes; the votes are just the score. The payout is a party nomination or a public office. The sum of the "resources", the office of president, etc, aren't affected by how the candidates play the game or how many voters get involved - just as the payout on a hand of poker isn't determined by the nature of the cards in the winning hand.
I think it's silly to say that elections are not zero-sum because the set of voters is not fixed. It's like saying that Soccer is not zero-sum because the number of goals scored is not fixed. You're not trying to score as many goals as possible; you're trying to score more than your opponent. You win iff your opponent loses, so I'd call it zero-sum.
A game of soccer isn't a zero sum game. You scoring one goal doesn't cost your opponent one goal. For it to be a zero-sum game, the benefits and losses have to add up to a constant, which you yourself said isn't the case.
A soccer tournament, otoh, is a zero sum game. Each game I win, is one my opponent loses.
Game theory is a fun topic (and a common source of bad math).
Auctions have provided interesting insight into games where the players don't communicate. In FCC spectrum auctions, big companies play a high-stakes auction game to get as much spectrum for as little money as possible. In an auction, cooperation can help you, as two deep pockets don't want to bid against each other. A trust of bidders could decide the winners in advance and allow each to win with only a nominal bid by declining to bid against each other.
To ensure that the price is fair and to prevent anti-competitive behaviors, antitrust laws prohibit any communication between bidders in these auctions. In one such auction, several big players developed a mechanism to use the bids themselves as a communications mechanism. These companies would encode their maximum bid in the small digits of the smaller opening bids (e.g., $235 million might be encoded as $1,000,235). After a few of these signal bids, the bidders would implicly agree on a winner, who could then buy the spectrum at a steal of a price.
Of course, the FCC lawyers felt that this communication was a violation of antitrust laws. Particularly fascinating is that to negotiate this behavior in advance would defeat the purpose: to deny you've communicated. It's an interesting example of a covert channel and emergent cooperative behavior where communication is nominally absent.
For more information, see Collusive Bidding: Lessons from the FCC Spectrum Auctions or some simple pop analysis from Forbes.
OK, this looks like it's becoming an argument about definitions.
I'd say that every game has utilities for the players as a function of the outcome, but not every game has votes or goal-posts or chess pieces. So when we say a game is zero-sum, we mean that your utility plus my utility equals zero (or a constant). We don't mean "your votes plus my votes equal zero (or a constant)," because there are games which don't involve voting, and we'd still like to say that these games can be non-zero-sum.
You're confusing "winnable games" with "zero-sum games". Zero-sum implies more than just "one player wins". There are tons of games that have winners, but which are not zero-sum.
Soccer isn't a zero sum game, because the set of resources that you're competing for (goals) isn't fixed. Elections aren't zero-sum, because the resources that you're competing for (voters) aren't fixed. They both have specific winners - but that's a different question.
To try to make it clear: you can imagine a kind of soccer tournament based on goals, where the winner of the tournament never won a single game.
Imagine that you had 5 teams competing: A, B, C, D, and E.
In A vs B, A scored 5, B scored 6.
In A vs C, A scored 3, C scored 4.
In A vs D, A scored 4, D scored 5.
In A vs E, A scored 5, E scored 6.
In B vs C, B scored 2, C scored 1.
In B vs D, B scored 1, D scored 0.
In B vs E, B scored 2, E scored 1.
In C vs D, C scored 1, D scored 2.
In C vs E, C scored 2, E scored 1.
And in D vs E, D scored 0, E scored 1.
B is undefeated: they won every game they played.
A lost every game they played.
But if you ranked them by goals scored, A scored 17 goals; B scored 11.
A tournament, which counts "games won" is a zero-sum game. In order for anyone to win, someone has to lose. But a single game of soccer isn't zero sum: the score isn't a fixed quantity. There can be any number of goals scored. Scoring a goal doesn't take anything away from your opponent.
I think the "Matching" card games like "Go Fish" or Gin are also good examples of zero-sum games. There are only so many cards in the deck, so if I get one, that one is denied to you.
I think Mark's point about soccer can also be made about elections. If you care about winning or vote shares, then they would be zero-sum games. If, for instance, you are in a primary, you will also care about voter turnout, outcome among target demographics, etc, and those criteria need not be the same across candidates, so that it isn't a zero-sum game.
You can think of an election as zero-sum if you consider the pool of possible voters as the resource, and then you have to consider them not voting as being a kind of player.
Possible voter in this case means anyone eligible (so unregistered count if it's before the registration date). Now it could still be complicated -- for example, if you had a strategy to change the eligibility rules (e.g. change the registration date, allow felons to vote, change the voting age).
Lou:
You're actually hitting on something pretty deep. In fact, if you get the definitions right, any non-zero sum game can be made into a zero-sum game by adding virtual players. The election can be made zero-sum by adding a "non-voting" player to the pool (or by adding multiple players: a "registered but not voting", and an "eligible but not registered" - since they each express a different pool of people).
I got nothing to add, just wanted to say that I'm really digging this series so far, Mark.
But elections and soccer still differ; you only have a limited and very exact amount of resources with elections. For example, if everyone with the right to vote would actually vote, this would be a clear example of a zero-sum game. Or, as stated above, if you consider the non-voting people as a not-exausthed-but-available pool, just as with some card game. You either steal a voter from another candidate, or you pick up a new one from the table; in both cases other candidates lost the voter in some manner.
You can't do that with soccer, because there is an infinite (well, not really) amount of goals "available" in a game. Or can you? How about we calculate the maximum possible number of goals in a game, i.e. a goal can be scored every 10 seconds. Now, every 10 seconds of the game, you either score a goal (thus "stealing" that exact goal from your opponent), receive a goal (the opponent stole that resource from you), or you both miss a chance (the resource remains unused). I don't really think this makes it a zero-sum game, but it's similar to the non-voting pool in the elections example. :)
Is poker a zero sum game or not?
from the wiki for zero sum games:
"Zero-sum can be thought of more generally as constant sum where the benefits and losses to all players sum to the same value."
"For example, a game of poker, disregarding the house's rake, played in a casino is a zero-sum game "
If you are defining it by who has the pot at the end, then poker is a zero sum game. It doesn't matter if you win with a royal flush or two pair, you still get the same pot. If on the other hand you are defining it by a score determined by the best hands getting the most points, and everyone walks away with their score after the game, then it is not.
Ditto for elections, I think. One player (the incumbent) brings his elected position to the game. The sum (the pot) = 1. Two or more players compete for it, but it doesn't matter if one wins by a landslide or by one vote: the pot is still one single elected position. The sum still = 1.
The problem I think people are having is they are talking about things like "elections" or "soccer" without fully specifying the game they want to use to model it. To have a game you need (at least) a set of players, the set of actions they can take, a set of outcomes determined by those strategies, and utility functions/sets of preferences for each player over those outcomes. "zero sum" is defined with respect to the utility assumed in the game. So soccer is zero sum when utility = 1/0/-1 for win/draw/lose, but it's not zero sum when utility = goal differential. When you're talking about a soccer game within a larger tournament, then the tournament as a whole is the complete game - and given a fixed prize pool would itself be zero-sum. A single soccer match would then be a subgame of the larger tournament game - and needn't be zero-sum.
Soccer (henceforth 'football', as I'm English) is an interesting example that I've wondered about re: zero-sum games.
In the English football leagues, each team plays each other team twice during the season. It used to be that a team got 2 points for a win, 1 for a draw and 0 for a loss. Therefore, the league as a whole was zero-sum - there was only a fixed number of points to be shared amongst the teams.
At some point, the rules were changed such that now you get 3 for a win, 1 for a draw and 0 for a loss, so now it's not zero-sum anymore - you get a bonus point for winning.
I'm not sure of the implications in terms of game-theory... anyone?
Another example is investing in stocks. Investing in stocks is not a zero sum game, but trying to outperform the broad market is.
What is being overlooked is that the general form of a game requires payoffs for each of the players for a given outcome. What makes it zero-sum is that the sum of these two payoffs is zero. When there is only one payoff p given, it is automatically a zero-sum game with payoffs p,-p (and the '-' has no non-mathematical significance, so which player is assigned the positive payoff doesn't matter). Note that this is a purely mathematical definition; mapping a game onto some real world situation is an entirely different matter. Thus to take the soccer example: We could consider one game in which the options are different strategies and the payoffs are numbers of goals scored; this is clearly not zero sum (for any normal teams) in the sense given above. On the other hand, if we count a win as 1, a loss as -1 and ties as 1/2 or -1/2 indifferently (actually the map should run from payoffs to scores, rather than v.v. as here), then this game is zero-sum. The problem with the informal use of 'zero-sum' in the media is that they never tell you what the mathematical game is (indeed, they don't really know) nor how the real world is mapped onto it.
In lot of countries elections IS a zero-sum game. Ukraine or Russia is a good examples of such countries.
Two things:
1: Any game (or contest, or election, or anything at all) can be called "zero-sum" if there is a winner and a loser (more precisely, if a winner implies a loser; the possibility of a tie does not keep it from being "zero-sum"). This is true, but trivial. It doesn't tell you anything about the nature of the game, which is the interesting subject. I think this discussion has clearly illustrated that games that are zero-sum in this trivial sense can be either zero-sum or non-zero-sum in the manner of play.
2: Mark -- your #10 above unfortunately muddies the water by referring to the voters as "players." They are really not players; they are "pieces" (or "men," in the gender-free chess sense).
3 (OK, I didn't count correctly): Elections with any variability in the electorate are not zero-sum. It is not correct to say that registering a new voter who votes for you is taking a vote away from your opponent. This approach would eliminate the binary character the zero-sum concept. Think of it this way: if you didn't get this previously-unregistered voter, what would your opponent have? There are clearly two possibilities: nothing, or that same voter registered and voting for him/her. So, the "sum" is not determined, and it can't be called a "zero-sum" game.