Private Pareto Optimal Exchange

Sampath Kannan, Jamie Morgenstern, Ryan M. Rogers, Aaron RothACM Trans. Economics and Comput 2015 · OpenReview

TL;DR

This paper tackles the challenge of achieving fair and efficient resource allocation in exchange economies (like kidney exchanges) while protecting participants' sensitive data using differential privacy. They show that strong privacy guarantees prevent efficient outcomes, but a novel, weaker privacy notion called "marginal differential privacy" allows for individually rational and nearly Pareto optimal allocations.

What Problem Does This Paper Address?

Imagine a market where people trade goods directly, without money – think of kidney exchanges where patients and donors are matched. The goal is to ensure everyone gets a good they prefer to their original one (individually rational) and that no one can be made better off without making someone else worse off (Pareto optimal). However, in many such scenarios, like kidney exchanges, the data involved (patient medical records, preferences) is highly sensitive. This paper asks: can we achieve these desirable allocation outcomes while providing formal privacy guarantees to the participants, specifically using the framework of differential privacy?

The authors highlight that standard differential privacy, which protects against an adversary seeing all but one person's data, is too strong for allocation problems. Even a weaker notion, "joint differential privacy" (protecting against collusions of other agents), proves insufficient for achieving non-trivial Pareto optimality. This leaves a gap: how to balance privacy with efficiency in these critical exchange scenarios.

Methods

The core of the paper is developing and analyzing a new privacy definition and an algorithm that works under it.

  • Marginal Differential Privacy: This is the key privacy concept introduced. It's a relaxation of joint differential privacy. Informally, it means an agent's privacy is protected from any single other agent, assuming they don't collude. This is weaker than joint differential privacy, which protects against collusions of multiple other agents.
  • Private Top Trading Cycles (PTTC) Algorithm: The authors propose an algorithm that implements exchanges under this new marginal differential privacy guarantee. It's a modification of the classic Top Trading Cycles algorithm. The algorithm involves:
  • Adding Noise to Arc Weights: To achieve privacy, noise is added to the "weights" of potential trades (representing how many agents want a specific trade). This step uses the Laplace mechanism, a standard tool in differential privacy.
  • Clearing Cycles: The algorithm identifies and "clears" cycles of trades where agents can exchange goods. This is done based on the noisy weights.
  • Randomized Selection: When agents are selected to trade within a cycle, the selection is randomized to maintain privacy.
  • Iterative Refinement: The process iteratively removes goods and agents, and re-evaluates trades until a stable allocation is reached.

Datasets

Not discussed in the paper. The paper focuses on theoretical mechanisms and algorithms for abstract exchange economies, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Privacy vs. Efficiency Trade-off: The paper strongly demonstrates that stronger privacy guarantees (like differential privacy or joint differential privacy) fundamentally limit the achievable efficiency (Pareto optimality) in exchange economies. This is because efficient allocations often reveal information about agents' preferences.
  • The Power of Marginal Privacy: The introduction of "marginal differential privacy" is a crucial contribution. It provides a sweet spot: strong enough to protect individual privacy from single adversaries but weak enough to allow for meaningful and efficient allocations. This highlights that privacy needs can be nuanced and don't always require the strictest definitions.
  • Barter is Harder than Two-Sided Markets: The paper shows that general barter exchange (where everyone gives and receives) is harder to make private and efficient than two-sided markets (like buyers and sellers), where existing work showed better results under joint differential privacy.
  • The Role of "Extra Goods": The paper touches upon how having a small supply of "extra" goods (like altruistic kidney donors) can help circumvent privacy limitations, particularly under joint differential privacy, by restoring feasibility.

Key Results

  • Impossibility under Stronger Privacy: Under joint differential privacy, it's impossible to achieve any non-trivial approximation to Pareto optimality while guaranteeing individual rationality.
  • Achievability under Marginal Privacy: The proposed PTTC algorithm achieves individually rational and approximately Pareto optimal allocations under marginal differential privacy.
  • Approximation Factor: The approximation to Pareto optimality achieved by PTTC is $O(\frac{k^{3/2}}{n\epsilon})$, where $k$ is the number of goods types, $n$ is the number of agents, and $\epsilon$ is the privacy parameter. This means efficiency improves as the number of agents grows (asymptotically Pareto optimal).
  • Lower Bound: A lower bound of $\Omega(k/n)$ is established for the approximation factor under marginal differential privacy, showing that the PTTC algorithm is close to optimal in terms of its dependence on $k$ and $n$.

Limitations and Future Work

  • Approximation Factor Dependence: The approximation factor depends polynomially on the number of goods types ($k$). The authors note it's natural to ask if this can be improved to a polylogarithmic dependence, similar to some results in two-sided markets.
  • Marginal Privacy vs. Coalition Privacy: The paper introduces "m-coalition differential privacy" as a spectrum between marginal and joint privacy. Future work could explore this spectrum and develop algorithms for intermediate privacy levels.
  • Incentive Compatibility: The current algorithms don't guarantee truthful reporting as a dominant strategy. Future work could investigate how to achieve incentive compatibility alongside privacy and efficiency, potentially by leveraging existing mechanisms for markets with indifferences.
  • Practical Implementation: While the theoretical framework is established, practical considerations for implementing such mechanisms in real-world scenarios (like kidney exchanges) would be a valuable next step.

Summary updated

Abstract

We consider the problem of implementing an individually rational, asymptotically Pareto optimal allocation in a barter-exchange economy where agents are endowed with goods and preferences over the goods of others, but may not use money as a medium of exchange. Because one of the most important instantiations of such economies is kidney exchange -- where the "input" to the problem consists of sensitive patient medical records -- we ask to what extent such exchanges can be carried out while providing formal privacy guarantees to the participants. We show that individually rational allocations cannot achieve any non-trivial approximation to Pareto optimality if carried out under the constraint of differential privacy -- or even the relaxation of joint-differential privacy, under which it is known that asymptotically optimal allocations can be computed in two sided markets [Hsu et al. STOC 2014]. We therefore consider a further relaxation that we call marginal-differential privacy --which promises, informally, that the privacy of every agent i is protected from every other agent j ≠ i so long as j does not collude or share allocation information with other agents. We show that under marginal differential privacy, it is possible to compute an individually rational and asymptotically Pareto optimal allocation in such exchange economies.
BibTeX
@article{kannan2015private,
  author = {Sampath Kannan and Jamie Morgenstern and Ryan M. Rogers and Aaron Roth},
  title = {{Private Pareto Optimal Exchange}},
  journal = {ACM Trans. Economics and Comput.},
  year = {2015},
  url = {https://openreview.net/forum?id=8BcjaPRV8m},
}
Figure