We study the mechanism design problem in the setting where agents are rewarded using information only. This problem is motivated by the increasing interest in secure multiparty computation techniques. More specifically, we consider the setting of a joint computation where different agents have inputs of different quality and each agent is interested in learning as much as possible while maintaining exclusivity for information. Our high level question is to design mechanisms that motivate all agents (even those with high-quality input) to participate in the computation and we formally study problems such as set union, intersection, and average.
The recent works of @cite_21 and @cite_0 investigate non-monetary mechanisms for cooperation among competing agents. However, an essential difference is that they consider a sequential delivery of outputs to different agents, such that the utility function is not merely in terms of information but also depends on the time or order when the output is delivered. For example, the treasure hunting problem" in @cite_21 is in particular very similar to the multiparty set intersection problem, except that in treasure-hunting only the first agent finding the common element gets positive utility while all others get zero.
@cite_0 @cite_21
2235738211 1717267627
The availability of vast amounts of data is changing how we can make medical discoveries, predict global market trends, save energy, and develop new educational strategies. In certain settings such as Genome Wide Association Studies or deep learning, the sheer size of data (patient files or labeled examples) seems critical to making discoveries. When data is held distributed by many parties, as often is the case, they must share itly to reap its full benefits. One obstacle is the reluctance of different entities to share their data, due to privacy concerns or loss of competitive edge. Work on cryptographic multi-party computation over the last 30 years address the privacy aspects, but sheds no light on individual parties' losses and gains when access to data carries tangible rewards. Is an individual collaborator better off by collaborating, even if it is clear that better overall conclusions can be drawn. 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 @math -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 collaborative equilibrium 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 different players in addition to guaranteeing privacy and correctness. In a search task, a group of agents compete to be the first to find the solution. Each agent has different private information to incorporate into its search. This problem is inspired by settings such as scientific research, Bitcoin hash inversion, or hunting for some buried treasure. A social planner such as a funding agency, mining pool, or pirate captain might like to convince the agents to collaborate, share their information, and greatly reduce the cost of searching. However, this cooperation is in tension with the individuals' competitive desire to each be the first to win the search. The planner's proposal should incentivize truthful information sharing, reduce the total cost of searching, and satisfy fairness properties that preserve the spirit of the competition. We design contract-based mechanisms for information sharing without money. The planner solicits the agents' information and assigns search locations to the agents, who may then search only within their assignments. Truthful reporting of information to the mechanism maximizes an agent's chance to win the search. e-voluntary participation is satisfied for large search spaces. In order to formalize the planner's goals of fairness and reduced search cost, we propose a simplified, simulated game as a benchmark and quantify fairness and search cost relative to this benchmark scenario. The game is also used to implement our mechanisms. Finally, we extend to the case where coalitions of agents may participate in the mechanism, forming larger coalitions recursively.