Tuesday, July 29, 2014

Abbreviated Game Theory Lesson

Context Summary

Contextually the students have been studying Game Theory. The understand the definition of a game. They have learned what a 2-person zero sum and non-zero sum game is. They will have learned how a game can be represented with a matrix along with payouts. Finally, the students will have learned what a 'strategy' is and how one can be dominant. Lessons after this reading will focus on Nash-Equilibria and how it is applied to Prisoner's Dilemma. The students will then look at other modern day examples where game theory can be useful. Game theory is a sub field of mathematics and the reading is designed for high school students.


Reading Summary

The article discusses the game theoretical situation called “Prisoner's Dilemma”. It is when two members of a criminal gang are arrested. The members must decide if they are going to “snitch” on their partner or remain silent. Each of the 4 possible scenarios result in different amounts of jail time for the criminals. The situation can be modeled by a matrix with different pay outs. The article discusses the confusing result that occurs when each players play “rationally”. The article then goes on to talk about extended “iterated” versions of the game where the game is played over and over between the same prisoners. After that the article discusses the tournaments that sprang from this iterated version of Prisoner's Dilemma.

Citation: Prisoner's Dilemma. In Wikipedia. Retrieved July 29th, 2014, from http://en.wikipedia.org/wiki/Prisoner's_dilemma

Flesch-Kincaid GradeLevel: 16.3




Prisoner's Dilemma Lesson Plan



2 mins

-Warmup: What is the difference between and zero-sum and non-zero some game?



20 mins

-Introduce Prisoner's Dilemma situation.

-Ask students how they would play the game

-Let students play the game with one partner

-Show the students that rational play and the idea of dominance leads both players to betray




10 minutes

-Introduce the idea of playing many consecutive rounds of the game

-Ask students what they think a good strategy might be like

-With the same partner let the students play a 10-iteration game of prisoner's dilemma





25 minutes

-Introduce the idea of playing multiple iterations with multiple pairs of partners

-Have students break into groups of 3 and play a round robin game of prisoner's dilemma with 10-iteration games

-Ask which students ending up with the highest score (lowest amount of jail time)

-Ask why students chose their strategy

-Introduce idea of cooperation





Tuesday, July 22, 2014

Game Theory Resources and Texts

Game Theory Resources 


1) Game Theory and Strategy, Phillip Straffin, Part III, The Mathematical Association of America



Summary
- 2-person games are the easiest to solve in game theory but most real life situations are modeled by -N > 2 person games, which are much more difficult
-There are still equilibria in n-person games but it is difficult to pick one over another as an assymetry exists
-things get further complicated if you allow communicate between players
-coalitions between players can affect the outcome
-a simplification to n-person games can be made if side-payments are allowed.

Motive: If you are interested in n-person games to simulate economic or population situations

Question: What would your strategy be in an n-person game? What conditions should an equilibria have for it to be considered a solution?

Difficulty: 86.9 Flesch-Kincaid Reading Ease


2) Game Theory Explained, Avinash Dixit, PBS


Summary:
-introduces definition of Game Theory
-desribes that game theory can be applied to sports, business, economics, politics, law, diplomacy and war
-Game theory got its start with the work of John von Neumann in the 1920s, which culminated in his book with Oskar Morgenstern. 
-introduces Nash Equilibria
-if the relationship between players is repeated over a long period of time

Motive: If you want a brief introductory into the history of Game Theory

Question: In what ways can game theory model real life?

Difficulty: 54.4 Flesch-Kincaid Reading Ease







3) Good Math, Bad Math, Introducing Game Theory, Mark C. Chu-Carroll, 3/19/08
-introduces Prisoner's Dilemma
-Game theory is not just about "games" as we think of them
-how 2 players maximizing their individual position can be a poorer choice
-is used in protocol design, models of markets

Motive: Read it if you want a basic introduction using the example situation "Prisoner's Dilemma"

Question: What would your strategy be if you were playing Prisoner's Dilemma?

Difficulty: 68.2 Flesch-Kincaid Reading Ease





4) The Evolution of Cooperation, Robert Axelrod, Basic Books, 1984

Summary:
-discusses the Prisoner's Dilemma tournaments and their winner "Tit for Tat"
-a game theoretic "live and let live" situation in the trenches of WWI. Soldiers would not shoot to kill so in return the other army would not shoot to kill
-cooperate can get started, evolve, and prove stable in situations that would otherwise appear very bleak
-for cooperate to occur the constant scenarios must go on for an indefinite period of time, otherwise slippery slope effect would take over
-the foundation of cooperation is not trust but rather the durability of the relationship
-the evolution simulation for Prisoner's Dilemma showed the retaliation should be done sooner rather than later
-the above is true due to signaling. Like with a pet, the punishment needs to directly proceed the event otherwise the correlation between behavior and punishment will not be made

