The Price of Forgetting: Incentive Mechanism Design for Machine Unlearning

Data protection policies (e.g., GDPR) enforce the right to be forgotten and require companies to perform machine unlearning once users request data removal. This process incurs costs for server and degrades model performance, impacting users' satisfaction. In this paper, we propose the first incentive mechanism for machine unlearning, where server compensates users to retain their data. We characterize server's major unlearning costs, accuracy degradation and consumed time, in data redemption amount through experiments on three datasets and two unlearning algorithms. We model server-users interaction as a two-stage Stackelberg game. In Stage I, server optimizes compensation unit prices to minimize costs. In Stage II, users jointly decide data redemption amounts as a non-cooperative game. By restricting the feasible set of Stage I to Nash Equilibrium of Stage II, we formulate a challenging non-convex bilevel optimization problem. We propose an iterative algorithm to compute optimal unit prices in Stage I and equilibrium data redemption amounts in Stage II by characterizing bilevel problem's convexity. We prove the distributed convergence of best response updates to the unique Nash equilibrium by showing Stage II is a submodular game. Experimental results show that our mechanism minimizes server cost and maximizes social welfare over two practical baselines