Archive for October 14th, 2008
| Heads | Tails | |
| Heads | +1, -1 | -1, +1 |
| Tails | -1, +1 | +1, -1 |
| Matching pennies | ||
Matching pennies is the name for a simple example game used in game theory. It is the two strategy equivalent of Rock, Paper, Scissors. Matching pennies, also called the Pesky Little Brother Game or Parity Game, is used primarily to illustrate the concept of mixed strategies and a mixed strategy Nash equilibrium.
The game is played between two players, Player A and Player B. Each player has a penny and must secretly turn the penny to heads or tails. The players then reveal their choices simultaneously. If the pennies match (both heads or both tails), Player A receives one dollar from Player B (+1 for A, -1 for B). If the pennies do not match (one heads and one tails), Player B receives one dollar from Player A (-1 for A, +1 for B). This is an example of a zero-sum game, where one player’s gain is exactly equal to the other player’s loss.
The game can be written in a payoff matrix pictured to the right. Each cell of the matrix shows the two players’ payoffs, with Player A’s payoffs listed first.
This game has no pure strategy Nash equilibrium since there is no pure strategy (heads or tails) that is a best response to a best response. Alternatively, there is no strategy set where neither player would want to switch when told what the other would do. Instead, the unique Nash equilibrium of this game is in mixed strategies: each player chooses heads or tails with equal probability. In this way, each player makes the other indifferent between choosing heads or tails, so neither player has an incentive to try another strategy.
Of course, most human players cannot or will not faithfully apply the equilibrium strategy, especially if Matching pennies is played repeatedly.
In a repeated game, if one is sufficiently adept at psychology, it may be possible to predict the opponent’s move and choose accordingly, in the same manner as expert Rock, Paper, Scissors players. In this way, a positive expected payoff might be attainable, whereas against an opponent who plays the equilibrium, one’s expected payoff is zero.
The matching pennies game is mathematically equivalent to a game children play called "choosing" or "odds and evens", where two players simultaneously display one or two fingers, with the winner determined by whether or not the number of fingers match. The only strategy for both these games to avoid being exploited is to perfectly randomize your selection.
Rock, Paper, Scissors is a common name for a popular two-person hand game. It may also be referred to as Paper, Rock, Scissors, or by other combinations of the three words. The game is often used as a selection method in a similar way to coin flipping or drawing straws to randomly select a person for some purpose. However, unlike truly random selections, it can be played with skill if the game extends over many sessions, as a player can often recognize and exploit the non-random behavior of an opponent.
Sportsmen often use the game (both officially and unofficially, in place of a coin toss) to decide on opening plays. Similarly, uncertain calls, or even the whole game in case of rain, may be so decided. It is also often used as a method for creating appropriately non-biased random results in live action role-playing games, as it requires no equipment. It is also used in some gambling sites as a form of novelty betting.
The exact name of the game can vary, with the three components appearing in a different order, or with "stone" in place of "rock". Non-English speakers often refer to the game by their words for "rock, paper, scissors" (though not necessarily in that order). Names for the game include Janken or Yakyuken in Japan, Kawi Bawi Bo in Korea, Pierre-Papier-Ciseaux in France, Jack En Poy or Bato Bato Pick (rock, rock, choose!) in the Philippines, Jó-kên-pô in Brazil, Kő-papír-olló in Hungary, Ca-Chi-Pun in Chile, and Ching-Chong-Cha (the words used in the ‘count’) in South Africa, 石头-剪子-布 in 中国.
The players both count aloud to three, or speak the name of the game (e.g. "Rock! Paper! Scissors!" or "Reaux! Sham! Beaux!"), each time raising one hand in a fist and swinging it down on the count. On the third count, or on a further beat after the third count (saying "shoot"), the players change their hands into one of three gestures, which they then "throw" by extending it towards their opponent.
Rock, represented by a closed fist.
Paper, represented by an open hand.
Scissors, represented by the index and middle fingers extended.
The objective is to select a gesture which defeats that of the opponent. Gestures are resolved as follows:
Paper, represented by an open hand.
Scissors, represented by the index and middle fingers extended.
The objective is to select a gesture which defeats that of the opponent. Gestures are resolved as follows:
Rock blunts/smashes scissors; rock wins.
Paper covers rock; paper wins.
Scissors cut paper; scissors wins.
If both players choose the same gesture, the game is tied and played again.
Paper covers rock; paper wins.
Scissors cut paper; scissors wins.
If both players choose the same gesture, the game is tied and played again.
In some variations of the game, the winner of each round "uses" the weapon on the opponent’s weapon, to demonstrate that they have won.
RPS is frequently played in a "best two out of three" match, and tournament players often prepare sequences of three gestures ahead of time. Jason Simmons, a competitive RPS champion, claims that women tend to start with scissors, while the World RPS Society states that males have a tendency to lead with rock. At World RPS tournaments, Paper is statistically the least common throw.
A common timing-based tactic on a throw of paper or scissors is to wait until the last possible moment to dupe an opponent into believing that one may actually be throwing a scissors or rock. This is usually regarded as a foul at competitive RPS matches. In competitive RPS, however, a foul can be called on any throw that is revealed after thrower’s arm swings past the perpendicular to his torso. In this case, the referee may then assign a throw of rock, or a "forced rock".
Priming is the number of bounces one does before revealing the throw. Another way to cheat is to prime three times to an opponent’s twice, so that one sees his opponent’s throw without revealing his own. In most such cases, though, the round will be most likely replayed.
To prevent timing-based cheating, the players may be asked to hold their throwing hands behind their backs and reveal their already-formed throws after the count of three. However, before playing, the two playing must decide which count they are going to throw their hands on.
Mathematics：Non-transitivity
RPS is also often used as an example of the mathematical concept of non-transitivity.
RPS is also often used as an example of the mathematical concept of non-transitivity.
A transitive relation R is one for which a R b and b R c implies a R c. A reflexive, antisymmetric, and transitive relation on a set is known as a partial ordering, from which notions of "greater" and "less" follow. A game option which is "greater" than another is closer to being optimal, but such a notion does not exist in RPS: The relation used to determine which throws defeat which is non-transitive. Rock defeats scissors, and Scissors defeat paper, but rock loses to paper. In fact, RPS could be called "antitransitive" because if A strictly defeats B, and B strictly defeats C, A necessarily loses against C.
For example, in mathematics, it can be shown that there exist magmas that are commutative but not associative. One example is given by the operation of RPS.
Video games
Combat or strategy-based video games often feature RPS-like cycles in their characters’ or units’ effectiveness against others. These often attempt to emulate cycles in real-world combat (such as where cavalry are effective against archers, archers have an edge over spearmen, and spearmen are strongest against cavalry), or simple elemental trinities such as fire, water and air.
Combat or strategy-based video games often feature RPS-like cycles in their characters’ or units’ effectiveness against others. These often attempt to emulate cycles in real-world combat (such as where cavalry are effective against archers, archers have an edge over spearmen, and spearmen are strongest against cavalry), or simple elemental trinities such as fire, water and air.
Such game mechanics can make a game somewhat self-balancing, by preventing any one simple strategy from dominating gameplay.
Many card-based video games in Japan use the RPS system as their core fighting system, with the winner of the RPS being able to carry out their designated attack.
The Nintendo Entertainment System video game, Princess Tomato in the Salad Kingdom, uses the RPS system to defeat enemies; although in the game RPS is referred to as "finger wars".
Alex the Kid for the Sega Master System uses RPS as the method of defeating end-of-level bosses similar to Princess Tomato
Mating strategies
Biologist Barry Sinervo from the University of California, Santa Cruz has discovered a RPS evolutionary strategy in the mating behaviour of the side-blotched lizard species Uta stansburiana. Males have either orange, blue or yellow throats and each type follows a fixed, heritable mating strategy:
Biologist Barry Sinervo from the University of California, Santa Cruz has discovered a RPS evolutionary strategy in the mating behaviour of the side-blotched lizard species Uta stansburiana. Males have either orange, blue or yellow throats and each type follows a fixed, heritable mating strategy:
Orange-throated males are strongest and do not form strong pair bonds; instead, they fight blue-throated males for their females. Yellow-throated males, however, manage to snatch females away from them for mating.
Blue-throated males are middle-sized and form strong pair bonds. While they are out competed by orange-throated males, they can defend against yellow-throated ones.
Yellow-throated males are smallest, and their coloration mimics females. Under this disguise, they can approach orange-throated males but not the stronger-bonding blue-throated specimens and mate while the orange-throats are engaged in fights.
This can be summarized as "orange beats blue, blue beats yellow, and yellow beats orange", which is similar to the rules of rock, paper, scissors.
Blue-throated males are middle-sized and form strong pair bonds. While they are out competed by orange-throated males, they can defend against yellow-throated ones.
Yellow-throated males are smallest, and their coloration mimics females. Under this disguise, they can approach orange-throated males but not the stronger-bonding blue-throated specimens and mate while the orange-throats are engaged in fights.
This can be summarized as "orange beats blue, blue beats yellow, and yellow beats orange", which is similar to the rules of rock, paper, scissors.
The proportion of each male type in a population is similar in the long run, but fluctuates widely in the short term. For periods of 4-5 years, one strategy predominates, after which it declines in frequency as the strategy that manages to exploit its weakness increases. This corresponds to the stable pattern of the game in the replicator dynamics where the dynamical system follows closed orbits around the mixed strategy Nash equilibrium (Sinervo & Lively, 1996; Sinervo, 2001; Alonzo & Sinervo, 2001; Sinervo & Clobert, 2003; Sinervo & Zamudio, 2001).
Bacteria also exhibit a rock-paper-scissors dynamic when they engage in antibiotic production. The theory for this finding was demonstrated by computer simulation and in the laboratory by Benjamin Kerr, working at Stanford University with Brendan Bohannan (Nature. 2002 Jul 11;418(6894):171-4.). The antibiotics in question are the bacteriocins – more specifically, colicins produced by Escherichia coli. Biologist Benjamin C. Kirkup, Jr. further demonstrated that the colicins were active as E. coli compete with each other in the intestines of mice, and that the rock-paper-scissors dynamics allowed for the continued competition between antibiotic producing and antibiotic sensitive strains, because antibiotic resistant strains would out-compete the producing strains, providing an environment in which sensitive strains could successfully become established again (Nature. 2004 Mar 25;428(6981):412-4.).
Cultural references
Because of its widespread use, the game has received substantial references in popular culture. Many television series poke fun at particular characters’ incompetence at understanding the rules, or show how mischievous characters are often able to "win" the game by inventing new objects which beat all the others.
Because of its widespread use, the game has received substantial references in popular culture. Many television series poke fun at particular characters’ incompetence at understanding the rules, or show how mischievous characters are often able to "win" the game by inventing new objects which beat all the others.
In 2006, Federal Judge Gregory Presnell from the Middle District of Florida ordered opposing sides in a lengthy court case to settle a trivial (but lengthily debated) point over the appropriate place for a deposition using the game of rock-paper-scissors. The ruling in Avista Management v. Wausau Underwriters stated:
"Upon consideration of the Motion – the latest in a series of Gordian knots that the parties have been unable to untangle without enlisting the assistance of the federal courts – it is ORDERED that said Motion is DENIED. Instead, the Court will fashion a new form of alternative dispute resolution, to wit: at 4:00 P.M. on Friday, June 30, 2006, counsel shall convene at a neutral site agreeable to both parties. If counsel cannot agree on a neutral site, they shall meet on the front steps of the Sam M. Gibbons U.S. Courthouse, 801 North Florida Ave., Tampa, Florida 33602. Each lawyer shall be entitled to be accompanied by one paralegal who shall act as an attendant and witness. At that time and location, counsel shall engage in one (1) game of "rock, paper, scissors." The winner of this engagement shall be entitled to select the location for the 30(b)(6) deposition to be held somewhere in Hillsborough County during the period July 11-12, 2006."
When Takashi Hashiyama, CEO of a Japanese television equipment manufacturer, decided to auction off the collection of Impressionist paintings owned by his corporation, including works by Cézanne, Picasso and van Gogh, he contacted two leading U.S. auction houses, Christie’s International and Sotheby’s Holdings, seeking their proposals on how they would bring the collection to the market as well as how they would maximize the profits from the sale. Both firms made elaborate proposals, but neither was persuasive enough to get Hashiyama’s business. Willing to split up the collection into separate auctions, Hashiyama asked the firms to decide between themselves who would get the Cézanne’s "Large Trees Under the Jas de Bouffan", worth $12-16 million. The houses were unable to reach a decision. Hashiyama told the two firms to play RPS, to decide who would get the rights to the auction, explaining that "it probably looks strange to others, but I believe this is the best way to decide between two things which are equally good". The auction houses had a weekend to come up with a choice of move. Christie’s went to the 11-year-old twin daughters of an employee, who suggested "scissors" because "Everybody expects you to choose ‘rock’." Sotheby’s said that they treated it as a game of chance and had no particular strategy for the game, but went with "paper". Christie’s won the match, with millions of dollars of commission for the auction house.
Starting in 2002, the World Rock Paper Scissors Society (WRPS) standardized a set of rules for international play and has overseen annual International World Championships. These open, competitive championships have been widely attended by players from around the world and have attracted widespread international media attention. WRPS events are noted for their large cash prizes, elaborate staging, and colourful competitors. In 2004, the championships were broadcast on the U.S. television network Fox Sports Net.
Professional poker player, Phil Gordon, hosts the annual World Series of Roshambo during the World Series of Poker every year. In 2006, Annie Duke outlasted a field of 64 players who paid $500 each to enter the tournament. First place prize was $10,000. This is the largest buy-in Roshambo event in the world.
USARPS League is the official Rock Paper Scissors League of the United States. It is sponsored by Bud Light. Matti Leshem is the co-commissioner of the USA Rock Paper Scissors League
In April 2006, the inaugural USA Rock Paper Scissors League Championship was held in Las Vegas, Nevada. Following months of regional qualifying tournaments held across the US, 257 players were flown to Las Vegas for a single-elimination tournament at the House of Blues where the winner received $50,000. The tournament was shown on the A&E Network on June 12, 2006.
At the first USA Rock Paper Scissors League Championship, Dave "The Drill" McGill defeated Robert "Fast Twitch" Twitchel to win the tournament. In addition, Jason "King of the Morning" Wood won a best-of-500 marathon to earn a brand new car.
The $50,000 2007 USARPS Tournament took place at the Las Vegas Mandalay Bay in May 2007 and was covered by RawVegas.tv and will also be airing on ESPN later this year. The winner was Jamie Langridge from Odessa, Texas and he went home with the Bud Light Trophy and $50,000.
The XtremeRPS National Competition is a Nationwide RPS competition with Preliminary Qualifying contests starting in January 2007 and ending in May 2008, followed by regional finals in June and July 2008. The national finals will be held in Des Moines in August 2008, with a chance to win up to $5,000.
very interesting…
time traveler 