Online Information Acquisition: Hiring Multiple Agents

We thank the reviewer for pointing out typos and for the questions. In the following, we address the comments made by the reviewer.

Re: "Why uncorrelated mechanisms are not dependent on the agents' actions as are the correlated mechanisms? I think the mechanism is still uncorrelated if $\gamma_i$ also depends on the action of agent $i$. [...] Similarly, why not keep the principal's action policy \pi dependent on the agents' actions? The principal's action does not seem to have any influence on the agents' payoffs, so keeping it dependent on the agents' actions will not introduce any actual externalities among the agents."

In order to keep the definition of uncorrelated mechanisms more clean and simple, we opted to specify such mechanisms as independent on the action of agent $i$. In particular, notice that each uncorrelated mechanism $(\boldsymbol{\gamma}, \boldsymbol{\pi})\in\mathcal U$ can be specified as an equivalent correlated mechanism $(\boldsymbol{\mu}^\prime, \boldsymbol{\gamma}^\prime, \boldsymbol{\pi}^\prime)\in\mathcal C$ in which the recommedation policy recommends deterministically the best-response (i.e., such that $\mu^\prime[\boldsymbol{b}^\circ(\boldsymbol{\gamma)}] = 1$) and in which the payment function and action selection policy are specified such that

and

Given these considerations, to lighten the notation, we opted to remove from the definition of the uncorrelated mechanism the deterministic recommendation policy $\boldsymbol{\mu}^\prime$ as well as the dependency of $\boldsymbol{\gamma}$ and $\boldsymbol{\pi}$ from the recommended action.

We thank the reviewer for the positive comments on our paper. In the following, we respond to specific questions raised by the reviewer

Re: "If the costs of the follower are directly observable, can the learning rate be improved?"

If the cost functions were observable by the principal, then we could avoid to execute the cost estimation phase of our algorithm. Nonetheless, this would not improve the regret bound in its dependency from $T$ as we would still need to run the estimation phase for the probability distributions.

Re: "Is the independency assumption $\mathbb{P}^{(i)}(s_i\vert \boldsymbol{b},\theta) = \mathbb{P}^{(i)}(s_i\vert b_i, \theta)$ necessary? If so, without the independency assumption, what could be added to the difficulty in terms of computation and statistical learning?"

The assumption is needed to guarantee the existence of uncorrelated mechanisms. Indeed, if the assumption does not hold, the posterior of an agent would depend on the actions of the others introducing externalities. This rules out the existence of uncorrelated mechanism. Hence, without this assumption, we would be forced to work with correlated mechanisms. In this case, at the beginning of the learning phase, it would be impossible for the principal to output non-trivial mechanisms which are IC and use the feedback received to learn the game parameters. Thus, we would be forced to use non-IC mechanisms in the intial phase. However, as discussed in Section 4, it is intractable (and also not clear how) to characterize equilibria unless the correlated mechanism is IC. To summarize, we believe that the problem without this assumption does not only lead to linear regret bounds but it is not even well-defined.

Re: "Could the author provide a detailed comparison between the information acquisition framework and the Bayesian Correlated Equilibrium (BCE) (Bergemann, D. 2016)? It seems to me that if the agents are not allowed to communicate with each other, these IC concepts are closely related and similar challenges occur for the learning phase."

According to the setting described in (Bergemann, 2016) a shared mediator sends to the players some signals which are sampled according to a joint probability distribution that depends on some state of nature observed by the mediator. Then, based on the signal received, the agents can decide which action to take. Our setting is different, since, while the signals received by the agents still depend on the state of nature, they are also dependent on some preliminary action $b$ taken by them. Furthermore, in our model, the principal assumes the role of changing the utility functions of the agents by means of payments, which fundamentally differs from the role of the mediator defined in (Bergemann, 2016). Indeed, the signals sent by the 'mediator' (as meant in (Bergemann, 2016)) are parameters of the game and cannot be changed by the principal. We thank the reviewer for the suggestion and we will include a comparison with this work in the revised version of the paper.

We thank the reviewer for the comments and questions and for reporting typos which will be corrected in the final version of the paper. In the following we address each question specifically.

Re: "Is there any real examples of the optimal mechanism that are uncorrelated?"

Consider a particular instance of the case that we reported as a motivating example, in which a portfolio manager wants to learn the potential of a company to make an informed investment. The manager could hire multiple analysts to conduct separate researches on the same company, where each analyst spends effort to produce a report. If the information received by each analyst is independent from the information received by the others given their effort levels and the state of the company (this is true for instance when each analyst simply does independent researches without interacting with the other analysts), then an optimal mechanism for the portfolio manager is uncorrelated. This follows from Theorem 4.2. In general, the optimal mechanism is uncorrelated when the signal received by each agent is independent from the one received by the other agents.

Re: "Is there any simulations, real data to demonstrate the effective of this ETC algorithm?"

