Incentivizing Truthfulness Through Audits in Strategic Classification
Incentivizing Truthfulness Through Audits in Strategic Classification
复制标题
DOI：
10.1609/aaai.v35i6.16674
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Andrew Estornell;Sanmay Das;Yevgeniy Vorobeychik
中科院分区：
文献类型：
--
作者：
Andrew Estornell;Sanmay Das;Yevgeniy Vorobeychik
在许多社会资源分配领域，机器学习方法越来越多地用于对代理进行评分或排名，以决定哪些代理应该从社会服务机构获得资源（例如，无家可归者服务）或审查（例如，儿童福利调查）。机构的评分功能通常基于一个特征向量，该特征向量包含自我报告的特征和机构可获得的有关个人或家庭的信息的组合。这可能会促使代理人为了获得资源或避免审查而歪曲其自我报告的特征，但代理机构可能能够有选择地审计代理人，以核实其报告的真实性。我们研究了在这种情况下代理的最优审计问题。当对一个代理的分数设置阈值做出决策时，最优审计策略的结构出奇地简单，即统一审计所有可能从撒谎中获益的代理。虽然这个策略通常很难计算，因为在给定一组完整的报告类型的情况下，很难识别能够从撒谎中受益的代理集，但我们也提出了充分的条件，在这些条件下它是可处理的。我们展示了稀缺资源设置更加困难，并在这种情况下展示了一个近似最优的审计策略。此外，我们表明，在这两种情况下，验证是否有可能激励精确的真实性甚至很难近似。然而，我们也展示了最优解这个问题和获得良好近似的充分条件。
In many societal resource allocation domains, machine learning methods are increasingly used to either score or rank agents in order to decide which ones should receive either resources (e.g., homeless services) or scrutiny (e.g., child welfare investigations) from social services agencies. An agency's scoring function typically operates on a feature vector that contains a combination of self-reported features and information available to the agency about individuals or households. This can create incentives for agents to misrepresent their self-reported features in order to receive resources or avoid scrutiny, but agencies may be able to selectively audit agents to verify the veracity of their reports. We study the problem of optimal auditing of agents in such settings. When decisions are made using a threshold on an agent's score, the optimal audit policy has a surprisingly simple structure, uniformly auditing all agents who could benefit from lying. While this policy can, in general be hard to compute because of the difficulty of identifying the set of agents who could benefit from lying given a complete set of reported types, we also present sufficient conditions under which it is tractable. We show that the scarce resource setting is more difficult, and exhibit an approximately optimal audit policy in this case. In addition, we show that in either setting verifying whether it is possible to incentivize exact truthfulness is hard even to approximate. However, we also exhibit sufficient conditions for solving this problem optimally, and for obtaining good approximations.