How to Incentivize Data-Driven Collaboration Among Competing Parties

The availability of vast amounts of data is changing how we can make medical discoveries, predict global market trends, save energy, and develop educational strategies. In some settings such as Genome Wide Association Studies or deep learning, sheer size of data seems critical. When data is held distributedly by many parties, they must share it to reap its full benefits. One obstacle to this revolution is the lack of willingness of different parties to share data, due to reasons such as loss of privacy or competitive edge. Cryptographic works address privacy aspects, but shed no light on individual parties' losses/gains when access to data carries tangible rewards. Even if it is clear that better overall conclusions can be drawn from collaboration, are individual collaborators better off by collaborating? Addressing this question is the topic of this paper. The order in which collaborators receive the outputs of a collaboration will be a crucial aspect of our modeling and solutions. We believe that timing is an important and unaddressed issue in data-based collaborations. Our contributions are as follows. We formalize a model of n-party collaboration for computing functions over private inputs in which the participants receive their outputs in sequence, and the order depends on their private inputs. Each output "improves" on all previous outputs according to a reward function. We say that a mechanism for collaboration achieves a collaborativee quilibrium if it guarantees a higher reward for all participants when joining a collaboration compared to not joining it. We show that while in general computing a collaborative equilibrium is NP-complete, we can design polynomial-time algorithms for computing it for a range of natural model settings. When possible, we design mechanisms to compute a distribution of outputs and an ordering of output delivery, based on the n participants' private inputs, which achieves a collaborative equilibrium. The collaboration mechanisms we develop are in the standard model, and thus require a central trusted party; however, we show that this assumption is not necessary under standard cryptographic assumptions. We show how the mechanisms can be implemented in a decentralized way by n distrustful parties using new extensions of classical secure multiparty computation that impose order and timing constraints on the delivery of outputs to di ff erent players, in addition to guaranteeing privacy and correctness.