The Price of Ignorance: Information-Free Quotation for Data Retention in Machine Unlearning
Authors: Bin Han, Di Feng, Zexin Fang, Jie Wang, Hans D. Schotten
Organizations: RPTU University Kaiserslautern-Landau, Germany · Dongbei University of Finance and Economics, China · Tongji University, China · German Research Center for Artificial Intelligence (DFKI), Germany
When users exercise data deletion rights under the General Data Protection Regulation (GDPR) and similar regulations, mobile network operators face a tradeoff: excessive machine unlearning degrades model accuracy and incurs retraining costs, yet existing pricing mechanisms for data retention require the server to know every user's private privacy and accuracy preferences, which is infeasible under the very regulations that motivate unlearning. We ask: what is the welfare cost of operating without this private information? We design an information-free ascending quotation mechanism where the server broadcasts progressively higher prices and users self-select their data supply, requiring no knowledge of users' parameters. Under complete information, the protocol admits a unique subgame-perfect Nash equilibrium characterized by single-period selling. We formalize the Price of Ignorance -- the welfare gap between optimal personalized pricing (which knows everything) and our information-free quotation (which knows nothing) -- and prove a three-regime efficiency ordering. Numerical evaluation across seven mechanisms and 5000 Monte Carlo runs shows that this price is near zero: the information-free mechanism achieves >=99% of the welfare of its information-intensive benchmarks, while providing noise-robust guarantees and comparable fairness.
Figures & tables
Fig. 1 : Different cases of the server’s cost function.
Parameter
Value
Remark
I
10
Number of users
di,∀i∈I
6000
Data amount per user
λi,∀i∈I
∼U(0.5,30)
Privacy valuation
θi,∀i∈I
∼U(0,5)
Accuracy sensitivity
ki,∀i∈I
1.0
Privacy elasticity
Δd
1
Unit data amount
TABLE I : Simulation Setup
Major-first
Minor-first
Prop.
Rand.
Server’s payoff
684.8
683.6
684.1
684.9
Users’ payoff
1133.5
1158.2
1150.2
1134.0
Social welfare
1818.4
1841.8
1834.3
1818.9
TABLE II : Comparing the oversupply-handling strategies
Fig. 2 : Privacy-only welfare comparison across mechanisms
Fig. 3 : Accuracy-aware welfare comparison ( θi∼U(0,5) ). The accuracy externality reduces welfare across all mechanisms.
Regime
OPP
CIQ
IIQ
IIQ/OPP
Under-supply (fill ≈66% )
1968
1981
1977
1.00
Over-supply (fill ≈89% )
7581
7619
4604
0.61
TABLE III : Social welfare across supply regimes (accuracy-aware).
Fig. 4 : Robustness: OPP welfare degrades with estimation noise σ , while IIQ remains constant (green dashed line, with ±1σ band).
Fig. 5 : Sensitivity of social welfare to key parameters. Each panel sweeps one parameter while holding others at defaults.
Fig. 6 : Left: Fairness-efficiency tradeoff across mechanisms. Right: Free-rider characterization—mean supply fraction by accuracy sensitivity level.
Fig. 7 : Convergence analysis. (a) Price increments to termination vs. ΔB (log-log; dashed: O(1/ΔB) reference). (b) Price increments vs. number of users I .
Property
OPP
CIQ
IIQ
Private params. required by server
Yes
No
No
Strategic reasoning required by users
No
Yes
No
Implementable in practice
No
No
Yes
Welfare at ρ=1 (acc.-aware)
1968
1981
1977
Robust to estimation noise
No
N/A
Yes
Ex post individually rational
Yes
Yes
Yes
TABLE IV : Practical comparison of the three regimes.
Privacy protection laws, such as the GDPR, grant individuals the right to request the forgetting of their personal data not only from databases but also from machine learning (ML) models trained on them. Machine unlearning has emerged as a practical means to facilitate model forgetting of data instances seen during training. Although some existing machine unlearning methods guarantee exact forgetting, they are typically costly in computational terms. On the other hand, more affordable methods do not offer forgetting guarantees and are applicable only to specific ML models. In this paper, we present efficient unlearning with privacy guarantees (EUPG), a novel machine unlearning framework that offers formal privacy guarantees to individuals whose data are being unlearned. EUPG involves pre-training ML models on data protected using privacy models, and it enables {\em efficient unlearning with the privacy guarantees offered by the privacy models in use}. Through empirical evaluation on four heterogeneous data sets protected with k-anonymity and ε-differential privacy as privacy models, our approach demonstrates utility and forgetting effectiveness comparable to those of exact unlearning methods, while significantly reducing computational and storage costs. Our code is available at https://github.com/najeebjebreel/EUPG.
Josep Domingo-Ferrer, Najeeb Jebreel, David Sánchez
1CYBERCAT (Center for Cybersecurity Research of2026 Catalonia), ComSCIAM-Center for Computational Science and Applied Mathematics, Department of Computer EngineeringJun and Mathematics, Universitat Rovira i Virgili, Av. Pa¨ısos26 Catalans 26, E-43007 Tarragona, Catalonia
There is a growing demand for efficient data removal to comply with regulations like the GDPR and to mitigate the influence of biased or corrupted data. This has motivated the field of machine unlearning, which aims to eliminate the influence of specific data subsets without the cost of full retraining. In this work, we propose a statistical framework for machine unlearning with generic loss functions and establish theoretical guarantees. For squared loss, especially, we develop Unlearning Least Squares (ULS) and establish its minimax optimality for estimating the model parameter of remaining data when only the pre-trained estimator, forget samples, and a small subsample of the remaining data are available. Our results reveal that the estimation error decomposes into an oracle term and an unlearning cost determined by the forget proportion and the forget model bias. We further establish asymptotically valid inference procedures without requiring full retraining. Numerical experiments and real-data applications demonstrate that the proposed method achieves performance close to retraining while requiring substantially less data access.
Jingyi Xie, Linjun Zhang, Sai Li
Institute of Statistics and Big Data, Renmin University of China, Beijing 100872, China · Department of Statistics, Rutgers University, Piscataway, NJ 08854, USA · Department of Statistics and Data Science, Tsinghua University, Beijing 100084, China
Machine unlearning aims to unlearn data points from a learned model, offering a principled way to process data-deletion requests and mitigate privacy risks without full retraining. Prior work has mainly studied unsupervised / supervised machine unlearning, leaving unlearning for sequential decision-making systems far less understood. We initiate the first study of a foundational sequential decision-making problem: offline stochastic multi-armed bandits (MAB). We formalize the privacy constraint for offline MAB and measure utility by the post-unlearning decision quality. We conduct a systematic study of both single- and multi-source unlearning scenarios under two data-generation models, the fixed-sample model and the distribution model. For these settings, our algorithmic design is built on two canonical base algorithms: Gaussian mechanism and rollback, and we propose adaptive algorithms that switch between them according to the data regime and privacy constraint. We further introduce a mixing procedure that elucidates the rationale behind these baselines. We provide performance guarantees across the above settings and establish lower bounds under both dataset models. Experiments validate the predicted tradeoffs and demonstrate the effectiveness of the proposed methods.
Zichun Ye, Runqi Wang, Xuchuang Wang +3
Shanghai Jiao Tong University, Shanghai, China · University of Massachusetts Amherst, Massachusetts, United States · University of Washington, Tacoma, United States