<p>Well, for this you need to define what a "finite game" is. The usual way to do so, is to define it as an extensive form game, which makes the whole issue circular. But there are different ways to model extensive form games at different levels of generality. For example, the first definition due to John von Neumann and Oskar Morgenstern made a number of strong restrictions on timing that look somewhat archaic from today's perspective. The subsequent definition by Harold Kuhn significantly generalized the class of possible extensive form games. An implicit restriction in the way Kuhn defined extensive form games was that no player is allowed to move through the same information set twice, an assumption weakened in the Ph.D. thesis of John Isbell. So there are various notions of extensive form games at various levels of generality, including versions that allow for infinite games.</p>

CC BY-SA 4.0
2018-09-23T12:04:36.737Z
Thank you! Could you point me in a direction of a book or paper that describes how to model an infinite game in extensive form please?
Arthur Tarasov
CC BY-SA 4.0
2018-09-23T20:12:57.070Z
The textbook by Osborne & Rubinstein should have enough to get you started. If you need more or something specific, let me know.
Michael Greinecker
CC BY-SA 4.0
2018-09-23T09:01:58.843Z
2018-09-23T09:01:58.843Z
Michael Greinecker
<p>An interesting thought...</p>

<p>I guess that recoursive games, where a result is dependent on playing the same game, in a dynamic count of times, cannot be represented in a form or a matrix</p>

<p>A more common case is multiplayer simultaneous games, when has 2 player requires a 2d  matrix, each new player will add a dimension to the matrix, more than 3 will not be able to have a graph representation, but only a database like schema</p>

CC BY-SA 4.0
2018-09-22T10:54:35.593Z
Games with loops and recoursive games are not finite games. The because of the loops, the number of decisions points and hence the number of strategies are infinite.
Giskard
CC BY-SA 4.0
2018-09-22T10:56:50.713Z
Perhaps I misunderstand your last paragraph, but game trees can depict $n$-player games easily even if $n>3$. You just have to annotate the decision points.
Giskard
CC BY-SA 4.0
2018-09-22T11:19:54.597Z
@denesp regarding the last paragraph, simultaneous games are described with a 2d matrix where each dimension represents a player, so adding a 3rd play will be described as a cube, and with a game of 4, the forth cannot be displayed
Guy Louzon
CC BY-SA 4.0
2018-09-22T11:21:05.407Z
@denesp why not? an finite yet unknown number of iterations, when each end of loop can lead to a different result, is a finite game with no ability to be modeled by a tree
Guy Louzon
CC BY-SA 4.0
2018-09-22T13:43:15.790Z
This comes down to the basic issue of what is an infinite sit. If I can think of any number, I will think of a finite number, but the set of numbers I can think of is still infinite. You invite the same issue by introducing loops.
Giskard
CC BY-SA 4.0
2018-09-22T14:05:25.290Z
ok, I get your point... even if you may have a 1000 identical iterations, but it is still finite, then they can be displayed on a tree...
Guy Louzon
CC BY-SA 4.0
2018-09-22T14:30:33.763Z
When I think about it, the only exception to that is recoursive games...
Guy Louzon
CC BY-SA 4.0
2018-09-22T20:01:52.117Z
I would like to reiterate my second comment, which you seem to have glossed over. $n$-player games, even simoultaneous games can be easily depicted via tree graphs. [An example](https://plato.stanford.edu/entries/game-theory/figure13.jpg) (albeit for a non-simoultanous move game, but the logic is the same).
Giskard
CC BY-SA 4.0
2018-09-22T07:35:07.207Z
2018-09-22T14:30:54.163Z
2018-09-22T14:30:54.163Z
Guy Louzon
<p>Is there a finite game that cannot be represented by an <a href="https://en.wikipedia.org/wiki/Extensive-form_game" rel="nofollow noreferrer">extensive form</a> or a game tree?</p>

<p>I know that many games are too long and complex to be represented by a tree of a reasonable size, but that's not what I'm looking for because it is in part a computational limitation.</p>

<p>Instead I wonder if there is something simple out there that just doesn't fit into an extensive form? All the books that I've read say something like </p>

<blockquote>
  <p>Various games can be represented by trees</p>
</blockquote>

<p>But I haven't seen "all games" claim anywhere. Are there any known exceptions?</p>

<game-theory>
Is there a game that cannot be represented by a game tree?
Arthur Tarasov
# Is there a game that cannot be represented by a game tree?

(Asked by: username_0 on 2018-09-22)

Is there a finite game that cannot be represented by an [extensive form](https://en.wikipedia.org/wiki/Extensive-form_game) or a game tree?

I know that many games are too long and complex to be represented by a tree of a reasonable size, but that's not what I'm looking for because it is in part a computational limitation.

Instead I wonder if there is something simple out there that just doesn't fit into an extensive form? All the books that I've read say something like

> Various games can be represented by trees

But I haven't seen "all games" claim anywhere. Are there any known exceptions?

**Tags:** game-theory


---

## 2 answers

### Answer by username_1 on 2018-09-23. Score: 7

Well, for this you need to define what a "finite game" is. The usual way to do so, is to define it as an extensive form game, which makes the whole issue circular. But there are different ways to model extensive form games at different levels of generality. For example, the first definition due to John von Neumann and Oskar Morgenstern made a number of strong restrictions on timing that look somewhat archaic from today's perspective. The subsequent definition by Harold Kuhn significantly generalized the class of possible extensive form games. An implicit restriction in the way Kuhn defined extensive form games was that no player is allowed to move through the same information set twice, an assumption weakened in the Ph.D. thesis of John Isbell. So there are various notions of extensive form games at various levels of generality, including versions that allow for infinite games.

> **Comments:**
> **username_0**: Thank you! Could you point me in a direction of a book or paper that describes how to model an infinite game in extensive form please?  
> **username_1**: The textbook by Osborne & Rubinstein should have enough to get you started. If you need more or something specific, let me know.  

---

### Answer by username_2 on 2018-09-22. Score: 0

An interesting thought...

I guess that recoursive games, where a result is dependent on playing the same game, in a dynamic count of times, cannot be represented in a form or a matrix

A more common case is multiplayer simultaneous games, when has 2 player requires a 2d matrix, each new player will add a dimension to the matrix, more than 3 will not be able to have a graph representation, but only a database like schema

> **Comments:**
> **username_3**: Games with loops and recoursive games are not finite games. The because of the loops, the number of decisions points and hence the number of strategies are infinite.  
> **username_3**: Perhaps I misunderstand your last paragraph, but game trees can depict $n$-player games easily even if $n>3$. You just have to annotate the decision points.  
> **username_2**: @denesp regarding the last paragraph, simultaneous games are described with a 2d matrix where each dimension represents a player, so adding a 3rd play will be described as a cube, and with a game of 4, the forth cannot be displayed  
> **username_2**: @denesp why not? an finite yet unknown number of iterations, when each end of loop can lead to a different result, is a finite game with no ability to be modeled by a tree  
> **username_3**: This comes down to the basic issue of what is an infinite sit. If I can think of any number, I will think of a finite number, but the set of numbers I can think of is still infinite. You invite the same issue by introducing loops.  
> **username_2**: ok, I get your point... even if you may have a 1000 identical iterations, but it is still finite, then they can be displayed on a tree...  
> **username_2**: When I think about it, the only exception to that is recoursive games...  
> **username_3**: I would like to reiterate my second comment, which you seem to have glossed over. $n$-player games, even simoultaneous games can be easily depicted via tree graphs. [An example](https://plato.stanford.edu/entries/game-theory/figure13.jpg) (albeit for a non-simoultanous move game, but the logic is the same).  

---

