Yes. In the original setting of FF the tournament setup enforces that everyone’s true source code is common knowledge. Most likely the problem is hard to solve without at least a little common knowledge.
Hmm, I’m not seeing what common knowledge has to do with it. Instead, what seems necessary is that the source code proving process must be consensual rather than unilateral. (The former has to exist, and the latter cannot, in order for FF to work.)
A model for a unilateral proof process would be a trustworthy device that accepts a string from the prover and then sends that string along with the message “1” to the receiver if the string is the prover’s source code, and “0″ otherwise.
A model for a consensual proof process would be a trustworthy device that accepts from the prover and verifier each a string, and sends a message “1” to both parties if the two strings are identical and represent the prover’s source code, and “0″ otherwise.
In your second case one party can still cheat by being out of town when the “1” message arrives. It seems to me that the whole endeavor hinges on the success of the exchange being common knowledge.
In your second case one party can still cheat by being out of town when the “1” message arrives.
I’m not getting you. Can you elaborate on which party can cheat, and how. And by “second case” do you mean the “unilateral” one or the “consensual” one?
For a rigorous demonstration, imagine this: while preparing to play the Freaky Fairness game, I managed to install a subtle bug into the tournament code that will slightly and randomly distort all source code inputs passed to my algorithm. Then I submit some nice regular quining-cooperative program. In the actual game your program will assume I will cooperate, while mine will see you as a defector and play to win. When the game gives players an incentive to misunderstand, even a slight violation of “you know that I know that you know...” can wreak havoc, hence my emphasis on common knowledge.
In the actual game your program will assume I will cooperate, while mine will see you as a defector and play to win.
I see what you’re saying now, but this seems easy to prevent. Since you have changed your source code to FF, and I know you have, I can simply ask you whether you believe I am a defector, and treat you as a defector if you say “yes”. I know your source code so I know you can’t lie (specify Freaky Fairness to include this honesty). Doesn’t that solve the problem?
ETA: There is still a chance of accidental miscommunication, but you no longer have an incentive to deliberately cheat.
In this solution you have an incentive to similarly be outa town when I say “no”. Think through it recursively. Related topics: two generals problem, two-phase commit.
Ok, let’s say that two FFs can establish a cryptographically secure channel. The two players can each choose to block the channel at any time, but it can’t read, inject, delete, or change the order of messages. Is that sufficient to make it arbitrarily unlikely for any player to put the FFs into a state where FF1 will treat FF2 as a cooperator, but FF2 will treat FF1 as a defector? I think the answer is yes, using the following protocol:
FF1 will start by sending a 1 or 0 (chosen randomly) to FF2. After that, each FF will send a 1 or 0 after it receives a 1 or 0 from the other, keeping the number of 1s sent no more than the number of 1s received plus one. If an FF receives N 1s before a time limit is reached, it will threat the other as a cooperator, otherwise as a defector. Now in order to cheat, a player would have to guess when to block the channel, and the probability of guessing the right time goes to 0 as N goes to infinity.
This is not necessarily the most efficient protocol, but it may be good enough as a proof of concept. On the other hand, the “merger by secure joint construction” approach seems to have the advantage of not having to deal with this problem. Or is there an analogous one that I’m not seeing?
Hmm, I’m not seeing what common knowledge has to do with it. Instead, what seems necessary is that the source code proving process must be consensual rather than unilateral. (The former has to exist, and the latter cannot, in order for FF to work.)
A model for a unilateral proof process would be a trustworthy device that accepts a string from the prover and then sends that string along with the message “1” to the receiver if the string is the prover’s source code, and “0″ otherwise.
A model for a consensual proof process would be a trustworthy device that accepts from the prover and verifier each a string, and sends a message “1” to both parties if the two strings are identical and represent the prover’s source code, and “0″ otherwise.
In your second case one party can still cheat by being out of town when the “1” message arrives. It seems to me that the whole endeavor hinges on the success of the exchange being common knowledge.
I’m not getting you. Can you elaborate on which party can cheat, and how. And by “second case” do you mean the “unilateral” one or the “consensual” one?
The “consensual” one.
For a rigorous demonstration, imagine this: while preparing to play the Freaky Fairness game, I managed to install a subtle bug into the tournament code that will slightly and randomly distort all source code inputs passed to my algorithm. Then I submit some nice regular quining-cooperative program. In the actual game your program will assume I will cooperate, while mine will see you as a defector and play to win. When the game gives players an incentive to misunderstand, even a slight violation of “you know that I know that you know...” can wreak havoc, hence my emphasis on common knowledge.
I see what you’re saying now, but this seems easy to prevent. Since you have changed your source code to FF, and I know you have, I can simply ask you whether you believe I am a defector, and treat you as a defector if you say “yes”. I know your source code so I know you can’t lie (specify Freaky Fairness to include this honesty). Doesn’t that solve the problem?
ETA: There is still a chance of accidental miscommunication, but you no longer have an incentive to deliberately cheat.
In this solution you have an incentive to similarly be outa town when I say “no”. Think through it recursively. Related topics: two generals problem, two-phase commit.
Ok, let’s say that two FFs can establish a cryptographically secure channel. The two players can each choose to block the channel at any time, but it can’t read, inject, delete, or change the order of messages. Is that sufficient to make it arbitrarily unlikely for any player to put the FFs into a state where FF1 will treat FF2 as a cooperator, but FF2 will treat FF1 as a defector? I think the answer is yes, using the following protocol:
FF1 will start by sending a 1 or 0 (chosen randomly) to FF2. After that, each FF will send a 1 or 0 after it receives a 1 or 0 from the other, keeping the number of 1s sent no more than the number of 1s received plus one. If an FF receives N 1s before a time limit is reached, it will threat the other as a cooperator, otherwise as a defector. Now in order to cheat, a player would have to guess when to block the channel, and the probability of guessing the right time goes to 0 as N goes to infinity.
This is not necessarily the most efficient protocol, but it may be good enough as a proof of concept. On the other hand, the “merger by secure joint construction” approach seems to have the advantage of not having to deal with this problem. Or is there an analogous one that I’m not seeing?