it's my favorite fictional portrayal of recursive mutual modeling.

The one I always think of is Poe's "The Purloined Letter":

But he perpetually errs by being too deep or too shallow, for the matter in hand; and many a schoolboy is a better reasoner than he. I knew one about eight years of age, whose success at guessing in the game of 'even and odd' attracted universal admiration. This game is simple, and is played with marbles. One player holds in his hand a number of these toys, and demands of another whether that number is even or odd. If the guess is right, the guesser wins one; if wrong, he loses one. The boy to whom I allude won all the marbles of the school. Of course he had some principle of guessing; and this lay in mere observation and admeasurement of the astuteness of his opponents. For example, an arrant simpleton is his opponent, and, holding up his closed hand, asks, 'are they even or odd?' Our schoolboy replies, 'odd,' and loses; but upon the second trial he wins, for he then says to himself, the simpleton had them even upon the first trial, and his amount of cunning is just sufficient to make him have them odd upon the second; I will therefore guess odd'; --he guesses odd, and wins. Now, with a simpleton a degree above the first, he would have reasoned thus: 'This fellow finds that in the first instance I guessed odd, and, in the second, he will propose to himself upon the first impulse, a simple variation from even to odd, as did the first simpleton; but then a second thought will suggest that this is too simple a variation, and finally he will decide upon putting it even as before. I will therefore guess even' guesses even, and wins. Now this mode of reasoning in the schoolboy, whom his fellows termed "lucky," --what, in its last analysis, is it?"

"It is merely," I said, "an identification of the reasoner's intellect with that of his opponent."

I wonder if there is an older appearance of this trope or if this is the Ur Example? (*checks TvTropes). The only older one listed is from the Romance of the Three Kingdoms, so Poe's might be the Ur Example in Western culture.

Here it is -- the classic "battle of wits" scene from The Princess Bride. (This clip cuts off before the explanation of the trick used by the victor.)