3
$\begingroup$

Is there a finite game that cannot be represented by an extensive form 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?

$\endgroup$
7
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Arthur Tarasov Sep 23 '18 at 12:04
  • 2
    $\begingroup$ The textbook by Osborne & Rubinstein should have enough to get you started. If you need more or something specific, let me know. $\endgroup$ – Michael Greinecker Sep 23 '18 at 20:12
0
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Giskard Sep 22 '18 at 10:54
  • $\begingroup$ 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. $\endgroup$ – Giskard Sep 22 '18 at 10:56
  • $\begingroup$ @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 $\endgroup$ – Guy Louzon Sep 22 '18 at 11:19
  • $\begingroup$ @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 $\endgroup$ – Guy Louzon Sep 22 '18 at 11:21
  • 2
    $\begingroup$ 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 (albeit for a non-simoultanous move game, but the logic is the same). $\endgroup$ – Giskard Sep 22 '18 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.