Archive for the ‘Game Theory’ Category

Rock, Paper, Scissors…

November 4, 2009

Rock, Paper, Scissors is alive and well in elementary schools, at least from what I can hear [and hear I do, nearly every day].  I figured it was a simple game, but it turns out that it’s maybe not as straightforward as I thought.

The first sign was when we were watching Big Bang Theorey and Sheldon proposed a variation:

Got that?  Here’s a diagram to help you out:

Rock_Paper_Scissors_Lizard_Spock_en.svg

But TwoPi discovered that Rock, Paper, Scissors, Lizard, Spock didn’t originate with the show:  it’s been around since at least 2005 according to The New York Times.

But back to the original game.  Did you know that there was an official league?  You did?    Well then, did you know that back in 2005 — apparently a banner year for Rock, Paper, Scissors — Takashi Hashiyama was going to sell his $20,000,000 art collection and he had to choose between Christie’s and Sotheby’s to run the auction, so he made them play Rock, Paper, Scissors.  He gave them some warning, and there’s some evidence (again according to The New York Times) that the Christie’s official conducted Actual Research, at least in the form of having a friend ask his daughters.

Mr. Maclean’s 11-year-old twins, Flora and Alice, turned out to be the experts Ms. Ishibashi was looking for. They play the game at school, Alice said, “practically every day.”

“Everybody knows you always start with scissors,” she added. “Rock is way too obvious, and scissors beats paper.” Flora piped in. “Since they were beginners, scissors was definitely the safest,” she said, adding that if the other side were also to choose scissors and another round was required, the correct play would be to stick to scissors – because, as Alice explained, “Everybody expects you to choose rock.”

Sotheby’s didn’t admit to any strategy.  Bad choice, perhaps, because the Sotheby’s official picked rock paper, which was beaten by the Christie’s person’s scissors.  Clearly 11-year olds know their game theory.

But wait, there’s more!  The following year, a judge made two parties settle a dispute using RPS:  (From CNNmoney.com):

This matter comes before the Court on Plaintiff’s Motion to designate location of a Rule 30(b)(6) deposition (Doc. 105). 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.

Humans aren’t the only ones with an eye towards the game.  According to Wikipedia, generator of this entire post and the inspiration of a new Category, E-coli plays as well:

antibiotic-producers defeat antibiotic-sensitives; antibiotic-resisters multiply and withstand and out-compete the antibiotic-producers, letting antibiotic-sensitives multiply and out-compete others; until antibiotic-producers multiply again.

And so do lizards out in California (from this bio page)Lizard

As in the rock-paper-scissors game where rock beats scissors, paper beats rock, and scissors beats paper, three morphs of lizards cycle from the ultra-dominant polygynous orange-throated males, which best the more monogamous mate gaurding blues; the oranges are in turn bested by the sneaker strategy of yellow-throated males, and the sneaker strategy of yellows is in turn bested by the mate guarding strategy of blue-throated males.

So there you have it.  Maybe not the simple game I thought it was after all.

Advertisements

KenKen

November 19, 2008

kenkenproblemBarbie might think math is hard, but perhaps she’d be willing to try this game.  I just heard about it yesterday around the water cooler copier (Thanks Lynn!).  It’s a little bit like Killer Sudoku, but with operations other than just addition.

The initial grid is a square, perhaps 4×4 or 6×6.  Like Sudoku, the digits 1-4 or 1-6 are put in cells so that each row contains exactly one of the digits and each column contains exactly one of the digits.

In addition, there are groups of cells (like the cages in Killer Sudoku).  In the corner is a number and an operation.  If the digits in a group are put together with that operation, they form the given number.  For example, if there are two cells with “8x” in the corner, the digits multiply to 8, and so must be 1&8 or 2&4 in some order.  Likewise, “2/” (using / for division) could be 1&2, 2&4, 3&6, or 4&8 where the pairs are in either order.  While you can’t repeat digits in any row or column, you can repeat digits in a group of cells.

Here’s one to try, courtesy of SGBailey.

kenkenproblem

(You can find the answers in the place that always gives you answers.)

If you search for KenKen there seem to be several sites where you can get your daily fix (including the New York Times), but most require registration.  And apparently in some of the harder versions the operation is left off so that you know the answer, but not whether it is a sum, product, quotient, or different.  I can totally imagine a variation that uses multiple operations in a single group of cells, but as far as I know that hasn’t been invented yet.