The great majority of recent works on the topic is more concerned with theoretical contributions rather than experimental evaluations (see e.g., Cacciamani et al., 2023, Chen et al., 2023). Moreover, we are the first to propose an algorithm for this kind of multi-agent information acquisition setting, and we would have no previous algorithms to compare ours with. This is aligned with related works on the topic.

Re: "In terms of sample size efficiency, the paper presents an opportunity for enhancement through the integration of more sample-efficient online learning algorithms, such as Upper Confidence Bound (UCB) or Thompson Sampling. These methodologies hold potential for yielding a more favorable regret profile."

Unfortunately, standard methods like UCB and Thompson Sampling are not applicable to our setting. Indeed, if you look at our problem as a general continuous learning problem: i) the reward are not Lipschitz, and ii) the constraints on the feasibility set are unknown. Dealing with such a complex problem requires more complex techniques than UCB and TS. Nonetheless, we point out that one of the components of our algorithm (specifically the definition of the objective function during the commit phase) exploits upper confidence bounds (similar to UCB).

We thank the reviewer for the comments and questions. In the following we address each question specifically.

Re: "what is the auxiliary variables z_i in eq (2c) equal to?"

The auxiliary variables $z_i \in \mathbb{R}^{|B_i|\times |B_i| \times |S_i|}_{\geq 0}$ are needed in order to provide upper bounds to the payment that agent $i$ can receive when she behaves untruthfully. In particular, for any two actions $b_i,b_i^\prime\in B_i$ and signal $s_i\in S_i$, the constraint (2c) guarantees that $z_i[b_i, b_i^\prime, s_i]$ is an upper bound to the payment that agent $i$ receives when she is recommended to play action $b_i$, she deviates by playing action $b_i^\prime$ and then she observes signal $s_i$. We apologize if this was not clear in the paper and we will clarify it in the final version.

Re: "Further, Theorem 3.1 has a collection of values C_1, C_n, have they been specified? [...] 3rd line in section 2, why are some c’s (for the cost function) capitalized and others are not"

The lowercase function $c_i: B_i\to [0,1]$ represents the cost function for agent $i$ that associates to each action in $B_i$ its cost. The collection of functions $C_1,...,C_n$, where $C_i\to B_i\times B_i\to [-1,1]$ for each $i\in\mathcal N$ are meant to represent pairwise cost differences, i.e., $C_i(b_i, b_i^\prime) = c_i(b_i) - c_i(b_i^\prime)$ for each $i\in\mathcal N$ and for each $b_i,b_i^\prime\in B_i$. In the third line of section 2 there is a typo (it should have been $C_i(b_i,b_i^\prime) = c_i(b_i) - c_i(b_i^\prime)$). We apologize for any inconvenience that this may have caused and we will clarify these points in the final version of the paper.

Re: "in the cumulative regret formula on page 6, why is T’_c not included is it because it is assumed to be empty, I found this sentence to be confusing “as discussed in Section 4, we used the fact that when the principal commits to a correlated mechanism which is not IC, then she can incur in a constant per-round regret in the worst case, since the behavior of the agents is unpredictable”"

As the reviewer correctly pointed out and as discussed in Section 4, whenever we commit to a non-IC correlated mechanisms we can incur in constant per-round regret. For the sake of exposition, we assume that the principal's utility is $0$ when she commits to a non-IC correlated mechanism. Hence, the regret is the following:

which gives exactly the definition of regret that we considered. Furthermore, notice that in light of the findings described in Section 4, we explicitly design our algorithm so to guarantee $T_c^\prime$ to be empty. To enhance clarity, we will explicitly state this aspect in the final version of the paper.

Re: "In theorem 5.1, is it not reasonable to have a setting where $\ell$ and/or $\iota$ can equal zero? Would this not break the algorithm?"

Settings in which $\ell$ and/or $\iota$ are equal to $0$ correspond to degenerate instances in which states of nature and/or signals are equivalent to the agents (since they are induced with equivalent probability). These degenerate instances can be reduced to non-degenerate ones as follows. If $\ell=0$, agents can avoid to distinguish between the two (or more) signals that induces the same posterior and replace them with a single signal. In a similar way, if $\iota=0$, we can simply remove from the instance the signal that is induced with probability $0$, since it is never observed.

Re: "In mechanism design settings it is reasonable to consider agents engaging in collusion. I did not find comments in the paper about that. This is not necessarily a weakness, since one may just ignore the collusion issue in a problem."

The basic scenarios considered in multi-agent principal-agent problems assumes that the agents are self-interested (see e.g., Cacciamani et al., 2023). Assuming that they can collude, would require a different definition of the IC constraints, with the need to consider more complex correlated deviations of the agents. This may introduce non-trivial complexities (such as the non-existence of equilibria) as it happens in strong correlated equilibria [1]. Notheless, studying these kind of settings constitutes undoubtedly an interesting direction for future research. We thank the reviewer for the suggestion.

[1] Ray, Indrajit. "Coalition-proof correlated equilibrium: A definition." Games and Economic Behavior 17.1 (1996): 56-79.