Classification with Few Tests through Self-Selection

No. 6: AAAI-21 Technical Tracks 6

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 35

AAAI Technical Track on Game Theory and Economic Paradigms

We study test-based binary classification, where a principal either accepts or rejects agents based on the outcomes they get in a set of tests. The principal commits to a policy, which consists of all sets of outcomes that lead to acceptance. Each agent is modeled by a distribution over the space of possible outcomes. When an agent takes a test, he pays a cost and receives an independent sample from his distribution as the outcome. Agents can always choose between taking another test and stopping. They maximize their expected utility, which is the value of acceptance if the principal's policy accepts the set of outcomes they have and 0 otherwise, minus the total cost of tests taken. We focus on the case where agents can be either "good" or "bad" (corresponding to their distribution over test outcomes), and the principal's goal is to accept good agents and reject bad ones. We show, roughly speaking, that as long as the good and bad agents have different distributions (which can be arbitrarily close to each other), the principal can always achieve perfect accuracy, meaning good agents are accepted with probability 1, and bad ones are rejected with probability 1. Moreover, there is a policy achieving perfect accuracy under which the maximum number of tests any agent needs to take is constant — in sharp contrast to the case where the principal directly observes samples from agents' distributions. The key technique is to choose the policy so that agents self-select into taking tests.

10.1609/aaai.v35i6.16727