Motive: If you want a much more in depth look into Game Theory

Question: What are some otherwise chaotic situations that could result in Game Theoretic cooperation?


Difficulty: 4.1 Flesch-Kincaid Reading Ease





Digital Media


Game Theory; Part 7, PatrickJMT, 9/23/12

Summary:
-goes over formulas to solve 2x2 matrix player games
-often times the result will be a mixed strategy
-for a general nxn matrix we will have to convert it to linear programming problems
-some higher nxn matrix games can be reduced down to 2x2 matrices

Motive: If you want to learn exactly how to solve the most simple 2x2 matrix games

Question: How might these formulas be generalized to higher order matrices?

Difficulty
Everything on scale 1-10, easy to hard
Content specific language: 9 (very many math specific words)
Difficult words: 5
Sentence Length and Complexity: 6



Game Theory Part 2: Nash Equilibrium, Bill Blaine, 5/28/13

Summary
-introduces the Prisonner's Dilemma game and matrix
-defines Nash Equilibria: when both players would lose value by changing their play, thus they stay in the same spot, ie. Equilibria
-finds Nash equilibria for Prisonner's dilemma
-finds that both players will confess in this equilibria

Motive: If you want to learn about basic Nash Equilibria and the solution to Prisoner's Dillema

Question: Why do the final strategies result in lower values than possible?

Difficulty
Everything on scale 1-10, easy to hard
Content specific language: 6 (reachable for non-mathematicians)
Difficult words: 4
Sentence Length and Complexity: 4


Use of texts in total
These texts can be used congruently. You would start with the articles that briefly introduce you to Game Theory and its history. You would then look at the articles dealing with Prisoner's Dilemma. Finally, you would look at the text that takes you into greater detail.

Thursday, July 17, 2014

Tit for Tat – Game Theory Infrograph!






When I upload my infrograph here it is too small, follow the links to see it

Tit for Tat – Game Theory Reflection


         Tit for Tat – Game Theory Reflection




          Some people think Game Theory is just about games, but it's not. It is the mathematical study of decision making and was created by John Von Neumann in the 1920s. A “game” is any situation between players that results in gains or losses for each player. It allows to assign a numerical value to each benefit or deficitt from the result of the game (situation) This might sound too theoretical but all you really need to know is peoples' relative
          The picture of the two people on my first page shows a game The picture is of a 2x2 matrix. Each square in the matrix has two numbers. One for you and one for your opponent. These numbers represent a numerical payout for each player. A negative number represents a loss. The particular picture on the page is called “Prisoner's Dilemma. It is a situation in which two people are suspected of a crime. Both people have a choice to make. They can confess or they can remain silent. The picture on the page helps you understand the consequences of each combination of choices ie. One player could confess and the other could remain silent, on both players could confess. The numbers on the picture represent the number of years in jail each person will have to serve. For example, if one player confesses and the other doesn't the confessing player will have no years in jail and the other player will receive 20 years in jail. However, If you look at the numbers carefully you will actually notice that no matter what you r opponent does it always best to confess. This makes things not very interesting. The interesting part comes when you start having multiple players each playing multiple one-ones. Is cooperation now a useful thing?
          This game of “Prisoner's Dilemma was so famous that a man named Robert Axlerod held a tournament. He invited about a dozen players including other game theorists, mathematicians, economists, and people from all fields. They players themselves did not consciously play in the tournament, however, their strategies did. They had to submit an algorithm that would tell you what move to make based on all the previous games. Axelrod decided that each game would have 200 iterations (choices) and that the tournament would be round robin . The player with the most cumulative points wins.
           Many players submit detailed complicated strategies to the tournament. Strategies that take many lines of computer code to write. However a strategy named “Tit for Tat” won the tournament . And had less than five lines of code. Everybody was astounded. How could this strategies have won?
After this the tournament got more popular and this time the tournament had 200 players. A Cinderalla story, Tit for Tat wins again. No only did it win but everyone knew exactly what strategy it was before the tournament.. This made such a commotions that they started analyzing what was going on.


