Proceedings

Maximizing Welfare with Incentive-Aware Evaluation Mechanisms

Video Download BibTeX Cite

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. Main track. Pages 160-166.

https://doi.org/10.24963/ijcai.2020/23

Abstract

Motivated by applications such as college admission and insurance rate determination, we study a classification problem where the inputs are controlled by strategic individuals who can modify their features at a cost. A learner can only partially observe the features, and aims to classify individuals with respect to a quality score. The goal is to design a classification mechanism that maximizes the overall quality score in the population, taking any strategic updating into account.

When scores are linear and mechanisms can assign their own scores to agents, we show that the optimal classifier is an appropriate projection of the quality score. For the more restrictive task of binary classification via linear thresholds, we construct a (1/4)-approximation to the optimal classifier when the underlying feature distribution is sufficiently smooth and admits an oracle for finding dense regions. We extend our results to settings where the prior distribution is unknown and must be learned from samples.

  1. [Alon et al., 2020] Tal Alon, Magdalen Dobson, Ariel D Procaccia, Inbal Talgam-Cohen, and Jamie Tucker-Foltz. Multiagent evaluation mechanisms. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), 2020.
  2. [Ben-David et al., 2002] Shai Ben-David, Nadav Eiron, and Hans Ulrich Simon. The computational complexity of densest region detection. Journal of Computer and Sys- tem Sciences, 64(1):22-47, 2002.
  3. [Blum et al., 2014] Avrim Blum, Nika Haghtalab, and Ariel D. Procaccia. Learning optimal commitment to overcome insecurity. In Proceedings of the 28th An- nual Conference on Neural Information Processing Sys- tems (NeurIPS), pages 1826-1834, 2014.
  4. [Cai et al., 2015] Yang Cai, Constantinos Daskalakis, and Christos Papadimitriou. Optimum statistical estimation with strategic data sources. In Proceedings of the 28th Conference on Computational Learning Theory (COLT), pages 280-296, 2015.
  5. [Carroll, 2015] Gabriel Carroll. Robustness and linear con- tracts. American Economic Review, 105(2):536-563, 2015.
  6. [Chen et al., 2018] Yiling Chen, Chara Podimata, Ariel D Procaccia, and Nisarg Shah. Strategyproof linear regres- sion in high dimensions. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 9-26. ACM, 2018.
  7. [Dekel et al., 2010] Ofer Dekel, Felix Fischer, and Ariel D. Procaccia. Incentive compatible regression learning. Jour- nal of Computer and System Sciences, 76(8):759-777, 2010.
  8. [Dong et al., 2018] Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strate- gic classification from revealed preferences. In Proceed- ings of the 19th ACM Conference on Economics and Com- putation (EC), pages 55-70, 2018.
  9. [Dütting et al., 2019] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen. Simple versus optimal contracts. In Proceedings of the 20th ACM Conference on Economics and Computation (EC), pages 369-387, 2019.
  10. [Grossman and Hart, 1983] Sanford J Grossman and Oliver D Hart. An analysis of the principal-agent problem. Econometrica, 51(1):7-45, 1983.
  11. [Haghtalab et al., 2016] Nika Haghtalab, Fei Fang, Thanh Hong Nguyen, Arunesh Sinha, Ariel D. Pro- caccia, and Milind Tambe. Three strategies to success: Learning adversary models in security games. In Pro- ceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), pages 308-314, 2016.
  12. [Hardt and Moitra, 2013] Moritz Hardt and Ankur Moitra. Algorithms and hardness for robust subspace recovery. In Conference on Computational Learning Theory (COLT), pages 354-375, 2013.
  13. [Hardt et al., 2016] Moritz Hardt, Nimrod Megiddo, Chris- tos Papadimitriou, and Mary Wootters. Strategic classi- fication. In Proceedings of the 7th ACM Conference on Innovations in Theoretical Computer Science Conference (ITCS), pages 111-122, 2016.
  14. [Holmstrom and Milgrom, 1987] Bengt Holmstrom and Paul Milgrom. Aggregation and linearity in the provision of intertemporal incentives. Econometrica, 55(2):303- 328, 1987.
  15. [Holmstrom and Milgrom, 1991] Bengt Holmstrom and Paul Milgrom. Multitask principal-agent analyses: Incen- tive contracts, asset ownership, and job design. Journal of Law, Economics, and Organization, 7:24-52, 1991.
  16. [Hu et al., 2019] Lily Hu, Nicole Immorlica, and Jen- nifer Wortman Vaughan. The disparate effects of strategic manipulation. In Proceedings of the 2nd ACM Conference on Fairness, Accountability, and Transparency (FAT*), pages 259-268, 2019.
  17. [Johnson and Preparata, 1978] David S. Johnson and Franco P Preparata. Theoretical Computer Science, 6(1):93-107, 1978.
  18. [Kleinberg and Raghavan, 2019] Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest ef- fort strategically? In Proceedings of the 20th ACM Con- ference on Economics and Computation (EC), pages 825- 844, 2019.
  19. [Mcafee and McMillan, 1986] R Preston Mcafee and John McMillan. Bidding for contracts: A principal-agent anal- ysis. The RAND Journal of Economics, 17(3):326-338, 1986.
  20. [Meir et al., 2012] Reshef Meir, Ariel D Procaccia, and Jef- frey S Rosenschein. Algorithms for strategyproof classifi- cation. Artificial Intelligence, 186:123-156, 2012.
  21. [Miller et al., 2020] John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in dis- guise. arXiv preprint arXiv:1910.10362, 2020.
  22. [Milli et al., 2019] Smitha Milli, John Miller, Anca D Dra- gan, and Moritz Hardt. The social cost of strategic clas- sification. In Proceedings of the 2nd ACM Conference on Fairness, Accountability, and Transparency (FAT*), pages 230-239, 2019.
  23. [Pollard, 2011] D. Pollard. Convergence of Stochastic Pro- cesses. Springer Series in Statistics. 2011.
  24. [Ross, 1973] Stephen A Ross. The economic theory of agency: The principal's problem. American Economic Re- view, 63(2):134-139, 1973.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards