Kuhn poker
Kuhn poker is a simplified form of poker developed by Harold W. Kuhn as a simple model zero-sum two-player imperfect-information game, amenable to a complete game-theoretic analysis. In Kuhn poker, the deck includes only three playing cards, for example a King, Queen, and Jack. One card is dealt to each player, which may place bets similarly to a standard poker. If both players bet or both players pass, the player with the higher card wins, otherwise, the betting player wins.
Game description
In conventional poker terms, a game of Kuhn poker proceeds as follows:
- Each player antes 1.
- Each player is dealt one of the three cards, and the third is put aside unseen.
- Player one can check or bet 1.
- If player one checks then player two can check or bet 1.
- If player two checks there is a showdown for the pot of 2 (i.e. the higher card wins 1 from the other player).
- If player two bets then player one can fold or call.
- If player one folds then player two takes the pot of 3 (i.e. winning 1 from player 1).
- If player one calls there is a showdown for the pot of 4 (i.e. the higher card wins 2 from the other player).
- If player one bets then player two can fold or call.
- If player two folds then player one takes the pot of 3 (i.e. winning 1 from player 2).
- If player two calls there is a showdown for the pot of 4 (i.e. the higher card wins 2 from the other player).
- If player one checks then player two can check or bet 1.
Optimal strategy
The game has a mixed-strategy Nash equilibrium; when both players play equilibrium strategies, the first player should expect to lose at a rate of −1/18 per hand (as the game is zero-sum, the second player should expect to win at a rate of +1/18). There is no pure-strategy equilibrium.
Kuhn demonstrated there are infinitely many equilibrium strategies for the first player, forming a continuum governed by a single parameter. In one possible formulation, player one freely chooses the probability with which he will bet when having a Jack (otherwise he checks; if the other player bets, he should always fold). When having a King, he should bet with the probability of (otherwise he checks; if the other player bets, he should always call). He should always check when having a Queen, and if the other player bets after this check, he should call with the probability of .
The second player has a single equilibrium strategy: Always betting or calling when having a King; when having a Queen, checking if possible, otherwise calling with the probability of 1/3; when having a Jack, never calling and betting with the probability of 1/3.
Generalized versions
In addition to the basic version invented by Kuhn, other versions appeared adding bigger deck, more players, betting rounds, etc., increasing the complexity of the game.
3-player Kuhn Poker
A variant for three players was introduced in 2010 by Nick Abou Risk and Duane Szafron. In this version, the deck includes four cards (adding a ten card), from which three are dealt to the players; otherwise, the basic structure is the same: while there is no outstanding bet, a player can check or bet, with an outstanding bet, a player can call or fold. If all players checked or at least one player called, the game proceeds to showdown, otherwise, the betting player wins.
A family of Nash equilibria for 3-player Kuhn poker is known analytically, which makes it the largest game with more than two players with analytic solution.[1] The family is parameterized using 4–6 parameters (depending on the chosen equilibrium). In all equilibria, player 1 has a fixed strategy, and he always checks as the first action; player 2's utility is constant, equal to –1/48 per hand. The discovered equilibrium profiles show an interesting feature: by adjusting a strategy parameter (between 0 and 1), player 2 can freely shift utility between the other two players while still remaining in equilibrium; player 1's utility is equal to (which is always worse than player 2's utility), player 3's utility is .
It is not known if this equilibrium family covers all Nash equilibria for the game.
References
- Kuhn, H. W. (1950). "Simplified Two-Person Poker". In Kuhn, H. W.; Tucker, A. W. (eds.). Contributions to the Theory of Games. Vol. 1. Princeton University Press. pp. 97–103.
- James Peck. "Perfect Bayesian Equilibrium" (PDF). Ohio State University. Retrieved 2 September 2016.: 19–29
- ^ Szafron, Duane; Gibson, Richard; Sturtevant, Nathan (May 2013). "A Parameterized Family of Equilibrium Profiles forThree-Player Kuhn Poker" (PDF). In Ito; Jonker; Gini; Shehory (eds.). Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013). Saint Paul, Minnesota, USA.
External links
- Effective Short-Term Opponent Exploitation in Simplified Poker
- v
- t
- e
- Congestion game
- Cooperative game
- Determinacy
- Escalation of commitment
- Extensive-form game
- First-player and second-player win
- Game complexity
- Graphical game
- Hierarchy of beliefs
- Information set
- Normal-form game
- Preference
- Sequential game
- Simultaneous game
- Simultaneous action selection
- Solved game
- Succinct game
concepts
- Bayes correlated equilibrium
- Bayesian Nash equilibrium
- Berge equilibrium
- Core
- Correlated equilibrium
- Epsilon-equilibrium
- Evolutionarily stable strategy
- Gibbs equilibrium
- Mertens-stable equilibrium
- Markov perfect equilibrium
- Nash equilibrium
- Pareto efficiency
- Perfect Bayesian equilibrium
- Proper equilibrium
- Quantal response equilibrium
- Quasi-perfect equilibrium
- Risk dominance
- Satisfaction equilibrium
- Self-confirming equilibrium
- Sequential equilibrium
- Shapley value
- Strong Nash equilibrium
- Subgame perfection
- Trembling hand
- Backward induction
- Bid shading
- Collusion
- Forward induction
- Grim trigger
- Markov strategy
- Dominant strategies
- Pure strategy
- Mixed strategy
- Strategy-stealing argument
- Tit for tat
of games
- Go
- Chess
- Infinite chess
- Checkers
- Tic-tac-toe
- Prisoner's dilemma
- Gift-exchange game
- Optional prisoner's dilemma
- Traveler's dilemma
- Coordination game
- Chicken
- Centipede game
- Lewis signaling game
- Volunteer's dilemma
- Dollar auction
- Battle of the sexes
- Stag hunt
- Matching pennies
- Ultimatum game
- Rock paper scissors
- Pirate game
- Dictator game
- Public goods game
- Blotto game
- War of attrition
- El Farol Bar problem
- Fair division
- Fair cake-cutting
- Cournot game
- Deadlock
- Diner's dilemma
- Guess 2/3 of the average
- Kuhn poker
- Nash bargaining game
- Induction puzzles
- Trust game
- Princess and monster game
- Rendezvous problem
figures
- Albert W. Tucker
- Amos Tversky
- Antoine Augustin Cournot
- Ariel Rubinstein
- Claude Shannon
- Daniel Kahneman
- David K. Levine
- David M. Kreps
- Donald B. Gillies
- Drew Fudenberg
- Eric Maskin
- Harold W. Kuhn
- Herbert Simon
- Hervé Moulin
- John Conway
- Jean Tirole
- Jean-François Mertens
- Jennifer Tour Chayes
- John Harsanyi
- John Maynard Smith
- John Nash
- John von Neumann
- Kenneth Arrow
- Kenneth Binmore
- Leonid Hurwicz
- Lloyd Shapley
- Melvin Dresher
- Merrill M. Flood
- Olga Bondareva
- Oskar Morgenstern
- Paul Milgrom
- Peyton Young
- Reinhard Selten
- Robert Axelrod
- Robert Aumann
- Robert B. Wilson
- Roger Myerson
- Samuel Bowles
- Suzanne Scotchmer
- Thomas Schelling
- William Vickrey
- All-pay auction
- Alpha–beta pruning
- Bertrand paradox
- Bounded rationality
- Combinatorial game theory
- Confrontation analysis
- Coopetition
- Evolutionary game theory
- First-move advantage in chess
- Glossary of game theory
- List of game theorists
- List of games in game theory
- No-win situation
- Solving chess
- Topological game
- Tragedy of the commons
- Tyranny of small decisions