Message Integrity

I have a question which I will present using a hypothetical. It's about a popular game called Sport. A game of Sport is played by two players and is recorded by one recordkeeper.

Alice and Beth love Sport, and they will go to each others' houses to play. If they play at Alice's house, the recordkeeper is always Alice's brother, Alex. If they play at Beth's house, the recordkeeper is always Beth's brother, Bob.

Alice and Beth are both part of a Sport League consisting of  hundreds of people. Whenever Alice and Beth play, their game records have to be reported to the Leaguemaster. Whoever has the most wins at the end of the season is given a cash prize, so it is important that the Leaguemaster's records are accurate.

For any given game of Sport being reported, the Leaguemaster must know:

1. Who played the game
2. That the game was played by normal league rules
3. Statistics about the game; especially, the game's winner

The problem: since Bob and Beth are related, Bob can't be trusted to not falsify the game record in Beth's favor whenever he gets to be recordkeeper. The same goes for Alex, who might falsify in Alice's favor whenever he gets the chance. Alex and Bob have also been known to rig the game itself in order to give their respective sister the advantage.

The question: How can the Leaguemaster guarantee that he is given accurate records about any given game?

alice leaks poop

I don't think it's possible for the Leaguemaster to know that the game was played by normal league rules if Alex and Bob rig the game without Alice and Beth knowing.
The accuracy of the record could be preserved by having Alice and Beth check and sign it after a game.

>>1
How can the Leaguemaster guarantee that he is given accurate records about any given game?
He'll have to record the games himself.

The answer: Make them fight to the death. It should be quite trivial to check which one is alive and has won.

Have them contact one of the other members in the league referee games.

Install hidden cameras in their showers.

>>3
What if Alice and Beth disagree about the record? Say, Alice thinks Bob's record is false, but Beth thinks it's right? Or, both Bob and Beth were playing fair and square, but Alice claims it's wrong because she doesn't want to lose?

It may be possible to track the disagreements as a third measure of reputation (Games Won, Lost, Disputed By/Against). But that still doesn't solve the problem of tracking unfair wins/losses, unless there is a set of rules that disqualifies you after a certain set conditions involving disputes is set.

And you're right, yhis still doesn't solve the problem of an unfair win that Alice and Beth don't know about.

>>4

The Leaguemaster's resources are limited. There are a lot more players that want to play than there are Leaguemasters or referees.

>>6
So Alice and Beth play at a third unknown person's house, let's say Claire, to be recorded by Claire's brother Chris (while Claire's not around -- Claire could even be playing at Beth's house at this time)? Chris might still rig the match or falsify records, but the idea is that Chris doesn't have any incentive to do so, because he doesn't know who Beth or Alice are, correct?

V I P

Change the rules of the game so that the winner is known in advance.  This is pretty much the only way to go, since solutions based on observing `reality' can never be guaranteed to work.

You should be looking at a solution that involves seperating hyperplanes and check my dubs.

They should play Sport on a Diebold® Voting Machine — Guaranteed* Unhackable™!

^{* No refunds.}

>>8
The Leaguemaster's resources are limited. There are a lot more players that want to play than there are Leaguemasters or referees.
Then they'll have to start their own league, bunch of spoiled brats!

>>2
*squeeze*

Play Touhou instead of sports. Now everyone in the league is a loser. Problem solved.

Just in case you derps don't get it, this is an analogy for a video game played over P2P with a centralized matchmaking system, persistent player identities, and public ladder.

>>16
What is there to "get"?  You're analogy is completely pointless.

>>15
You mad a typo! You mean to say that everyone who plays Touhou is a winner, surely. Too bad we don't have an edit function for you to correct that mistake. You will just have to deal with the humiliation I'm afraid. Sorry.

just have each player sign his moves with a private key, i don't understand what the big deal is here.

>>19
you're not really allowed to make sense around here

The solution is obvious

Remove the monetary incentive and the people will start to cheat MUCH less frequently.

>>16
It's a stupid anal-ogy. Alex and Bob are completely superfluous (just like all men), and their functions can be performed by Alice and Beth, respectively. Which lets us remove the stupid houses as well.
Now we're left with two players and a she-said-she-said scenario.
If the state of the game is known to both players, say Sport is go or chess, each player can sign each move they make. The game could end when a player refuses to sign a move, and scores be awarded as-is. That could penalize long-term strategies though, since the other player could just quit at any time it was advantageous.
If the game must be played to completion, both players could announce their intent to play up front, and an unfinished game would penalize both players heavily, more than any lost game.
That assumes both players are playing for score, i.e. no griefers, etc.