Thanks for the comments! I’ll take a look at both papers (I recall reading the Abernethy, et. al paper a few years ago). I found some slides on Bounded-Loss Private Prediction Markets and it definitely looks like there is quite a bit of similarity in some ways. The \Theta(\log^2 n) bound from your work is also quite curious because I had initially had a bound of that form for CFMMs but later found a way to reduce it to \Theta(\log n). I should note that we do add randomness to trades; what we prove is the following set of claims whose assumptions weaken as one goes down the list
- If the trades are ‘well-separated’ and ‘none are too big’, then permuting the trades randomly achieves (\mu \log n, \delta)-DP
- If you add \mathsf{Lap}(a) noise to each trade, where a = a(\Delta_1, \ldots, \Delta_n) is a function of the trades to be executed in a batch, then you can force trades to be “well-separated” with high probability
- If you split each trade \Delta into m pieces using \pi \sim \mathsf{Dir}(\frac{1}{m}, \ldots, \frac{1}{m}) (e.g \Delta_i = \Delta \pi_i), you can achieve the “none are too big” condition
(Note: I put “well-separated” and “none are too big” in quotes as these monikers hide some technical nuances.)
I believe that the similarity between our two methods (at least at a high level) comes from the latter two operations, whereas the former operation is unique to CFMMs (since they are path-deficient rather than path-independent)
Thanks for the response! Will get back with more comments once I read your paper