Adaptive Anonymity via b-Matching

The adaptive anonymity problem is formalized where each individual shares their data along with an integervalue to indicate their personallevel of desired privacy. This problem leads to a generalization of k-anonymity to the b-matching setting. Novel algorithms and theory are provided to implement this type of anonymity. The relaxation achieves better utility, admits theoretical privacyguaranteesthat are as strong, and, most importantly, accommodatesa variable level of anonymity for each individual. Empirical results confirm improved utility on benchmark and social data-sets.