Crossnumbers

July 9, 2008

The San Francisco Chronicle carries Sudoku by the comics, but it turns out that it has an additional Sudoku-like puzzle hidden in the classifieds. And by Sudoku-like, I mean not really at all like Sudoku except that it involves digits being put into boxes. Actually, it’s more like Kakuro now that I think about it, except you can have the same digit appear more than once in a row or column. So, in fact, it’s not really like either one.

The idea is that there is a 4×4 grid with one digit in each box. The sum of each row is given on the right (shown below in bold), the sum of each column is given below the column (shown here in bold), and the sum of the diagonals is also given. In addition, some of the entries are already given.

Cross Numbers
18
3 1 12
6 19
4 18
1 4 13
23 7 17 15 11

In theory, these could be solved logically, but it turns out that (at least for the puzzles in the Chronicle) there are multiple solutions, and the practice of making a guess, checking how far off you are, and then adjusting the guess works pretty well for these.

Aside: My brother-in-law Scott, who brought these to our attention (thanks Scott!) said he’d looked around on the internet for info on this puzzle but couldn’t really find anything. This may be due to the fact that “Cross Numbers” seems to refer to more than one game: I also found a game that was more like Crossword puzzles, with teach Across or Down clue leading to a number, one digit per square. You can see an example here.

Scoring March Madness

March 27, 2008

basketball.pngThis weekend marks the second weekend of the NCAA basketball tournament (aka March Madness). For many, the NCAA tournament is the last chance to watch some of the best college basketball around. For others, it’s a time to fill out brackets, decide which 10-7 upset to pick, flip a coin on the 8-9 games, and cross your fingers.

If you’ve ever participated in an NCAA office pool, you’re familiar with at least one way of scoring correct bracket picks. For example, each correct pick is worth 1, 2, 4, 8, 16, and 32 points, in the 1st, 2nd, 3rd, 4th, 5th, and 6th rounds, respectively. This makes each round worth the same number of points, and thus gives equal weight to each round. But is that the best way to do things?

When I was still in graduate school, several of us (looking for another way to kill time so as to avoid doing real work) decided to examine different schemes for scoring brackets. Not that we were participating in an office pool – just in case we ever wanted to join one. Or start one. Or run one for several years.

With the above scheme (1, 2, 4, 8, 16, 32), there are 192 points available in the entire tournament, and each round is worth 1/6 of those points, giving each round equal weight. This places a great deal of weight on the final game, and for whatever reason, we found that unacceptable. Of course, being able to determine the overall winner out of 64 (now 65) teams ought to be significant, but we didn’t want an incorrect pick to essentially eliminate someone from the contest. So we started analyzing other natural-looking sequences of length 6, computing the relative weights of each round for each sequence:

Points per game (Rds. 1-6) Relative round weights (%)
1, 2, 4, 8, 16, 32 16.7, 16.7, 16.7, 16.7, 16.7, 16.7
1, 2, 3, 4, 5, 6 26.7, 26.7, 20, 13.3, 8.3, 5
1, 2, 3, 5, 8, 13 23.4, 23.4, 17.5, 14.6, 11.7, 9.5
1, 2, 3, 5, 10, 15 22.4, 22.4, 16.8, 14, 14, 10.4
2, 3, 5, 7, 11, 13 29.8, 22.3, 18.6, 13, 10.2, 6

Certainly there are other “natural” sequences that could be analyzed. We ended up choosing liking 1, 2, 3, 5, 10, 15 (although I no longer remember why). Perhaps it was a happy medium between schemes which weighted the final game too low (5 or 6%) and schemes that weighted it too high (16.7%). Regardless, we congratulated each other on an excellent nerding.

Later that spring, I discovered that Microsoft has an Excel template for scoring NCAA brackets, and I went berserk playing with it… but that’s a story for another day.

Math in the News: Infinities

January 16, 2008

infinity.jpgYesterday’s Science News Online featured the article “Small Infinity, Big Infinity” by Julie J. Rehmeyer, also available in blog form with some interesting comments here, in which Rehmeyer describes a brand new method by Matthew H. Baker of proving that the set of real numbers is uncountable!!! Cool beans! Click to read more about the article and Baker’s method!

