# Test 1 Flashcards

0
Q

Coordinate for battle of the sexes

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

Coordinates for chicken

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

Prisoner’s Dilemma

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

Dominant strategy

A

A common best response for both strategies of the other player

4
Q

Nash equilibrium

A

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

5
Q

2 dom strategies = how many Nash equilibriums?

A

1

6
Q

1 dominant strategy = how many Nash equilibriums?

A

1

7
Q

0 dominant strategies = how many Nash equilibrium?

A

0 or 2

8
Q

A

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
Q

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

A

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
Q

Player twos winning strategy in Nim(m,n)

A

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

11
Q

Player ones winning strategy in RNim(m,n)

A

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
Q

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

A

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

13
Q

ChooseNim winning strategy

A

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

14
Q

What does TFGWT stand for

A

Totally finite games without ties

15
Q

Five properties of TFGWT

A

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
Q

Strategy in TFGWT

A

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

17
Q

Winning strategy

A

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

18
Q

Sub tree

A

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

19
Q

Play

A

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

20
Q

Branch

A

The sequence of nodes of a winning strategy

21
Q

Fork

A

The different strategy results coming from a node

22
Q

Pigeonhole Principle finite version

A

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
Q

Pigeonhole principle infinite version

A

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

24
Q

Konig’s Infinity Lemma

A

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
Q

Variants of KIL

A

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

Variant 2 every tree satisfying both1 and 3 violates 2

26
Q

What are the bins in the applying PHP to prove KIL

A

Subtrees

27
Q

Zermelo’s Theorem

A

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