论文标题
线性回归中战略噪声的影响
The Effect of Strategic Noise in Linear Regression
论文作者
论文摘要
我们以新兴的工作为基础，研究为机器学习算法提供的培训数据中的战略操纵。具体而言，我们专注于线性回归的普遍任务。先前的工作重点是策略性防护算法的设计，该算法旨在通过对齐数据源的激励措施来完全防止此类操作。但是，实践中使用的算法通常不是策略性的，这会引起代理商之间的战略游戏。我们专注于一类用于线性回归的非策略型量算法，即$ \ ell_p $ norm norm Minimization（$ p> 1 $），并具有凸正则化。我们表明，当操纵界定时，此类中的每种算法都可以接受独特的纯纳什均衡结果。我们还通过在更广泛的环境中揭示了策略性防止算法与纯粹的非战略型算法的纯纳什平衡之间令人惊讶的联系，从而阐明了这种平衡的结构，这可能具有独立的兴趣。最后，我们根据无政府状态的价格分析了这些算法下的平衡质量。
We build on an emerging line of work which studies strategic manipulations in training data provided to machine learning algorithms. Specifically, we focus on the ubiquitous task of linear regression. Prior work focused on the design of strategyproof algorithms, which aim to prevent such manipulations altogether by aligning the incentives of data sources. However, algorithms used in practice are often not strategyproof, which induces a strategic game among the agents. We focus on a broad class of non-strategyproof algorithms for linear regression, namely $\ell_p$ norm minimization ($p > 1$) with convex regularization. We show that when manipulations are bounded, every algorithm in this class admits a unique pure Nash equilibrium outcome. We also shed light on the structure of this equilibrium by uncovering a surprising connection between strategyproof algorithms and pure Nash equilibria of non-strategyproof algorithms in a broader setting, which may be of independent interest. Finally, we analyze the quality of equilibria under these algorithms in terms of the price of anarchy.
