Data Sharing Markets

The recent rapid advances in machine learning algorithms, hardware, and platforms has had a major effect on fielded applications—access to data has become the limiting constraint in many such applications. The limitation often arises because data is generated in a decentralized fashion, held privately under a variety of ownership models. There is accordingly a growing need to study distributed machine learning problems in which self-interested agents are incentivized to share their data. Designing such incentives requires understanding the costs that users incur in sharing their data, including communication and privacy costs, and trading off those costs against possible benefits from data analysis. The costs and benefits will generally be agent- and type-specific. The overall problem is a complex market-design problem that aims at incentivizing the sharing of data while achieving computational, economic, and statistical efficiencies (Agarwal et al.,, 2019; Fernandez et al.,, 2020; Liang and Madsen,, 2020).

As an example consider banks who are interested in deploying up-to-date fraud detection algorithms. Each bank has its own data on financial frauds coming from its historical record of transactions. But such data will often not have good coverage and may be out of date. Rather than relying solely on its own data, banks would ideally share data, obtaining a better model than would be possible without sharing. As another example, hospitals each have their own set of patient data; e.g. radiology data, genomic data, or epidemiological data. The data available to a single hospital may be not sufficient for accurate inference or particularly for causal inference. Indeed, the per hospital data may be biased in various ways. Ideally, hospitals would share data to mitigate these and other problems.

Data has unique features as a commodity that make data markets distinct from other markets. First, in some cases data is traded for other data (bilateral sharing) as opposed to an exchange of data for money (unilateral sharing). In bilateral sharing, the agents gain access to each others’ data. Bilateral sharing is natural in use cases in which it is hard to evaluate and attach a price to data (Mehta et al.,, 2019). Indeed, the fundamental challenge of quantifying the value of data in algorithmic predictions and decision-making is an active research area (Ghorbani and Zou,, 2019; Mehta et al.,, 2019). It is also natural when regulations do not permit the exchange of money for data; this would be the case for the sharing of patient data. Bilateral trade without money also arises in other markets. Companies exchange their pool of patents with each other because they can not evaluate and attach a price to their patent pool. Also, regulatory limits on trading commodities with money also exist for various forms of matching markets, including kidney exchange markets. Relationships, such as friendships or marriage, are other forms of markets with bilateral exchange where money is not used. Even within the context of such examples, however, data markets are distinct. In particular, data is traded often at some privacy and communication cost for agents (in contrast to patent market) and one agent can share data with multiple agents through bilateral exchanges (in contrast to organ donation or marriage markets).

Our first problem of study in this paper, in the tradition of the seminal paper of Gale and Shapley, (1962), is to find conditions under which stable outcomes exist for bilateral sharing, and can be found in polynomial time. We model bilateral sharing as a general network/graph formation game, similar to Jackson and Wolinsky, (1996) and Jackson and Van den Nouweland, (2005). This game is a more general version of hedonic games that are known not to have core stable outcomes in general (Bogomolnaia and Jackson,, 2002). We also consider the notion of strong stability. In this case, without imposing a utility structure on the agents, we find conditions under which the game has a strongly stable outcome and we design an algorithm that can find such outcomes in $O(N^{2})$ time, where $N$ is the number of agents. Our framework weakens some of the unrealistic assumptions that have traditionally been imposed in the literature on strongly stable outcomes (Ostrovsky,, 2008); in particular, we allow cyclicity in the trades and limited complementarity. We achieve this weakening by isolating a property—the top agent property—which defines an ordering for agents that is based on how much each agent is preferred by all other agents. Limited complementarity then arises by ensuring that no subset of agents ranked below an agent can be preferred to that agent. Our notion of top agent property has similarities to that of ordered coalitions in Bogomolnaia and Jackson, (2002), the notion of the common ranking property (Farrell and Scotchmer,, 1988; Caskurlu and Kizilkaya,, 2019) and the top coalition property (Banerjee et al.,, 2001) used in establishing the existence of core stable outcomes in hedonic games.

