17
$\begingroup$

There seems to be a huge discrepancy in what people refer to when they speak of "game theory". I tend to think of it as including, among other things:

  • Combinatorial game theory dealing with certain games of perfect information, i.e., things like the Sprague-Grundy theory of (terminating, perfect information) impartial games, but also partizan games à la Berlekamp, Conway and Guy, and more (e.g., not necessarily terminating games where non-termination is counted as a draw).

  • Questions of determinacy: Martin's proof of Borel determinacy, for instance, is probably more commonly classified as being part of set theory, but it seems odd to me not to (also) consider it part of game theory.

  • Games with application to model theory, like semantic games, Ehrenfeucht-Fraïssé games, etc.

  • Differential game theory.

  • Various questions of algorithmic computability or complexity linked to some of the above.

  • ...and probably much more that I've never even heard about (quantum game theory?).

On the other hand, if we look at this online course (by Jackson, Leyton-Brown and Shoham) that is simply called "game theory", it is obvious from the syllabus that their focus is much narrower:

  • Week 1. Introduction: Introduction, overview, uses of game theory, some applications and examples, and formal definitions of: the normal form, payoffs, strategies, pure strategy Nash equilibrium, dominated strategies.

  • Week 2. Mixed-strategy Nash equilibria: Definitions, examples, real-world evidence.

  • Week 3. Alternate solution concepts: iterative removal of strictly dominated strategies, minimax strategies and the minimax theorem for zero-sum game, correlated equilibria.

  • Week 4. Extensive-form games: Perfect information games: trees, players assigned to nodes, payoffs, backward Induction, subgame perfect equilibrium, introduction to imperfect-information games, mixed versus behavioral strategies.

  • Week 5. Repeated games: Repeated prisoners dilemma, finite and infinite repeated games, limited-average versus future-discounted reward, folk theorems, stochastic games and learning.

  • Week 6. Coalitional games: Transferable utility cooperative games, Shapley value, Core, applications.

  • Week 7. Bayesian games: General definitions, ex ante/interim Bayesian Nash equilibrium.

Evidently they don't intend to teach about the various things I mentioned above.

Now this presents the unfortunate problem that I don't know how to refer to this particular sub-branch of game-theory-in-the-wide-sense, or, alternatively, if we reserve the term "game theory" to this game-theory-in-the-narrow-sense, how to rename game-theory-in-the-wide-sense. I've thought of calling it "Nashian game theory", but I don't want to be caught making up names for branches of mathematics that I'm in no way a specialist of, at least not without some kind of asking about.

Sadly, neither the Wikipedia article (which sort-of favors using "game theory" in the wide sense) nor the AMS classification (which is really unclear as to what goes into 91Axx — do we seriously think that "Games involving topology or set theory" should be part of "Game theory, economics, social and behavioral sciences"?) seem to have an idea as to what game-theory-in-the-narrow-sense might be called.

So, can someone suggest less ambiguous terminology, and possibly a map of the layout of game theory (how the different sub-domains stand in relation to each other)? I'm also curious to know how wide the intersections are (some descriptions seem to suggest that combinatorial game theory and Nashian(?) game theory are almost a partition, but the picture is probably much more complex).

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Just to make the task harder, you might include Schmidt games in your list, a very interesting class of measure/metric games ams.org/journals/tran/1966-123-01/S0002-9947-1966-0195595-4/…. $\endgroup$
    – Lee Mosher
    Commented Mar 9, 2016 at 17:27
  • 2
    $\begingroup$ You might organize it by founder/proponent or by era. I would call the work of Morgenstern-Von Neumann either "Classical Game Theory" or some variation of "MV Game Theory". Similarly, for combinatorial game theory I might use " modern " or "BCG" as a modifier. For the games in logic I would use terms like "descriptive set theory" instead. Gerhard "Would Not Use 'Drew Carey'" Paseman, 2016.03.09. $\endgroup$
    – Gerhard Paseman
    Commented Mar 9, 2016 at 19:25
  • 4
    $\begingroup$ Historically, game theory has its roots in economics, and that's the area you call "narrow" for some reason. en.wikipedia.org/wiki/Theory_of_Games_and_Economic_Behavior was published in 1944, and most of the topics you mention in the beginning of your question have little to do with this area, it's simply something quite different. $\endgroup$
    – Dima Pasechnik
    Commented Mar 9, 2016 at 20:57
  • 4
    $\begingroup$ @DimaPasechnik: I call it "narrow" for lack of a better name—since a better name is precisely what I am asking for! Also, tracing the historical roots of the subject is delicate as long as the subject itself isn't clearly defined: one could argue that the root of game theory is Zermelo's 1913 paper Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels (where he proves that chess is determined), so that would make combinatorial game theory older than the von Neumann–Morgenstern book. (contd.) $\endgroup$
    – Gro-Tsen
    Commented Mar 9, 2016 at 21:15
  • 1
    $\begingroup$ (contd.) Also, Édouard Lucas's Récréations mathématiques (circa 1891) has a lot about games including some results which one could call precursors to game theory. But I don't want to get drawn into a historical debate: what matters to me is how I can clearly and unambiguously refer to the part of game theory that has its root in economics, and/or, conversely, how I can unambiguously refer to the larger domain which also comprises combinatorial game theory, differential games and everything else. $\endgroup$
    – Gro-Tsen
    Commented Mar 9, 2016 at 21:20

