Classification of Game Agents and Analysis of General Discrete and Linear Models for Algorithmic Learning
Saba Ahmadi, Hedyeh Beyhaghi, Avrim L. Blum, Keziah Naggita · Digital Signal Processing and Artificial Intelligence for Automatic Learning · 2025
In this paper, we address the classification of agents that can game and also improve.For instance, individuals seeking a loan can undertake actions that enhance their perceived creditworthiness and others that improve their actual creditworthiness.A decision-maker would prefer to construct a classification rule with minimal false positives (does not issue many bad loans) but gives many true positives (making many good loans), which involves motivating agents to upgrade to be true positives if feasible.We analyze two models for this task, general discrete and linear models, and establish algorithmic, learning, and hardness results for both.For the general discrete model, we provide an efficient algorithm for the maximization problem the quantity of true positives under no false positives, and demonstrate how to generalize this to a partial information learning environment.We also demonstrate hardness for maximizing the number of true positives under a nonzero limit to the number of false positives and that this hardness persists even for a finitepoint version of our linear model.We also demonstrate that maximizing the number of true positives under no false positive is NP-hard in our complete linear model.We further give an algorithm that identifies if there is a linear classifier that classifies all agents correctly, renders all improvable agents qualified, and provides more results for low-dimensional data.