We also consider unilateral data sharing where agents can assess the value of data and can trade data for money. An example of this paradigm arises in the case of renewable energy forecasts (Gonçalves et al.,, 2020). Here we build on the seminal work of Shapley and Shubik, (1971), and study conditions that allow existence of competitive prices in these markets which also implement social-welfare-maximizing sharing. Our data sharing model is a one-sided, many-to-many sharing protocol, limited to trading of a single indivisible good in each directed trade. We show that if the agents’ cost of sharing is additive with respect to the agents that gain access to their data, then there exists set of competitive prices, and every social-welfare-maximizing outcome can be implemented with such competitive prices in a way that it will be a stable outcome.

Data has other unique features that influence the design of markets. In particular, the quality of data shared with other agents can be distorted upward or downward at almost zero cost, and without impact on the quality of data passed to other agents. There are several ways in which the quality of data can be distorted. For example, downward distortion can be achieved by removing part of one agent’s data when passed to the another agent, and upward distortion can be obtained by adding new data that is delivered to an agent (e.g., by generating new data by using generative adversarial networks). Alternatively, noise can be added to the data, or in more complicated setups where agents share a machine learning models, the quality of those models can be distorted. All these distortions can take place without impact on the quality of data received by other agents.

Our third problem is designing market mechanisms for unilateral data sharing when agents have private types. The market is run by a social planner. We consider Vickrey-Clarke-Groves (VCG) mechanisms (Vickrey,, 1961), which have been shown to uniquely implement social welfare at dominant strategies (Holmström,, 1979). However, VCG mechanisms are known to suffer from budget imbalance for the intermediary. We look for market mechanisms that have the following features: they implement approximate social-welfare-maximizing outcomes at dominant strategies, are individually rational, and are budget balanced. To this end, we propose a variation of the VCG mechanism which we refer to as mixed-VCG. Mixed-VCG uses both data distortion, referred to as data money, and monetary payment, to achieve budget balance while implementing social welfare via calibration to the value of budget imbalance of the standard VCG mechanism. Mixed-VCG uses downward distortion for budget surplus and upward distortion for budget deficit of the intermediary. While distorting data quality downward is practically at zero cost, for example by adding noise to the data, an upward distortion may be costly to the intermediary. To address this issue, we present a mechanism that we refer to as the distorted-mixed-VCG mechanism. Here the intermediary adds a fixed base downward distortion of data in a zero cost way, for example fixed noise added to data. Then instead of adding new data, the intermediary simply lifts controlled amounts of the fixed noise.

While our presentation focuses on the essential components of a data sharing market, we note that our model can be extended to more complicated algorithms for data sharing. For example a popular data sharing mechanism is one in which each agent only asks for outcome of an inquiry over another agent’s data and the second agent incurs a privacy cost per inquiry. We will also show that our model and results can be extended to capture this setup.

The rest of the paper is organized as follows. Section 2 reviews the relevant background literature. In Section 3, we study our first problem for existence of stable outcomes for bilateral sharing. In Section 4, we show the existence of competitive prices for unilateral sharing, and Section 5 proposes the mixed-VCG mechanism for unilateral sharing with private information. In Section 6 we extend our model and results to the case of data sharing limited to incremental inquiries over data under a restriction expressed in terms of differential privacy. We conclude the paper and discuss further research directions in Section 7.

In this section we review some of the relevant literature, focusing on four main areas: an emerging literature on data markets, and three classical areas in microeconomics, specifically stable outcomes in cooperative games, competitive equilibrium, and social-welfare-maximizing mechanism design. We discuss these areas separately below.

Data markets and relevant applications: There is a growing recent literature for data markets that studies specific properties of data as a economic good [see, e.g., for a survey Mehta et al., (2019)]. The literature addresses market structures and mechanisms for sales of data and data products (e.g., ratings, predictions, recommendations, and machine learning models).

