A game-theoretic framework for data privacy
Sender’s sensitive data, held privately and never shared.
x \in \mathsf{X}
A (deterministic or randomised) mechanism.
M: (\mathsf{X}, \mathcal{T}) \rightarrow [0,1]
Markov kernel w.r.t. measurable space (\mathsf{T}, \mathcal{T}).
Generated from mechanism and shared with Receiver.
T \sim M(x, \cdot)
Shared with Receiver for transparency, so that the privacy of M can be verified externally.
Assumption 1 dictates that the privacy guarantee can not depend on x directly. This prevents information leakage about the data through transparency. As such, communication of the guarantee to Receiver does not affect the data-posterior.
The privacy function encodes how Receiver’s decision affect the privacy of Sender.
Under the data-posterior Q_T, with Receiver’s optimal decision d^{Q_T}, the realised privacy for Sender is
\rho(d^{Q_T},x).
The receiver’s assumed prior over the data is
Q \in \mathcal{P}(\mathsf{X}).
In Assumption 5 we have a class of prior distributions \mathcal{Q}_x \subset \mathcal{P}(\mathsf{X}) for which Q \in \mathcal{Q}_x and Sender assesses the worst case.
Receiver’s posterior given the release of T is
Q_T = Q(\,\cdot \mid T), which will depend on the chosen mechanism M.
By Assumption 1, Q_T does not depend on \mathfrak{C}.
Receiver’s decision is formed by posterior Q_T and loss \ell.
d^{Q_T} \in \arg\inf_{d \in \mathcal{D}} \mathbb{E}_{z \sim Q_T}[ \ell(d,z)]
Assumption 3 dictates that \ell = \rho.
Receiver’s loss function for decision making.
Assumption 3 dictates that \ell = \rho. In other words, Receiver directly targets Sender’s notion of privacy.
Custodian of sensitive data x. Chooses M to persuade Receiver to make decisions with limited impact on privacy.
Sender conducts a robust assessment of privacy. These are formalised in Assumption 4 and Assumption 5.
Receiver is a potential adversary who will make a decision after observing output T \sim M(x,\cdot).
Receiver is Bayes rational by Assumption 2. Therefore, they hold a prior Q over (unknown) data x, and make decisions with respect to some loss function \ell.
Joshua J. Bon1, James Bailie2, Judith Rousseau3, Christian P. Robert4 5
Forty-Third International Conference on Machine Learning (ICML 2026)
We propose a two-player Stackelberg game between a Sender (custodian of the sensitive data) and a Receiver (adversary) to construct a new class of privacy definitions. The construction is closely related to Bayesian persuasion (Kamenica et al., 2011), but differs in three key ways: information asymmetry, related utility functions, and semi-robustness.
We assess the privacy of a mechanism M, a Markov kernel with output T \sim M(x,\cdot), where M(x,\cdot) is a distribution on (\mathsf{T},\mathcal{T}) for the Sender’s private data x \in \mathsf{X}.
Sender chooses M to persuade Receiver to make decisions with limited privacy impact.
Example players
A government agency releases small area statistics on a disease.
An insurance company raises premiums using inferred disease prevalence in a small town.
Differential privacy [DP; Dwork et al. (2006)] and its variants (Desfontaines et al., 2020) are the de facto standard, but face persistent challenges — hard-to-interpret parameters (Cummings et al., 2023) and large, potentially vacuous, privacy budgets in practice. We develop a framework to:
Unlike DP, whose semantic interpretations are constructed post-hoc, our agent-based game is a semantics-first approach where each assumption can be tested against real-world considerations. Moreover, deterministic algorithms are incompatible with DP, yet central to releasing invariant statistics (e.g. the US Decennial Census) (Abowd et al., 2022).
Sender measures privacy with a privacy function \rho, depending on Receiver’s decision d \in \mathcal{D} and the data value x \in \mathsf{X},
\rho: (\mathcal{D},\mathsf{X}) \rightarrow \mathbb{R}.
The privacy function orders Sender’s preferences over Receiver’s decisions: if Sender prefers d_1 to d_2 given x, then \rho(d_1,x) > \rho(d_2,x). That is, \rho is positively oriented.
Let \mathcal{D} = \{[a,b]: a,b \in \mathbb{R}, a \leq b\} and \mathsf{X}=\mathbb{R}. Given s > 0,
\rho(d,x) = \begin{cases} 0 & \text{if } x\in d \text{ and } \vert d \vert \leq s,\\ 1 & \text{otherwise}. \end{cases}
Let \mathcal{D} be the set of probability density functions on \mathsf{X}=\mathbb{R} with respect to some measure \mu. For d \in \mathcal{D} and x \in \mathsf{X}, the negative log-probability privacy function is \rho(d,x) = -\log d(x).
Transparency is typically required so that the privacy status of M can be externally verified. Sharing some (yet to be specified) privacy definition \mathrm{D} is equivalent to sharing \mathfrak{C} = \{\text{Markov kernels}~M~\text{satisfying}~\mathrm{D}\}.
Sender shares the mechanism M and privacy class \mathfrak{C}, for which M \in \mathfrak{C}, with Receiver. Further, the definitions of M and \mathfrak{C} do not depend on the data.
Receiver is Bayes rational.
Under Assumption 2, Receiver will hold a data-prior Q expressing their uncertainty about the true value of x. They will also make decisions with respect to some loss function \ell.
Under the data-prior, Receiver’s best response is
d^{Q} \in \arg\inf_{d \in \mathcal{D}} \mathbb{E}_{z\sim Q}\left[ \ell(d,z) \right].
After observing T \sim M(x,\cdot), Receiver forms the data-posterior Q_T = Q(\,\cdot \mid T) and their best response is
d^{Q_T} \in \arg\inf_{d \in \mathcal{D}} \mathbb{E}_{z\sim Q_T}\left[ \ell(d,z) \right].
The following assumption, links Sender’s privacy function and Receiver’s loss.
Receiver’s loss function satisfies \ell(d,x) = \rho(d,x) for all d \in \mathcal{D} and x \in \mathsf{X}.
Setting Receiver’s loss as \ell = \rho can be interpreted as the data-averaged worst case privacy outcome for Sender (see Proposition 1 in paper).
Sender’s attained privacy is \rho(d^{Q_T}, x), conditional on output T, data-prior Q, and the true value x. When \ell = \rho (from Assumption 3), the attained privacy is a (negatively-oriented) proper scoring rule (Gneiting et al., 2007; Grünwald et al., 2004),
S(P,x) = \rho(d^{P}, x),
measuring how well Receiver’s belief P predicts x. We use privacy scores due to this equivalence. Privacy attained under the data-prior and data-posterior are S(Q,x) and S(Q_T,x) respectively.
In our framework privacy functions naturally lead to privacy scores (proper scoring rules). Further, a proper scoring rule will always have a dual privacy function. Therefore, designing a privacy score or a privacy function are both appropriate strategies.
We continue with privacy score perspective for simplicity.
Sender must assess privacy with respect to (possible) stochasticity in T, potential data-priors Q \in \mathcal{Q}_x held by Receiver, and all potential datasets x \in \mathsf{X} (due to Assumption 1). We use two robust assessment assumptions for Sender, though others are possible.
The relative privacy loss is defined as
\Delta(Q,T,x) = S(Q,x) - S(Q_T,x), measuring the change in privacy score from the data-prior Q to data-posterior Q_T.
For a given data-prior Q and dataset x, Sender considers a mechanism M private only if
\mathbb{P}_x\left[\Delta(Q,T,x) \leq \kappa \right] \geq 1 - \delta, \tag{1}
with \Delta(Q,T,x) = S(Q,x) - S(Q_T,x), for some maximum acceptable privacy loss \kappa\geq0 and probability of failure 0 \leq \delta \ll 1. The probability \mathbb{P}_x is with respect to M(x,\cdot).
Sender considers M private if (1) holds uniformly for all data-priors Q \in \mathcal{Q}_x and datasets x \in \mathsf{X}.
Fix a non-empty set of privacy scores \mathcal{S} on \mathsf{X}, a class of data-priors \mathcal{Q}_x \subset \mathcal{P}(\mathsf{X}), a maximum acceptable privacy loss \kappa \geq 0, and a small probability of failure 0\leq\delta \ll 1.
Assumptions 1, 2, 3, 4, 5 define Persuasive Privacy as follows.
A mechanism M is (\mathcal{S}, \mathcal{Q}_x, \kappa, \delta)\text{-PP} if
\inf_{S\in\mathcal{S}}\;\inf_{x\in\mathsf{X}}\;\inf_{Q\in\mathcal{Q}_x} \mathbb{P}_x\!\left[\Delta_S(Q,T,x) \leq \kappa \right] \geq 1 - \delta,
for \Delta_S(Q,T,x) = S(Q,x) - S(Q_{T},x).
Multiple scoring rules (equivalent to multiple privacy functions) are allowed by considering all S\in \mathcal{S}.
Probabilistic DP [PDP; Machanavajjhala et al. (2008)] is exactly recovered. Let L be the (discrete) negative log-probability score and \mathcal{H} the class of two-point neighbouring alternative hypothesis data-priors, \mathcal{H} = \{Q : \exists\, (x,x^\prime)\in\mathfrak{N},\ Q(\{x,x^\prime\})=1\}, for some neighbour relation \mathfrak{N}. Then
M~\text{is}~(\varepsilon,\delta)\text{-PDP} \quad\Longleftrightarrow\quad M~\text{is}~(L,\mathcal{H},\varepsilon,\delta)\text{-PP}.
Since pure \varepsilon-DP is a special case of PDP when \delta=0, we also recover \varepsilon-DP.
Changing Assumption 4 from a tail-probability condition to an expected-value condition instead recovers Rényi DP (Mironov, 2017) under otherwise identical settings. See Appendix C in the paper.
Our framework enables separation of two properties conflated as “post-processing”:
PDP does not satisfy (Sender) post-processing (Kifer et al., 2012). Distinguishing Receiver/Sender post-processing reveals this is not a drawback for the adversarial protections afforded by PDP, but rather a restriction of (Sender) post-processing as a mathematical tool for establishing a PDP guarantee.
Let \mathsf{X} = \mathbb{R}^n where x_i is a sensitive value for each individual in the dataset. Consider the marginal Dawid–Sebastiani score (Dawid et al., 1999) for each i\in [1:n],
D_i(Q,x) = \log \sigma_i^2(Q) + \frac{[x_i - \mu_i(Q)]^2}{\sigma^{2}_i(Q)},
where \mu_i(Q) = \mathbb{E}_{X\sim Q}[X_i] and \sigma_i^2(Q) = \mathrm{Var}_{X\sim Q}[X_i], the ith marginal mean and variance of Q. Define the data-prior class
\mathcal{G}_x^r =\left\{ \mathcal{N}(\mu,\Sigma)\in \mathcal{P}(\mathbb{R}^n): \frac{(\bar{x}-\bar{\mu})^2}{\overline{\Sigma}} \leq r_1,\; c_\Phi \leq r_2 \left(1-\frac{\max_i\sigma_i^2}{\Vert\sigma\Vert_2^2}\right)\right\},
bounding Receiver’s strength via mean and correlation-variance constraints, where c_\Phi is the condition number of the correlation matrix of \Sigma and \sigma^2 = \text{diag}(\Sigma). Denoting \mathcal{I} = \{D_i\}_{i=1}^n,
M(x,\cdot) = \delta_{\bar{x}}~\text{is}~(\mathcal{I},\,\mathcal{G}_x^r,\,r_1 + \log r_2,\,0)\text{-PP}.
Interpretation: releasing the average with no noise is private if Receiver’s prior guess for \bar{x} is not too poor, no single marginal prior variance dominates, and the data-prior is not too correlated.