Test 1 Flashcards Preview

Game Theory > Test 1 > Flashcards

Flashcards in Test 1 Deck (28)
Loading flashcards...
0

Coordinates for chicken

C= swerve n= not swerve
CC 3,3
CN 2,4
NN 1,1
NC 4,2

1

Coordinate for battle of the sexes

O opera B baseball
BB 4,3
OB 1,1
BO 2,2
OO 3,4

2

Prisoner's Dilemma

C don't tell N tell
CC 3,3
NC 4,1
CN 1,4
NN 2,2

3

Dominant strategy

A common best response for both strategies of the other player

4

Nash equilibrium

A strategy profile for which neither player gains by unilaterally switching strategies

5

2 dom strategies = how many Nash equilibriums?

1

6

1 dominant strategy = how many Nash equilibriums?

1

7

0 dominant strategies = how many Nash equilibrium?

0 or 2

8

What is paradoxical about Prisoner's Dilemma?

They both have a CBR of N and N but strategy profile NN doesn't have the best outcome since it is ranked 2,2

9

Winning strategy for player 1 in nim(m,n)

If m is not a variable of n+1. First move reduce running sum to a multiple of n+1. Subsequent moves respond to j with (n+1)-j

10

Player twos winning strategy in Nim(m,n)

If m is a multiple if n+1 respond to j with (n+1)-j

11

Player ones winning strategy in RNim(m,n)

If m is not a variable of one more than n+1. First move reduce running sum to a multiple of one more than n+1. Respond to j with (n+1)-j

12

Winning strategy for player two in RNim(m,n)

If m is a multiple of one more than n+1 respond to j with (n+1)-j

13

ChooseNim winning strategy

Player one only! Choose a number for m that is not a multiple of (n+1)

14

What does TFGWT stand for

Totally finite games without ties

15

Five properties of TFGWT

1 there are two players, player I and player II, who move alternately with player I going first
2 no randomizing mechanisms are used
3 whenever a play ends, exactly one winner exists
4 each play ends after finitely many moves
5 at any moment, in any play, tyre at only finitely many options for a legal next move.

16

Strategy in TFGWT

A set of rules that specify a single move for every partial play leading up to turn

17

Winning strategy

A strategy that makes it impossible for a play to lose a play of the game by following the rules

18

Sub tree

The part if a tree containing a node with all the nodes hanging from that node

19

Play

A legal sequence of moves hat begins before anyone has moved and ends when the game is over

20

Branch

The sequence of nodes of a winning strategy

21

Fork

The different strategy results coming from a node

22

Pigeonhole Principle finite version

If we have n amount of items to put into m bins and n>m then at least one bin will have more than one object.

23

Pigeonhole principle infinite version

If we have infinitely many object and finite many bns, some bins will have infinitely many objects,

24

Konig's Infinity Lemma

No tree can satisfy the following three:
1 every fork of t is finite in width
2 every branch of T is finite in length
3 T has infinitely many nodes altogether

25

Variants of KIL

Variant 1- every tree satisfying both 1 and 2 violates 3
Variant 2 every tree satisfying both1 and 3 violates 2

26

What are the bins in the applying PHP to prove KIL

Subtrees

27

Zermelo's Theorem

For every TFGWT, either player I or player II has the winning strategy