To the best of our knowledge, our paper is the first to study non-monetary mechanisms for the trade of data (bilateral data exchange). There has been, however, a growing literature on monetary data market mechanisms which we review here. The first set of papers in this area study data sharing among strategic agents/firms. These papers implement information sharing among competing agents via the use of an intermediary. In this literature the intermediary is treated as a welfare maximizer, and is limited to aggregating data from agents and sharing it with all others (see, e.g., Raith,, 1996). Bergemann and Morris, (2013) and Bergemann et al., (2018) extend this literature to the case of a rent-seeking intermediary who can also distort data. In contrast to this literature, we do not consider competition among the agents in downstream markets, and we also do not pose corresponding restricting assumptions on trade and on utility functions. We allow for bilateral trade, both with and without intermediaries. In our study, the intermediary is a social-welfare maximizer and we also allow the intermediary to add noise to the model.

The other relevant strand of the data-market literature are two-sided markets where buyers and sellers are separate. Agarwal et al., (2019) propose a market mechanism for finding prices and distributing welfare while allowing individual prices per buyer. The prices are not allowed to be seller specific. They also not consider the cost of sharing, including privacy costs. Our work extends this model to buyer-seller specific prices in a setup where buyers can also be sellers. We also consider the cost of sharing, as do Ghosh and Roth, (2011) and Ligett and Roth, (2012) who study the tradeoff with revenue gain. Acemoglu et al., (2019) discuss the externalities in data privacy.

There are several applications similar to data sharing. These can be unified under information economics. Patents have similar features to data (Lerner and Tirole,, 2004). They can be sold to multiple agents, can be combined together for higher productivity, and can be ordered in their value for consumers. However, the literature on patents assumes a negligible cost of sharing. Moreover patent quality can not be distorted by the intermediary. Ad auctions (Varian,, 2009) and online matching (Mehta,, 2013) are other relevant applications where intermediaries sell data about customers or the other side of the market. In these markets the sales of data is limited, a single ad shown to a target customer, data for each customer is sold to a single advertiser, and there is a one-to-one matching in online matching.

Stable outcomes in cooperative games: There is an extensive literature of cooperative matching games dating back to the seminal work of (Gale and Shapley,, 1962). The major question is to existence of stable outcomes and efficient (polynomial order) algorithms for finding them. The games studied differ in various ways—in the structure of the matching market (e.g., two-sided vs one-sided, one-to-one vs one-to many vs many-to-many, etc.), and in the particular notion of stability employed (strong stability, core stability, Nash stability, individual stability, contractual individual stability, etc). (Gale and Shapley,, 1962) studied two-sided games with two-sided preferences and established the existence of a core stable outcome via a deferred acceptance algorithm that runs in time $O(n^{2})$. Two-sided matching games with one-sided preferences and with ownership is studied in Shapley and Scarf, (1974) where the top-trading cycle algorithm demonstrates the existence of a core stable outcome calculated in time $O(n^{2})$. Finally, two-sided games without ownership are studied in Hylland and Zeckhauser, (1979), who studied a class of “random serial dictatorship” algorithms, and in Abdulkadiroğlu and Sönmez, (1998), who proposed a “core from random endowment mechanism.” While the majority of this work involves two-sided matching, Irving, (1985) studied core stable outcomes in one-sided team formation problems in the context of roommate matching. This is a special case of hedonic games where agents form disjoint partitions and have preferences only in terms of agents in their own coalition (Bogomolnaia and Jackson,, 2002). Hedonic games do not have core stable outcomes in general. Bogomolnaia and Jackson, (2002) show that hedonic game with ordered coalitions or when players have additive and separable preferences have individually stable coalitions.

Our game is more general than hedonic games since matchings are not necessarily in coalition partitions; it could be that agents A and B share data together but C only shares data with A and not B. Therefore our game is a network/graph formation game (Jackson and Wolinsky,, 1996).

Another difference between our work and existing literature is that the latter focuses on core stable outcomes, while focus on strong stability. We will henceforth refer to strong stability as “stability.” Recall that the outcome of the game is strongly stable if there is no deviating coalition of agents that can form contracts among each other, also keeping or dropping their existing contracts with agents out of the deviating coalition at will, in a way such that all members of the deviating coalition weakly prefer the new outcome and at least one of them strongly prefers the new outcome.

