Preventing Collusion

Question

Over on Code Golf Stack Exchange, competitions are run where multiple programmers compete against one another. One particular class of challenges is "King of the Hill". Here is an example of a King of the Hill challenge. The unique aspect of King of the Hill is that the players must interact until a winner emerges. Most of the other competitions are non-interactive.

When interaction is introduced into a game, collusion become an issue. In real life, collusion is often not in the best interest of the players due to social consequences. However, on the Internet, the social factors play an almost nonexistent role. Anonymity allows multiple players to collude in private, or even allow a single person to manipulate multiple players.

I really have two questions, but they both address the same problem from different angles.

• How can collusion be discouraged or prevented in an online, multiplayer, interactive game?
• How can collusion be caught and punished in an online, multiplayer, interactive game?

Things to keep in mind:

• This is not a Kingmaking scenario. "Kingmaker" specifically describes a player who chooses to collude as a result of being doomed to lose.
• One player may unintentionally help another player while trying to win. This is not collusion.
• Simply prefacing every challenge with "No colluding allowed." will lead to an argument over what constitutes collusion. Can it be objectively defined, given the previous bullet point?
• In case anyone is unfamiliar with the culture differences between sites, Code Golf Stack Exchange does not subscribe to the "Question and Answers" format. The format is geared towards "Challenge and Solutions".

I found some information on collusion detection from online poker sites. They detect collusion by flagging accounts who always play at the same table, and either manually or automatically take action. This solution does not translate well to the Stack Exchange format, but it seems like a step in the right direction.

Answer 1

My first thought is that generally this is not an easy problem. It's like trying to put swear filters in a game because people will get around that $h1t so many ways. But it's an interesting problem so here's some musings on it that may or may not qualify as an answer.

So for players to collude, they must be able to...

1. Have contact with each other before the game to scheme about colluding.
2. Derive some benefit from collusion.
3. Be in the same game together.
4. Be able to recognize each other in the game so they can collude.

To each of these points...

Block contact

For starters, you can't prevent communications by the nature of ... nature.

Minimize collusion benefits

Minimizing benefits to collusion gets into the realm of game design, where perhaps there is some clever way to craft the game where collusion ultimately will lead to one of the participants losing, and the other benefiting - and no way for the winner to share the benefits. You don't collude because it's just not worth it.

Keep collusionists from being in the same game

Keeping collusionists apart you can kind of prevent by having a huge number of games, or some kind of match maker that automatically creates matches so that players can't predictably be in the same game. If you are only in the same game as your collusion partner a small percentage of games, the benefits of collusion will have to be very high to make it worth while.

Prevent collusionists from identifying each other

Last but not least is not letting players identify each other easily, which I think is where it starts to get interesting and closer to the technical realm. If two players do not know if they are in the same game, then they can't collude. And with that, here are some ideas and thoughts. They are in no way perfect, but they might give you some ideas...

• For starters, dynamically create IDs for players that change with every game. Then a player can't join as "Cheater 1" and tell their friend to just look for them by ID.

• Of course then a player could just say, "Hey I'm 969935993 this round", so don't tell a player their own ID. Do tell them the ID of the other players though. If you don't know your own ID, you can't share it with others. Your friend may be in the same game, but they have no way (via IDs) to say, "Hey it's me."

• Don't allow chat. Kind of allows players to identify each other. This might put a crimp in the game, but it helps.

• Assume players will come up with novel and alternate ways to make in-game signals to identify each other. E.g., "I just played a 10 - did you see anyone play a 10?" Yes, this will allow identification, however depending on the game's complexity, it may not be a given that players can absolutely identify each other in a single play. This initial uncertainty potentially puts the players at a disadvantage as they are not playing initially to win, but rather to identify each other. That puts them behind the other players, especially if it takes multiple rounds to identify each other. There's got to be a really big benefit to collusion for them to do this, and not be concentrating on the game's goals.

• Change their IDs every game, so each round they must go through the whole "Are you there? Is that you?" cycle.

This isn't all ideal really, and there are probably various holes in the approach. And if done wrong it probably could make for a crappy game experience. Keep in mind that "ID" is something you use to identify someone. It could be a number or a name. Or it could be a dynamically created avatar face that is distinctive from another player.

In the end it seems like making collusion nonproductive so players go, "Why bother it's not worth it" is in a way the best solution.