Lesson Time

This article is part of a series entitled Everyday Game Theory. See also:
1. The Escalator’s Dilemma; 2. Electoral College; 3. Passing Curiosity; 4. Lesson Time

This is (a slightly modified version of) a text message exchange which recently occurred between my violin teacher and me.

  1. Teacher: “Can we meet today instead of tomorrow?”
  2. Me: “That’d be great!”
  3. Teacher: “Cool, see you this afternoon.”
  4. Me: “Ok.”

It would not have been acceptable for me to fail to respond to my teacher’s message (1). If I didn’t respond, my teacher would have no way to know whether I ever received her message – and, hence, whether to come today or tomorrow.

Neither would it have been ok, for that matter, for my teacher to let the conversation end at message (2). Until I receive her confirmation (3), I can in no way be sure whether she has seen or acknowledged my message (2). In other words, with her message (3) unsaid, it could remain the case, for all I know, that my teacher, as yet unaware of my response (2), imagines me unaware of (1) and still intent to come tomorrow.

Even after I received my teacher’s message (3), though, it was important for me to send the further message (4). After all, until she receives my message (4), my teacher may well imagine me unaware of her message (3). In that situation — her thought process might go — I would, unaware of her confirmation (3), be liable to suspect her unaware of my response (2), and hence unsure of my receipt of (1), and so liable to come tomorrow.

Why doesn’t this continue?

  1. Teacher: “Great.”
  2. Me: “Yep.”
  3. Teacher. “Indeed.”

The situation is very complicated.

Significance in game theory

This sort of situation occurs, to begin with, in the presence of a coordination game where the cost of failure to coordinate is high. (Who wants to take the bus all the way to down to Peabody for nothing?) In this situation, though, the interesting behavior is rooted in communication. In a very subtle way, it is difficult for both parties to agree upon a change in strategy. Observe, for example, that this phenomenon is particularly pronounced whenever communication is unreliable, opaque, or intermittent. Indeed, the latency of communication is key.

Today Tomorrow
Today 10, 10 0, 0
Tomorrow 0, 0 8, 8

Before either of us — my teacher or I — might be willing to change times, this person must be sure that the other party intends to do the same. This first person’s confidence in the prospect that the other party will do so, however, depends in a crucial way on this player’s conviction that the other party believes that the first player will change. This imagined belief on the part of the other party, in turn, depends on the imagined presence of a further corresponding belief in the first player, and so on. Each level of confidence depends on the next. This continues infinitely.

Is this just idle speculation? Probably. On the other hand, if we set the stakes high enough, then this phenomenon, I contend, can become very real. Let’s imagine, indeed, that our coordination game imposes very high costs on acting alone. I don’t want to show up when my teacher is not there; suppose in fact that the shuttle to Peabody requires tickets, of which I have only one. I certainly don’t want my teacher to arrive without me; that would be rude, and makeup lessons aren’t available, as it turns out. Finally, suppose that my recital is this weekend.

Today Tomorrow
Today 10, 10 -1000, -1000
Tomorrow -1000, -1000 8, 8

To emphasize the role of communication, furthermore, let’s also assume that my violin teacher is often unable to check her texts, and that she, due to her musical obligations, frequently turns her phone on silent.

(None of this is true.) In this situation, we might imagine that the conversation initially described above could continue well past stage (4).

We’ll see that this phenomenon can be explicated in a quite transparent, formal way.

General analysis

We’ve seen that to act with confidence requires an infinite chain of affirmations on the part of the two players. This chain, however, can only ever be extended to finite length. The first absent element will create cause for uncertainty.

Take a sequence of messages (1), (2), …, (n), as above, consisting of a proposal for change followed by a series of affirmations. The inevitable result is that:

The recipient of (n) fears that the recipient of (n-1) fears that the recipient of (n-2) fears that… the recipient of (1) fears that the sender of (1) worries that (1) was never delivered.

Here is an outline of the inductive process that leads to the above belief.

  • To begin with, the recipient of (n) fears that the sender of (n) worries that (n) was never delivered.
  • In fact, suppose that the recipient of (n) fears that the recipient of (n-1) fears that… the recipient of (i) fears that the sender of (i) worries that (i) was never delivered.
  • Because message (i) serves to confirm the receipt of message (i-1), and because the recipient of (i) fears that the message’s sender doubts its successful delivery, the recipient of (i) begins, according to this nested chain of beliefs, to postulate an additional fear, whereby the sender of (i) — who, incidentally, received message (i-1) — fears that the sender of (i-1) in turn doubts message (i-1)’s successful delivery.
  • In other words, the recipient of (n) fears that the recipient of (n-1) fears that… the recipient of (i-1) fears that the sender of (i-1) worries that (i-1) was never delivered.
  • Eventually, we deduce from the initial hypothesis that, unfortunately, the recipient of (n) fears that the recipient of (n-1) fears that… the recipient of (1) fears that the sender of (1) worries that (1) was never delivered.

Hence the eventual transmission of message (n+1). The result of this transmission is, of course, that

The sender of (n) knows that the sender of (n-1) knows that… the sender of (1) knows that (1) was delivered.

Indeed, after message (n+1) is received,

  • The sender of (n) now knows that (n) was delivered.
  • In fact, suppose that the sender of (n) knows that the sender of (n-1) knows that… the sender of (i) knows that (i) was delivered.
  • Because message (i) serves to confirm the delivery of message (i-1), in this nested chain of beliefs, the sender of (i) now also knows that the sender of (i-1) knows that (i-1) was delivered.
  • In other words, the sender of (n) knows that the sender of (n-1) knows that … the sender of (i-1) knows that (i-1) was delivered.
  • By induction, we deduce that the sender of (n) knows that the sender of (n-1) knows that… the sender of (1) knows that (1) was delivered.

But the transmission of (n+1) just adds to this regression one further level of depth! Here’s the problem:

  • The recipient of (n+1) fears that the sender of (n+1) worries that (n+1) was never delivered.

Now the first induction begins again in the mind of the recipient of (n+1).

Practical factors in achieving certainty

How is certainty achieved? It’s not clear that it ever is – through text message, at least. Confidence does grow as the conversation lengthens, converging, in some sense, to surety. In practice, the two communicators will simply achieve a level of certainty sufficient for them to stop. (For us, this occurred at message (4).)

This convergence occurs for a number of reasons. Firstly, as the number of messages exchanged increases, the relevant fears become more intricate and consequently less plausible. Furthermore, an increase in conversation length – and more importantly, response speed – renders the fear of missed messages less compelling. If a number of messages are exchanged in short succession, each party may reasonably take the other to have his/her phone on hand, and the probability that the most recent message awaits unread becomes quite low.

Another solution – from outside, so to speak – is the read receipts featured in many more sophisticated messaging clients; these indicate to a message’s sender that the message has been read. The fact that a message has been read does not provide conclusive information about the reader’s response. In certain situations, though, it can provide crucial clues. In particular, if, in a conversation such as that described above – and, in particular, in one of its later stages – the recipient of message (n) understands its sender to have received a read receipt, then he/she may directly bypass the cycle of worry which lead to the transmission of message (n+1). (If a change of plans were afoot, for one, the recipient would have spoken up, and a read receipt in this special case can be understood as an acknowledgement.)

There’s one crucial flaw, though. The message’s recipient might worry that the message’s sender hasn’t actually seen the read receipt. This, in fact, is the same sort of worry which set off the above cascade to begin with. Read receipts offer no solution at all, and actually just recast the earlier problem in a different form. We would need receipts of the receipt of read receipts, and so on.

Even setting this aside (assuming, that is, that all receipts are seen), there are further difficulties. What if the read receipt were generated accidentally or incorrectly? This prospect would decrease the faith on the part of the message’s recipient that its sender, upon receiving the receipt, would cease to worry about the message’s successful delivery. What if one party took the other to be the sort of rude person who, despite an intent to change or cancel plans, might read a message and fail to respond to it? This prospect, the recipient might fear, could impair the disposition of the sender to accept the read receipt as a confirmation by situational inference alone. These uncertainties are of a different sort, though, and in any case read receipts could speed the process of convergence.

One final possibility is in-person communication. The process of eye contact shortens, in effect, the messages’ latency time to 0, and instantly creates an infinite chain of certainty.

Handshaking in computer science

In computer science, a client and a server seeking to open a channel for secure communication must undergo a process called handshaking. In the TCP (Transmission Control Protocol) three-way handshake, for example:

  • The client sends a synchronize message with a random number A.
  • The host sends back the synchronize-acknowledgement number, A+1, together with a second random number, B.
  • The client sends back the synchronization acknowledgment B+1, to which the host need not reply. [1] [2]