You can see from my infrograph that they determined that Tit for Tat had three important qualities. Being nice, being punishing, and being forgiving.. but what exactly do I mean..


  1. Being nice is cooperating on the first move
  2. Punishing is punishing your opponent after they hurt you
  3. Forgiving is when you stop punishing an opponent when they start cooperating again.



          This data led to more research. What if we looked at things from an evolutionary view point? One game theorist did. He used a super computer and ran 9000 sequential tournaments. Meaning there were 9000 birth and deaths cycles to allow for evolution. Amazingly, the data they found showed strategies that were very similar to Tit for Tat. This is beautiful and gives a mathematical reason that our evolution is towards altruism.

Sunday, July 6, 2014

Introduction to Game Theory, Equilibrium, and John Nash

Game theory is a fascinating subject.  It is the mathematical study of decision making.  The name is a little mislead as it is not just the games we think of.  A ‘game’ is any situation in which two or more players make choices which result in gains or losses.  It is the study of making decisions logically.
                There are two types of games.  Zero-sum games non-zero sum games.  A zero-sum game is one in which a gain by any player has to come from a loss by another player.  This is why it is zero-sum, if you add up every players gains and losses you will get 0.  This is not true for a non-zero sum game.  In this game there are choices that can be made that result in gains for both players involved.   This makes cooperation possible.  However, it is still cut throat.  All players are still trying to optimize their gains.  In games like this alliances might form and players may get punished.  It is obvious that non-zero sum games are the ones that model reality much better.  However the zero-sum games are much simpler.  In fact, the field of finite zero-sum games for 2 players is completely solved.  Meaning for any situation each player can find their optimal decision by using math. 
                The solution to the problem is also called an equilibrium, because this is the spot in which both players lay.  If a player strays from that equilibrium at all, they lower their net-pay off and so thus both players stay.  The method for finding this equilibrium was proven by John von Neumann (the founder of Game Theory as a discipline!).
                This is where John Nash comes in.  His breakthrough was finding equilibriums in non-zero sum games.  This is gigantic because non-zero sum games are much more complicated.  It was his most famous contribution and he won the Nobel Prize in Economics for it, (because economic situations could be represented in this way.  There is a funny story (only to me) where a young mathematician is walking by John von Neumanna and asks John if he thought his zero-sum game equilibrium could be generalized to non-zero sum games.  John just kind of waves it off dismissing it and mutters “yes, I’m sure of it”.  Implying that he thought it could be done but that it wasn’t very important.  I guess this was fortunate for John Nash.  Sometimes even the smartest mathematicians can’t always predict which of their ideas will be the biggest, even many years after their death.
This introduction to game theory took most of this post length so I will have to make succinct the things that I would like to learn more about.  I will include a link below them where I can learn more about it:
a)      I want to learn more about non-zero sum games involving more than two people


(a webpage/article)

b)      I want to learn the ways in which game theory has been put into practice in real life
(a TED talk)



c)       I want to learn which activities I can use to introduce my students to Game Theory
(A simple introductory game called “Prisoners Dilemma”)

d)      I want to learn more about John Nash and his struggle with mental illness. http://www.amazon.com/The-Essential-John-nash/dp/0691096104/ref=zg_bs_917108_7

(a Biography)

Saturday, July 5, 2014

Dan Strelnick and John Nash

My name is Dan Strelnick.  I’m 29 years old and was born in Madison.  I was a math/physics double major at Beloit College.  My final year I got to study in the Budapest Semester in Mathematics program in Hungary.  I’ve loved math since I was little and am still in awe of how it combines of rigor and beauty. 

These things inspired me to go to Grad School, however, I ended up leaving.  I wanted to do something that directly helped people and doing theoretical mathematics started seeming like a game. The desire to help people led me to teaching. 

I taught full-time for one year until my emergency licensure wore out.  Since then I have worked as a paraprofessional for MPS.  I have gotten to work with some amazing teachers and I know that I’ve learned a lot just by watching them.  I think that is the fastest way to learn, to watch the best. You pick up the intangible things they do.  I like teaching very much, it is a lot like a performance.  I like showing students the beauty of math, I like making fun of students, and I like teaching students to think, which to me, is the essence of math.


My blog will be about game theory, how I can teach it to students, and it will be about famous Mathematician and Game Theorist named John Nash.  John is a Nobel Laureate and famous for his contributions to Game Theory.  His ideas have been used in economics, political science, the military, and any type of negotiations.  He has also had a movie made about him,  “A Beautiful Mind”.  I’m going to talk about his life, his contributions to mathematics, and the mental illness he eventually developed.

I chose game theory because it's a fascinating topic and I chose Nash because he has a very interesting story.  Game theory also lends itself to lots of hands on activities and games so I am excited about teaching it to students. I am also interested in looking at the mental illness aspect of his life, as this seems to be a theme among some of the most brilliant people.