**Our upper bounding function has to include $c_i, \epsilon$ and $\delta$, where $c_i$ is the privacy cost coefficient.**
| **Paper** | **Upper Bounding Function** | **Data Assumption** | **Privacy Guarantee** |
|-----------|--------------------------------------|---------------------|-------------------------------|
| Ours | $c_i(1+\delta) \epsilon^3 $ | Sub-Gaussian | $(\epsilon, \delta)$-JDP |
| [1] |$ c_i(1+\gamma) \epsilon^4 $ | Sub-Gaussian | $(\epsilon, \gamma)$-RJDP |
| [1] |$ c_i(1+\gamma) \epsilon^9 $ | Heavy-tailed | $(\epsilon, \gamma)$-RJDP |
| [2] | $ c_i \epsilon^2 $ | Bounded |$ \epsilon$-JDP |
It is clear that due to different data settings, our assumption is weaker than that of [1] but is stronger than the assumption in [2] which was first introduced by [3] and later adopted by [4].
To see why the upper bounding function in [2] is quadratic in $\epsilon$, we additionally define $g_i$ as the privacy cost for reporting $(x_i
, y_i)$ to the mechanism $M$ when all other agents report $(X_{-i}, y_{−i})$ and the output is $\hat{\theta}$.
In [3], the authors assume that
$g_i\left(M, \hat{\theta},\left(x_i, y_i\right),\left(X_{-i}, y_{-i}\right)\right) \leq c_i \ln \left(\max_{y_i^{\prime}, y_i^{\prime \prime}} \frac{\operatorname{Pr}\left[M\left(X, y_i^{\prime}, y_{-i}\right)=\hat{\theta}\right]}{\operatorname{Pr}\left[M\left(X, y_i^{\prime \prime}, y_{-i}\right)=\hat{\theta}\right]}\right)$.
This assumption is natural because if $g_i$ is small if the agent $i$'s report exerts little influence on $\hat{\theta}$ and therefore should be upper bounded by a function that depends on the effect that the agent $i$’s report has on the mechanism’s output.
And by Composition Lemma (Lemma 3.2 in [3]),
$\mathbb{E}\left[g_i\left(M, M(X, y),\left(x_i, y_i\right),\left(X_{-i}, y_{-i}\right)\right)\right]-\mathbb{E}\left[g_i\left(M, M\left(X, y_i^{\prime}, y_{-i}\right),\left(x_i, y_i\right),\left(X_{-i}, y_{-i}\right)\right)\right] \leq 2 c_i \epsilon\left(e^\epsilon-1\right) \leq 4 c_i \epsilon^2$
Therefore by setting the privacy cost function $f_i = \frac{1}{4} \mathbb{E}\left[g_i\left(M, M(X, y),\left(x_i, y_i\right),\left(X_{-i}, y_{-i}\right)\right)\right]$, it can be interpreted as the agent $i$’s expected cost for participating in the mechanism up to a scaling constant.
Given that our assumption regarding $f_i$ stems from natural ground and has been used widely in similar settings, we argue that it is a reasonable assumption.
[1] Qiu, Yuan, Jinyan Liu, and Di Wang. "Truthful Generalized Linear Models." arXiv preprint arXiv:2209.07815 (2022).
[2] Cummings, Rachel, Stratis Ioannidis, and Katrina Ligett. "Truthful linear regression." Conference on Learning Theory. PMLR, 2015.
[3] Chen, Yiling, et al. "Truthful mechanisms for agents that value privacy." ACM Transactions on Economics and Computation (TEAC) 4.3 (2016): 1-30.
[4] Ghosh, Arpita, et al. "Buying private data without verification." Proceedings of the fifteenth ACM conference on Economics and computation. 2014.