1 Answer 1

Reset to default
12
$\begingroup$

If we include the larger research community -- economics, computer science, social sciences, business schools, operations research, etc -- I think there really is a partition between combinatorial game theory and what I would propose to call "equilibrium" game theory. Most in econ and related fields who study/use game theory extensively have probably never even heard of the combinatorial kind! And even those who have usually don't encounter it in their research. (For instance the course you link is by two computer scientists and an economist.)

And I think this divide illustrates the nature of the partition, namely, "equilibrium" game theory is at home in microeconomics: Its purpose is understanding the behavior of groups of strategic / self-interested agents. I think the following motivation helps illustrate. A choice facing a single agent is simply an optimization problem about maximizing utility and hence, once written down, has a well-defined solution. With multiple agents making decisions, however, one needs to propose a "solution concept" describing or predicting how groups of agents might behave. There is no necessarily right or best answer. The insight developed by von Neumann, Nash, etc was to propose as solution concepts equilibria, where the key point of equilibrium is that all agents are simultaneously optimizing. Essentially all game theory of the second kind, in my experience, follows this motivation and solution approach, hence my proposal for "equilibrium" as the descriptive term.

(By the way, for this reason I would argue that "cooperative game theory" is a misnomer. Although it is also taught in the same economics classes, it has little to do with "game theory proper". It fits better within social choice.)

On the other hand, while I have almost no experience with combinatorial GT and probably shouldn't risk putting my foot in my mouth, my impression is that it is not generally motivated by modeling strategic agents. Instead, it tends to use a "game" as an analogy or mental picture for describing a well-defined mathematical problem in which issues surrounding strategic behavior, and especially the problem of solution concepts, do not tend to play a role. The question, although described as involving multiple agents, is more about understanding the (well-defined and uncontroversial) optimization problem.

To highlight this, in my (limited) experience, even in artificial intelligence where problems related to combinatorial game theory come up (planning, alpha-beta pruning, solving perfect-info zero-sum games like checkers/chess/go), the problem is not really described as falling under game theory (which to that crowd tends to mean equilibrium game theory) but rather simply algorithm design or optimization.

So in summary, I'm hoping to put forward two points. The first is that "equilibrium game theory" may be a good disambiguation name for the second kind of game theory you mention. I think the notion of equilibrium actually quite closely capture both necessity and sufficiency for falling into that category. The second point is that, if you look at the broader research community than in mathematics (not to mention popular culture), a large majority equate "game theory" exclusively to equilibrium game theory (and generally out of ignorance rather than conscious choice). I'm not sure what the point of that point is, but maybe it's useful.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Combinatorial game theory can also be summarized as an extension of the Sprague-Grundy theory en.wikipedia.org/wiki/Sprague-Grundy_theorem of impartial games ( = generalized Nim ) to games that may be "partial" in the sense that the two opponents needn't always have the same move sets. $\endgroup$
    – Noam D. Elkies
    Commented Apr 18, 2016 at 4:07
  • $\begingroup$ I think "non-cooperative game theory" is more usualand fits better than "equilibrium game theory". Rationalizability is not an equilibrium notion butclearly falls within the area. $\endgroup$
    – Michael Greinecker
    Commented Apr 26, 2016 at 21:22
  • 1
    $\begingroup$ I was lucky to have a correspondence with with Aviezri Fraenkel for a few months and he was gracious in explaining the scope of the field of CGT (ever expanding as the tools for mathematical analysis expand.) My sense of CGT is that it is concerned with solving, or proving the unsolvability, of games that have a combinatorial nature. Initially this was restricted to sequential 2 player, non-chance, perfect information games, but Fraenkel made a point of TS Ferguson's work in poker to as a demonstration of the expansion in scope. $\endgroup$
    – DukeZhou
    Commented May 18, 2018 at 17:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .