“Asynchronous Revision Games with Deadline,” Y. Kamada & T. Sugaya (2011)

Sugaya and Kamada are both Japanese job market stars in theory this year – Sugaya infamously has a job market paper nearly 300 pages long. The present, much shorter paper strikes me as a particularly interesting contribution. Consider a game where we choose actions continuously but only the state of our action choices at time T matters for payoffs. At various time t before T – perhaps given by some Poisson process – we have an opportunity to switch our action choice. How will equilibria differ from the stage game with the same payoff matrix? Such games are called “revision games” and have previously been described in a paper by Kamada with a different coauthor. They actually have quite a few uses: I’ve changed a paper of mine in auction theory to fit the revision game framework, and you might also consider timing games where the timing is endogenous. For example, it may not be obvious ex-post who the Stackelberg leader in a duopoly game is. Or we might want to allow communication with limited commitment using a revision game, where the state before T is a reflection of which suppliers you’ve been in contact with, for example.

The problem, as I found out a few years ago trying to work out my auction, is that such games are very difficult to solve. Kamada and Sugaya consider the case where opportunities to revise strategies arrive for each player i according to a Poisson process with parameter L(i), and let T be arbitrarily large so that each player has arbitrarily many opportunities to revise. They prove that if the game has a unique, strictly Pareto dominant action profile, and payoffs across players are “almost” the same, then the Pareto dominant NE is the unique equilibrium. Further, in 2-player 2×2 games with 2 unique Nash equilibria (say, Battle of the Sexes), a tiny bit of asymmetry in player payoffs can lead to a unique equilibrium favoring the strongest player. Both of these results may be counterintuitive. The first may be counterintuitive because many refinements of coordination games select the risk-dominant, not the Pareto dominant, equilibrium. Kamada and Sugaya’s model get around this result because the “preparation” before time T means the only risk of miscoordination is when the other player doesn’t get a change to revise before T, which happens with probability zero as T goes to infinity. The second result is surprising simply because tiny changes in payoffs radically change the equilibrium set. Let’s look at this result further.

Consider a battle of the sexes game, with payoffs (L,l)=(2+e,1), (R,r)=(1,2) and otherwise (0,0). In the usual parlance, the husband and wife want to meet somewhere and get no utility if they are apart, but given that they are together, the husband prefers the ballgame and the wife the opera. Note that the husband gets epsilon more utility from baseball than the wife from Puccini. At time 0, both players choose an action. Let both get a chance to revise their action over time according to Poisson processes with identical parameters, and let T be arbitrarily large. We will show that if e>0, the unique subgame perfect equilibrium is (L,l). I do not prove this here, but if e=0, both (L,l) and (R,r), as well as many mixtures, are equilibria.

The intuition, perhaps, is that the husband has slightly more incentive to wait for the wife to yield and see the ballgame than the wife does for husband to yield and go to the opera. Note that as we get close to T, both husband and wife will revise to match the other if they have not done so yet; this is simply because the probability that no one gets to revise again is converging to 1, and with no revision, both get payoff 0, whereas by yielding and matching your partner’s preparation, the minimum payoff is 1. Let’s work backward in time, assuming that both players yield to their spouse’s current state if they get a chance to revise after the current time, and find the cutoffs representing the earliest either spouse will yield to the other given an opportunity to revise. The payoff from yielding is 1, which must be equal at the right cutoff to the payoff from not yielding, conditional on both players yielding any time they get a chance in the future, is equal to

Pr(Revise before T given current time)*2+1/2

for the wife. The probability is just the chance that anyone will get to revise again, and the right side means the wife gets 2 half the time (the husband gets the first future chance to yield) and gets 1 half the time (she yields first in the future). Note that the same equality has the 2 replaced by 2+e for the husband. Plugging in Poisson rates for the probability in the equation above and solving gives you that the wife has an earlier cutoff to begin yielding that the husband.

But what should the wife’s cutoff t* be? Assume we are at some time t<t*. At t*, the continuation payoff is 1, and we have already shown that the husband will not revise, meaning switch from holding out for baseball to yielding to his wife’s preference for opera, before t*. After t*, the wife's continuation value is strictly less than one since the probability that time runs out before either of us get to revise again is increasing. The wife, at any time she is able to revise, can lock in a payoff of 1 by yielding. If she does not yield, her continuation value is strictly less than one, since at any chance to revise, she never can lock in more than one, and there is a positive probability neither player will get a chance to revise before T, giving payoff zero. Therefore, the wife will yield at the start of the game. Another way to see this is to note that the continuation value of the game conditional on not yielding is decreasing over time.

The full proof is a bit trickier since we also have to show that given the current states are (L,l) or (R,r), neither player will want to revise again. This is technically difficult to prove, but involves nothing more complicated that pages of algebra. For the theory geeks out there, proving similar results with continuous action spaces is considerably more difficult, because of the need to get around using tiny changes in strategy as a “counter” for non-Markov punishment. What I do in my work here is to restrict attention to equilibria of the game in constant strategies, meaning that on the equilibrium path, no one ever revises their strategy. There are a few reasons why this helps that I’ll get to when I write up the auctions result.

http://www.princeton.edu/~tsugaya/selection_revision_game (July 2010 working paper – currently under revision at TE. A very much related paper by Calcagno and Lovo deals with the same issue of preopening revision of strategies.)

Advertisements
%d bloggers like this: