In social settings, people often reason about unobservable mental content of other people, such as their beliefs, goals, or intentions. This ability helps them to understand and predict the behavior of others. People can even take this ability further, and use higher-order theory of mind to reason about the way others use theory of mind, for example in 'Alice believes that Bob does not know about the surprise'. However, empirical evidence suggests that people do not spontaneously use higher-order theory of mind in strategic games. In this paper, we let participants negotiate with computational theory of mind agents in the setting of Colored Trails. We find that even though participants are unaware of the level of sophistication of their trading partner, within a few rounds of play, participants’ offers are more indicative of second-order theory of mind reasoning when their trading partner was using second-order theory of mind as well.