Indifferential Privacy: A New Paradigm and Its Applications to Optimal Matching in Dark Pool Auctions (aamas25-00189)

Given a finite set \(R=B\cup S\) of complete order types \(t=(\sigma_t,p_t,q_t)\), rational society masses \(\mu\in\Delta_R\), and compatibility \(p_b\ge p_s\), compute a nonnegative flow \(z_{bs}\) maximizing \(\sum_{b,s}z_{bs}\), subject to \(z_{bs}=0\) for incompatible pairs, \(\sum_s z_{bs}\le q_b\mu_b\), and \(\sum_b z_{bs}\le q_s\mu_s\).

There is one traded commodity, so \(m=1\). An order type is \(t=(\sigma_t,p_t,q_t)\), where \(\sigma_t\in\{\mathrm{buy},\mathrm{sell}\}\), \(p_t\in\mathbb{Q}_{>0}\) is its limit price, and \(q_t\in\mathbb{Z}_{>0}\) is its quantity. Let \(R=B\mathbin{\dot\cup}S\) partition the types by direction.
A society is given by its support: the list of the \(\tau=|R|\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_{t\in R}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. All numerical inputs use binary encoding; \(L\) is their total bit length.
A feasible allocation consists of divisible traded quantities \(z_{bs}\in\mathbb{R}_{\geq0}\), satisfying \(z_{bs}=0\) whenever \(p_b<p_s\), \(\sum_{s\in S}z_{bs}\leq q_b\mu_b\), and \(\sum_{b\in B}z_{bs}\leq q_s\mu_s\). Equal prices are compatible, partial execution is allowed, and any maximizing allocation is acceptable. The objective is \(\max\sum_{b\in B,s\in S}z_{bs}\).

Is computing an exact maximum-volume allocation polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?

For discrete unit-node orders, a greedy matching protocol returns a maximum matching between genuine buy and sell nodes, even with auxiliary fake nodes; its computation is polynomial in the number of submitted unit nodes. [Polychroniadou, Chan, and Agrawal](https://arxiv.org/html/2502.13415v1).
No result explicitly treating this support-encoded mass formulation was identified in the search.

Result

Computing an exact maximum-volume allocation is polynomial-time solvable for the stated case \(m=1\). In fact, a greedy algorithm operates directly on the supported types and produces at most \(\tau\) positive allocation entries.

The proof below handles divisible quantities and binary-encoded rational masses without expanding quantities into unit orders.

1. Capacities and existence of an optimum

Write \(c_t=q_t\mu_t\). Thus a type \(t\) has total available capacity \(c_t\), and the problem is to maximize

\[ \sum_{b\in B,s\in S}z_{bs} \]

subject to the stated compatibility and capacity constraints.

If either side is empty, the zero allocation is optimal. Otherwise, the feasible set is nonempty, closed, and bounded: every coordinate satisfies \(0\leq z_{bs}\leq\min(c_b,c_s)\). It is therefore compact, so the continuous objective attains a maximum.

The same existence argument applies to every residual instance obtained by reducing capacities and deleting exhausted types.

2. Exchange lemma

Lemma. Consider a residual instance with strictly positive capacities. Let \(b\) be a buyer of minimum price and \(s\) a seller of minimum price. If \(p_b\geq p_s\), there is an optimal allocation satisfying

\[ z_{bs}=\min(c_b,c_s). \]

Proof. Among all optimal allocations, choose one maximizing \(z_{bs}\). Such a choice exists by compactness. Suppose, for a contradiction, that \(z_{bs}<\min(c_b,c_s)\). Define its unused capacities by

\[ r_b=c_b-\sum_{v\in S}z_{bv}, \qquad r_s=c_s-\sum_{u\in B}z_{us}. \]

There are four cases.

• Both \(r_b>0\) and \(r_s>0\). Increasing \(z_{bs}\) by \(\delta=\min(r_b,r_s)>0\) is feasible and increases total volume, contradicting optimality.

• \(r_b>0\) and \(r_s=0\). Because \(z_{bs}<c_s\), some buyer \(d\ne b\) satisfies \(z_{ds}>0\). Transfer \(\delta=\min(r_b,z_{ds})>0\) from \(z_{ds}\) to \(z_{bs}\). Seller \(s\)'s total is unchanged, buyer \(b\) remains within capacity, and buyer \(d\)'s total decreases. Volume is unchanged, but \(z_{bs}\) increases, contradicting its maximality among optimal allocations.

• \(r_b=0\) and \(r_s>0\). Because \(z_{bs}<c_b\), some seller \(e\ne s\) satisfies \(z_{be}>0\). Transfer \(\delta=\min(r_s,z_{be})>0\) from \(z_{be}\) to \(z_{bs}\). This is feasible, preserves volume, and increases \(z_{bs}\), again a contradiction.

• Both \(r_b=0\) and \(r_s=0\). There are \(e\ne s\) and \(d\ne b\) with \(z_{be}>0\) and \(z_{ds}>0\). Since \(b\) has minimum buyer price and \(z_{be}>0\) is compatible,

\[ p_d\geq p_b\geq p_e. \]

Thus \(d\) and \(e\) are compatible. For \(\delta=\min(z_{be},z_{ds})>0\), make the changes

\[ z_{be}\leftarrow z_{be}-\delta,\qquad z_{ds}\leftarrow z_{ds}-\delta,\qquad z_{bs}\leftarrow z_{bs}+\delta,\qquad z_{de}\leftarrow z_{de}+\delta. \]

All row and column totals are unchanged, all entries remain nonnegative, and both increased entries are compatible. Volume is unchanged while \(z_{bs}\) increases, a contradiction.

Every case contradicts the chosen allocation. Hence \(z_{bs}=\min(c_b,c_s)\). \(\square\)

3. Algorithm and correctness

Sort buyers and sellers separately by increasing price, breaking ties arbitrarily. Initialize all allocation entries to zero. Repeatedly take the first remaining buyer \(b\) and seller \(s\):

• If \(p_b<p_s\), discard \(b\).
• Otherwise, allocate \(\delta=\min(c_b,c_s)\) to the pair \((b,s)\), subtract \(\delta\) from both residual capacities, and remove every exhausted type.

Stop when either list is empty.

Feasibility. The algorithm allocates only between compatible types and never exceeds a residual capacity. Thus its output satisfies every original constraint.

Optimality. If \(p_b<p_s\), every remaining seller has price at least \(p_s\), so \(b\) has no compatible seller. Discarding it does not change the optimal volume.

Otherwise, the exchange lemma provides an optimum containing the algorithm's trade of size \(\delta\). Subtracting that trade from this optimum gives a feasible allocation for the residual instance. Conversely, adding the trade to any feasible residual allocation gives a feasible allocation for the current instance. Therefore,

\[ \operatorname{OPT}(\text{current}) = \delta+\operatorname{OPT}(\text{residual}). \]

At least one type is exhausted by each trade. Induction on the number of remaining types now proves that the algorithm's total volume is optimal.

Equal prices are handled by the compatible branch because its condition is \(p_b\geq p_s\).

4. Exact arithmetic and polynomial bit complexity

Represent each input mass as \(\mu_t=a_t/d_t\), with positive integers \(a_t,d_t\) in binary. Define

\[ D=\prod_{t\in R}d_t, \qquad C_t=Dc_t=q_ta_t\frac{D}{d_t}. \]

Every \(C_t\) is an integer. Scaling every capacity and allocation by \(D\) preserves feasibility and multiplies the objective by \(D\), so we may run the algorithm using these integer capacities and divide its output by \(D\).

Although \(D\) can be numerically large, its bit length is polynomially bounded:

\[ \log_2 D=\sum_{t\in R}\log_2 d_t=O(L). \]

Each \(C_t\) also has \(O(L)\) bits. During the algorithm, residual capacities and traded quantities never exceed their initial capacities, so all capacity arithmetic uses \(O(L)\)-bit integers.

Rational prices are compared exactly by cross multiplication. Their comparison operands have \(O(L)\) bits. Sorting takes \(O(\tau\log(\tau+1))\) comparisons, and the subsequent algorithm has at most \(\tau\) iterations because each iteration removes a type. Integer multiplication, division, comparison, and subtraction on these bit lengths take polynomial time.

Each nonzero output is an integer traded quantity divided by \(D\), hence has polynomial encoding length. There are at most \(\tau\) such entries; even writing the entire matrix, including zeros, requires only polynomial space and time.

Consequently, the algorithm computes an exact maximum-volume allocation in time polynomial in \(\tau,L\), and therefore in the requested parameters \(m,\tau,L\) with \(m=1\).

The cited [Polychroniadou–Chan–Agrawal paper](https://arxiv.org/html/2502.13415v1) represents order quantities using unit nodes. The proof above establishes the support-encoded result directly; its running time does not depend on the number of units represented by the capacities.

⟨structured verdict parsed — rendered above⟩

The prover resolves the stated task correctly: computing an exact maximum-volume allocation is polynomial-time solvable for \(m=1\), with binary-encoded rational masses and support size \(\tau\). The argument is rigorous and self-contained. I found no major or minor issues requiring repair.

• Capacities and existence of an optimum

The substitution \(c_t=q_t\mu_t\) exactly matches the capacities in the task. These capacities are positive rational numbers for every supported type.

If either side is empty, there are no possible trades, so the zero allocation is optimal. Otherwise, the allocation space has finitely many coordinates. The compatibility constraints, nonnegativity constraints, and capacity inequalities define a closed feasible set. The stated coordinate bounds establish boundedness, and the zero allocation establishes nonemptiness. Compactness and continuity therefore justify existence of an optimum.

Reducing capacities and deleting exhausted types preserves these properties. Residual masses need not sum to one: the proof correctly treats residual instances through their capacities alone.

• Exchange lemma: selection and case coverage

The lemma applies to the minimum-price remaining buyer and seller when they are compatible. The set of optimal allocations is nonempty and compact, so maximizing the coordinate \(z_{bs}\) within that set is justified.

Both unused capacities are nonnegative. Consequently, the four cases listed exhaust all possibilities. Under the contradiction assumption, \(z_{bs}<c_b\) and \(z_{bs}<c_s\), as needed in the subsequent cases.

• Exchange lemma: verification of each modification

• Both capacities unused: The chosen positive increment respects both capacity constraints. Compatibility follows from the lemma’s hypothesis. The objective increases, contradicting optimality.
• Only the buyer has unused capacity: Saturation of seller \(s\), together with \(z_{bs}<c_s\), guarantees a positive entry \(z_{ds}\) with \(d\ne b\). The transfer preserves seller usage and total volume, respects buyer capacities, and increases \(z_{bs}\).
• Only the seller has unused capacity: Saturation of buyer \(b\), together with \(z_{bs}<c_b\), guarantees a positive entry \(z_{be}\) with \(e\ne s\). The stated transfer has the corresponding feasibility and objective-preservation properties.
• Both capacities saturated: The required positive entries exist for the same reasons. Minimum buyer price gives \(p_d\geq p_b\), while feasibility of \(z_{be}>0\) gives \(p_b\geq p_e\). Thus the newly increased entry \(z_{de}\) is compatible. The other increased entry \(z_{bs}\) is compatible by hypothesis. The four modified coordinates are distinct because \(d\ne b\) and \(e\ne s\). The chosen increment preserves nonnegativity, all row and column totals, and total volume.

Every case contradicts either optimality or the chosen coordinate’s maximality. The lemma follows without an omitted compatibility assumption.

• Algorithm and residual-instance correctness

Increasing-price sorting supplies the minimum-price types required by the lemma. Arbitrary tie-breaking is valid because the proof uses non-strict price inequalities.

When \(p_b<p_s\), every remaining seller is incompatible with \(b\). Discarding that buyer therefore preserves the residual optimum.

In the compatible branch, the lemma supplies an optimum containing exactly the selected trade. Subtracting that trade respects the reduced capacities. Any exhausted type has no remaining allocation incident to it, so deleting exhausted types is legitimate. Conversely, adding the selected trade to a feasible residual allocation respects the original capacities. These two statements justify the displayed equality between current and residual optimal values.

Each iteration removes at least one type. The empty-side optimum supplies the induction’s base case, and the two branches supply its inductive steps. The resulting allocation is feasible and optimal. Equal prices are correctly accepted.

• Exact arithmetic and binary complexity

The common denominator \(D\) is valid whether or not the input fractions are reduced. Every \(D/d_t\) is an integer, so every scaled capacity \(C_t\) is an integer. Scaling preserves the constraints and objective exactly.

The bit-length calculation is correct: the sum of denominator bit lengths is bounded by the total input length \(L\), so \(D\) has \(O(L)\) bits. Multiplication by \(q_ta_t\) leaves each \(C_t\) with \(O(L)\) bits. Residual capacities and trade amounts remain bounded by initial scaled capacities.

Exact price comparisons by cross multiplication also use \(O(L)\)-bit integers. Constructing the scaled capacities, sorting, and performing at most \(\tau\) iterations therefore require polynomial time.

Each positive output entry has an integer numerator and denominator \(D\), both of polynomial encoding length. At most \(\tau\) trades occur. Writing all zero entries as well requires at most \(|B||S|\) coordinates, which remains polynomial in \(\tau\).

• Scope and citation

The conclusion is restricted correctly to the task’s fixed case \(m=1\). The proof does not expand capacities into unit orders and does not rely on the cited paper’s matching theorem. The contextual statement that the paper represents quantities using unit nodes agrees with its description. [Polychroniadou–Chan–Agrawal](https://arxiv.org/html/2502.13415v1).

No additional clarification or mathematical repair is needed.

⟨structured verdict parsed — rendered above⟩