Corelab Seminar

Stratis Ioannidis (Technicolor research center in Los Altos, CA)
Linear Regression as a Non-Cooperative Game

The statistical analysis of personal data is a cornerstone of several experimental sciences, such as medicine and sociology, and has recently become a commonplace-yet controversial-aspect of the Internet economy. The monetary and societal benefits of statistical estimation over personal data are often off-set by a privacy cost incurred by participating individuals. We propose a game-theoretic model to express this trade-off in the context of linear regression, a ubiquitous statistical task. In particular, we consider an analyst wishing to learn a linear model over responses solicited from several individuals. Though individuals benefit from correct estimation of the model, they also incur a privacy cost when revealing their responses. To address this, individuals strategically add noise to their responses, to minimize a cost that captures both how well the model is estimated, as well as the privacy violation they incur. We study the Nash equilibria of the resulting non-cooperative game, establishing the existence of a unique equilibrium for which costs are finite. We also determine the price of stability for several classes of privacy and estimation costs. Finally, we prove that estimating the linear model through a generalized least-squares minimization is optimal among all linear unbiased estimators: this result extends the famous Aitken/Gauss-Markov theorem in statistics, indicating that its conclusion persists even when individuals add noise strategically.

This is joint work with Patrick Loiseau and Michela Chessa from Eurecom, France.