Incentivizing Truthful Machine Unlearning via Hierarchical Auditing

1 Introduction

With the rapid commercialization of artificial intelligence (AI), particularly the surge in large language models, machine learning as a service (MLaaS) has become a dominant paradigm for deploying high-value models. In domains such as healthcare, finance, and personalized AI services, MLaaS platforms routinely train AI models on massive volumes of sensitive user data. As regulatory frameworks such as the GDPR and the CCPA increasingly enforce the right to be forgotten, machine unlearning (MU) has emerged as a critical capability for MLaaS [Guo et al., 2025]. It mandates service providers to permanently remove the influence of specific data samples from deployed models upon request.

∗Zhou Su and Yuntao Wang are the corresponding authors.

Although various MU algorithms have been proposed [Lee et al., 2025; Lyu et al., 2025; He et al., 2025; Yang et al., 2025; Li et al., 2025], most existing studies primarily focus on improving computational efficiency and minimizing accuracy degradation. However, algorithmic unlearning does not imply verifiable unlearning. In large-scale MLaaS systems, faithful unlearning often incurs substantial economic costs (e.g., tens to hundreds of GPU hours) and can cause nonnegligible performance loss. This creates strong incentives for profit-driven service providers to claim compliance (i.e., unlearning has been executed) while strategically avoiding costly unlearning operations. Hence, ensuring verifiability of unlearning has become a fundamental prerequisite for establishing trust among users, auditors, and MLaaS providers.

Recent studies have explored verifiable unlearning mechanisms to assess whether requested data has been properly removed, typically by detecting residual information associated with forgotten samples. Existing approaches can be broadly categorized into three classes. Trigger-based methods [Sommer et al., 2022; Guo et al., 2024; Han et al., 2025] inject carefully crafted samples during training and verify unlearning by probing the model's responses to these triggers. However, such methods are fundamentally limited in practice: users generally cannot anticipate which samples will require unlearning after deployment, making it infeasible to pre-embed triggers for targeted data during training [Wang et al., 2025b]. Moreover, trigger injection may degrade model utility and compromise the privacy of unrelated data contributors [Zhang et al., 2024; Xu et al., 2026].

To better align with practical deployments, recent works have shifted towards post-hoc verification approaches compatible with MLaaS. Among them, membership inferencebased methods [Chen et al., 2021; Golatkar et al., 2021; Jia et al., 2023; Kurmanji et al., 2023] assess whether forgotten samples remain distinguishable from unseen data, whereas reconstruction-based methods [Xu et al., 2026; Wang et al., 2025b] quantify behavioral differences before and after unlearning. However, these methods face a fundamental cost-accuracy-security dilemma. High-precision verification techniques can improve detection accuracy but incur prohibitive computational and operational costs if applied frequently. In contrast, lightweight checks are inexpensive yet offer limited deterrence and can be strategically bypassed by a profit-driven service provider. Besides, unlearning verification is inherently strategic, as the server's compliance behavior adapts to the auditor's verification frequency, detection accuracy, and penalty structure. It remains an open challenge to design an efficient unlearning auditing mechanism that balances verification cost, detection effectiveness, and robustness to strategic manipulation.

To bridge this gap, this paper proposes the first practical machine Unlearning Audit Game (UAG) for MLaaS systems, which explicitly models unlearning verification as a strategic interaction between a profit-driven server and a resourceconstrained auditor. By theoretically characterizing equilibrium behavior, UAG provides principled guidance for resolving the cost-accuracy-security dilemma in real-world unlearning scenarios. Specifically, UAG consists of the following two tightly coupled components.

1) Hierarchical Unlearning Audit Game. We model the strategic interaction between the server and the auditor as a three-stage dynamic Bayesian game under incomplete information. The core idea is to integrate scalable, low-cost screening mechanisms (e.g., membership inference attack (MIA)-based test [Jia et al., 2023]) as a first-line audit, with high-precision but expensive verification (e.g., reconstruction-based test [Wang et al., 2025b]) that is selectively triggered upon detecting suspicious signals. This strategic audit structure transforms costly verification from a constant operational burden into a credible probabilistic threat. By embedding heterogeneous audit mechanisms within a unified game-theoretic framework, UAG achieves effective strategic deterrence while preserving audit scalability in practical MLaaS deployments.

2) Equilibrium Analysis and Optimal Strategy Design. Within the UAG framework, we develop an efficient analytical approach to jointly derive equilibrium strategies, including the auditor's optimal audit frequency and the server's optimal compliance probability. Through rigorous equilibrium analysis, we reveal how the auditor should calibrate audit intensity and penalty levels to balance deterrence and operational cost. Specifically, the equilibrium analysis identifies two practically relevant operating regions. In the audit-light equilibrium, sufficiently strong penalties and accurate screening make dishonest unlearning unattractive, allowing the auditor to rely primarily on low-cost screening and trigger highprecision verification only upon alert signals, thereby maintaining low auditing overhead without sacrificing security. In contrast, when penalties are insufficient or screening reliability is too low to deter strategic non-compliance, the system shifts to an audit-intensive equilibrium, in which the auditor should increase the frequency of high-precision audits to incentivize honest unlearning.

We conduct extensive experiments to compare UAG with state-of-the-art schemes, including MIA [Jia et al., 2023] and TAPE [Wang et al., 2025b]. The results show that UAG achieves a favorable cost-deterrence trade-off, maintaining a server honesty rate of around 0.95 with a basic audit probability of around 0.5. UAG also provides higher audit reliability and substantially lower overhead than existing schemes. Overall, our study offers practical insights into designing incentive-compatible unlearning auditing mechanisms with strong security guarantees and controlled operational costs.

2 RelatedWorks

Verifiable MU Approaches. Existing verifiable MU approaches aim to provide evidence that the influence of specific data has been effectively removed from a trained model. Hardware-assisted approaches leverage trusted execution environments to certify unlearning operations [Weng et al., 2024], offering strong correctness guarantees while relying on specialized hardware and facing scalability limitations.

In parallel, a dominant line of work verifies unlearning through attack-based detection. For instance, backdoor-based schemes embed verification triggers during training and assess unlearning by probing model responses [Sommer et al., 2022; Guo et al., 2024; Hu et al., 2022; Han et al., 2025], whereas inference-based approaches evaluate whether the model's predictive confidence on a target sample decays to a level indistinguishable from unseen data [Chen et al., 2021; Golatkar et al., 2021; Jia et al., 2023; Kurmanji et al., 2023]. More recently, reconstruction-based methods quantify unlearning by examining behavioral discrepancies between pre- and post-unlearning models [Xu et al., 2026; Wang et al., 2025b]. However, these approaches either require intrusive modifications to the training pipeline or offer limited deterrence against strategic non-compliance. In contrast, our framework integrates low-cost screening with highprecision verification, achieving effective deterrence without disrupting the model training process.

MechanismDesign forMU. Game-theoretic modeling has recently been introduced to MU to address both internal algorithmic trade-offs and external incentive design. From an algorithmic perspective, prior studies formulate unlearning as a strategic interaction among competing objectives. For example, [Wu and Harandi, 2025] applies Nash bargaining to balance forgetting and model utility, while [Liu et al., 2025] characterizes the trade-off between unlearning effectiveness and privacy leakage to limit additional risks. From an economic perspective, existing studies design incentives to regulate unlearning-related behaviors of servers and users. Representative works employ Stackelberg games to price data retention and reduce unlearning costs [Cui and Cheung, 2025], use contract theory to encourage data contribution through unlearning guarantees [Wang et al., 2025a] or to balance personalized privacy and model utility [Pan et al., 2026], and apply evolutionary games to motivate resource sharing for collaborative retraining [Lin et al., 2024]. Most existing studies implicitly assume faithful execution of unlearning by the server and overlook strategic deviations in practice. In contrast, our work models the server as a strategic player and introduces a Bayesian auditing mechanism to deter noncompliance under incomplete information.

3 Model

As depicted in Fig. 1, we consider an MU setting with three entities: an ML server S, a set of data providers I = {1, . . . , I}, and a third-party auditor A. Each provider i contributes a local dataset Di with size di = |Di|. The server aggregates all datasets D = ⋃i∈I Di to train a global model Ψ and offers prediction services [Wang et al., 2021].

Nota. Description

Table 1: Summary of key notations used.

