Incentivized Collaboration in Active Learning
This addresses the challenge of ensuring cooperation in multi-agent learning systems, though it is incremental as it builds on existing approximation methods.
The paper tackles the problem of incentivizing collaboration among rational agents in active learning to minimize label complexity, showing that running an optimal algorithm over all data is individually rational but NP-hard, and provides tractable protocols comparable to known approximations.
In collaborative active learning, where multiple agents try to learn labels from a common hypothesis, we introduce an innovative framework for incentivized collaboration. Here, rational agents aim to obtain labels for their data sets while keeping label complexity at a minimum. We focus on designing (strict) individually rational (IR) collaboration protocols, ensuring that agents cannot reduce their expected label complexity by acting individually. We first show that given any optimal active learning algorithm, the collaboration protocol that runs the algorithm as is over the entire data is already IR. However, computing the optimal algorithm is NP-hard. We therefore provide collaboration protocols that achieve (strict) IR and are comparable with the best known tractable approximation algorithm in terms of label complexity.