Game Theory and Logic – Rough Work
Question 1
Given the payoff matrix, Player II must be indifferent between L and R for Player I to mix.
Let p be the probability that Player I plays B.
Payoff to Player II from L:
u(L) = 1(1 − p) + 0(p) = 1 − p
Payoff to Player II from R:
u(R) = 0(1 − p) + 1(p) = p
Indifference gives 1 − p = p ⇒ p = 12 .
Now let q be the probability that Player II plays R.
Payoff to Player I from T:
u(T ) = 2(1 − q) + 4q = 2 + 2q
Payoff to Player I from B:
u(B) = 1(1 − q) + 3q = 1 + 2q
Since u(T ) > u(B) for all q, Player I always prefers T.
Thus p = 0, q = 0 and
7p + 2q = 0
Question 2
Player I commits to a mixed strategy and Player II best-responds.
Let Player I play B with probability p.
Player II payoff:
u(L) = 1 − p, u(R) = p
1
Player II chooses L if p < 2
and R if p > 12 .
Player I payoff if p < 21 :
uI = 2(1 − p) + 1(p) = 2 − p
If p > 21 :
uI = 4(1 − p) + 3(p) = 4 − p
1+
Taking p → gives payoff 3.5.
2
Thus Player I improves his payoff to 3.5.
1
Question 3
A forced checkmate in 4 moves exists with perfect play.
White is rational and therefore chooses the winning strategy. Black rationally defends
but cannot avoid mate.
Thus: White chooses (b) and Black chooses (c).
Question 4
Since a forced mate exists and White plays optimally, White wins.
Question 5
With two glass balls, use decreasing step strategy.
Find smallest n such that:
n(n + 1)
≥ 100
2
n = 14.
Worst case drops = 14.
Best case occurs if first drop determines outcome.
Best case drops = 1.
Question 6
If there are n cheating husbands, wives reason inductively.
No one is kicked out until night n.
Given no one was kicked out until the 9th night and some were kicked out on the 10th
night:
n = 10
Question 7
Let y be number of citizens whose salary increases and n whose salary decreases.
Voting rule:
y>n
Money balance:
King’s gain = n − y
If y > n, then n − y < 0.
So king cannot increase his salary.
Maximum salary = 1.
2
Question 8
After observing 100, probabilities are not symmetric unless improper priors are assumed.
Expected values cancel under proper modeling.
Thus switching gives no clear advantage.
Question 9
This is the poisoned chocolate (Chomp) game.
For all m, n > 1, the first player has a winning strategy.
Thus Player 1 wins for all listed cases.
Question 10
Let A play Rock, Paper, Scissors with probabilities R, P, S.
Indifference conditions:
P − 2S = −R + S = 2R − P
Solving gives:
1 1
R=S= , P =
4 2
Compute:
7R + 5P + 3S = 7(0.25) + 5(0.5) + 3(0.25) = 5.00
Question 11
Opponent offers trade only if holding card 1.
Keeping card 2 guarantees a win.
Thus trade should be rejected.
Question 12
Minimum moves equals number of bits needed to represent 2026.
210 = 1024, 211 = 2048
Thus minimum moves = 11.
Question 13
The knight graph on a chessboard has a Hamiltonian path.
Alice chooses starting square and follows it.
Thus Alice has a winning strategy.
3
Question 14
Each row is a take-1-or-2 game.
Rows with size ≡ 1, 2 (mod 3) have odd number of moves.
Tracking turn alternation gives the starting player per row.
Encoding bottom to top:
10110101
Question 15
Using backward induction:
Final distribution:
A = 98, B = 0, C = 1, D = 0, E=1
Compute:
11A + 7B + 5C + 3D + E = 11(98) + 5 + 1 = 1084