Unlearning Objective. For privacy or regulatory reasons, each provider i ∈ I may request the removal of a subset Du i ⊆ Di of size dui . Upon receiving unlearning requests, the server is expected to release an unlearned model Ψ∗u that eliminates the influence of the target data while preserving the utility of the remaining data. Ideally, the optimal unlearned model Ψ∗u can be obtained by minimizing the empirical risk on the remaining data [Wang et al., 2024]:

where L(·) denotes a task-specific loss function, D = ∑i di is the total training data size, and Du = ∑i dui represents the total volume requested to be removed.

Server's Action. In practice, obtaining Ψ∗u may require costly retraining and degrade model performance, creating incentives for the server to deviate from honest unlearning. We model the server as a strategic agent choosing an action a ∈ {ah, ac}, where ah denotes faithful unlearning and ac denotes cheating by skipping the unlearning process.

Auditor's Action. The auditor verifies unlearning compliance (i.e., whether the server performs truthful unlearning) under limited resources. High-precision verification ensures reliability but is economically infeasible at scale, whereas lightweight screening is inexpensive yet vulnerable to evasion [Sommer et al., 2022]. To balance audit accuracy and cost, a hierarchical audit mechanism is devised as follows.

Definition 1 (Hierarchical Audit Mechanism). The mechanismM = ⟨Vb, Ve⟩ combines low-cost screening (basic audit) with selectively triggered high-precision verification (extended audit):

1. Basic audit. With probability α ∈ [0, 1], the auditor conducts a lightweight screening Vb, which yields a binary signal s ∈ S = {s0, s1}, corresponding to negative (safe) and positive (alert), respectively. The screening is imperfect and characterized by true positive rate ηb (i.e., Pr(s1|ac)) and false positive rate ϵb (i.e., Pr(s1|ah)). We can instantiate Vb via MIA, which provides fast and non-intrusive statistical evidence of whether the removed data still influences the model. While efficient, such tests are inherently noisy and cannot provide definitive guarantees [Sommer et al., 2022].
2. ii) Extended audit. Conditioned on signal s, the auditor may escalate to Ve following a signal-dependent strategy Γ = {γ0, γ1}, where γj = Pr(Ve|sj) for j ∈ {0, 1}. Compared with basic screening, extended audits are more expensive but provide near-definitive outcomes, characterized by a higher true positive rate ηe > ηb and a lower false positive rate ϵe < ϵb. The audit Ve outputs a verdict v ∈ {vp, vf}, corresponding to pass or fail. The extended audit can be instantiated using a high-precision verification method, such as TAPE [Wang et al., 2025b], which reconstructs residual information from model posterior differences to assess whether the requested data has been effectively removed.

Consequently, the auditing process terminates in one of four outcomes V = {v∅, vt, vp, vf}: no audit, termination after screening, passing the extended audit, or failing the extended audit with a fine.

4 Unlearning Audit Game

4.1 Motivation and Game Overview

The interaction between the server and the auditor is inherently strategic under information asymmetry. The server holds private knowledge of its unlearning execution status and may bypass costly unlearning when the perceived audit risk is low. In contrast, the auditor aims to enforce compliance while controlling verification costs.

Game Process. We model this strategic interaction as a multi-stage dynamic Bayesian game. As illustrated in Fig. 2, the game proceeds in three stages. First, the server chooses its execution strategy, deciding whether to perform honest unlearning or to cheat. Second, the auditor decides whether to perform a basic audit, which yields a preliminary verification signal. Third, after observing the signal, the auditor updates its belief and decides whether to escalate to an extended audit. By analyzing this game, we characterize the optimal responses of both parties and derive the auditor's optimal audit policy, including the audit frequency and escalation rule, to effectively deter server cheating.

Definition 2 (Unlearning Audit Game (UAG)). The strategic interaction is formally modeled as a dynamic Bayesian game G = ⟨N , Φ, U⟩, characterized by:

• Players (N): The player set is N = {S,A}, representing the server and auditor, respectively.
• Strategy spaces (Φ): i) The server's strategy ϕS is parameterized by the honesty probability x, defined as

Pr(a = ah). ii) The auditor's strategy is a tuple ϕA = (α, Γ), comprising the basic screening probability α and extended audit probabilities Γ = {γ0, γ1}.