Juxtapositions: Killer Sudoku

December 23, 2007

killer-sudoku.jpgIn a comment on an earlier post aboout Sudoku and Kakuro, Batman mentioned a combination of the two games known alternately as Killer Sudoku, Samunamupure or Sum Number Place. As in traditional Sudoku, Killer Sudoku is played on a 9×9 grid in which the digits 1-9 are placed so that each digit appears once in each row, each column, and each 3×3 grid (nonet). As in Kakuro, groups of cells (cages) add to given sums, and within each cage the digits must be distinct. Click to read more and see an enlargement of the game pictured here at the left.

Hashi (Bridges)

November 28, 2007

bridge.jpgIn the game Hashi or Hashiwokakero (Bridges/Chopsticks or Let’s Build Bridges!), you are given islands and you have to build bridges north-south or east-west between them. You are told the total number of bridges attached to each island, and you can build at most two bridges between any pair of islands. The bridges can’t cross, and it must be possible at the end to go from any island to any other island via some combination of bridges.

In other words, you are given the vertices of a graph and you have to construct vertical or horizontal edges. You are told the degree of each vertex, and you can have up to two edges between each pair of vertices. The final graph is planar and connected. Sound like fun? Then try it out here!

There are several mathematical questions you can ask:  What is the greatest number of bridges emanating from a single island?  What are the greatest/fewest number of bridges you could have for a given number or configuration of islands?  A quick search didn’t reveal nearly as much published on the mathematics of Hashi compared to, say, Sudoku, so this might be a fruitful area for some fun research!

The photograph of the bridge over the Struma River in Bulgaria is copyrighted © Nikola Gruev and is published on Wikipedia Commons under the terms of the GNU Free Documentation License.

And speaking of the Prisoner’s Dilemma…

November 22, 2007

My favorite example of the Prisoner’s Dilemma in literature occurs in the book Golem in the Gears by Piers Anthony (book 9 in the Xanth series).  In this book, a character examines the best strategy for playing the game multiple times, with different people (or beings, as the case may be).

Tryptophan and Game Theory

November 21, 2007

l-tryptophan-3d-sticks.pngYou may have heard the fact that turkey contains tryptophan, an amino acid that the body uses in the production of serotonin. You may also have heard that it’s the tryptophan that causes post-Thanksgiving drowsiness.

This direct link is questionable (see, for example, Live Science). However, there’s a new connection afoot: tryptophan has been shown to affect trust and cooperation. And the study measuring that effect used Game Theory!

According to ABC News earlier today, neuroeconomists [did you even know there was such a job title?] used the Prisoner’s Dilemma to measure cooperation. Volunteers who drank a substance reducing their tryptophan levels were significantly less likely to cooperate than those with normal tryptophan levels, and they were also more suspicious of other players. Does this mean that eating turkey will make you more cooperative? Probably not (the levels are likely too low to make any difference), but we’re still happy to have an Actual Math Post related to Thanksgiving Day.

Juxtapositions: The Rubik’s Hypercube

November 18, 2007

Rubik's cube variationsMany people are familiar with the Rubik’s Cube, the 3x3x3 cube with colored faces that can be moved out of position and then, ideally, twisted back into place. This toy, originally called the Magic Cube, was invented by Ernő Rubik in 1974 while he was a lecturer at the Academy of Applied Arts and Crafts in Budapest, Hungary. In 1980 the cube made its way to other countries and spawned, among other things, a one-season cartoon series Rubik, the Amazing Cube in which some kids use a magical come-to-life Rubik’s Cube to solve mysteries, while avoiding the mandatory evil magician who wants to steal the Cube.

Click to read more and watch the Cartoon Intro, because you know you want to

Sudoku and Kakuro

November 12, 2007

In recent years many people have played Sudoku, a number game in which a nine-by-nine grid is filled with the digits 1-9 so that each row, each column, and each group of nine squares contains exactly one of each digit. Read more about Sudoku and Kakuro

Toilet Seat Gymnastics

November 2, 2007

Economist Hammad Siddiqi has used game theory to model the seat up/seat down “conflict” as a two-person noncooperative game. It’s amusing, but the math is real.

In other toilet-related news (what a way to start off a blog, eh?), this won an award for “Most Bizarre” micrograph. (via Good Math, Bad Math).