I like the concept of the Paranoid Debating game, but would propose one modification. Rather than always having a player assigned to deceive, have one with 50% probability, but don't reveal to anyone (except the deceiver) whether there is a deceiver in the group. To implement this with a group of n players, first choose a spokesman and give him a spade, then deal each other player one card from a deck containing 2n-3 black cards and one red card.

As another possible variant, introduce a small (say, 1/52) chance that everyone except the spokesman is red, and everyone except the spokesman knows it. To implement this, first choose a spokesman at random, then choose a dealer from the remaining players. The dealer looks at one card at random. If it's the ace of diamonds, he prepares a deck containing only diamonds; otherwise, he prepares a deck containing 2n-3 black cards and one heart, shuffles it and then deals from it. Getting a diamond means that everyone else has a diamond; getting a heart means that everyone else has black cards.