collusion: game theoretical solution without smart contract - golemfactory/golem-rd GitHub Wiki
This is an idea of a solution for the Collusion problem.
This table describes three possible modes of collusion between two providers that are computing the same subtask. Honest - no collusion. Trade - one sells other hash of the result or the result itself. Junk - both decide to generate identical junk. When both providers are getting paid junk generation is the best strategy. When only one of providers is being paid, providers have reasons to stop trusting each other. This approach ignores the existence of smart contracts on Ethereum!
| honest | trade | junk | |
|---|---|---|---|
| 2c 2u 2 | 1c 3u 1d 2 | 0c 2u 2 | both are getting paid |
| 2c 2u 1h | 1c 1rc 2u 1h ** | 0c 2u 1h *** | one is getting paid |
Legend:
- 1c - one computational cost
- 1rc - one computational cost by requestor
- 1u - one upload cost
- 1d - one download cost
- 1 - one reward
- 1h - one reward for honest node
- ** - one computes and tells the other wrong result; subtask is being recomputed by requestor; cunning provider gets paid
- *** - can we make those two distrust each other? Details are below.
| P1 coop's | P1 cheats | |
|---|---|---|
| P2 coop's | 0c 1u 0.5 | 1c 1u 1 |
| P2 cheats | 0c 1u 0 | 1c 1u 0.5 |
Outcomes are the outcomes of P1. It seems that cheating is in Nash equilibrium. Expected outcome of cooperating strategy is zero. See computations.
One more note (thx to @chfast). If actual cost of computation is greater than reward, cooperation becomes prevailing strategy. This is bad since it creates new market behavior - bid below actual price and cooperate on black market to be profitable. To combat this we may pay extra (e.g. double) for duplicated tasks (double but to only one of providers!).
Problems:
- What about enforcing of cooperation with smart contract? For analysis see collusion: game theoretical solution with smart contract. Short answer - no, it is not viable to enforce cooperation with smart contract here.
- Game theoretical proof is just that. It does not guarantee that such behavior will not happen. It just makes it unprofitable.