• Payoffs (U): The utilities of the server and the auditor are denoted by US and UA, respectively, and their expected utilities are denoted by US and UA.

4.2 Server's Utility

The server aims to maximize the residual utility of the deployed model while minimizing unlearning cost and potential penalties. Its utility is defined as

i) Residual model utility. Honest unlearning typically induces a non-linear degradation in model accuracy [Cui and Cheung, 2025; Jiao et al., 2021]. To capture this, we model the residual utility Vres using an exponential decay form:

where δ converts model performance into economic utility, and A1,A2,A3, z are curve-fitting constants obtained from empirical findings [Cui and Cheung, 2025].

ii) Unlearning execution cost. Honest execution incurs computational costs (e.g., retraining time), typically linear in the remaining data size [Bourtoule et al., 2021; Chen et al., 2021; Warnecke et al., 2023]:

where c0 denotes unit computational cost [Wang et al., 2022]. iii) Conviction penalty. If convicted, the server pays a fixed

fine, expressed asΦpen(v) = I(v = vf )Vpen.

4.3 Auditor's Utility

The auditor aims to deter cheating while controlling audit costs and decision risks (including both false negatives and false positives). Its utility is given by

i) Conviction revenue. Upon issuing the conviction verdict vf , the auditor receives penalty revenue Φpen (cf. Eq. (4)).

ii) Hierarchical audit cost. The operational cost depends on audit depth. Let cb and ce denote the costs of basic and extended verification (ce > cb), respectively, we have

iii) Error loss. The auditor incurs a loss for incorrect decisions. We quantify the risks of failing to penalize a cheating server incurs λfn, while wrongfully convicting an honest server incurs λfp, and is given by:

We assume λfp > Vpen to discourage wrongful convictions.

5 EquilibriumAnalysis

The analysis proceeds as follows: we first characterize the auditor's belief update (Sec. 5.1) and optimal extended audit policy in Stage III (Sec. 5.2), which partition the game into three regions. Then, we derive the equilibrium strategies for both players within each region (Secs. 5.3-5.5) and present an equilibrium strategy derivation algorithm in Sec. 5.6.

5.1 Posterior Belief Update

In Stage III, the auditor observes a realization of the screening signal s ∈ S and updates its belief about the server's compliance according to Bayes' rule. Let µ(s) ≜ Pr(ac|s) denote the posterior belief that the server has cheated. Specifically, when the screening returns an alert signal s1, the auditor derives the posterior suspicion as

Similarly, upon observing s0, the posterior belief is

Given that the basic audit is informative (i.e., ηb > ϵb) [Sommer et al., 2022], an alert signal induces a higher posterior suspicion than a safe signal. Consequently, the monotonicity property µ(s1) > µ(s0) holds for any x.

5.2 Optimal Extended Audit Policy

In Stage III, after observing s, the auditor applies the escalation strategy Γ = {γ0, γ1} to decide whether to trigger the extended audit. We first derive the critical belief threshold that governs this escalation decision.

Lemma 1 (Investigation Threshold). There exists a critical belief τ ∗ such that the auditor escalates to an extended audit (γ ∗ = 1) if the posterior suspicion µ(s) > τ ∗ , terminates the audit if µ(s) < τ ∗ , and is indifferent when µ(s) = τ ∗ . This threshold is given by

Remark: All proofs are provided in the online appendix [Guo et al., 2026a]; see Appendix 1 for the proof of Lemma 1. Intuitively, τ ∗ is the break-even belief at which the auditor's expected gain from detecting a violation balances the cost of the extended audit and the risk of wrongful conviction.

While τ ∗ is defined in the belief space, the server controls the strategy space via the honesty parameter x. Since µ(s) is strictly decreasing in x, we can translate τ ∗ into thresholds over x by inverting the Bayesian update functions in Eqs. (6)- (7). The resulting thresholds divide the server's strategy space into regions with different optimal escalation decisions.

Definition 3 (Strategy-Space Boundaries). The server's strategy space x ∈ [0, 1] is divided by two critical honesty probabilities, ˆxsafe and ˆxalert, derived by inverting the Bayesian belief functions at µ = τ ∗ :

1. High Suspicion Boundary (ˆxsafe): The honesty probability below which even a safe signal s0 fails to reduce suspicion below τ ∗ . Solving µ(s0) = τ ∗ yields:

