研究多人策略性操纵下的分类器设计，揭示其均衡可计算且能学习。
Strategic Classification With Externalities
- 将代理间影响建模为斯塔克尔伯格博弈，推导出唯一纯纳什均衡。
- 在随机代理达均衡时，仍能保证分类器损失最小化，具备理论学习保障。
- 适用于需应对多方策略行为的现实场景，如公平评分系统。
我们提出战略分类问题的新变体：一个主方发布分类器，n个代理报告其（可能被操纵的）特征以接受分类。受现实应用启发，该模型关键允许一个代理的操纵影响另一个代理，即显式捕获了代理间的外部性。主方与代理的互动被形式化为斯塔克尔伯格博弈，而由此产生的代理操纵动态则表现为一个同时博弈。我们证明，在某些假设下，该代理操纵博弈的纯纳什均衡唯一且可高效计算。利用这一结果，我们为学习者建立了PAC学习保证：粗略而言，即使有随机数量的代理操纵至纯纳什均衡，仍可学习到在分布上损失最小的分类器。我们还讨论了通过基于梯度的方法优化此类分类器。本工作为分析在共同环境中多个策略主体交互下具有鲁棒性的分类器奠定了理论基础。
原文摘要 · Abstract (English)
We propose a new variant of the strategic classification problem: a principal reveals a classifier, and $n$ agents report their (possibly manipulated) features to be classified. Motivated by real-world applications, our model crucially allows the manipulation of one agent to affect another; that is, it explicitly captures inter-agent externalities. The principal-agent interactions are formally modeled as a Stackelberg game, with the resulting agent manipulation dynamics captured as a simultaneous game. We show that under certain assumptions, the pure Nash Equilibrium of this agent manipulation game is unique and can be efficiently computed. Leveraging this result, PAC learning guarantees are established for the learner: informally, we show that it is possible to learn classifiers that minimize loss on the distribution, even when a random number of agents are manipulating their way to a pure Nash Equilibrium. We also comment on the optimization of such classifiers through gradient-based approaches. This work sets the theoretical foundations for a more realistic analysis of classifiers that are robust against multiple strategic actors interacting in a common environment.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。