لطفا منتظر باشید ...
Cake Division
It is finally time to take a look at a real game theory game. The following description is taken from Prisoner's Dilemma and is the classic "cake division" game theory problem: Most people have heard of the reputed best way to let two bratty children split a piece of cake. No matter how carefully a parent divides it, one child (or both!) feels he has been slighted with the smaller piece. The solution is to let one child divide the cake and let the other choose which piece he wants. Greed ensures fair division. The first child can't object that the cake was divided unevenly because he did it himself.The second child can't complain since he has his choice of pieces…. The cake problem is a conflict of interests. Both children want the same thing—as much of the cake as possible. The ultimate decision of the cake depends both on how one child cuts the cake and which piece the other child chooses. It is important that each child anticipates what the other will do. This is what makes the situation a game in Von Neumann's sense. Game theory searches for solutions—rational outcomes—of games. Dividing the cake evenly is the best strategy for the first child, since he anticipates that the other child's strategy will be to take the biggest piece. Equal division of the cake is therefore the solution to this game. The solution does not depend on a child's generosity or sense of fair play. It is enforced by both children's self interest. Game theory seeks solutions precisely of this sort.[8]
Cake division payoff grid
The cake division problem contains all of the elements of a game theory "game" listed earlier. There are two rational players (the children motivated by self interest). These two players choose a strategy about how to behave (how to cut or select the pieces).These strategies result in some kind of utility for the two players, measured in how much cake they get. Note that even though the "play" of this very simple game consists of a two-part action (first slice the cake and then choose a slice), the two players can still reveal and enact their strategies simultaneously. For example, the strategy of the player that chooses from the two pieces is always going to be "take the bigger piece." A rational piece-choosing player is going to choose this strategy regardless of the strategy that the cake-cutting player takes. (Note that although these "strategies" may seem like forgone conclusions rather than choices, this is because this game theory game has a saddle point, a concept explained in detail later on.) A powerful analytical tool provided by game theory is to map this decision making process into a grid. One axis of the grid represents one player's decision. The other axis represents the other player's decision. The cells in the grid represent the outcomes reached depending on which decisions were made. A game theory table of this sort is called a payoff matrix (payoff being another term for utility). Figure 1 shows a payoff matrix for the cake division problem, taken from Prisoner's Dilemma. Note that William Poundstone makes the assumption that the cake slicing is going to happen in an imperfect world, so that even if the child that cuts the cake tries to slice it evenly, the two resulting slices will still differ a tiny bit, say by one crumb. Along the left side of the matrix are strategies that the cutter can take: either cut the cake evenly or cut it unevenly. Although there are any number of ways to cut the cake, these are the two essential strategies from which the cutter can choose. Across the top of the matrix are strategies the chooser can take: choose the bigger piece or choose the smaller piece. The cells show the utility or payoff for only one of the players (the cutter), but it can be assumed that the inverse payoff would happen for the chooser. If the payoff matrix indicates that the cutter receives the "small piece," the chooser would therefore receive the "big piece." This is also true for half of the cake plus or minus a crumb.
The cake division problem illustrates two important game theory concepts. The first is the concept of a zero-sum game. In a zero-sum game, the utilities of the two players for each game outcome are the inverse of each other. In other words, for every gain by one player, the other player suffers an equal loss. For example, playing a version of Poker in which everyone puts money into a pot is a zero-sum game. At the end of the game, every dollar won by one player is a dollar lost by another player. A group of gamblers playing Roulette is not a zero-sum game between the players, because they are not playing directly against each other. On the other hand, if we frame Roulette so that one player is playing against the casino, then it is a zero-sum situation: if a player wins a dollar, it is taken from the house, and vice-versa. Many games are zero-sum games, even those that do not involve money. When one player wins a game of Checkers and the other player loses, the loss by one player equals a gain for the other player. In this case, game theory would assign a utility of –1 for the loss and +1 for the gain. The utilities add up to zero, which is exactly why it is called a "zero-sum" game. Some games, such as the cooperative board game Lord of the Rings, are not zero sum games. In the basic version of Lord of the Rings, players cooperate against the game system itself. Players other. If one player receives half of the cake minus a crumb (-1) the other player will receive half of the cake plus a crumb (+1). The total is zero. Cake division is a zero-sum game.
We know that the two player outcomes are inverses of each Why is this important? Because, according to game theory, every finite, zero-sum, two-player game has a solution (a proper way to play the game), the strategy that any rational player would take. What is the solution to the cake division problem? The game will always end in the upper left corner. The cutter will get half of the cake minus a crumb and the chooser will get half of the cake plus a crumb. Why is this so? Look at the cut-ter's strategies. The cutter would love to end up with the lower right cell, where he gets the big piece. So perhaps he should choose the strategy of cutting the pieces unequally. But the cutter also knows that if the chooser is given the chance to choose, the chooser will always choose the bigger piece. As a result, the cutter has to minimize the bigger piece that the chooser will select by cutting the cake as evenly as possible. The game resolves to the upper left corner. This situation clearly illustrates another key game theory concept: the saddle point property of payoff grids. In cake division, each player is trying to maximize his own gains while minimizing the gains of the other player. When the choices of both players lead to the same cell, the result is what Von Neumann and Morganstern call a saddle point. A saddle point refers to a saddle-shaped mountain pass, the intersection of a valley that goes between two adjacent mountains. The height of the pass is both the minimum elevation that a traveler going across the two mountains will reach, as well as the maximum elevation that a valley traveler crossing the mountain pass will achieve. The mathematical proof of saddle points in games is called the minimax theorem, which Von Neumann first published in 1928, many years before the 1944 publication of Theory of Games and Economic Behavior.
The concept of saddle points is extremely important in game design. In general, you want to avoid them like the plague. Remember, a saddle point is an optimal solution to a game. Once a player finds it, there is no other reason to do anything else. Think about the cake division saddle point: if either player deviates, that player will lose even more cake. If you think of the space of possibility that you are crafting as a large 3D structure carefully crafted to give a certain shape to the experience of your players, saddle points are short-circuits in the structure that allow players to make the same decision over and over. That kind of play experience does not usually provide very meaningful play. Why? Because if there is always a knowable saddle point solution to a game, a best action regardless of what other players do or what state the system is in, the game loses the uncertainty of possible action. Meaningful play then goes out the window. Saddle points do not just occur in game theory games. Many fighting games are ruined, for example, because despite all of the special moves and combinations that are designed into the game, the best strategy to use against opponents is simply to use the same powerful attack again and again and again. Saddle point! Another common occurrence of saddle points involves the programming of computer opponents. In many real-time strategy games there are "holes" or weaknesses in the AI that allow for saddle points. If a player discovers that the computer opponent does not know how to defend well against a certain type of unit, he is likely to abandon all other game strategies and simply hammer on the AI's weakness over and over, regardless of how much care went into carefully designing missions that require different kinds of problem-solving. Saddle point! This style of play, based on exploiting a strategic saddle point, is called an exploit or degenerate strategy. A degenerate strategy is a way of playing a game that ensures victory every time. The negative connotation of the terms "exploit" and "degenerate" imply that players are consciously eschewing the designed experience in favor of the shortest route to victory. There are some players that will refuse to make use of degenerate strategies, even after they find out about them, because they wish to play the game in a "proper" manner. On the other hand, many players will not hesitate to employ a degenerate strategy, especially if their winnings are displayed in a larger social space outside the game, such as an online high score list.
Degenerate strategies can be painful for game designers, as players shortcut all of the attention lavished on a game's rich set of possibilities. Try to find degenerate strategies and get rid of them! We learned in the previous schema that positive and negative feedback systems can emerge unexpectedly from within a game's structure and can ruin a game experience for players. The same is true of degenerate strategies. A close analysis of your game design can sometimes reveal them but the only real way to root them out is through rigorous playtesting. If you see players drawn to a particular set of strategies again and again, they may be exploiting a weakness in your design. [8]Poundstone, Prisoner's Dilemma, p. 43.