1. High Trust Boundary (ˆxalert): The honesty probability above which even an alert signal s1 is insufficient to raise suspicion above τ ∗ . Solving µ(s1) = τ ∗ yields:

Given ηb > ϵb, we have ˆxsafe < ˆxalert. These boundaries define three extended audit regions, as shown in Table 2:

• Region I (Indiscriminate escalation): When x < ˆxsafe, the prior trust is so low that the auditor escalates regardless of the screening outcome, i.e., Γ∗ = (1, 1).
• Region II (Conditional escalation): When ˆxsafe < x < ˆxalert, the auditor relies on the screening signal and escalates only after an alert, i.e., Γ∗ = (0, 1).
• Region III (High trust): When x > ˆxalert, the cost of verification outweighs the perceived risk, leading to no escalation, i.e., Γ∗ = (0, 0).

5.3 EquilibriumAnalysis in Region I

Region I is a high-suspicion region, where the auditor's posterior belief always exceeds the investigation threshold. Thus, the auditor executes the extended audit regardless of the screening outcome. The resulting mixed-strategy equilibrium is characterized as follows [Guo et al., 2026b; Barron, 2024].

Theorem 1 (Audit-Intensive Equilibrium). Under the Region I escalation policy ΓI = (1, 1), the candidate strategy profile is ΩI = (x∗I , α∗ I , ΓI), where

Here, Du = ∑i∈I dui and Drem = ∑i∈I (di - dui ). If 0 ≤ x∗I < ˆxsafe and 0 ≤ α∗ I ≤ 1, then ΩI constitutes a feasible mixed-strategy equilibrium in Region I.

Remark: The proof of Theorem 1 is given in Appendix 2. In Region I, any execution of the basic audit always leads to the extended audit, regardless of the screening outcome. Consequently, the auditor's strategic decision reduces to how frequently to conduct a basic audit. The equilibrium reveals two key observations: i) lower auditing costs (cb and ce) increase the server's equilibriumhonesty probability (higher x∗ ). ii) A larger conviction penalty increases the expected loss from being caught, which allows the auditor to inspect less frequently (lower α∗ ) while preserving deterrence.

5.4 EquilibriumAnalysis in Region II

In Region II, an alert signal raises the posterior belief above the threshold and triggers escalation (γ ∗ 1 = 1), while a safe signal suppresses escalation (γ ∗ 0 = 0). Next, we characterize the equilibrium within this region in Theorem 2.

Theorem 2 (Audit-Light Equilibrium). Under the Region II escalation policy ΓII = (0, 1), the candidate strategy profile is ΩII = (x∗II , α∗ II , ΓII), where

If ˆxsafe < x∗II < ˆxalert and 0 ≤ α∗ II ≤ 1, then ΩII constitutes a feasible mixed-strategy equilibrium in Region II.

Remark: Theorem 2 is proved in Appendix 3. Region II characterizes the most effective operating regime of UAG. Here, the basic audit acts as a risk filter: alert signals trigger escalation, whereas safe signals terminate the audit. Instead of applying costly extended audits indiscriminately, the auditor escalates only when there is sufficient suspicion of noncompliance. This signal-dependent escalation makes screening quality crucial: improving screening accuracy enables the auditor to reduce the inspection frequency α∗ while inducing a higher server honesty probability x∗ .

5.5 EquilibriumAnalysis in Region III

In Region III, even an alert signal fails to raise suspicion above τ ∗ , yielding a policy of zero escalation. However, we prove that no stable equilibrium exists in this region.

Proposition 1 (Non-Existence of Equilibrium in Region III). In Region III, no equilibrium can be sustained as the auditor's escalation threat is not credible.

Algorithm 1 Equilibrium Characterization Algorithm

