Researchers at UCSB have recently found that cheater detection is an age-old cognitive system. Using a subject they call “R.M.” who has a cognitive disability to the part of his brain that decodes social and emotional signals, they found that this fellow performed much better in certain tests of honesty than others, showing that the subsystem that controls cheater detection is separate from other areas of cognitive faculty.
Cheater detection also appears to be an evolutionarily old system, which can be found in all social primates. My limited experience with my dog Montana shows that even domesticated pets are quite good at this sort of thing. After playing fetch with him for a few years, I started to play tricks (as all good dog owners do), pretending to throw a stick and then hiding it behind my back. After one or two tosses, his cheater detector became quite refined, and he subsequently refused to play fetch with me for months. And then he ran away. These events may or may not be connected.