Cho and Kreps: "Signaling games and stable equilibria" (1987)

Because games often have several equilibria and no obvious way of choosing between them, it is always good sport to try to come up with some new, stronger refinement of the concept of the Nash equilibrium. This paper investigates a number of ways of doing so, mainly motivated by a single type of equilibrium that the authors find unintuitive.

The game that Cho and Kreps investigates is given by the following tree:

They motivate the game by the following annoyingly ridiculous story:

• A can have two types, "wimp" (with 10% probability) and "surly" (with 90%).
• A prefers quiche for breakfast when he's "wimp" and beer when he's "surly." He gets 1 point for having the breakfast he prefers, and 0 otherwise.
• In addition, A prefers not to duel B, and he gets 2 points for avoiding a duel.
• B prefers to duel A iff A is a "wimp" and not to duel him iff he is "surly." B gets 1 point for making the right decision and 0 otherwise.

Under these assumptions, the game has the following two equilibria:

1. A has beer for breakfast regardless of his type; B duels A iff he has quiche for breakfast.
2. A has quiche for breakfast regardless of his type; B duels A iff he has beer for breakfast.

So in the  first equilibrium, the game ends in one of the two lower branches of the subtrees on the left, with payoffs (2, 0) or (3, 1). In the other equilibrium, the game ends in one of the two lower branches of the subtrees on the right, with payoffs (3, 0) or (2, 1).

It is equilibrium no. 2 that Cho and Kreps find unintuitive and spend the most of the paper combatting. Their main focus in this effort is the notion of "stable equilibria" as defined by Elon Kohlberg and Jean-Francois Mertens in a 1986 paper—a concept that Cho and Kreps state that they have "mixed feelings" about (p. 181).

Johan van Benthem: "Games that make sense" (2008)

This is a chatty note on the various uses of game theory in semantics and pragmatics. It makes two points that I find worth mentioning.

First, van Benthem correctly points out that there are two different notions of "game" in play in semantics, and that these are sometimes confused. One is Hintikka-style verification games, and the other is Parikh-style signaling games. Although the verification games may in some sense be taken as idealized roadmap for a conversation, this fact is not completely obvious and cannot be taken for granted.

Second, he notes that signaling games have thrown a lot of the syntactic and semantic structure from logic overboard in its attempts to model the emergence of meaning. Since logic usually models hard, conventional facts about a language, this means that game-theoretic approaches to pragmatics have a hard time getting off the ground, because they take everything to be up to debate and revision in the online conversation situation. This is a false assumption in many cases.

Van Benthem writes:

Finally, from the viewpoint of natural language, we have not even reached the complete picture of what goes on in ordinary conversation. There may be games that fix meanings for lexical items and for truth or falsity of expressions whose meaning is understood. But having achieved all that, the ‘game of conversation’ only starts, since we must now convey information, try to persuade others, and generally, further our goals – and maybe a bit of the others’ as well. (p. 7)

He gives a tip of the hat to a number of people in dynamic epistemic logic and then continues:

But conversation and communication is also an arena where game theorists have entered independently, witness the earlier references in Van Rooij [42], and the recent signaling games for conversation proposed in Feinberg [22]. Again, there is an interface between logic and game theory to be developed here, and it has not happened yet. (p. 8)

But certainly a number of people are currently trying to smuggle more logical assumptions into the games, with various levels of success. 

Staudacher: Use Theories of Meaning (2010)

By and large, Marc Staudacher endorses the use of evolutionary perspectives on signaling game in his dissertation.

However, in section 7.2.3, he reiterates his concern about a fact that he observed on his blog two years ago: Although there are models of signaling games with infinitely many signals, no model plausibly explains how syntactically structured signals can be aligned with semantically compositional meanings.

"But it seems to be more of a technical problem that will eventually be solved," he adds (pp. 214-15). That seems to be a sound enough intuition. The semantics of a language with finitely many atoms and finitely many relations is learnable in finite time, even if the syntactic span of the language is infinite.

A temporal difference approach could for instance do the trick. Given a signal f(x,y) = b, where b is 0 or 1, an agent could record all of the sentences f(0,0) = b, f(0,1) = b, f(1,0) = b, and f(1,1) = b with fractional observation counts determined by the subjective probability of x = 0, x = 1, y = 0, and y = 1.