Most of the literature is based on two assumptions that are used to establish the existence of strong stability (Ostrovsky,, 2008): substitutability and acyclicity of trade. We relax both assumptions in this study.

Games that weaken the acyclicity assumption are studied by Jackson and Wolinsky, (1996) in the context of friendship networks. The results, however, are limited to a weak notion of pair-wise stability and to restricted value allocation for the outcomes. Jackson and Van den Nouweland, (2005) studied strong stability in network formation games but imposed strong assumptions on the structure of the value function; for example, component-wise separability. In contrast we consider strong stability and general preferences without value functions.

A line of work that relaxes complementarity is presented for large markets by Azevedo and Hatfield, (2018) but it relies on the existence of transferable (monetary payments) between agents. Pycia, (2012) study the existence of stability in two-sided matching markets but assume that preferences are pair-wise aligned in two sides. In this paper, we study a network formation game involving finite number of agents with general preferences (without utility functions). We also consider a limited complementarity property which is satisfied (for example) under the substitutability condition of Ostrovsky, (2008) but also holds more broadly.

In our work the limited complementarity property arises from the top agent property, which induces an ordering among the agents on how much they are preferred by others. Our notion of top agent property has similarities to that of “ordered coalitions” in Bogomolnaia and Jackson, (2002) as well as the notion of the “common ranking property” (Farrell and Scotchmer,, 1988; Caskurlu and Kizilkaya,, 2019) and the “top coalition property” (Banerjee et al.,, 2001) used for establishing the existence of core stable outcomes in Hedonic games.

Finally while it is NP hard to find core stable outcomes in hedonic games under the assumptions that are generally made in the literature, in our setup we we are able to derive an algorithm that finds stable outcomes in time $O(N^{2})$, where $N$ is the number of agents.

Competitive equilibrium: There is an extensive literature on competitive prices. The main questions are existence of competitive prices, their structure, mechanisms that can find/form those prices, and their properties (including fairness, stability, and efficiency). Shapley and Shubik, (1971) studied two-sided matching games in which agents can have monetary transfer and show the existence of competitive prices. They also show that these prices realize core stable outcomes, and are social-welfare maximizing. The extension to the case of non-quasilinear utility is studied in Demange and Gale, (1985) and Alaei et al., (2016). Sotomayor, (1992) provide an extension to multi-partner two-sided matching markets case where each worker (firm) can have multiple but a limited number of jobs (hiring positions). Further study of many-to-one matching and many-to-many matching in two-sided matching markets is provided in Gul and Stacchetti, (1999) and Ausubel and Milgrom, (2002). Our data sharing market is not two-sided and allows multiple partners without limitation on their number. we also consider quasilinear utilities. However, we only allow one unit of an indivisible good to be traded in each directed partnership. Considering an additive structure on the utility function, we establish the existence of competitive prices for this setup, and we show that every social-welfare-maximizing outcome can be implemented with competitive prices such that it will be a stable outcome.

Social-welfare-maximizing mechanism design: There is large literature on mechanism design where agents have private information. The VCG mechanism, presented in the seminal paper of Vickrey, (1961), is the only truthful dominant mechanisms that maximizes the utilitarian social welfare under certain assumptions, including unrestricted preferences and at least three different outcomes (Holmström,, 1979). VCG mechanisms are also ex-post individually rational under monotonicity of the choice set and non-negativity of externalities. However, VCG mechanisms have major practical shortcomings. In particular, they are not individually rational and budget balanced at the same time.

Green-Laffont’s impossibility result shows that no dominant-strategy incentive-compatible mechanism is always both social-welfare maximizing and weakly budget balanced (Green and Laffont,, 1977). We extend the VCG mechanism to address these issues by leveraging the structure of the data sharing economy. We consider unique features of data, particularly the possibility of distort the quality of data for an agent at zero cost and without impact on other agents’ utilities. We then introduce a “mixed-VCG” framework that achieves approximately optimal social welfare, dominant strategy incentive compatibility, budget balance, and ex-post individual rationality.