1: Input: c0, cb, ce, z, Vpen, λfn, λfp, ηb, ϵb, ηe, ϵe, A1, A2, A3, Du, Drem, δ. 2: Output: Equilibrium strategy set E ∗ . 3: Compute Gu ← c0Drem + δ(A1zA2Du - A3). 4: Compute the investigation threshold: 5: τ ∗ ← ce+ϵe(λfp-Vpen) ηe(Vpen+λfn)+ϵe(λfp-Vpen) . 6: Compute the strategic boundaries: 7: ˆxsafe ← (1-ηb)(1-τ ∗ ) (1-ηb)(1-τ∗)+(1-ϵb)τ∗ ; 8: ˆxalert ← ηb(1-τ ∗ ) ηb(1-τ∗)+ϵbτ∗ . 9: Initialize E ∗ ← ∅. 10: Region I candidate equilibrium: 11: xI ← ηe(Vpen+λfn)-(cb+ce) ηe(Vpen+λfn)+ϵe(λfp-Vpen) ; 12: αI ← Gu Vpen(ηe-ϵe) . 13: if 0 ≤ xI < ˆxsafe and 0 ≤ αI ≤ 1 then 14: Add ΩI = (xI, αI, (1, 1)) to E ∗ . 15: end if 16: Region II candidate equilibrium: 17: xII ← ηb[ηe(Vpen+λfn)-ce]-cb ηb[ηe(Vpen+λfn)-ce]+ϵb[ce+ϵe(λfp-Vpen)] ; 18: αII ← Gu Vpen(ηbηe-ϵbϵe) . 19: if ˆxsafe < xII < ˆxalert and 0 ≤ αII ≤ 1 then 20: Add ΩII = (xII, αII, (0, 1)) to E ∗ . 21: end if 22: if E ∗ = ∅ then 23: Return NOFEASIBLEEQUILIBRIUM. 24: else 25: Return E ∗ . 26: end if

Remark: Proposition 1 is proved in Appendix 4. In a hightrust region, auditing appears economically irrational, as the expected benefit no longer offsets the audit cost, rendering the audit threat non-credible. However, once this auditing threat is removed, a rational server has an incentive to deviate to cheating to avoid the unlearning cost. Consequently, sustained compliance cannot be supported without a credible audit threat, causing the mechanism to collapse.

5.6 EquilibriumCharacterization Algorithm

Based on the above equilibrium analysis, we develop the algorithm 1 for deriving equilibrium strategies. The algorithm first computes the investigation threshold τ ∗ and the honesty boundaries ˆxsafe and ˆxalert. It then evaluates the candidate equilibria for Regions I and II separately, retaining only those that satisfy the corresponding feasibility conditions. The algorithm returns the resulting set of feasible equilibrium strategies E ∗ ; if no candidate is feasible, it returns NOFEASIBLEEQUILIBRIUM.

6 Performance Evaluation

6.1 Experiment Setup

Models, Datasets & Settings. Our framework is evaluated on the CIFAR-10 dataset [Krizhevsky and others, 2009] using a ResNet-18 architecture. We consider a representative unlearning scenario with 100 data providers, with the training data uniformly distributed among them. To examine the impact of different unlearning intensities, the unlearning request size is varied within [1, 300]. The model accuracy degradation due to unlearning in Eq. (3) is modeled using an exponential decay function [Cui and Cheung, 2025] fitted from empirical results on a standard unlearning benchmark (i.e., SISA [Bourtoule et al., 2021]), with parameters A1 = 10, A2 = 0.01, and A3 = 5. The default conviction penalty is set to 400, while the liabilities for false negatives and false positives are set to 600 and 800, respectively.

ComparativeMethods. We compare UAGwith two representative auditing approaches. (i) Inference-based (MIA [Jia et al., 2023]): an efficient method that infers data membership by analyzing the confidence gap in the model's prediction outputs between training and non-training samples. (ii) Reconstruction-based (TAPE [Wang et al., 2025b]): a highprecision audit approach by quantifying the posterior difference of model parameters to detect traces of erased data.

Evaluation Metrics. We evaluate system performance using five metrics: (i) auditor utility (UA) and (ii) server utility (US), which measure the expected payoffs of both players; (iii) honesty ratio (x∗ ), defined as the equilibrium probability of the server faithfully executing the unlearning request; (iv) audit reliability, measured as the ratio of true positives to all positive audit outcomes. It indicates the trustworthiness of enforcement, representing the probability that a penalized server is indeed guilty; and (v) cost-effectiveness ratio, defined as the detection effectiveness normalized by the total operational and risk costs. Specifically, it captures howmuch effective deterrence is achieved per unit cost, accounting for both audit expenses and losses caused by misclassification.

