N players are playing a perfect information game (the kind of game where everyone knows moves of everyone) by making moves by turn (
... till the game will finish). Game has specific rules for every player (if a player makes a move against the rules - he loses automatically) and can finish only if one of the players win. I am trying to figure out whether it is possible to implement a secure game without having a reliable arbiter (who can be trusted). By secure I mean that none of players would be able to cheat and be unnoticed.
Here are some of my thoughts about it:
If none of the players cheat, than nothing should be done: players just make move and in the end the winner is announced. But if players can cheat, each next player can verify that the previous player has not cheated (it is perfect information and the rules are known) and if previous player cheated - he will lose right after this. If players can start to cooperate with each other (player 1 cheated and player 2 decided to cooperate) every player can verify all previous moves and players who cheated or cooperated will lose.
But here is a problem. Nothing prevents a next player to tell that previous player cheated even if he is not. Of course next players can check for this, but if only 2 player are in the game it will not work.
On the other hand it is possible to have a trusted arbiter who verifies every move. Player 1 makes a move - gives it to arbiter. It verifies it and transmits it to other players. And so on.
So is there a way to make a secure game without the arbiter?
- if this sounds too abstract, think about this as a chess game. 2 players, perfect information, rules are rules of chess how to move, players can cheat by making illegal move
- I am not really sure that this is a correct place. I hesitated between mathematics, security and cryptography. If I am wrong, please move it to another place.