The numbers A and B, by analogy, might represent the two parties’ respective strategies in some sort of large coordination game. And yet if the proposed channel represented a change from a previous pair of numbers — or from no channel at all — we might ask why the problems discussed above wouldn’t continue to exist here.

The three-way handshake offers a subtle perspective on our problem. The computers declare in advance, as a matter of norm, to cut short the conversation after three steps. (Though the number three here is essentially arbitrary, it permits the communication of both parties’ parameters as well as the recognition on the part of each party that the other party received its parameter.) If things were to proceed as our earlier examples did, then the host might now begin to wonder whether the client is fretting about the successful delivery of his acknowledgement B+1 (and so on). With the handshake norm in place, though, the host need not entertain any such worry — the host understands that, by protocol, he is not expected to reply.

This might seem like an artificially imposed solution. The fact that the host is forbidden from responding does nothing, in the host’s mind, to allay his worries that the client, doubting the host’s successful receipt of the acknowledgement B+1 (and so on), fears the latter’s failure to consider the handshake complete. After all, in the client’s mind (the host imagines), the host’s failure to respond could be a result of protocol or of a failure to receive the message in the first place.

Here’s the thing. The host can instead open the connection immediately after receiving the client’s initial request A. Though the host, as we’ve already mentioned, might imagine, after receiving the final confirmation B+1, that the client wonders whether the confirmation was received, such wondering, if it existed, would be inconsequential on the part of the client, who now has the right to expect — by protocol — that the host has already opened the connection by the time the first confirmation A+1 arrives.

Now it might appear that we’ve just traded this problem for a simpler one. After all, to demand that the host open the connection immediately after receiving the message A is to ask that the host open this connection at a time when, for all the host knows, the client has yet to receive A+1 and B at all and might never receive them. In other words, we’re demanding that the host open the connection using A before being sure that the client will open the connection using B. This seems to violate the “coordination game” philosophy we’ve developed — this demand, according to the standard analysis, represents a significant risk for the host.

The solution might be a disappointing one. This really is not a coordination game. Indeed, we can safely suppose that the host, in offering a connection which might ultimately go unused, has little to lose. The crucial problem hasn’t gone anywhere! (It’s possible that I’m understanding the handshake incorrectly. It’s not clear to me whether the host actually initiates the connection after step 1 or step 3. In any case, each of these strategies has issues, as I describe above.)

This seems to be an unavoidable difficulty in the theory of coordination games.


  1. Wikipedia: Handshaking
  2. Wikipedia: Transmission Control Protocol

3 comments on “Lesson Time

  1. Ben says:

    A similar phenomenon occurs in the uncomfortable situation in which, well, two people who would prefer not to talk to each other pass each other. Imagine that two college acquaintances — who, let’s say, desire to bypass the campus norm whereby each encounter merits effusive conversation — see each other at a distance.

    I will describe a series of cases, each from the vantage point of a single, arbitrarily chosen party, whom I will fix once and for all. Of course, each of these cases could occur just as well for the other party, and, moreover, different cases might present themselves to each of the two parties. (The above two sentences are riddled with quantifications. I might soon write a blog post about the problems related to quantification in language.)

    The first case is that the first party believes that he passed unseen by the other party. In short: “He didn’t see me. Therefore we don’t know we avoided each other.”

    It could happen instead that this person believes that the other party saw him. This could be grounds for concern; on the other hand, the first party may still entertain the prospect that the other party believes our party did not see him. In short: “He saw me, but he doesn’t know that I saw him. For all he knows, I had no idea he was there. Therefore we don’t know we avoided each other.”

    Even if the first party believes that the other party believes that the first party witnessed the other’s glance, the first party may console himself with the prospect that the other party, despite his belief that his glance was seen, himself believes it possible that the first party believes that the latter party doesn’t know that the first party knows that the glance was seen. In that case, the first party deduces that the second party might reason that, for all the first party knows, the second party doesn’t know that he was seen, and thus doesn’t think he was being avoided. In short: “Sure, he saw me, and he thinks that I know that he saw me. But he doesn’t know that I suspect that he knows I saw him. For all he knows, I don’t realize that he knows that I know that he saw me, and thus I still entertain the possibility that he doesn’t know I know he saw me, and still believes possible he wasn’t being avoided. Therefore we don’t know we avoided each other.”

    In general:

    I suspect that he suspects that I suspect that he suspects that… I didn’t see his glance, and we didn’t avoid each other.

    Each of these can, again, occur for the other party, where the matter at hand there is whether the first party saw him.

    (Actually, we can be agnostic about who saw who — or replace the event with the generic “passed each other” altogether. What’s relevant is who knows what.)

    Each party can, in short, take solace in the fact that it’s not the case that each party knows that an avoidance occurred, and they’re mutually aware of this knowledge, and they’re aware of the awareness, etc., ad infinitum. This is what it would take for complete awkwardness to occur. In fact, this situation has in common with the situation discussed in the blog post precisely that the occurrence of some phenomenon depends on an infinite reciprocal chain of awarenesses on the part of the two parties. In this case, the inability to achieve complete reciprocal awareness is grounds for celebration, not concern.

    One other fact mirrors the situation discussed above. If they make eye contact? Then they’re both hosed.

  2. Ben says:

    Here’s another hilarious complication. What if there’s a chain of people?

    Sure, I’m able to meet today instead of tomorrow. Before I agree, though, I have to contact the accompanist who had agreed to play with us. We could even imagine that before he can agree to the new time, he has to contact his page-turner… And so on.

    One simple way this could go is the following. When my teacher contacts me, I simply wait to reply until the message makes its way to the end of the line and then back. In other words, I don’t respond right away and instead immediately contact the accompanist with the same message. “Could you do today instead of tomorrow?” He immediately contacts the page-turner with the same message, waiting to respond to me. At the end of the chain, the affirmative response “That’d be great!” makes its way back up. “Cool, see you then” then makes its way back down the chain. And so on. This situation differs from the above in that for any given party and at any given time, the content of that party’s uncertainty concerns not just the single counter-party but in fact all of those parties beyond our given party in the chain. (Think of, on a finite totally ordered set, the relations < and > — depending on which way the message is traveling, or what is the same, whether the message number is even or odd.) The structural characteristics of the uncertainty between any given pair of (not-necessarily-adjacent!) parties is, on the other hand, very much the same.

    Things get more complicated if we permit players to message each other right away before waiting. For example, I might wish to respond immediately to my teacher’s email, with “I’m fine with it, but I have to contact the accompanist first.” Then she could respond “Sure, let’s plan for it contingent on the accompanist.” The structure of the uncertainty is too complicated for me to bother with here.

    Another point: our coordination game now, instead of a square, is a “cube” with as many dimensions as we have players.

  3. Richard says:

    Interesting. If you’re fascinated by the issues of coordination problems in communication, you should consider looking at David Lewis’s PhD thesis, published as the book Convention. It’s pretty famous nowadays in phil. of language.

    It’s interesting to consider these knowledge problems and how they relate to the underlying assumptions about the elementary nature of communication, i.e. that it involves some discrete, precise chunk of information passed from sender to receiver via a channel. Then, when we eventually question the functionality/reliability of the sender/receiver/channel, the issues of confirmation and success come up.

    But I think the problem runs deeper than you explicitly mention. In fact, if one is going to be open to these problems of certainty at all, then issues are much more serious, for some pretty deep reasons.

    For example, when discussing receipts, you note: “There’s one crucial flaw, though. The message’s recipient might worry that the message’s sender hasn’t actually seen the read receipt. This, in fact, is the same sort of worry which set off the above cascade to begin with. Read receipts offer no solution at all, and actually just recast the earlier problem in a different form. We would need receipts of the receipt of read receipts, and so on.”

    This led me to ask: How, at all, is a receipt any different from a response message? There are lots of ways. But one might think that it’s excusable to follow up a receipt with “did you get my message?”, if no response is forthcoming. But one presumably can’t do this with a manual response. If one is going to be skeptical about whether one’s interlocutor has received the message generated by a receipt, however, then one should be skeptical about whether one’s interlocutor has received the message generated by a manually produced text. So a new dimension of uncertainty: how long does one wait before one can follow up with: “did you get my message?”. Can one do it immediately? Should that lead to an indefinitely extensible sequence of

    (n) Did you get message n-1?

    until a confirmation is eventually given?

    Also, why does eye contact establish anything special? It sounds romantic to say so, and maybe you were joking, but people’s eyes can meet without both being aware that it is happening, and aware that the other is aware that it’s happening, and aware that the other is aware that the other is aware … etc etc. Daydreaming permits this, at the very least.

    As far as I can see, there are some issues here which make the underlying model of communication ripe for some of the criticisms in Wittgenstein’s later work, though I’m not sure I buy all of what’s attributed to Wittgenstein in this regard. Basically, the complaint might be: if, in order to successfully communicate we must, in general, not be in a state of doubt about having successfully communicated, then these coordination regresses indicate that we never successfully communicate. The later Wittgenstein would probably say: but we do communicate successfully – much of the time – so communication must not work in the way assumed by the simple model, i.e. the model of a discrete internally accessed chunk of information passed imperfectly from sender to receiver.

    For Wittgenstein, the point of attack would be the conception of communicated information here, namely, that it cannot be the kind of thing which requires an infinite regress of receipt confirmations. Instead, communicated meaning, and information generally, is something that is exhausted by whatever norms happen to prevail in our messy, imperfect mass of human behaviour. For him, it would be a mistake to be skeptical about whether one has successfully communicated after a few exchanges of confirmation. Instead, although the number of responses necessary to establish successful communication will be radically indeterminate outside of a context (and the context itself may not be specifiable in a precise way) communication gets done nonetheless. Given human limitations, communication happens precisely because it doesn’t involve anything as precise as what would need these perfectly complete coordination signals.

    Witt. then extends this view in some radical ways which have some interesting consequences for semantics, information theory, and logic/mathematics generally. But, as I say, I don’t know that I buy it all. For example, he has ‘arguments’ (gnomic remarks) which seem to lead from this view of communication (shared meanings) to a view about thought in general (private meanings). Long story short: he sort of thinks that similar skeptical coordination issues can arise between a message sender and herself (i.e. in thinking – where maybe this is conceived as an internal dialogue of sorts), and so if we are to think at all, then we must not think by means of privately possessed determinate meanings which are transparent to us in a way that they are not to others. Instead, our information must be (in principle) totally public: exhausted by the messy ways in which we actually happen to use symbols and signs in communicating, writing etc.

    Here’s another way of thinking about it. Suppose we think of all thoughts as the kinds of things that can themselves be thought about, so that if you think that P, then you can think that you think that P, and so on. Then, if we were tempted by the idea that if you think that P, then you must be able to know that you are thinking that P, we arrive at a similar problem. Wittgenstein thinks that on some prevailing assumptions about how thinking works (viz. that it involves determinate private mental representations that can embed recursively in certain ways) we should accept that if one thinks that P, one must not, in that same instant, be in any doubt that one is thinking that P. (So, for example, try thinking about an object near to you, and, as you think about it, see if you can also doubt whether you are actually thinking about it. Witt. says you can’t.)

    If we accept this point from Witt. then we must accept that if one thinks that P, then one must be able to be certain, upon reflection, that one is thinking that P. But, as you can see, this recurses to generate a sort of ‘omega-sequence thought’ of the form “I am certain that I am certain that I am certain that … I am certain that I am thinking that P”. But we cannot think this thought, can we? Certainly we cannot explicitly ascend through the infinite sequence seriatim and thus achieve certainty, for we’re finite creatures. Can we do it instantaneously, perhaps? If not, then the requirement of the capacity for certainty means that we’re never certain that we’re thinking any particular thought. It is crucial to this conclusion that ‘thought’ is here conceived in the private, determinate, representational, and recursive way that we’ve assumed here in the underlying model of communication. Indeed, Witt.’s conclusion is that we do not think in this way. Due to our limitations, none of our thinking can be of this private, representational variety where perfect certainty is required. Again, what it is to think a thought (to have a mind, to mean a meaning) is going to be much more indeterminate, and utterly suffused with all the blurred tones of human inadequacy.

    Of course, you may want to bite the bullet and conclude that we never actually think (or, mutatis mutandis, that we never actually communicate). Personally, I am more reluctant to accept the ‘We do not think’ conclusion. I am less reluctant to conclude the ‘we do not communicate’ conclusion. I am very reluctant to accept the total revisions Witt. has in mind for meaning and thought conceived in this private, deterministic way. But in order to resist his prompts, I am tempted to say that either I (we) have some unusual ability to achieve infinite results with finite capacities, or, instead, that the requirement that If I think (mean) that P then I can be certain that I think (mean) that P, somehow fails.

    Currently my money is on the latter, for reasons at least partly to do with so called “Anti-Luminosity Arguments”, first outlined by Tim Williamson in his /Knowledge and its Limits/ (O.U.P. 2000)

    Again, enjoyable post, Ben.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s