6.2 Experimental Results

Analysis of Equilibrium Strategies. We first show that UAG induces a cost-effective equilibrium, enabling the auditor to maintain high server honesty with low audit frequency. Fig. 3 visualizes the joint impact of unlearning data size du and conviction penalty Vpen on the equilibrium strategies in Region II. As observed in Fig. 3 (a), the basic audit probability α∗ adapts to the honesty probability. Specifically, as du increases, the server has stronger incentives to cheat, requiring a higher α∗ to maintain deterrence. Conversely, increasing the penalty allows the auditor to reduce α∗ , as stronger penalties substitute for frequent checks. Correspondingly, Fig. 3 (b) shows that UAG maintains robust compliance

(above 0.9) across most of the parameter space. Notably, under a moderate penalty (e.g., 300), an audit frequency of 0.5 suffices to enforce an honesty ratio close to 95%, demonstrating strong deterrence with limited auditing effort.

Impact of Conviction Penalty. UAG achieves strong deterrence under lower penalties while yielding higher utilities than baselines. Fig. 4 illustrates the system performance as the conviction penalty Vpen increases. 1) Higher utilities & effective deterrence: Fig. 4 (a) and (b) show that UAG consistently outperforms MIA and TAPE in terms of payoffs. For the auditor, UAG avoids the high cost of always invoking the extended audit while mitigating the revenue loss from missed detections under MIA. For the server, utility remains high and stable because UAG reduces the risk of wrongful punishment via reliable verification. Consequently, as shown in Fig. 4 (c), UAG achieves a robust honesty ratio (above 0.96) with much lower penalties, whereas baselines require significantly harsher fines to induce comparable compliance. 2) Superior reliability & cost-effectiveness: Fig. 4 (d) and (e) further highlight the operational advantages of UAG. Notably, in Fig. 4 (d), the reliability of MIA decreases as the penalty increases. This is because higher penalties increase the server's honesty, making actual cheating rare. Under such conditions, MIA's false alarms can dominate the few true detections, causing many penalized servers to be innocent. In contrast, UAG adopts a "screen-and-verify" design, where the basic audit flags suspicious cases and the extended audit confirms them. This two-stage verification effectively reduces wrongful punishment and maintains near-perfect audit reliability. Furthermore, Fig. 4 (e) shows that UAG achieves the highest cost-effectiveness ratio by reserving the expensive extended audit for only a small number of flagged cases, thereby providing TAPE-level reliability at a much lower cost.

Impact on Unlearning Data Size. UAGmaintains stable audit performance and high server honesty even as the unlearning workload increases. Fig. 5 reports the system performance as unlearning request size du increases from 10 to 300. 1) Stable auditing performance: As shown in Fig. 5 (a), (d), and (e), the auditor's utility, audit reliability, and efficiency remain invariant as du grows. It indicates that the auditing overhead in UAG is largely insensitive to the erased data size, consistent with TAPE, whose audit cost is dominated by the size of the user's local data rather than the volume of unlearned data. 2) Robust compliance incentives: Fig. 5(b) shows that the server's utility decreases with du due to the increasing unlearning burden, yet UAG consistently achieves higher utility than the baselines. More importantly, Fig. 5 (c) shows the server's honesty ratio remains high and stable under UAG, demonstrating that UAG continues to incentivize honest unlearning even under heavy workloads.

7 Conclusion

In this paper, we address the key problem of enforcing truthful unlearning in MLaaS systems, where profit-driven servers may strategically misreport compliance. We propose UAG, a game-theoretic auditing framework that replaces exhaustive verification with strategic deterrence. To reduce auditing overhead, UAG adopts a hierarchical auditing mechanism that integrates low-cost screening with selectively triggered high-precision verification, and models the interaction between the auditor and the server as a dynamic Bayesian game. Through rigorous equilibrium analysis, we derive optimal auditing and compliance strategies that guide server behavior and deter deceptive unlearning. Extensive experiments demonstrate that UAG significantly reduces auditing overhead while maintaining a high level of server honesty.

Acknowledgments

This work was supported in part by NSFC (Nos. U24A20237, U22A2029, 62302387, U23A20276) and the Youth Innovation Team of Shaanxi Universities.