Online Information Acquisition: Hiring Multiple Agents

We investigate the mechanism design problem faced by a principal who hires multiple agents to gather and report costly information. Then, the principal exploits the information to make an informed decision. We model this problem as a game, where the principal announces a mechanism consisting in action recommendations and a payment function, a.k.a. scoring rule. Then, each agent chooses an effort level and receives partial information about an underlying state of nature based on the effort. Finally, the agents report the information (possibly non-truthfully), the principal takes a decision based on this information, and the agents are paid according to the scoring rule. While previous work focuses on single-agent problems, we consider multi-agents settings. This poses the challenge of coordinating the agents' efforts and aggregating correlated information. Indeed, we show that optimal mechanisms must correlate agents' efforts, which introduces externalities among the agents, and hence complex incentive compatibility constraints and equilibrium selection problems. First, we design a polynomial-time algorithm to find an optimal incentive compatible mechanism. Then, we study an online problem, where the principal repeatedly interacts with a group of unknown agents. We design a no-regret algorithm that provides O(T 2/3 ) regret with respect to an optimal mechanism, matching the state-of-the-art bound for single-agent settings. Preliminaries Game model. We investigate games between a principal and a set N = [n] of n agents 1 . We assume that n is constant. 2 . Each agent i ∈ N can choose an action b i from a set B i of k actions, 1 In this work, for any n ∈ N>0, we use [n] = 1, .., n to denote the set of the first n natural numbers. 2 This avoids computational issues related to the exponential-size representation of the problem instance. Most of our results continue to hold for arbitrary n.