We begin by presenting our model of the bidirectional data sharing problem, posing it as as a network formation game. Then we present our results on the existence of strongly stable outcomes for this game.

In this Section, we study the case where data is traded with money. To this end we first extend the model in Section 3 to include utility functions and allow money transfer. Following Shapley and Scarf, (1974), we investigate existence of competitive prices that can realize stable outcomes. We will present structures on the utility function that guarantee existence of such prices.

In this section we extend the model by assuming agents belong in type space $\Theta$, determining their utility from sharing. We further assume types are private information known only to the agents themselves. There also exists a social planner intermediary who runs a market for coordinating data sharing. We look for market mechanisms that have the following features: they implement approximate social-welfare-maximizing outcomes at dominant equilibrium, they are individually rational, and they are budget balanced. To this end, we propose a variation of the VCG mechanisms—mixed VCG—which uses a mix of data distortion (referred to as “data money”) and monetary payment to achieve budget balance. We will then investigate how to address communication/message complexity of the VCG mechanisms for data sharing, using specific features of data.

In this section we briefly show how the model and results can be adapted to a more complicated setting, by bringing differential privacy into the picture. We relax full reporting of data in Assumption 3.1, and assume agents make queries over each others’ data, where for each query there is a differential privacy cost for the data owner. In this setup, the unit of commodity offered by each agent $n$ is the outcome of a query over its data, rather than its whole raw data. We omit the proofs of this section.

We update the model by extending the results in Section 3 to 5. First, the sharing graph $G$ in Definition 3.1 is extended with integer weights on the edges $\tilde{w}_{i,j}$ which reflect the number of queries agent $i$ runs on agent $j$’s data. We refer to this graph by $\tilde{G}$. The cost and utility functions in Assumptions 4.2 are extended to be a function of graph $\tilde{S}^{O}_{i}$ and $\tilde{S}^{I}_{i}$, $V_{i}(\tilde{G})=U_{i}(\tilde{S}^{O}_{i})-C_{i}(\tilde{S}^{O}_{i})$, where $\tilde{S}^{I}_{i}=\{(j,\tilde{w}_{i,j}):j\in N\}$, $\tilde{S}^{O}_{i}=\{(j,\tilde{w}_{j,i}):j\in N\}$ Given these updates to the model, together with Proposition 3.1, we can show that a core stable outcome exists and can be found by updating the ordered match algorithm as follows: every time an agent $n$ swipes an agent $\ell$, it also proposes a set of sharing weights $\{(\tilde{w}_{n,\ell},\tilde{w}_{\ell,n})\}$ that are acceptable to $n$ (the benefits of sharing are greater than costs). Agent $\ell$ then either accepts to share by choosing from this set or rejects the sharing of data.

Next consider a cost structure in which each agent $i$ has a differential privacy cost which, along the line of (4) is additively decomposable with respect to the agents he is sharing data with:

Then, along the lines of Proposition 4.1, there exists a set of competitive prices where each agent $i$ charges agent $j$ an amount of $c_{i}(j)$ per inquiry. Moreover, each other agent $j$ is allowed to purchase multiple inquiries from agent $i$.

Finally, the VCG mechanism in Section 5 can be updating by considering doubly weighted directed graphs $\hat{\tilde{G}}$ with weights on each edge from $i$ to $j$ being $\tilde{w}_{i,j}$ the number of inquiries of $j$ on $i$’s data, and $w_{i,j}$ the distortion to quality of each inquiry. Then (36) can be extended as

The mixed-VCG mechanism is updated to include weights $\tilde{w}_{ij}$ determined by the intermediary.

We have studied data sharing markets for both bidirectional (data-data exchange) and unidirectional (data-money exchange) sharing. We proved existence of strongly stable outcomes for bilateral sharing via formulating the problem as a network formation game. We achieved this with limited complementarity and without posing utility structure on agents’ preferences. For unilateral sharing, we constructed competitive prices that implement socially optimal outcomes, and in the case of agents’ private information of their types, we also presented budget balanced mechanisms which truthfully implement approximately optimal outcomes.