# Does game-theoretical fairness work in when the goal of one party is randomness

When we take the coin flip in Blum's algorithm in "Coin flipping by telephone a protocol for solving impossible problems", where Alice and Bob both want ownership over the same car, then one party (the adversary / Alice) can abort the protocol. Provided there does exist a powerful third party (e.g. the law), the protocol can be extended, to give the car to Bob in case Alice aborts. This makes the algorithm game-theoretical fair, because Alice no longer has any desire to abort.

But let's say we–the general public–and Bob do not desire a specific outcome, but a random outcome, yet Alice still desires the car. The set of desired results is thus not longer disjunct. Now Alice can can calculate the result and if she decides it is not in her favor, she can abort. Bob will have to flip the coin again, providing Alice a second chance for her desired outcome. Bob could also use the first flip, but this would still give Alice two options to chose from. Since Alice can chose from two random numbers, it's not longer true random to Bob. Yet we can't punish Alice by giving the car to Bob, because the result would not be true random either.

If we instead take the Commit-Reveal scheme, the party acting last would also get the choice. My question is thus, does there exist a protocol which can guarantee a random selection if Bob has honest intentions and Alice may wants to abort?

To me, the issue of game-theoretical fairness lies in the punishment being contained in the coin flip itself. In a real-world we would probably resort to independent measures like fines or prison sentences, but it's hard to prove their impact on game-theoretical fairness, so it would be much better to have a formal protocol which can guarantee a random number while punishing Alice.

Edit 1: I already see there are some issues with my approach. Even if we maintain the rule to give the car to Bob in case Alice aborts, Alice would always take the random choice to maximize profit and never aborts, so we never end up with the non-random scenario of giving the car to Bob. I need to extend the problem a bit further to get to the core issue i originally wanted to discuss: Alice does not want the car for herself, but she has a hidden preference for either Alice or Bob which we don't know. But we and Bob want a random selection So we can't punish her by giving the car to Bob, because this could have been her intention and she would abort the protocol, resulting in the aforementioned issue of giving her an advantage.

• If I understand correctly, why not set the rule to be that Bob independently flips a coin if Alice aborts? That satisfies Bob's preference and is the best Alice can hope for with the honest protocol. You'd need to show that Alice cannot abort after learning the outcome of the honest protocol, I suppose (e.g., if she aborts after that point, the outcome is already decided for Bob and third parties). Commented May 8, 2023 at 12:27
• @SamJaques If Bob flips a random coin after Alice aborts, Alice has a chance larger than 50% to achieve her preference. She can either stay with the protocol if she knows her desired outcome will become true after revealing her secret, or if the outcome will be bad, she can abort and force Bob to flip again increasing her overall chances to 75%. Thus it's no longer true random. Commented May 8, 2023 at 13:14

If the goal is to design a 2-party protocol such that outputs a fair coin even when one party could leave early, then that is impossible due to Cleve 1986, STOC. Roughly, the paper says that for any protocol of $$R$$ rounds, a malicious party that may abort early can deviate the outcome of the coin by $$\Omega(1/R)$$. This impossibility holds no matter what cryptographic assumption is used in the protocol. Recent results strengthened the bounds on the deviation.