Indifferential Privacy: A New Paradigm and Its Applications to Optimal Matching in Dark Pool Auctions

The strongest honest case is a population mirror of the paper’s exact matching result, with the privacy contribution as a more ambitious secondary mirror.

The lead anchor is Lemma 3.2, proved in this paper: “Algorithm 1 returns a maximum matching between real buy and sell nodes in the matching graph.” The paper does not state a numbered \(P\), NP-hardness, or parameterized-complexity theorem; Lemma 3.2 is a correctness result for a computational problem. That is still a valid anchor, but the distinction matters.

I would call the mirror Continuum Dark-Pool Clearing.

An instance consists of a finite set of complete order types
\[ R=B\cup S,\qquad t=(\sigma_t,p_t,q_t), \]
where \(\sigma_t\in\{\mathrm{Buy},\mathrm{Sell}\}\), \(p_t\in\mathbb Q_{\ge0}\) is the public price, and \(q_t\in\mathbb Z_{>0}\) is the common order quantity of agents of that type. The society is a rational mass vector \(\mu\in\mathbb Q_{\ge0}^{R}\) with \(\sum_t\mu_t=1\). Thus \(\mu_t\) is the fraction of clients of type \(t\), and \(a_t=q_t\mu_t\) is their aggregate order volume.

The solution is a matching-flow vector \(z=(z_{bs})_{b\in B,s\in S}\), where
\[ z_{bs}\ge0,\qquad z_{bs}=0\ \text{if }p_b<p_s, \]
and
\[ \sum_s z_{bs}\le a_b,\qquad \sum_b z_{bs}\le a_s. \]
The objective is to maximize
\[ \sum_{b,s}z_{bs}, \]
the total matched volume. A solution is the flow together with its matched-volume certificate.

This is recognisably the authors’ problem: the same buy–sell compatibility condition, the same objective of maximizing matched units, and the same price ordering that drives their polar-opposite strategy. The only change is that repeated unit nodes are represented by capacity mass. For a finite repeated-agent election with \(n_t\) agents of type \(t\), set \(\mu_t=n_t/N\). Multiplying the continuous solution by \(N\) gives an integral capacitated bipartite matching problem, because the underlying flow polytope is integral. Thus this is not merely a fractional relaxation: on the repeated-type slice it exactly recovers the discrete maximum matching after scaling.

The natural regime is a large dark-pool clearinghouse receiving many institutional child orders, with prices drawn from a moderate number of ticks and order sizes drawn from a moderate number of standard lot classes. There may be millions of orders but only \(\tau\) repeated side–price–quantity types, with \(\tau\ll n\). Agents of the same type are indistinguishable for the matching objective and compatibility relation. If every order has an idiosyncratic price, quantity, or priority rule, this regime is inappropriate; the mirror is explicitly for a repeated-order environment.

I would expect Continuum Dark-Pool Clearing to be in Class A. A sorted sweep, or equivalently a small transportation LP, computes the optimum in time polynomial in \(\tau\) and the rational input length. The paper’s Lemma 3.2 supplies the structural justification: matching the most attractive remaining buy and sell blocks can be made compatible with an optimum. In the continuum this becomes an exchange argument over mass rather than individual nodes.

A secondary anchor is Lemma 3.3, also proved here: using an ideal commitment scheme, the protocol is \((\epsilon,\delta)\)-indifferentially private. Corollary 3.4, proved here as well, gives computational IDP with a real-world commitment scheme. I would treat these as one privacy anchor rather than two separate problems.

The corresponding question is Resolution-\(\eta\) Continuum-IDP Clearing. Let \(u=(\sigma,p)\) be a public order class and let \(q\) be a hidden quantity class. The society is a rational mass distribution \(\mu_{u,q}\). The server observes only the public projection
\[ \nu_u=\sum_q\mu_{u,q}. \]
A neighboring input moves mass \(\eta\) from \((u,q)\) to \((u,q+1)\), leaving every public class unchanged. Here \(\eta\) is an explicit privacy resolution, analogous to one client in a finite population normalized by its population size.

The protocol must output a maximum true matched volume while adding committed fake order mass \(\eta N_u\), where \(N_u\) is sampled from the bounded geometric distribution used in the paper. Its transcript must satisfy
\[ HS^{F_\eta}_{e^\epsilon} \bigl(\mathrm{View}(\mu)\,\|\,\mathrm{View}(\widehat\mu)\bigr) \le\delta, \]
where \(F_\eta\) pairs identical transcripts, except that two transcripts may diverge after the smaller hidden quantity \(q\eta\) has been fully matched. This is exactly the paper’s “privacy may be relaxed after full execution” principle, expressed at mass resolution. The matching part remains the same polar-opposite sweep, with fake mass discarded when opened.

Under a finite type set, rational encoding, and bounded noise support, I would expect this aggregate version also to be Class A: the matching computation is a chain-structured flow problem, and the privacy analysis should follow the paper’s coupling of shifted geometric distributions. The further questions are whether the guarantee composes across many repeated agents, how to handle multiple assets or time priority, and whether a useful finite-population rounding theorem preserves both exact matching and IDP.

The weakest point is the privacy mirror. Literal individual-level privacy does not survive unchanged in an atomless population: a single agent has zero mass, so changing that agent’s quantity is either invisible or requires an external resolution parameter. The \(\eta\)-formulation therefore protects a small cohort or aggregate volume, not literally one named user. Moreover, the paper samples noise per user, whereas the continuum version naturally samples noise per public type or mass block. I would not claim that Corollary 3.4 transfers automatically.

That weakness does not undermine the lead case. Continuum Dark-Pool Clearing is already a precise, faithful mirror of Lemma 3.2, with an exact high-multiplicity bridge and an efficient continuous algorithm. The scope should stop there if necessary: it covers the paper’s maximum-matching result, not its implementation benchmarks, FHE comparisons, or full per-user cryptographic privacy theorem. The paper’s use of “continuous double auction” refers mainly to trading over time; the proposed mirror continuizes the population, which is a separate and legitimate operation.