# Analytically solving (calculating Nash equilibrium for) 3-player extensive form games

Let's say we extend the popular half-street Kuhn poker variant to 3 players. The rules would be as follows:

Rules of 3-Player Half-Street Kuhn Poker
- 3 Players
- 4 cards in the deck (J, Q, K, A; or 0-3 if you prefer)
- All players ante 1 chip
- P1 can bet or check
- If P1 checks, P2 and P3 must check. Showndown occurs.
- If P1 bets, P2 and P3 can each call or fold.


This is effectively an extensive form game, where you have 24 possible combinations of hands:

P1=A P2=K P3=Q
P1=A P2=K P3=J
P1=A P2=Q P3=K
P1=A P2=Q P3=J
P1=A P2=J P3=K
P1=A P2=J P3=Q
... (18 more)


Each combination starts a subtree with one decision node each for P1 and P2, and two nodes for P3:

Prob(P1 bets)
Prob(P2 calls | P1 bets)
Prob(P3 calls | P1 bets and P2 calls)
Prob(P3 calls | P1 bets and P2 folds)


Each subtree results in 5 leaf nodes: c, bcc, bcf, bfc, bcf. This means we have a game tree of $24*5=120$ leaf nodes.

My question is two-fold. First, this game seems small enough to solve analytically-- how would that work? Second, are there any iterative methods guaranteed to converge to an optimal solution for > 2 player games? I know Counterfactual Regret Minimization and Fictitious-Play are only assured for 2-player games.

-
if P1 bets, is it 1 chip, or any number of chips ? – Xoff Jan 18 '13 at 15:55
It's fixed at 1 bet. – Wesley Tansey Jan 19 '13 at 0:40

## 1 Answer

Many analytical solutions have been found, see http://poker.cs.ualberta.ca/publications/AAMAS13-3pkuhn.pdf.

As for iterative methods, it has been proven that counterfactual regret minimization ". . . eliminates strictly dominated plays . . ." in games that are not two player zero-sum (see Richard Gibson's dissertation: http://poker.cs.ualberta.ca/publications/gibson.phd.pdf).

-