Authors' rebuttal
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:
$$
R^T = \sum_{t\in[T]} U(\boldsymbol{\mu}^\star, \boldsymbol{\gamma}^\star, \boldsymbol{\pi}^\star) - \sum_{t\in T_c} U(\boldsymbol{\mu}^t, \boldsymbol{\gamma}^t, \boldsymbol{\pi}^t) - \sum_{t\in T_u} U^\circ(\boldsymbol{\gamma}^t, \boldsymbol{\pi}^t) - \sum_{t\in T_c^\prime} 0,
$$
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.