Online Information Acquisition: Hiring Multiple Agents
Authors: Federico Cacciamani
Matteo Castiglioni
Nicola Gatti
Venue: ICLR 2024 poster (2024)
Keywords: online learning
information acquisition
mechanism design
Primary area: reinforcement learning

Abstract: We investigate the mechanism design problem faced by a principal who hires \emph{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 $\widetilde{\mathcal{O}}(T^{2/3})$ regret with respect to an optimal mechanism, matching the state-of-the-art bound for single-agent settings.

Published as a conference paper at ICLR 2024
ONLINE INFORMATION ACQUISITION: HIRING MULTIPLE AGENTS
Federico Cacciamani
Matteo Castiglioni
Politecnico di Milano federi roc cacci amani @po1 imi. iit
Politecnico di Milano
matteo. castigll ioniiiiiiin 8po1 imi it
Nicola Gatti
Politecnico di Milano
nicola gatti@polimi it
ABSTRACT
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 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 the effort. Finally, the agents report the information (possibly non sontruutffull),, the principal takes a decision based on this information, and the agents are paid according to the scoring rule. While previous work focuses single-agent prob- lems, we consider multi-agents settings. This poses the challenge of coordinating the agents' efforts and aggregating correlated information. Indeed, show that optimal mechanisms must correlate agents' efforts, which introduces externalities among the agents, and hence complex incentive compatibility constraints and algorithm
equilibrium selection problems. First, we design a polynomial find an optimal incentive compatible mechanism. Then, we study an online problem, where the principal repeatedly interacts with group of unknown agents. We design no-regret algorithm that provides ((T2/3) regret with respect optimal mechanism, matching the state-of-the-aa bound for single-agent settings.
INTRODUCTION
Acquiring reliable information is crucial in any decision making problem. Often, decision makers delegate the task of gathering information to other parties. In the classical information acquisition scenario (Savage 1971). principal delegates single agent acquire information (Chen & Yu 202T Papireddygari & Waggoner, 2022] Li et al., 2022] Chen et al. 2023). However, in many real-world scenarios, the principal may have multiple sources of information (Cacciamani al.) 2023). Consider a portfolio manager that 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 report. The manager gains information from the reports and decides whether or not to make the investment. To incentivize the analysts to produce accurate reports, the manager designs a payment scheme that pays the analysts based on the reports accuracy. Formally, this problems can modeled as a game between principal that wants to acquire information about stochastic state and group of agents that receive information about this state through signals whose accuracy depends on undertaken effort (effort levels are modeled through different actions). The game goes follows. First, the principal commits to distribution μ over action recommendations and payment function, a.k.a., scoring rule (Oesterheld & Conitzer 2020 Neyman et (202)) Then, each agent i observes an action recommendation sampled from μ and performs a costly action b; Each agent receives a signal from a joint probability distribution p(() (s|b, 8) and reports the signal (possibly non-truthfully) to the principal. Based on the reported information, the principal makes decision E A. Finally, the agents paid according to the

---

Published as a conference paper at ICLR 2024
scoring rule. Our goal is twofold. First, we want to analyze the optimization problem of computing optimal mechanisms, characterizing their properties and computational complexity. Moreover, we study online problem in which the principal does not have prior knowledge about the agents. Our goal is to design online no-regret learning algorithms that repeatedly interacts with an unknown group of agents maximizing the cumulative principal's utility[ [
Original contributions. We study the design of efficient algorithms for the multi-agent information acquisition problem, with a focus on both the optimization problem and the online learning problem arising when a principal interacts repeatedly with unknown agents. First, we assume that the principal knows all the game parameters. We show that an optimal mechanism can be computed efficiently. Our algorithm solves a quadratic optimization problem by providing a linear relaxation and then recovers solution to the original problem in polynomial time. Moreover, we characterize the settings in which the optimal mechanism is correlated, i.e., each agent's payment depends also on the signals reported by other agents, and the settings in which the optimal mechanism is uncorrelated, i.e., each agent's payment depends only from her reported signal and the state of nature. Next, we consider the online problem in which the principal does not know the game parameterrs and needs to learn them by repeatedly interacting with the agents. We present an online algorithm that attains ( regret with respect to an optimal mechanism, which matches the offe-oo-thhearr bound for single-agen ageen settings (Chen et al. 2023). Our algorithm comprises three phases. In the first one, we estimate the probability distribution over states of nature induced by the agents' signals. Ensuring that the estimations are sufficiently accurate is the main challenge in this phase. The required level of accuracy depends on the specific instance and it is crucial for designing triettl-incentive compatible (IC) scoring rules, which maintain truthfulness under uncertainty. In the second phase, the algorithm estimates the differences among costs of the agents' actions. To do so, we employ non-truthful mechanisms, which require a non-trivial analysis of the agents' behavior. Finally, the algorithm commits to an approximately optimal strategy while ensuring truthfulness under uncertainty. We achieve this goal by leveraging the estimations obtained in the previous phases. Specifically, we find an approximately optimal and approximately IC mechanism by exploiting the estimations. Then, we take a convex combination between this scoring rule and an ad-hoc strictly IC scoring rule to obtain an IC mechanism.
2 PRELIMINARIES
Game model. We investigate games between a principal and a set V = [n] of n agent We assume that n is constant
| Each agent E A can choose an action b from a set B, of actions, each one with cost (b specified by a cost function c B, [0, 1]. For i E / and by 1/4 E B, we let (b,,, 14) = (b,),) - ca (b)). We denote the set of all possible action profiles as B == XiEN B, and the set of all possible action profiles excluding agent i's action as B_ = X By Given b E B. we denote as b_, E B_, the tuple obtained from b by removing element b. relative to agent i. The interaction model we consider enhanced with a pre-play round of communication between the principal and the agents in which the principal can privately recommend to each agent which action to take. F After each agent takes an action b, E B, (not necessarily equal to the action recommended by the principal), state of nature 0 is sampled from a finite set θ {Oi,..., 0m) according to prior p E ( The state of nature is observed neither by the principal nor by the agents. Instead, depending the action profile b B chosen by all the agents, each agent i observes signal s; drawn from a finite (-dimensional set S,. The signal profile received by the principal is denoted as ($1,...,,,,) The set of all possible signal profiles is S S,S, Moreover, the set of all possible signal profiles excluding agent i's signal is denoted as S_, = SJ Given a signal profile S, we let s.; S_; the signal profile obtained from s; by removing signal st. The signal profile and the state of nature are sampled according to a joint probability distribution that depends
For space constraints, we defer a discussion on the related works to Appendix A 'In this work, for any n E Nyo, we use [n] {1,,..,?) to denote the set of the first n natural numbers. 'This avoids computational issues related to the exponential-size representation of the problem instance.
Most of our results continue to hold for arbitrary
'In Section 4 we show that optimal mechanisms correlate the agents' efforts and hence this step funda- mental to maximize the principal's 's utility.
In this work, given finite Z, we denote A (Z) the [Z/-dimensionnl probability simplex.
2

---

Published as a conference paper at ICLR 2024
on the agent's action profile PP (s. = p|0 b). The marginal signal probability of agent i is defined as p()) (s; b, 0) = (s|b, 0), where use the superscript (i) to explicit that we are considering the probability with which agent i receives signal s; E S, We assume that the information received by each agent i is independent from the actions taken by other agents i.e.
(#t bb. 0) Vi N,, Vs, E S vb B, v0 O. p(() (8i 0) p()
Notice that this does not exclude that the signals received by the agents are correlated. Moreover, denote as p(() (s,(b.) == E. p(0)P(()) (s.l6,, 0) the probability with which agent i observes signal s; after the agent played action by Finally, denote with p(x) (0lbe, 8:) the probability of state 0 in the posterior induced to agent i E / by signal 8; E S; and action b; E B, In our model, the agents can communicate signal observation (possibly lying and communicating a signal s/ different than the signal s; actually received) to the principal, which can pay the agents to reward their communication. After receiving signal profile s' from the agents, the principal chooses an action from a finite set A = [ai,..., )dd and receives utility u(a, 0) E [0, 1].
Mechanisms. A mechanism for the principal must specify three different components: (i) recommendation policy l that determines which actions are recommended to the agents, (ii) payment scheme y = (7,,..: - also called scoring rule - specifying how each agent will be paid, and (ii) action policy π encoding which action the principal chooses function of the received signal profile and the recommended actions. In this work we are interested in the class of correlated mechanisms, in which the payment received by agent depends recommended to the agents and on the whole signal profile s received by the principal, as well as on the state of nature 0. The set of correlated mechanisms is denoted as C. Formally,
the whole action profile
C: {1,7 T) μ E A(B), %/ B S ④ [0, M] E N,, π B x S + A(A))
where M is parameter that limits the principal's budget. When the principal uses mechanism (n. 7: T), the action profile recommended is b E B, the signal profile reported is s E and the state of nature is 6, the payment received by agent i is 1a(b, s, 0), while (l, denotes the probability with which the principal plays action E A.
Optimal mechanisms and incentive compatibility. The objective of the principal is to find an optimal mechanism, i.e., a mechanism guaranteeing the maximum possible difference between utility of the principal and total payments. By the revelation principle, it is possible restrict our attention to mechanism that are truthful, i.e., such that the agents are incentivized to follow the principal's s recommendations and to report truthfully the signals they observe. Hence, we denote the expected payment received by player when she behaves truthfully and the mechanism is (H, TT) as:
7( = ΣΣΣ
A[BlIP (s, b) 7:|6, 8, 0j.
bEB #ES BEe
Then, the expected utility of the principal is obtained as the difference between the expected utility received by actions in A and the total expected payments (assuming truthful behavior of the agents):
Uh, ΣΣΣ
μdbiP (s, Blb)
Σ n s, alu((, 0) LOEA
Σ Fe(M, 7).
BEB aES BEG
EN
To ensure that truthful behavior is optimal (i.e., the mechanism is IC), we introduce the concept of deviation functions, which model the possible deviations from truthful behavior. Formally, the set i of agent i's deviation functions is 4; = {(Ø, sp) Φ: B, + B,, Φ: B, x S; + S,) Given any couple (ő, up) E D;, the function ó models the deviation from the recommended action, while yp models untruthful reporting of the received signal. Agent i's expected payment when she deviates according to (ò, sp, all the other agents behave truthfully, and the mechanism is (Ju, 7, πτ) is:
Fr (p,
Σ ΣΣΣ BE #ES BEe
m|b]IP (s, ((()(b,), b-+)) (bb,, (sr(b,, 81), 8 e)
'Intuitively, this assumption models those cases in which the information received by an agent depends exclusively on her level of effort.
"Bounding the payments is a classical assumption in online problems related to information acquisition and in principal-agent problems (Chnn et al. (2023): 7hu et al. (023). Without this assumption the learner decision space unbounded.
3

---

Published as a conference paper at ICLR 2024
An optimal correlated mechanism can be found solution of the following optimization problem:
max (H.T))EC
(la)
s.t.
7.( 17 2 (ut Vi E,,, v(O, E 4;
(1b)
BEB
The objective function of Equation T is the maximization of principal's expected utility assum- ing honest behavior of the agents, and Equation (lb) guarantees that the mechanism is incentive compatible (IC), i.e., it guarantees that, for all agents, truthful behavior an equilibrium.
3 A LINEAR PROGRAMMING RELAXATION FOR COMPUTING OPTIMAL MECHANISMS
In this section, we provide a polynomial- algorithm to solve Problem ( i.e., to find an optimal
mechanism. As a first step, we provide Linear Program (LP) relaxation of (T. Notice that (T) presents two main issues: (i) the objective function and the constraints are non-linear in the variables
(H, 7: R), and (ii) it has exponential number of constraints, since | k*ttk, To address (i), we introduce variables x = (#11..,, F,,) and y. where an E 20 x|x]] for each i E N,
and y E R220 |[] Intuitively, 2,[6, s, 0] represents the product [b, s, 0). while y(b, s, a] represents the product y|b] [b,, s, a), thus making the objective function and the constraints linear. This yields relaxation of the original non-linear optimization problem. Then, in order to be able to recover valid mechanisms from variables C;, y. we introduce additional constraints. For what concerns (ii), in order to reduce the number of constraints, we observe that it is possible safely consider a restricted set of deviations for each agent, while still guarantecing incentive compatibility w.r.t. deviations in 2;. In the following. we will denote the expected payment received by agent when she is recommended to play by E Bi, she plays By. observes E S,, and reports s/ E St as:
fi ( (b, by, 8i, s/,
Σ bIIEB_, OEG
Σ Σ
xi [[bs, b-:), (6/, 8);, OJP ((si, 8-;), 016b, b)),
where we made explicit fi's dependency from the probability distribution IP (c,-1b) E ASS θ). Moreover, we write [a, s, P)= s,,
== [,, b, 83, IP) to denote the expected payment received by agent i when she is recommended action b, B,, she observes signal s; S, and she behaves honestly. Then, consider the following LP, which we denote as LP LC, E). It is parameterized by Ç. A and e, where Ç = (Gb)ber is collection of probability distributions over S Q, A = (A1,-.,, An) with A;: B₁ x B; + 1- represent pairwise cost differences, and e > 0:
max O0 #2 (())((
ΣΣΣ
lulb, a/So| Olu(a, [)] - Σ xi 8, 0,6o|s,0| Σ LaEdd
s.t. (2a)
BEB AEE
iEN
Σ [fi(zzlbe, Sic 5²) 2/,b b/, $|1
Σ b.:),, -E Vi ViE by E B, (2b)
9,E8;
:EB
2/ (bi, U/ 8i] 2 [i(x; U/, 84, 8/ 5¹)
ViEW Vo, U/ E B,, Vs,, 8, E S; (2c)
Σ y(b, s.a] = [bb
bb Vs E S (2d)
aEA
1, 8, 0] < Mp(b]
ViE,, Y V0 E θ (2c)
Intuitively, constraint (cc) ensures that the auxiliary variable 2, 2b b', s,] provides an upper bound on the expected payment that agent i could get through any untruthful signal reporting when she was recommended to play b, she played bj and observes 8;. Constraint (b) exploits the auxiliary variables z (2), zn) with z; I8 [11.
to guarantee that no deviation is profitable for
agent i. The following theorem shows how to recover an optimal correlated mechanism from LP R
*All the proofs omitted from the main paper can he found in the Appendix.
4

---

Published as a conference paper at ICLR 2024
Theorem 3.1. Let (x", yy. 1t",, 2²)) be optimal solution to LP (I, (PPC,,), where C' (C1,... Cr......p.)) Then, let 7² = (7i..., Ya) and π be such that
#i (6) p (b)
if + O otherwise
y [. if if + 0
l,, 8,0
x rb1,
=
otherwise.
d
Then (n* , TT* is an optimal solution to Problem
As consequence of Theorem 3.1 noticing that the linear program has a number of constraints and variables polynomial in k, I and m, obtain the following corollary.
Corollary 3.2. An optimal mechanism can be found in polynomial time.
4 CORRELATED VS UNCORRELATED MECHANISMS
Before introducing our online learning problem, we discuss one of the main issues arising from the adoption of correlated mechanism. Indeed, consider the case in which the principal is not able to commit to an IC mechanism, for instance because she is uncertain about the game parameters and thus she is not able characterize the set of IC mechanisms. When the principal uses non-IC mechanisms it becomes complex to characterize the behavior of the agents. This is because correlated mechanisms introduce externalities among the agents. More precisely, since the payments received by agent depend also on the deviation policies (6), E 2 adopted by agents * i, the agents should play an equilibrium of the n-players game induced by the correlated mechanism. This introduces well-known issues related to both computational complexity and equilibrium selection Daskalakis al. (2009). Thus, committing to correlated mechanism which is not IC induces an unpredictable behavior of the agents, which in online settings makes it impossible for the learner to even estimate the game parameters.
To address such drawbacks of correlated mechanisms, we introduce the class of uncorrelated mecha- nisms. An uncorrelated mechanism is composed by an uncorrelated scoring rule 7 = (7,, 7n) and an action policy Formally, the set of uncorrelated mechanisms is defined as:
u {(>,7) .)) 7/ St x θ [0, M] Vi E W,, π S A(A))
Notice that any uncorrelated mechanism can be represented as a correlated mechanism and hence u C C. Differently from correlated mechanisms, any (7, E Ll induces a well-defined best response for each agent. In particular, the best-response problem can be framed Stackelberg game. Given any (y, π) E U, we define the optimal action ((()) E B, and the optimal signal reporting policy (-(m))) S; + Sy when the principal commits to mechanism (7, π as:
single-follower
{ Σ
(im))) E arg max B. S
p(t)) 0(b,) (lp(s)) 0) - c((b))
S.ES GEG
where, as common in the literature, ties are broken in favor of the principal. Therefore, the expected utility of the principal when she commits to mechanism (y, πτ) E ll is:
U2(y, TT) ΣΣ (s, (g.00(((rr))
( aaE
ग (s)))s) -
-E mll iEN
SESREO
where (7()) = (bf(7)), ..., b...,,,, (7,)) and (aly)) = (s1(s11))) P (s))7))) Uncorrelated mechanisms eliminate all externalities among the agents, inducing predictable agents' responses. Hence, they are appealing in online settings in which the principal must learn from agents' behavior. We conclude the section showing that despite their advantages that make uncorrelated mechanisms very useful tool, they can be suboptimal with respect to correlated mechanisms.
Theorem 4.1. There exists a game which no uncorrelated mechanism is optimal.
However, while uncorrelated mechanisms are suboptimal in general, there exists realistic classes of games in which optimal mechanisms are uncorrelated as shown by the following theorem.
Theorem 4.2. Assume there for each i E N, 0 E O and by E B,, there exists a probability distribution ()b)) (SS)) such that vb E Vs and VO O P (s. 0bb) = pi0 IL (hr f). Then, there exists mechanism (y, π U that is optimal among correlated mechanisms.
5

---

Published as a conference paper at ICLR 2024
This condition models scenarios in which the signals received by the agents independent. The absence of signals correlation makes the expressive power correlated mechanisms futile.
LEARNING THE OPTIMAL MECHANISM
We study an online learning scenario in which the principal interacts for T' rounds with n agents without knowing neither the joint probability distribution P (s, 0|b) nor the cost functions o, At each round E [T]. the principal publicly announces her mechanism. If the mechanism is correlated, then the agents receive recommendations b' μ.. Then, each N chooses action öf (possibly different that 69) incurring the cost c, (6)). If the mechanism is uncorrelated the agents play according to the tuple of best responses b, = b (7)". To avoid the issues highlighted in Section 4 we will never employ correlated mechanisms that are not IC. Then, a state of nature 0f and signal profile sf are sampled according to P(ss, 0 (6)). Each agent i observes signal 8; and reports signal 8 the principal. If the mechanism is correlated, then s = If the mechanism is uncorrelated, then 8 = yo m Finally, the principal takes action af according to the scoring rule. At the end of the round, the feedback received by the learner includes the actions 5' taken by the agents 9 the signals 8' reported by the agents, and the state of nature 0*, while she not able to observe the signals sf that were actually observed by the agents.
=lb². st -1 and gets utility u(a", .0) while each agent is paid
The performances of the algorithm are measured in terms of cumulative regret R which represents the expected loss of utility for the principal due to not having selected the optimal mechanism each t E [T'. Formally, let (n²", yY", R²" be an optimal mechanism (i.e., an optimal solution to (I). and let Te, Tu, C S [T] be the sets of rounds in which the principal committed to a correlated and IC mechanism, to uncorrelated mechanism, and correlated and non-IC mechanism, respectively (it holds Te U., U U.% = [T].. Then, the cumulative regret defined as:
RT
Σ U(H "oun.,"" ,,""" Ev(n', M ,','') EU(GTT)) SE(T]
TET.
TET,
where, as discussed in Section 4 we used the fact that when the principal commits to correlated mechanism which not IC, then she can incur in a constant per-round regret the worst case, since the behavior of the agents is unpredictable. Our goal is to design an algorithm that achieves R2 = oT)). In the following, we let l > O be the minimum distance between the posteriors induced by two signals, i.e., l = B. and & > 0 be the minimum probability with which each signal is received by an agent, iee., L = min; (P(() (s,(b.).
Eoco (IP() (0lb;, s;) p(t) (0lb,, st)) ?
5.1 ALGORITHM OVERVIEW AND ASSUMPTIONS
For each agent i E N and action b; E B, we assume to know uncorrelated scoring rule strictly incentivizing to play action b; while also incentivizing her to report truthfully the observed signal. Assumption 1. For each
E N, the learner knows set of scoring rules S x + [0, M] b, B.} and such that
T; (n,
ΣΣ s,ES; OEE
p(0) (si, 01b,) 7 [st, p(()) (st, 0166) (ee(s)) 2 C(bi, +
(3)
for all B, E B, {b,) and ip E S S,, and such that
Σ BEE
p(o) (0)s;, b.) [..0 [ss, 0] 7 [64, 2
Vo,, St.
Intuitively, Eq. 33 guarantees that for each agent i, following the action recommendation strictly better than deviating different action, while Eq. (4) guarantees that reporting the observed signal is never worse in expectation than reporting a different one. This assumption is common in the literature (see, e.g.. Chen et al. (2023)). and is necessary to achieve incentive compatibility under uncertainly. Throughout the remaining of the paper, we let {>/ (7/"1 ..... 2.h b E B).
It is common in the literature to assume that agents' actions can be observed (see, e.g., Chen et al. 2023 ) Intuitively, this is because the truthful reporting of signals can he used discriminate between different actions.

---

Published as a conference paper at ICLR 2024
Algorithm 1 provides an high-level overview of our algorithm. The proce- dure is divided in two phases, explo- ration phase and a commit phase. The ex- ploration phase is devoted to finding the estimators Çb E A(S x ②) of the joint probabilities IP (6)(6) for each b, the es-
Algorithm 1 Online Information Acquisition
Require: T,N1, N2,Nss p. 1,
D Exploration phase V.V.E.P))) + ESTIMATEPROB (N1, 0) Sec. (A, t- ESTIMATACOSTS N3, r Sec. & Commit Phase C, p, Sec.
(t) timators Sb..e; E A()) of the posteriors (-Ib,, 84) for each E N, b, B; and E St, and the estimators A,,,, 14) of the cost differences Cbb,, bf) for E N, bi, Df E Bj, together with the respective confidence bounds v, o: X Rgz. During the commit phase, instead, we leverage the estimates obtained in the previous rounds output sequence of IC mechanisms that guarantee sublinear cumulative regret. As imputs to the algorithm we provide the total number of rounds T,, the minimum number of rounds N1, N22, N3 that regulate the length of the exploration phase, the scoring rules r, the scalar described in Assumption | and the desired confidence level E (0, 1) on the regret bound. We provide description of the three algorithms ESTIMATEPROB, ESTIMATECOSTS are stated in the
and COMMIT in Sections 7 and g respectively. The guarantees of Algorithm [ following theorem.
Theorem 5.1. Let n = 289 m2 In (12] de. For any 5 E (0, 1), with probability at least
1 - 6, rumning Algorithm with N1 = N3 = T2/3 and N2 log(T) guarantees
M3
Rd
v (n(1/)) max .k))
pl
The upper bound on Rd presents a term max(72/3 n). For T' sufficiently large, x -that depends on the instance and logarithmically on T- is dominated by T2/3 and we recover the ((T2/3) bound 10
6 ESTIMATION OF THE PROBABILITY DISTRIBUTIONS
The estimation phase is devoted to the estimation of the joint probabilities IP (:, ((b) and of the posteriors p(9) (-18;, b,) induced by action-signal couples. Let Tp C T be the set of rounds devoted to ESTIMATEPROB. Furthermore, for b B, b, E B, and E S, let Tp(b) {t E Tp b' b}
and T (b,, 8;) = {t E Tp $ Ss. bj = b,}. For K = T| nm, we introduce estimators So A(S θ) and S
(()) with their confidence bounds us and Cb...
(6) defined as
In(2K/5) 2TTz(b))
0
[b)
Σ [ = =]]
1b
vb, 8,0
(5)
(E)
and
In In(2K/8)
Sh..s, 10]
-
Lb..:
Vi, bi,bi,s, s1,0.
(6)
TT (b., s:)l (b..))
2|T (3) (b,, st]
The procedure for obtaining such estimators described in Algorithm 2 leverages the knowledge of the scoring rules in Assumption to guarantee sufficient number of samples for each probability distribution that we want to estimate. In particular, the algorithm iterates over all E B and commits to scoring rule 7 E П for at least Ni rounds and until specific condition is met. Committing to 7o guarantees that the agents are incentivized to play b (Eq. 3 and that they report the received signal (Eq, 4 This ensures that the feedback received is reliable for estimating both probability distributions. The condition < d/ 13m on the confidence bounds guarantees that we have collected enough samples to estimate each posterior distribution. The required precision depends on the instance parameters and & and will be fundamental to design approximately optimal mechanism that are IC (see Section (). To formalize the guarantees of Algorithm 2
we introduce the clean event Ep-
10We remark that our algorithm does not need to know and i. advance, but implicitly estimates them during the exccution. In this work, denote as [[]] the indicator function.

---

Published as a conference paper at ICLR 2024
Definition 6.1 (Clean event for probability estimation). Let 289 (2(K/ (22 Let V/ := maxbEs Vb and = maxiEN lbr.e The clean event En holds if, for all t E Tp it holds that:
Cols, 0 - IP (s, S V s,,
bb. pp() (0)b,, si)1
Vi, bi,b,, s4
and if, whenever (T)( 2 Ri it holds that
1
IT, ( (b., s:)l 2 2 [dTT(() VEN, vb E, Vs: E St,
Using standard concentration arguments, it is possi- ble to show the following.
Algorithm 2 ESTIMATEPROR
Require: N,,
Lemma 6.1. The clean event Ep holds with probabil- ity at least 2-
TT(()) < {0} Vb
(b,, 8:) +- (0) Vi,b;
Λ a a = -1/d Vs,a
Before concluding this section, we point out that the number of samples (b) needed for each b E B to have @ S d/ d/13m depends on the value of the param- eters E and Indeed, the smaller are the minimum signal probability and the minimum posteriors dis- tance é, the higher is the number of samples needed to have an accurate estimation and to satisfy the above condition. However, setting N1 = T2/3, the number of samples needed to satisfy the two terminating con- ditions becomes dominated by N₁ in non-degenerate instances in which 7' is sufficiently large. Formally,
for b do
while (T(b)] < N1 V `> 13m do
d
Select (70, πT) and observe 8 0r
Tx(b) + (b) U {t}
T (b;, 51) T 8 U (t) Vi
Update (Go, ub) as in Eq. 5
Update (Si. (. in Eq.
(1)
6 vi
(i)
f maxi Db..s
+ ming,a..d
Lemma 6.2. Assume the clean event Ep holds. Then, at the end of the execution of ESTIMATEPROR, for each be E B it holds that (Tp(b) S max ( f:)
end while
end for return (Co)o, v, (4 )ib.es
7 ESTIMATION OF THE COST DIFFERENCES
The second phase aims at obtaining high-confidence bounds for the cost differences (b,,, bi) for i E N. b,, lg E B, For each agent E N, the algorithm explores each pair b; by E B, and executes a binary search (BS) routine in order to estimate C,(b,, K(). leveraging the knowledge of the uncorrelated scoring rules 7," Yh b TT, In particular, playing convex combinations of the two scoring rules for N2 rounds, the algorithm finds two scoring rules 7 and 7 such that (i) - & M/2 (ii) 7 incentivizes b, over 11, and (iii) 7/ incentivizes is, over b2- Then, the algorithm estimates for N3 rounds the expected payments received by agent under scoring rules 7/ and 7/1 and uses such estimates, together with the bound on 1h% - >illo.. to obtain the estimator (b, b.) and the confidence bound Xi [b, Bj]. However, it might happen that the BS routine ends before finding such scoring rules, thus requiring a recursive execution of the algorithm. Due to space constraints, the study of those cases, as well as a more thorough description of ESTIMATECOSTS, are deferred to Appendix B To formalize the theoretical guarantees of ESTIMATECOSTS, we need the following clean event.
Definition 7.1 (Clean event for cost estimation). Let x = max4,b,.0 Xelb,, Bl1 The clean event E, holds if at the end of the execution of ESTIMATECOSTS:
(b, b)) x (, b() < A, B)) + X Wi Vb, bj. B,,
Then, it is possible to provide a lower bound on the probability with which & is verified.
Lemma 7.1. The clean event & holds with probability at least 1
Furthermore, to conclude this section, we show how the number of rounds used by ESTIMATECOSTS varies as a function of N₂ and N3.
Lemma 7.2. Let Ta be the set of rounds devoted to the execution of ESTIMATECOSTS. Then it holds that [aal 12 Nz).
8

---

Published as a conference paper at ICLR 2024
8 COMMIT PHASE
In the commit phase, the algorithm exploits the estimations of the probability distribu- tions and the pairwise cost differences. Here, the learner selects a sequence of mechanisms (n²,, 7", x²) E C. that pursues twofold objec- tive: the minimization of the regret R" and the satisfaction of the IC constraints, To find regret minimizing mechanism, we first obtain a mech- anism (n² 7., π²) from an optimal solution to LP E) through the function GETMECII- ANISM as specified by Theorem 3.1 where 2M SM/5/m// + X. The parameters chosen to guarantee that, assuming clean events & and Ep hold, the optimal mechanism (n* y >T") is in the feasibility set. Then, since the objective function of LP(C, &,&) and the one of (PP, C) have close values, it follows that -assuming that all the agents behave truthfully- mechanism (μ'', 56, x²) guarantees vanishing per-round regret w.r.t. (n* 7", )²" However, the following lemma shows that (n', 5 x²) is not IC and hence the agents
Algorithm COMMIT
Require:
E, U, X, Construction of IC mechanism
E + 2M my + X
(Ø', D fi x²) < Opt. solution to A, (n', 1n',", x + GETMECHANISM VV (4")
Define of in Eq. & Vi ViE..
Commil rounds
while S T do
Commit to mechanism (x², xx)")) end while
incentivized to behave truthfully.
Lemma 8.1. Assume clean events & and Ep hold. Let (μ,, 7, T)) be an optimal solution LP(C, A, E). where 2M (m X. Then, letting À 2M (k: + 1) (v + x), it holds that:
F( F.: (H,
Σ
[bb o(..))
vi Vi v(o,))
We recall that, in light of the discussion carried out in Section 4 committing to non-IC mechanism yields an unpredictable response of the agents which can induce a constant per-round regret in the worst case. Thus, provide a modification of (μ²', 7", x²) that makes the mechanism IC, while maintaining vanishing per-round regret w.r.t. the optimal mechanism. To do so, we exploit the posterior estimates & obtained during the estimation phase, as well the scoring rules I described in 4mg- We define two coefficients a (pf) (pe + 65A) and = (45 + (18p 45 + E). Moreover, for each agent we define the uncorrelated scoring rules (4 b. such that
Assumption particular, let i bi.s,, [1 <b..e 11.. E = i+ 4mg and f
7/2 [si, 0J
Sb... [0] + Hi
12
E E St 40 E
2
where H, = maxi _11 b,.s, 11 and the correlated scoring rule of such that:
bb,, 8,0 of. 8, + a)) [B>5 [st, 0 -31, ( 0] vb E BVs E (8)
The correlated scoring rule 7ē is a convex combination of the correlated scoring rule 5 and two
uncorrelated scoring rules 7; and 1. The latter two compensate the violation of the IC constraints of 9t. as shown in Lemma 8. In particular, scoring rules 4%/1 are designed to strictly incentivize agents' truthful reporting. We conclude proving that 14',n", T') is indeed an IC mechanism.
Assume clean events &., Ep hold. If mechanism (n², r², T²) is chosen according to Algorithm then is IC, i.e., if satisfies Equation (Tb) of optimization problem 7
Lemma 8.2,
Lemma 8.2 provides the formal guarantees on the incentive compatibility (μ', "', T'). ). By noticing that the parameter is chosen to balance correctly the regret minimizing scoring rule ÿ' and the other two uncorrelated scoring rules, we can recover sublinear regret during the commit phase. We refer the reader to the proof of Theorem 5.1 for the technical details on this aspect.
We remark that also scoring rules in incentivize such truthful reporting (see Eq. 4 ) but not a strict way. Thus, scoring rules 2. is necessary compensate the IC violations of n²"

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This paper supported by the FAIR (Future Artificial Intelligence Research) project, funded by the NextCieneratioEUU program within the PNRR-PE-AI scheme (M4C2, Investment 1.3, Line Artificial Intelligence), and by the EU Horizon project ELIAS (European Lighthouse of Al for Sustainability, No. 120237..
REFERENCES
Tal Alon, Paul Dütting, and Inbal Falgam-Coher Contracts with private cost per unit-of-effort. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 52-69, 2021.
Moshe Babaioff, Michal Feldman, Noam Nisan, and Eyal Winter. Combinatorial agency. Journal of Economic Theory, 147(3):999-1033 2012.
Martino Bernasconi. Matteo Castiglioni, Alberto Marchesi, Nicola Gatti, and Francesco Trovò. Sequential information design: Learning to persuade in the dark. In Advances in Neural Information Processing Systems, 2022.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Francesco Trovò, and Nicola Gatti. Optimal rates and efficient algorithms for online bayesian persuasion. In International Conference Machine Learning, pp. 2164-2183. PMLR, 2023.
Federico Cacciamani, Matteo Castiglioni, and Nicola Gatti. Online mechanism design for information acquisition. In International Conference on Machine Learning, pp. 3299-3326. PMLR, 2023.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online Bayesian persuasion. In NeurlPS, pp. 16188-1611 16198, 2020.
Matteo Castiglioni, Alberto Marchesi, Andrea Celli, and Nicola Gatti. Multi-receiver online bayesian persuasion. In ICML. volume 139, pp. 1314-1323, 2021.
Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Designing menus of contracts efficiently: The power of randomization. In EC '22: The 23rd ACM Conference Economics and Computation, pp. 705-735, 2022a.
Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Bayesian agency: Linear versus tractable contracts. Artificial Intelligence, 307, 2022b.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Regret minimization in online bayesian persuasion: Handling adversarial receiver's types under full and partial feedback models. Artificial Intelligence, 314:10382] 2023.
Siyu Chen, Jibang Wu, Yifan Wu, and Zhuoran Yang. Learning to incentivize information acquisition: Proper scoring rules meet principal-agent model. In International Conference on Machine Learning, pp. 5194-5218. PMLR, 2023.
Yiling Chen and Fang-Yi Yu. Optimal scoring rule design. arXiv preprint arXiv:2107.074200 2021.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. Communications of the ACM, 52(2):89-97, 2009.
Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen. Simple versus optimal contracts. In Proceedings of the 2019 ACM Conference Economics and Computation, pp. 369-387, 2019.
Paul Dutting, Tim Roughgarden, and Inbal Talgam-Cohen The complexity of contracts. SIAM Journal on Computing, 50(1):211-254 2021.
Guru Guruganesh, Jon Schneider, and Joshua R Wang. Contracts under moral hazard and adverse selection. In EC '21: The 22nd ACM Conference on Economics and Computation, pp. 563-582, 2021.
Yingkai Li, Jason D Hartline, Liren Shan, and Yifan Wu. Optimization of scoring rules. In Proceedings of the 23rd ACM Conference Economics and Computation, pp. 988-989 988-989,95 2022.
10

---

Published as a conference paper at ICLR 2024
Eric Neyman, Georgy Noarov, and S Matthew Weinberg. Binary scoring rules that incentivize precision. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 718-733, 2021.
Caspar Oesterheld and Vincent Conitzer. Minimum-regret contracts for principal-expert problems. In Web and Internet Economics: 16th International Conference, WINE 2020, Beijing, China, December 7-11, 2020, Proceedings 16, pp. 430 443.. Springer, 2020.
Maneesha Papireddygari and Bo Waggoner. Contracts with information acquisition, via scoring rules. In Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 703-704, 2022.
Leonard J Savage. Elicitation of personal probabilities and expectations. Journal of the American Statistical Association, 66(336):783 801, 1971.
Jibang Wu, Zixuan Zhang, Zhe Feng. Zhaoran Wang, Zhuoran Yang, Michael Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient reinforcement learning. In Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 471 4722 2022.
Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. The sample complexity of online contract design, 2023.
You Zu, Krishnamurthy Iyer. and Haifeng Xu. Learning to persuade the fly: Robustness against ignorance. In EC, pp. 927-928, 2021.

---

Published as a conference paper at ICLR 2024
A
RELATED WORKS
The study of information acquisition has been mostly confined to economics. However, in recent years, computational problems related information acquisition have received increasing attention. Several works have focused optimization problems related to the computation of scoring rules (Chen Yu, 2021 Papireddygari & Waggoner, 2022] Li et al. 2022, Neyman et al. (021). The closest to our work is (Chen et al. 2023), which studies online learning problem in which
principal acquires information from single agent. Chen et al. (203)) provide ( regret bound. To the best of our knowledge, ours is the first computational work that considers scoring rules with multiple agents. In the online multi-agent information acquisition problem, (Cacciamani et al. 2023 is the closest work. Cacciamani et al. (203)) study an online mechanism design problem without money in which the agents' utilities depend on the principal's ' action and the principal tries to incentivize the agents to report the information playing agent- favorable actions. The information acquisition problem is also related to the principal-agent problem, a.k.a. contract design, in which payment scheme to incentivize an agent to play a hidden action (Babaioff al., 2012, Guruganesh et al.) 2021 Alon al., 2021 Castiglioni al. 2022b a Dütting al. 2019; Dutting al. 2021). A recent work that is closely related to ours Zhu et al. (2023), which studies the repeated interaction between a principal and an agent, providing sublinear regret bounds. Finally, online information acquisition problem is related to Bayesian persuasion in online settings (Castiglioni et al. 2021 2020 2023) Wu et al., 2022 Bernasconi et al.) 2023). The
principal designs an nutcome-dependee
works closest to ours consider online problems in which the agents do not know the prior over the states of nature. [zu et al. (202T) studies an online persuasion problem in which the sender and the receiver do not know the prior. Bernasconi al. (2022) extend the analysis to sequential games.
B MORE DETAILS ON COSTS ESTIMATION
Algorithm ESTIMATECOSTS
Require: N2, NN, for i E N do for b,, b/g
E B,
By do
b. ET,
Y
b rr
A (b, b)), Xibi, bJ + (i, by 1/, 7/ Ne, N2, N3,
end for
end for return (Ai)EEN b, xilbi,b]
In this section we exhaustively describe the algorithm for cost estimation. The pseudocode for the main algorithm is presented in Algorithm For each agent E N, the algorithm iteratively explores each pair b,, 6/ E B; to obtain an estimate (,,b, b() of the cost difference Cg(b, 6,) as well as an high confidence bound Xi (b, b.] such that
(b, b0) Xalb, 69] S C, b/) S A, bG) xrlb,, b4].
To this extent, we leverage the knowledge of scoring rules T3 described Assumption and use them as starting points of binary search routine that is described below. As input to the Algorithm, we provide the number of rounds N2, Na that regulate the amount of rounds used by the binary search routine, the scoring rules I' described in Assumtpion I and the desired confidence level ô.
B. BINARY SEARCH
The pseudocode for BS is presented in Algorithm 5 For clarity, we fix agent A and two actions b,, by E B, and describe the execution of the BS algorithm for estimation of cost difference C,(b, b,). Intuitively, the binary search routine between the actions b,, B, is structured in three distinct phases. The first phase is a search phase that implements a search over the space of scoring rules obtain two uncorrelated scoring rules 7/2 % S, O [0, M] with appropriately
12

---

Published as a conference paper at ICLR 2024
Algorithm 5 Binary Search (BS)
Require: i. b/y Vo. Vi N2,NN,, No. 8
T T[8,0) = =1/d v8 S, va E A
Search phase
for t [N2] do
Y: 2% + 1/
Commit to (7, ④) and observe 8y
if bf b; then
Vi 6 %
else if 6; = by then
Y +
else
Split phase
21, 1/1 < BS(i, bi, b4, 7, N2, Na, V,A.,
22. 1/2 BS D4 9,76 , N2, No, Ai Xi,
return 21 + 12, U1 + y2
end if end for
Payment estimation phase Commit for N3 rounds to (7: π and observe 7 0*1 for t E [Ng]
Commit for N3 rounds (7', TT) and observe 7 [8% #* for [Ng]
F1,31 t- compute in Equation 14
return 21. /1
bounded distance between them such that y, incentivizes action b, and 7/ incentivizes action 6/- The second phase, i.e. the payment estimation phase, estimates the expected payment received by agent i when the principal commits the two scoring rules 7/ and 7/2 and uses such estimates to recover an high-confidence interval for the cost difference (b,,, 69). The third phase is called split phase and is needed to manage all those cases in which the scoring rules found during the search phase are not adequate to recover meaningful upper and lower bounds for the cost difference.
The algorithm takes as input the agent i, the actions b;, by, two uncorrelated scoring rules YYa 7/ S, θ + [0, .M] that incentivize action b, and b/. respectively, and the desired confidence level d. To formalize the characteristics of scoring rules Ya. 7. we define the maximum expected payment received by agent when the principal commits to an uncorrelated scoring rule ?/ and agent plays action b; B;, using a best-response policy for signal reporting:
Σ
Σ p(t) (si, 0lbe) (elp(()).
max p
7 incentivizes action 1/6 by noticing that Then, if 7i incentivizes action by and Cb(bi, 60) (b,, b.), we get that
(P(7)(b)) (x)1) 2 C,(b, (4 F7 (7/1))) < C, B().
(9a)
(9b)
Equation 9 provides a rather natural way of finding upper and lower bounds to (b,,, Ky). We will leverage this idea obtain estimator for C2 (b,,, K)) In the following distinctly analyze each of the three phases of the algorithm.
Search phase. The search phase for agent between two actions b,, by E B, aims at finding two uncorrelated scoring rules Yi 7 that satisfy Equations (9a) and (9b). while also guaranteeing that || - Ao S for some 1) > 0. To do so, for N₂ rounds we interpolate between the two scoring rules and iteratively update them using the feedback received from the online interaction. In particular, let ( (b., b() be the of rounds used by the search phase, when we want estimate
Recall that uncorrelated scoring rule " incentivizes action b; if 9y (7%) by.
13

---

Published as a conference paper at ICLR 2024
the cost difference Ci(b,, K)) Then, each 1 E T. 4. (b:, 1(), the principal commits scoring rule % = 177 + +2 and observes the action bj = (5) played by agent i. If bjj = b; the scoring rules " incentivizes action b; and thus, we proceed by updating 7/- = % Similarly, if ig b,, then the scoring rule 7 incentivizes action iú and we update of = %. If, instead b2 + b,, Ui, we enter the so-called split phase, which, for clarity,
describe next. If we never enter the split phase, the search phase ends after N2 rounds (i.e., when [T (b,, 62) = N2). At this point, scoring rules % 7/ satisfy Equations (a and (9b), since the feedback received from the environment guarantees that bf (7t) = by and (x() By. Furthermore,
show the following bound the distance
between the two scoring rules.
Lemma B.1. For any agent E N and actions by, Ug Be, assume the search phase is completed without entering into the split phase. Let " 7/ be the scoring rules obtained at the end of the search phase. Then the following holds:
M
1h - 7/11o S 2N
Proof. Fix agent and actions b,, by E B,. Let d' be the distance between scoring rules and 7i at iteration t T (b,, K)). With an abuse of notation, we denote as d the distance between the two scoring rules at the beginning of the search phase. Trivially, it holds d S.. Assume without loss of generality that b = by. Then, we have that
++ lh: 7:lls0 = lm 2 2 1r -7llo = Zd
21
=²d
(10)
Thus, by recalling that if we do not enter the split phase, then [T (b,, B,)1 = N2, can iteratively apply Equation 10) to bound N² and obtain the result.
After the completion of the search phase, the algorithm enters into the payment estimation phase, in which we leverage knowledge of the scoring rules Yi 7/S to recover an estimate of Cb(b, b().
Payment estimation phase. The payment estimation phase starts after the completion of the search phase. In this phase we aim at finding estimates of the expected payments F (7)(:)) and Fy (7) and then use those to obtain an high-confidence bound for (b,,, K)). leveraging both the properties of and y mentioned above and Equation In particular, notice that when the principal commits uncorrelated scoring rule 7/s the payment 7 0*] is an unbiased estimate of F/ (rra (b:) since:
E ha (1, 0²] = Σ
Σ
Tp()) (s,, 0 (76) 75 (su)re))
s: BEE
pp()) (s,, 0lb)) (12)(ssm))))
max SAS: S s:ES 8CB
(r)(b.)
F9 Similarly, when the principal commits to scoring rule 7/ it holds that E = Thus, in order obtain high confidence bounds for the expected payments F. (7r (b;) and Pi (n/ B)) we commit to each one of the two scoring rules for N3 rounds and obtain the following estimates,
(x(())b))))
Σ
69
F
Σ
Ais 0*),
N₂
N
(T))
KET (0
where T.19) (75) denotes the set of round in which the principal committed to scoring rule Y during the payment estimation phase. Moreover, using standard concentration arguments, we can provide the following high-confidence bounds for the estimated p.p.
Lemma B.2. For each 7, S, x - [0, M), each d E (0, 1) and for each K O, the following holds:
In (2KK/8)
8
P ( (7(rbbb) $ M
2 1 K
2N
14

---

Published as a conference paper at ICLR 2024
where b, bg (7t).
Proof. The result follows directly from Hoeffding's 's bound, noticing that for all E (xp))))
S 7115% 0*] z M, for all E TTp (1)). S 7/15% 09]
I M and that
(rili)) = (Ti(be),
E (PGG = (761))
Starting from Equation (9), the last elements needed in order obtain an high high-confidence interval
for the cost difference C,(b,, 8)) are estimates for the expected payments F (T(iiibi) (b{) and F. ( (b))
We observe that, differently than F. (7iiii (b)) and F (>((b)) it is not possible to estimate F3 (7 b
and FT (Y/16,) directly using the feedback collected from the online interaction, since every time the principal commits to scoring rule Y,. agent i would respond by playing action 6; rather than action b
(the same holds for scoring rule y' and action 6,). Nonetheless, it is possible to leverage the bound
on the distance between YY and 7 shown Lemma B.1 to address this issue. Formally,
Lemma B.3. Let Yi, Y St x O + M] be such that 11%: - Alloo S 1). Then, for each by E B, the following holds
(F(())b)) - (7/1b)) s
Proof. Fix by E B, Let P, & be such that
s E arg max S:
Σ
p(t) (s; 01b,))))))))) 7=(((s)).0)
S.ES, OE
max F E arg
Σ S.ES AEO
p() (st, (1, (((()
Then, we have that
F. (T(b.)
Σ p())
(st, (b,) ()
EEe
Σ p()
(s,, b.) (s))
#
2 Σ p(()
(si, 0 b.)) (F
AE0
P. (b:) - 7
and, similarly,
F? (r
Σ
p(()) (s,, 01b,) (l))
8ce
Σ
pP() (s
(p(s))))
RE0
Σ
[P())
(si, 01:b) 71 (1
860
(r(()) 77
Combining the two inequalities, we get
F.(T/bb))) - S F((7)bb) & F((T(b))) + n
which gives the result.
15

---

Published as a conference paper at ICLR 2024
In the following, for each agent i N,, we define D, S B; x B, the set that contains all the couples (b,, b)) for which the execution of the binary search reached the cost estimation phase. Furthermore, for each i E N and by D; let Vi,b, and Yi,o be the scoring rules found at the end of the search phase, incentivizing actions b; and B/, respectively. To conclude the analysis of the payment estimation phase and to show how to leverage the results of Lemma [.]] Lemma B.2 and Lemma recover upper and lower confidence bounds for the expected payment (, b,), we introduce the auxiliary clean event Eg.
Definition B.I (Auxiliary clean event for cost estimation). The clean event & holds if
In(nk2200
(HL,, FP(T),,,bb))) & M V
2Ng
WEE V(b,, bi) E D,.
In(4nk2/0)
(Han))) (P S MV
2Ng
Lemma B.4. The clean event Ea holds with probability at least 2"
Proof. By Lemma B.2 we have that
1n(4nk2/8) /5)
5
P (1,,,,,,),)) F? (mr,0166)) S MV
N 1
2N3
2nk:2
WiE, (b,,b)) ED.
In(4nk2/0) 28)
P
(T),))))))) - (m.,))16) S M
1
2Ns
2nk
The result follows from union bound, noticing that
Σ iEN (b;
2nk2
2
The introduction of the auxiliary clean event allows to define, for all E / and for all pairs of actions (b,, 1)) E "D for which the binary search algorithms reached the cost estimation phase, the following estimators and confidence bounds:
(be, b,) = F F. (YY,,) (b))
(14a)
In In(4nk2/ 15)
M
X 1,, bj] = 1
(14b)
2N3
2N2
We formally prove that, if event Ea holds, then the above definitions yield, indeed, valid high- confidence region for the pairwise cost differences.
Lemma B.5. Assume clean event Ea holds. Then the following holds: vi v(b,. by) D,.
[A,(b, b)) - Ce(br, bb)l S xilb,,b) b1
Proof. Fix i E A and (b,, b() D. By Equation Dap. have that C,(b,, bb) Fí (Tr,,, (7 1b()
(15a)
M
(r.o, Fr (b() +
(15b)
2N2
M
In(4nk2 /8)
< Ff....) ( (b() +
+ 2M
(15c)
2N
2N3
16

---

Published as a conference paper at ICLR 2024
where the first equation follows from Lemma [B.3 and Lemma B.1 from the definition of Ed. Similarly, from Equation 9b), we get
while the last equation follows
Ca(b,, bi) F. (T).::bb))) F. (7%,0, (6{)
(16a)
M
(T F. (7V,02 (6()
(16b)
2
M
Iu(4nk2/0)
2 (mr,,,))))) F7 (b1
2M
(16c)
2
2N,
where, also in this case, the first equation follows from Lemma B.3 and Lemma B. while the
last equation follows from the definition of &a- The result follows by substituting the definitions of (b, 6,) and x. 6[].
Split phase. The analysis of the payment estimation phase suggested that whenever we are able to successfully complete the search phase, then we can easily recover high-confidence regions for the cost differences. However, unfortunately, this is not always the case, since it might happen that during the search phase for agent and between two actions 6,, b' B,, the agent responds with an action ö which is different than b, and 6,, thus causing the search phase to end. In such a case, the algorithm enters the split phase, The intuition upon which the design of the split phase is based is that the cost difference C,(b, 66) can be expressed in terms of the cost differences C,(b,, 6f) and (b,,, bt) as follows:
C, 80) C,,b,, b3) + (,(
Then, this shows that it is possible to recursively obtain an high-confidence interval for Ci(bs, k)) starting from high-confidence intervals for (b,b, b() and C,( 83). In particular,
(b,b, +))+A.( (4) [b,, b1] -x MI s (bb,, bt) S (,, +))AA.00 xxiles b M1,
which allows us to define the estimator and confidence bound for Ci(b,, 16) as
(b, b)) = Ac(b,, b1) + A, (,, 14) Xi [6, by] = x lr, 63] + xx10%, 61.
Hence, when the algorithm enters into the split phase, it instantiates distinct bynary search routines, one for estimating the cost difference (b,,, 03) using starting points the scoring rules % and 7: and the other for estimating C, (b6) 16) starting from scoring rules 7. and %
We proceed by bounding the number of times the algorithm enters the split phase, thus allowing us to bound the number of rounds used by ESTIMATECOSTS, as well as the high-confidence bound X = ma Xi (b, b1]. To address this question, we consider the binary search procedures instantiated by the main loop of the algorithm. For the sake of presentation, let us fix an agent i and two actions b/ r, Then, b,, &/ B, and consider a binary search between the uncorrelated scoring rules > 7 the maximum number of times the algorithm enters the split phase during the process of estimating the cost difference (b,, 16) can be characterized by investigating all the possible convex combinations M of the two scoring rules 7 Y. In particular, introduce best-response (BR) regions, i.e., sets g, B)) C [0, 1] such that for each a E G. solbe, b,), the best response of agent to scoring rule 7 M. an b. + (1 a) does not change. Formally,
glb,,, b)) = { [0. (7 abibk) = b, (s (a.il (p(ss)
Vss E s
Trivially, [0.1] U Gi(bi, plbb, b)) and G, spbb, 0)) (i Il b() = 2 for all 0, 8, E B and for all sp, pp S, + St, thus, the set
g (ō, sbbb, b)) by B,, 4 S; + S., g,(b,, pb 8)) + の)
provides a partition of [o, 1]. In principle, [0, 1] can be partitioned in many BR regions (since the number of different signal reporting policies yp : S; S, is ('). As show next, there exist in fact limited number of non-empty BR regions. Before proving such result, we introduce an accessory Lemma.
17

---

Published as a conference paper at ICLR 2024
Lemma B.6. Let H. C IR be closed, convex subset of R and {G) ...., g" be set of partitions
of H. where G = {G),..., G,,} with Gj convex for each i, E [n]. Let P = [PP....,PPm be
partition of H such that for j E [n], Pj = Nie(m) (eem)))((.))) (6.2) for some f(i,j) E [n]. Then, it holds that m n² n 1.
(()) J. for m(k) E Nso be partition of H such that for each [m((k)),, P(()) is convex and Pf()) NEj G (1.)))) with (1,5) E [n]. In other words, (()) is set of non-empty and disjoint intervals p/() C H such that Ujem(k) ((k) = Ht in which each element P/A) is obtained as the intersection of one element from each [g] .. Similarly, define p(k-1) = {P| (p(k-1) : , p((k-1) m(k- for
Proof. Let p(i) = G' and m(1) n. Let now (pk) = (P(M) ..... Pul
m(kk - 1) E Noo be
De G² (1x-) for (i, [n]. Notice that, by definition of 1), in holds that Vý E [m(()], p)()) = G n p, for some a E [m]. b E [m(k - 1)]. Furthermore, it is easy to see that by convexity of every p!k-1) and GJ. m(k) can be at most n + m(k 1) - 1. Thus, we can conclude the following chain of inequalities: m m(n) n+ m 1) - < mm This concludes the proof.
partition of H such that for each j [mo(k - 1)], P/
(n-1))+mmil (n 1) -
We proceed to bound the maximum number of non-empty BR regions.
Lemma B.7. For any agent i and actions b,, b/ B;, there exist most kl? non-empty BR regions, i... | < kla, Furthermore, for each b; B; and yp S; + S,, the set Gi(bi, :lb,, b)) is convex.
Proof. Fix agent and actions by, b/ B, We first prove the convexity of the BR regions and then we proceed to bound their number.
Convexity. To prove that the sets (b; =/bb, bt) are convex for each 0, E B, and yp S; -> S₁ let us explicit the constraints defining such sets. particular, imposing that and oo are BR for agent i equivalent to imposing the following constraints for each E B, and for all yp S - Sy:
Σ Σ
pp())
(1.)) % .b..% ( [s(s)), 0 - -p()) s/ .16b) Yi ah, (8 (s.), 0] 2 0.
S; BEE
Clearly, since % convexity of the set.
is a linear expression in a, all the constraints are linear in a, thus implying the o,
Bound on the number of non-empty BR regions. To bound the number of non-empty BR regions, we introduce, for two signals 8;, s E St and an action E Br, the set G, (b,, 8,, s/Ibe, b() S [0, 1]. containing all those [0, for which agent i's BR scoring rule 7, o.hi, after having played action by B, and having observed signal s; E S,, is to report signal s/c. Formally.
Gi(b,, st (,, 60== aa E [0,
Σ p(o s/ 01:6)) a. (0.. 020
[5/.00 -4.00-1: 7
a.b.% [3 1
00 2 0 V3, E S
Furthermore, for each b, E B, and p St S. we let, with slight abuse of notation, G, spbs, bp) be the subset of (0, 1] such that, after having selected action b. the best-response policy for agent to scoring rule y; o.b..% is to report signals according sp. Formally,
Gi(b,, G/b,, 8)) a E [0. 1]
Σ p(o) 81, 0/b,)
a.b.0% [(p(s)). --, (1
- 1..bb:013,
Vs, & S
8EB
18

---

Published as a conference paper at ICLR 2024
By definition, each (, splb,, 8,) can be obtained the intersection of suitably chosen BR regions Gelbi, St, s/Ib;, (,), i.e,
G.(b,, blbe, B,) M.Es, Gi(b,, 84, 41, (ss))), b()
vb. E Ba, : S.-
Moreover, we highlight that, by definition, for each 6; E B, and E Sü the set (G, Si, s,lbi, 6,)
& E St) provides partition of [0, 1]. Then, by Lemma B.6 we conclude that [G, (h,, plbs 1)) S 1 12-1- 1+1. Notice that, in general holds that for each b, B, and p S - S₁ Gb spbb, b() 2 9, (l,,, b(), since by definition of G, splb, 1(), for each a belonging to the set, the signal reporting policy yp is a best-response for agent to 7 a,b., after the agent played action b, but nothing guarantees that action b; is a best-response itself. To conclude the proof it is enough to notice that, in the worst case, for each 6, E B, and y S; - S₁ Gi(bi, splb,, bt) = Gi s/b,, i() and since the number of non-empty Gz to lbs Kt) is at most 12 + 1, we can conclude that [9] k(( 1+ 1) S k This concludes the proof.
The result Lemma allows us to bound the maximum possible confidence bound as follows.
Lemma B.8. At the end of the execution of ESTIMATECOSTS it holds that
In In(4nk²/5)
k
max max iEN b.K,
Xi!b,, 2k M
+ 2N2
2N3
Proof. By Lemma B.7 since for each i N and for each bi, b2 E B,, [0, 1] can partitioned in at most kl? convex BR regions, the condition for entering the split phase will be triggered at most | w/² times during the routine for the estimation of Cb b(), triggering the beginning of a new search phase at most kl2 times. The result follows since the confidence bound xi (b., 1t] is obtained as the sum of all confidence bounds obtained at the end the corresponding payment estimation phases, hence:
Xalb,, 61 S 2 In(4nk2/0)
kPM
2N3
N
This concludes the proof.
B.2 FORMAL GUARANTEES OF ESTIMATECOSTS
We conclude this Section by formally proving main properties of Algorithm Lemma 7.1. The clean event & holds with probubility at least 1 - 5
2.
Proof. Assume auxiliary clean event Eg holds. By Lemma B.5 for all i E N and for all (b,,b)) E D..
[A,(,, 66) - C.(b,, 61) S x1 61] S x.
Then, let fix i A and consider couple (b,, D,- Let D, b() be the set that contains all the pairs of actions (b,, i() for which the payment estimation phase has been reached during the procedure for estimating C, b)). Then, the algorithm guarantees that
Cr(b,, b))
Σ
C,(6,, B/).
(b.
The result follows from Lemma
B.5 noticing that D, b3) E BED Ar(b, B(), and x: Eo..))ED x: Bs].
C D, Ar(bi,bi)
Lemma 7.2. Let Ta be the set of rounds devoted to the execution of ESTIMATECOSTS. Then it holds that [Tal (N2 Nz).
19

---

Published as a conference paper at ICLR 2024
Proof. By Lemma B.7 since for each i W and for each b, 8/ B,, H,(b,, b() can be partitioned
kf at most kl? BR regions, the agent will change her action at most 2- times during the routine for the estimation of (b,, 6,), triggering the beginning new search phase at most kd² times. This implies that
Tal S Σ
Σ iEN b.
IP + Ns) S nk n + Na).
This concludes the proof.
C PROOFS OMITTED FROM SECTION 3
Theorem 3.1. Let (a*,, y², ,t"", x=) be an optimal solution LP (IP, C,O), where C' (Ci Cn.. Then, let y* = (Yi, Yn) and π be such that
oi lb.00 6
fp 0 otherwise
y b.... 1=
1/ + #0
1/ b, s, 0
x
xb s. al
otherwise.
Then (n², ,"', ) is an optimal solution to Problem
Proof. We start the proof this theorem by showing that (w", y ,²") ) is feasible for optimization problem
Then, prove that (μ", yY", xT*) is also optimal.
Feasibility. First, notice that
0 ( 2 M Vi E, Ab B 10 EO,
thus guaranteeing that > is valid scoring rule. Furthermore,
EoEA [
vb.aa w
1b 40 =1 Ab E B, Vs S
Σ aEA
T' (, s, al
otherwisse
which implies that क is valid action policy. For what concerns incentive compatibility, for each e E let us notice that:
Fi(p", x
1 [b]]]] (b, (s,
(17a)
#
x;(b, [b, s, (), (b)
(17b)
be S deg
ΣΣ Σ beB, sES, b_,EB_,
b.), (8)
(17c)
860
E BEB, SES;
(17d)
20

---

Published as a conference paper at ICLR 2024
Similarly, for each E W and for each (Ø. yp) Ø2:
P. (1² = Σ
M 16 lb, (9((1,, si), 8-1), 0JP (s, (b,,, b-i))
(18a)
be
#
Σ
(18b)
beB ac8 BgG
Σ Σ
Σ
(s
(18c)
Pe sES, b-IEB_;
8-
BEB
Σ Σ
T,, ((b), sbb,,,,)))))))))))) P),
(18d)
BEB, sES:
Σ
(b,b)(b).ss)
(18c)
BeB, SE
where the last incquality follows from feasibility of (x" y², ,,,"=) ,²*). Combining Equations 17d and (8c). we get:
File" - (1"
Σ
Σ
-21b,,))))
(19a)
bE B; sES,
Σ
1 (((b)bb))]]((0))((((
-
(19b)
BEB; b.,
Σ
(c co(((b)))).
(19c)
where the second inequality follows from feasibility of (x* y" p², x²). This proves the incentive compatibility of (M², y ).
Optimality.
To prove that (μ*,, y" )T* is optimal, assume, by contradiction that there exists an IC mechanism (j,, y. T) such that U U1, 7, T) > Ul"" T²). Let (æx, y, 2) be such that:
2 b 8 = μ|b/% b. s, 8
E, vb B, V A
y/b, s. a) n|b]m(ss Bb Vs E, Va A
26,,6', max (f b', s,s. ViEN, vb, E B₁ Vs S.
Let us notice that (æ, ,4 2) satisfy, by definition, constraints 2ch. prove that they satisfy also constraints (2b), for each N and 6, B, let (0, sp) & be such that:
(2 and 2e of LP(PP C, To
10 V 6"
if otherwise
o(b")
and ((b",s) =s Ab" B, (b), Vs E S..
21

---

Published as a conference paper at ICLR 2024
Then, by incentive compatibility of (H., 7, r):
Σu(b) (c) c(((6))) BEB
Σ (((() c(6)) b b-IEB_1
(2la)
P((H,)) - -(( (1:))
(2lb)
(s)
o
(b:))))
beg seS AEe
(21c)
Σ x4 b s, Pss (s, x, 1, (b,, s.). 0PP (s, 0((b, ((b,))
beB
S A
(21d)
Σ [f(x fi(w;lb, s,b, (0b, s))]
(21e)
SES,
[f( 2,1b,6 b', s]]
(21f)
SES;
Thus we can conclude that (x, y, x) is feasible for LP C, 0). Moreover:
y|b, s, Σ [P(s.00))(a)00))
-E
z; s, 0JP (s,0
(22a)
BEB
SEN BEB
AES
u s,
P (s, u(a, [P(S.)D)u(a00)1
Σ
Σ Σ
[bb)% s, (s) (22b)
BEB BES aEA
MEE
be
#ES
= Ulu,7 7, b)
(22c)
Ulu ,²)b")
(22d)
]]
1r" [b] [b, 8
Σ P(s EP(ss((b)
ΣΣ (,
bEB
AEE
TEN be
(22e)
lb s,
Σ P (s, B(b) u(a.
ΣΣ x; b, s, (s.
(22f)
DEB 8E3
aEA
0EB
which contradicts the assumption the optimality of (x*, y" ,", x*). This concludes the proof.
D PROOFS OMITTED FROM SECTION 4
Before proving the formal results of Section 4 we introduce useful preliminary result.
Lemma D.1. For any uncorrelated mechanism (y, π)) U, there exists an equivalent uncorrelated
mechanism (Y', π²) E U which is truthfud, i.c., such that for any i E N and s; E S, (salr)) = S; and such that
U -r"))(+))
Proof. Let (Y', T') be such that
Nis 0 = (117(()177)) W, As, E S₁, V0 e e,
and
n [s - AsES, Va E.A.
22

---

Published as a conference paper at ICLR 2024
First, we show that for any agent i N, (6, (6). :p! ) is best response Y', where up is the #f
honest signal reporting function such that ii (s:) contradiction, that there exists b2 B, and sp:
for all 8; E S. Fix i É N. Assume, by 5 such that
ΣΣN MES, dEE
po()) (st. 016)) M (1,)
ΣΣ
MEr
pl() (s,, (106))((0) 0J c((b (r4)),
s,E8,
and let & : S + S such that ((((z) = 4 (p(((:))) Then, we have that
Σ S,ES; AEO
Σ
p() (s,, (1))))(())))) (12) c((((())))
Σ
p(() (s,, (0.00((()))) mis.. (x))))
#ES BEB
P(() (s,, 0 (1pp (b(b)
9:E8; BEB
IP()) (s,, 06) (s.) 0, (bb))
which contradicts the assumption that by (%) po (11r) is a best response agent i to scoring rule % To conclude the proof, we show that U (7, U' x'). Notice that
U (7,, nT
ΣΣ #ES BEB
P (s)))
Σ k|p (sm))
E
(24a)
ENN
ΣΣ
P (s, (x))
T rs(s [[s,a]u(a, Ex((s,jjua.00))
Σ Miss, 0] iEN
(24b)
AEB
= U (r T').
(24c)
This concludes the proof.
Now are ready to prove Theorem 4.1
Theorem 4.1. There exists a game in which no uncorrelated mechanism is optimal.
(b., h1) and S; = ( (8,,84) Vi E N. The action costs specified such that C₁ (bg. = c2 co (ba) 0, eq (b.,) < 1/24. The set of states of nature is θ = 02). The joint probability distributions are defined as in the following tables:
Proof. Consider a game in which N = (1,2), B;
IP (0, bb.b
8p
8.84
8q
8484
P (0, s/bpbb.)
8388p
8p34
8q8p
8q84
0
1/8
1/8
1/8
1/8
01
1/8
1/8
1/8
1/8
02
1/8
1/8
1/8
1/8
1/8
1/8
1/8
1/8
(0, 8lbbbb)
8,82
8p84
848p
5
(0, 8(baba)
8.88
8p.8q
8q8p
8g8c
1/6
1/6
1/12
1/12
01
1/3
0
1/6
02
1/12
1/12
1/6
1/6
0g
1/6
0
0
1/3
Optimal Uncorrelated Mechanism.
first step, we characterize the of optimal uncorrelated
mechanisms for this game. Since the cost of both actions for agent 2 is O, we can trivially 7/ = for each E 52 and 0 E to minimize payments without affecting the incentive compatibility of the mechanism. As direct implication of Lemma D.I. there exists an optimal uncorrelated mechanism which incentivizes truthful signal reporting, thus, in order to find an optimal uncorrelated enumerate among the optimal uncorrelated mechanisms incentivizing each action profile while incentivizing each agent to report truthfully her information. Furthermore, it easy to that, when players report their information truthfully, signal profiles (b, and (bgba) induce the
mechanism,
23

---

Published as a conference paper at ICLR 2024
same posteriors over the states of nature. The same holds for signal profile (babs) and (baba). Thus, we have that:
T|s, a|P (s, (b).bb))) u(a, 0) max
T|s, al (s,0)).))))))))) u(a, 1/2
(25)
max
T(8, a (s, (s,b)bbb))) u)a max
T(8. a|P (s, (s,0lbaba) u(a, =2/3.
(26)
Moreover, fixing the action profile b E B that want to incentivize, for any scoring rule % [0, MM R xxxxx consider the incentive compatibility constraints (recall that we can trivially ignore the incentive compatibility constraints of agent by setting 7/2 0 as discussed above):
Σ 71 (jp(2)) (s, 0(bi) - 71 (o(b), 8), (p((2) (s. (l)(b)) 2 ei (b sES; BEB
Ve, E L1,
while the expected utility of the principal when the agents behave honestly
}
(b) max ΣΣΣ SES DESDEEREE
( a (s, 0|b) u(a, 0) )
ΣΣ #ES dEG
p()) (s, (1,) n1s.0).
Noticing that, for any two action profiles b, b' B, if bf does not change and that, by equations (25) and (26). ((bbb,)) = (bbbb.) and (bbbb.)) = bb.b..) it follows that the problem can be reduced whether to incentivize action l. or by to agent 1. Hence, let us fix, without loss of generality, be as the action played by Since action be has a cost eı (bb) = 0 for agent 1, it can be trivially incentivized by setting Y1 = 0. guaranteeing utility for action profile (bp, ba) of U (b.baa) = 1/2.
then the incentive compatibility
single-agent problem in which have decide
Consider, instead, action profile balig Given scoring rule 7, the expected payment received by agent 1 is:
Fibbaba 7) = Σ Σ 11s 0)p(2) (s, 6(ba)
#E AEO
3 I'2 [sp
[sp 011 + 1s 02ll + 6 Imlss, 01] + r1ss, (ils,,02] 02]1
Similarly, consider the deviation (0) x)) E t1 such that (bba) = by and y(bb,, 8) = s for any 8 E Sj. Then:
(babar v) = Σ Σ [s, 0)1((1) (s,0
sESi dEe
[m 0.] + 1s 02] + 71 11 01] + 71 02]]
The associated incentive compatibility constraint is, therefore:
12 [s 01] 71 [8a, 02]1
12 In [s>, 0z] + 71 (1 01]] K.
Repeating the same procedure for all possible deviation functions, obtain the following incentive compatibility constraints:
1
(mi (sp,
0,] + 71 [sa, 02]]
(m [sb,
0g]
+ 71 [Sa, 0:]] 2 K
12
12
1
1
3
?'
[Sa, 0z]
+
6
[san 01]
Yi [sp, 0,]
3
71
[8, 02] 2
1
1
1
3 71 [se, 0z]
[8>,
01]
m (8q: 0ı]
71
[Sa, 0z)
2 K
6
3
01] + (8a, 02]l
[m [sa, (aa,00 0i] + 71
[sp,
02]] 2 0.
24

---

Published as a conference paper at ICLR 2024
Thus, it is easy to check that in order to minimize the expected payment, while satisfying the above constraints it is enough to select a scoring rule such that
T1 |5, 01 = 71 (s.. 02) 6K
?1 88, 02] 0
71 88, 01] = 0.
Since K S 1/24 by assumption, have that the optimal utility achievable by using an uncorrelated mechanism is 2/3 - -K..
Optimal Correlated Mechanism. Consider the correlated mechanism (Jt, 7, T) defined such that ya yibbalal = E and y [[bbby] e for some & = 12K/5 1/10. Similarly before, since all actions for agent have cost 0, can be incentive compatible by setting 72 0. The scoring rule for agent 1 is defined as:
7 b, s 0
vb E (b, bab babot. V v
71 bbaba s, {1]
Vs E S {8
bbg 02] O
Vs E S {$484}
71 (bbby Sp: 1 m milbbba, Sc 02]
Let π be such that E arg max {U,,, 7 T')} Simple calculations show that Un, x) 2/3 2z/3. It is possible show that the above mechanism incentive compatible. In particular, the expected payment received by agent is:
(1 7) 3
Consider any two deviation functions (ø, .p) E 2 such that ((ba) = by. The expected payment received by agent when she deviates according to (Ø) up) is:
F 7 =/4 Vip.
Similarly, for any deviation functions (d, (p) D; such that p(bb) ba the expected payment
c/3
if (bba, sp) Sa plbb, sa) Sp
20/3
if Tpp(be 80) = 8 (p 8a) = -84
E 1P (H,,) 7) =
0
if (ba, sp) sa A pbb sa) = Sp
e/3
otherwise.
Thus, the incentive compatibility constraints that are yielded are:
5e
12
2 0,
3
which are trivially satisfied since, by assumption, =12K/5 0. Hence, the expected utility of the principal is
2
212 3
Un, π
K
4K.
3
3
Any optimal correlated mechanism (u²,"* T)) achieves a utility U , U,, TT)> 2/3 4K, hence we can conclude that this game there does not exist an uncorrelated mechanism which is optimal for optimization problem This concludes the proof
Theorem 4.2. Assume there for each i E E 0 O and by E Br, there exists a probability distribution (bba)1b)) (SS)) such that vb E Vs and V0 O P (s. 0(b) = pi0 ILe (isss 0). Then, there exists mechanism (y, π ) U that is optimal among correlated mechanisms.
25

---

Published as a conference paper at ICLR 2024
Let (H²", ,²"xx") C be optimal correlated mechanism. For each b B, let G(b) be such Proof. that
G(b) = Σ
P (s, 8(b)
Σ x
Σ REN
75 [b, 8, 01
#ES DEB
LEEA
is easy to see that holds U arg ma [b]20 {G(b)) be the action profile yielding optimal utility to the principal and define the uncorrelated scoring rule 7 (71,.171 7x. be such that
Eber 1 (b) Let b
71.81 0 Eo LEB /r ((b,, b-il]
Σ 10 b b-i)
II (5,0),, (0 b-i), (8i, 8 8-1), JEN(()
b-.EB-. -.:.._
[8, [s = x [b, 8, al. possible to show that for each N, (be, sof) ) is best response for agent to uncorrelated mechanism (7, π), where off S; - S the honest signal reporting policy, í.e., such that o (s;) = s; for all s; E S.. In particular, notice that the expected payment received by agent when the principal commits mechanism (μ² , x)" can be written as
Furthermore, let æ such that т
Fi(p",
Σ pp()) (si, O(b,)
Σ 1'b b-i) II (y(s))b; b-1), (8i, o))), b_.EB_. :E8
b.EBB
JEA(()
and similarly, for each (Ø, s2) E D..
p (n²", ,Y))
Σ pp(t) ((((be) b.E.. $1ES. AEG
Σ (0is b-:) II ()7 b b)x), (pp(br, 8i), 8 jEA(()
b-.EB_. 8 8...
For any by E B, and vp S. + Si, let (p) E Φ be the deviation functions such that ((b,) = b, for
all b, E B, {b.). @(b,) = b/, (bb,, s;) = s, for all b, E B, [b:b and s; S,, and (ob,, 8.) = (s.(s))
for all E Sg. Then, by substituting the definition of 7 into the expressions for F; and F. we can write the following:
F((H",>)) (M" (M)
Exm(b biill
Σ S.ES; dEe
Σ
pb)) (s%, 0(b.) niss,, 0] (p()) (st, 016() [ld((ss),
(27a)
6-,EB_,
2 Σ [0r C,)C,,
(27b)
b..EB_.
where
27b follows from incentive compatibility of ("", By dividing for
E. bb_ EB 1e [(be, b-1),, we get
Σ
pp()) (si, (b:))) 71s6, 0] -p(i (s;, 01, (s)) o]] 2 Ci(bs,
8:ES, BEB
which proves that (b,, 1pth ) is a best response of agent to mechanism (T, U. The result follows by noting that U (7, π G(b) U(H", 7 T²).
E PROOFS OMITTED FROM SECTION 6
Lemma 6.1. The clean event Ep holds with probability least
26

---

Published as a conference paper at ICLR 2024
Proof. By Hoeffding bound, we have that
P ([Cb|s, 0 - (s, 016] < - K
vb E B, E 40 VO VI Ub Tp and similarly,
P ( (9)
( - p() (0 [0)b; 8;) S 21
5 K
b.,s
N, vb, Bi, vs, S, 40 6, Vt UbTp(b).
Moreover, let be such that [b) 2 n. Notice that for any i N and st E S
ITp (b., s,)l Σ Σ
1| = s.].
8'EB: (ETx(') &.=b.
Therefore, |Tp (1) (bi, s4)l can be seen as the sum of sequence of Bernoulli random variables with parameter (() (s: b,). Additionally,
E
T (b,, st)
Σ
Σ
plo (sa(b,) 2 Σ
2 (T)(
(28)
DB (ET;(b) 8=b,
EB
b/=b
By applying Chernoff bound together with Equation 28 Vt E (b))
we get that vb E B, Vi E N., Vs, E S.
e (b(
T (0) (bi, s:)l 2 2 211z((6)
2 exp
exp
2
2
2 1 exp
K
289m² 2
2 1 exp
IIn(2K/8)
462
2 1 5
K
The Lemma follows by applying a union bound with = 6|B[T] nm.
Lemma 6.2. Assume the clean event Ep holds. Then, at the end of the execution of ESTIMATEPROB, for each holds that [T, (b)) S max (N1, k).
Proof. The prove this Lemma, we show that for any B, if [T,(b)] max {Mi x}, then the condition (b) < N1 v d
13m is not satisfied, and hence the while loop in Algorithm
terminates. To prove this, we show that if [T(b] max (N., then ē S 13m=
Fix E B. Since the clean event Ep holds, and since, by assumption, [T)( 2 x we have that
(T(00 (b,, st) 1 2 2 (T 2 in ViEN, Vs, E S..
(29)
Furthermore, let (i, St, s() E arg minign.,....ee bi.e: b..s
lE By definition, we have that
(i) d bi.e, b I22 By definition of and by assumption that the clean event holds, for all 0 E e we have that
(2)
IP (0)b,, s;) IP (Olb,, sf) S |o bo.,,
[0]
60.,211111 20.
(0)
and thus
P( 8;) P (8]bb, st) 12 12 (1)
(1)
112 4m d + 4mp²
27

---

Published as a conference paper at ICLR 2024
Rearranging, get the following chain of inequalities:
d 2 PP (0)b,, 8,) P (8)bb 8/)
4m
(30a)
AE
2 i 4mg 13mØ 13ml
(30b)
= l 17m@ + 13m@
(30c)
ln(2K/6) + 13m@
= L 17m
(30d)
2/7, (1) (hi, 8:)1
In(2K/0) /6)
2 17m
+ 13m@
(30e)
UK
2ul2
l 17m
+ 13m@
(30f)
289m
8 (1 v2
13m@
(30g)
2 13m@.
(30h)
where Equation (3bb) follows from the definition of l and from the fact that S whenever [T>(b) 2 and Equation 30d) follows by definition of Rearranging, we get S concludes the proof.
d which
13m
F PROOFS OMITTED FROM SECTION g
Lemma F.1. Let (x" yy" p=, ,²²²)) be an optimal solution LP(P, C,O). Then, if clean events &, and Ea hold, there exists z' such that (x* y² ,,,"" 2²) is feasible solution for LP(C A, 2M 2M + x).
Proof. Let z be such that 2([b,, s,. 1b, b/. s.] MMS my, for E N, b, b. E B, and
St. Trivially, (x", y" ," x²) satisfy constraints (dd and (2e) of LP(S, A, 2M my + x).
Consider now constraint (c). By feasibility of (x*, y" p x*)) we have that
2 [br, b/, s3] 2 f((x;
[b;,
b/, Si, s PP)
(31a)
Σ
2,,(b b b).), s-),, O|P ((s,, (1.)), b..))
(31b)
b.
Σ
x Lib b..,, s-)), ( 8
(31c)
b_.EB,
$-iES_.
dEe
2 [( bb U/, 81, 8/ M|S-./mm.
(31d)
Rearranging and substituting the definition of z', we get 2([b,, b/, st] 2 f. 64. sts S/ C), thus proving that constraint (2c) satisfied.
28

---

Published as a conference paper at ICLR 2024
Let consider constraint (2b. By feasibility of (a*, y² 10, 2²",, for any E N and by, 82 B,, the following holds:
Σ b-IEB_c
b,i,,, - Σ
[f(( 81,
81,
1b, b/2 8]]
(32a)
sES;
Σ
b,, O) (s, (b;,, b-)))l
Σ
2 [b; Bi 8t]
(32b)
B.
a.ES,
aES
AE
< Σ
[,) b_,; 8, 0)] (1,
Σ
2 [b,, U/, si]
(32c)
b.IEB,
a.
#ES
DE6
M|8(ma +
[f((z] zz(bi, b/. 8i] + MMS_,|mv)
(32d)
#
2M +
Σ
[i( 86, z/(0,, si]l
(32e)
e.ES.
Furthermore, notice that
Σ -
b(]((,,),,))(((
Σ
x² p"((b; b-:]] (Ai(be, b() -x)
(33a)
Σ
[n"1(b;, b.:)__.)Abb -
(33b)
6.1EB_.
Putting all together, we get
[f((=)lb,, st 5) - 2/[b,, b/, s:ll
Σ
[p"[(b,, b. b,,A,, 8111 (x + -2M)5mmv)
S,ES;
which gives the desired result.
Lemma 8.1. Assume clean events & and Ep hold. Let (j,, T) be an optimal solution to LP(C, A,),. where & 2M [| + X. Then, letting 2M (I: +1) 1) (v + x), it holds that:
F, F. (4, v) 2 Σ (b..
Vi v(o,)) +..
Proof. Let (Ø', 5i, 2t) be the vectors from which mechanism ( 5 #²) is obtained, i.e., an optimal solution LP(Ç, A). Fix an agent N and a deviation (Ø, sp) E 4.. Notice that:
7bb (8,00b)
(34a)
9E0
2
Σ
[p'b)s s. 0,0][ 0] M|Smm my
(34b)
dEe
Σ
[aflb, 8, 0[6b[8 0] M[Smm
(34c)
AES
BE8
= Σ
Σ
(34d)
b, a.ES,
29

---

Published as a conference paper at ICLR 2024
Similarly,
(p',5") =
7' 6. (p((b,, (.) (s, (6(6,),
(35a)
BEB aE&
BEe
(000 0] + M MS
(35b)
BEB
#E6
Σ
[allb, (1() s|s, + M|
(35c)
bE
Σ
Σ
((b,, 8t))] M M|Smmw
(35d)
b.BB, 8.E9.
$ Σ
Σ b. o(b,), s:l + M|.
(35e)
B a,ES, La,ES,
Thus, by feasibility of (æ', i0", fi', )²), we have that:
F, 8) 2 Σ
Σ Le.ES
Sa 81 () - i [b, o(bi), sil
22M|Smm (36a)
b,EB,
j [b] (b; ((b)) - 2M (1- + 1) - 1-x
(36b)
BEB
Σ DEB
j [bb,, ((b)) 2M|S (K: + 1) -- (A: + 1)x
(36c)
i [l (bb)) 2M/5 (K: + 1) (v+
(36d)
BEB
This concludes the proof.
Lemma F.2. Assume clean events Ep and Ea hold. Then, at the end of the execution of ESTI- MATEPROB, it holds that
Σ
p(0 (0)b;,8:) pp()) (8lb,, #b}] 2 9mg ViEN, b, E B,, 8: E S.
EEB
Proof. Fix i E N. by E B, and 8; E S, Notice that
( [0] 1 [0]] < p(() (0)bs, 8:) -p(-)()) (8lb;, s/) 2g.
and thus
pp(i) (Olbi, -P(i) (8)b,, st) + 22
(37a)
9
4mg²
pp(() (8lb,, s:) - p(()) (0lb; xt)²
(37b)
REB
where the second inequality follows from triangle inequality. Hence, rearranging, we get
p((() (0lbe, sz) pp(() (0lbe, st}]
(8) b
,
112 4mo² 13mp 4mg² > 9me,
8EB
where the third inequality follows from g S since e S d/ 13m. This concludes the proof.
Lemma F.3. For each E N and by E B, let gf: be an uncorrelated scoring rule defined according Then, assuming clean events Ep and Ea are verified, the following holds
to Equation 7
p(i) (0)s;;b)) by) (10 0) -/% 00 z
ViEN, Vh, E Bi, Vs, 8 S:.
18
30

---

Published as a conference paper at ICLR 2024
Proof. Fix i E N, b, B, and s: of E Sj. Then, can state the following:
Σ AEO
p(0 (0|s;, 0.) 1/0 (s;, 0 =
Σ
p())
(0)8;, 0;)
( [0] H; 2 =116 11
(38a)
AEO
H4-
(1)
12
++]
pp() (0) st b.)
(1)
Sb.,., 10]
(38b)
2 H Sb.is,
<bb.., [0] e) Sb..a (0)
(38c)
8E0
H₂ + 2 S..s. 2
(38d)
Furthermore,
Σ pl0 (0)s (0 b.) 1/ 16,
Σ
p(i) (01s;, b:)
< [0.00:10]+
10] + H, 2 11
1 (
(39a)
DEG
OEG
H
Σ p(() (0)s;, b,) Sb.. [0]
(39b)
PEE
S H 2
+
Sb [0] + e) St..s [0]
(39c)
= H 2
1 +
e +
Sby.s 1155 (+) (0)
(39d)
AE
Combining the two results, we get
p(() (0|s, bi)
|//0 [s., 0] - 1// 01
(40a)
DE
2
2
1
1
Sbc.s:
1 + 2 115600 113 Σ
Sbr,s
(()
105 Sb..e: [0] - 22
(40b)
AEE
1 Σ
(,,,,, [0]
(1)
(1)
1915 [0] + (<!..>
(010=1110) [0] -2
(40c)
OEN
s [8] 2 22
So [0]
(40d)
OEN
1
pp(()
(0)b,, st) - pli)) (0lb,, x/}] }3)²² -2me² -20
(40c)
AEN
4mg
(40f)
8 4
>
- l
(40g)
9
(40h)
18
where Equation (4ep) follows from the fact that, since clean event E, holds, 1|c.
Enser [p()) (0) bi, s:)
p(t) (0 bi, s/)²² 2 4mg²,, Equation (400 follows from the definition of and Equation (40g) follows from Lemma This concludes the proof.
Lemma F.4 Assume the clean events Ep and En hold. Let 7 = (hh be such that
A/b, 8, 0) = - [si, 0) + (1 - 3)1 [st, O].
where 3 = =445 + (18 + 45 + f). Then, the following holds
pl
F - F (ū)))')= 2 Σ
[bb ((b))
ViE,, v(O,p) E +,.
65
beB
31

---

Published as a conference paper at ICLR 2024
Proof. Fix agent i E - and deviation policy (0) E Φ2- With slight abuse of notation, let 0] B) (ss, 0). Then, write the following:
Vilbe, 81, 0) " (ss,
Fi(pe ( P >')
Σ
66]
p(()) (ss, 0lb:) 1/bb,, s1, 0J pp()) (st, (lb()))) (lbb)) sobb, 85), 0]
d(b,)abb,
AE
+ Σ
Σ
p(i) (ss, Blb,) 74 S,, 0] - pp()) 016,) 7/1,,, (o s;),
(41a)
bE ((b,)=b;
s:ES, OEE
Let us analyze the two terms separately.
Term A.
First, notice that, by Assumption I holds that
Σ
b
p(i (8t, 01,,) ( [sc, 0] p(()) (ss. 0l0(0.)) 7 (1(b),
E.ES
HEE
it (bb +p.
(42a)
BEB:
(b.)).b.
Furthermore, noticing that (b,,, (bb:)) < and that, by definition, [s, 0] s 3/2 for all e W, bg E Bi, 8, E S, and θ we can write the following
Σ
pb
[p(9) (s;, 0lb,) 12 (ss, 0) pp()) (ss, 0lo(b,)) ( (s((b, s:). 0| - Cb,,,, o(b;))
BEB: @(h))ybb
#r #EG
5 j7' [b].
(43a)
(bb,)
Rearranging, we get
Σ nb[b]
Σ p(O) (s,,010,) [s, 0] p(() (ss, 0l)((.)) 5: [p(b,, si),
BEB:
R.ES,
((b.)#b.
dee
p pb Ci(bs, ((b:)) 2
(44a)
BEB olb.
By linearity and by definition of y. we get
jb
(b,b, + 3p (3)
(45a)
BEB: (bb
pe
Σ pd|b] C,(b,, +
(45b)
18p + 45 +
BEB: bbb.)$bb
Ci(ss, ((b.)) + pl
jd'6b]
(45c)
65
2b.
where Equation (55b) follows from the definition of 3 and Equation (45c) follows from p <
(w.llo.g.), &. < 2 (by the stopping condition of Algorithm 2 and
(since clean event &p holds).
32

---

Published as a conference paper at ICLR 2024
Term B
By assumption 1
holds that
Σ
[6
Σ
p
(st, 000;0bb)))))) 7,th [sc, -pp(())ppp)))))))) p(.) (s;, 0lb,) 7.th [0(b,,, 8:), 01
BEB:
S. BEB
o(b,)=b,
Σ
j7 [b]
Σ
p(t)
(b:)
Σ
p(i) (Olbs, 8;) (7. (sc, 0J - 7/t (o(les 8e), 01
(46a)
BEB:
#:ES;
8E8
d(b))=b,
Σ
bb
Σ
p(0)
(s:(b,)
Σ
p(()) (8)be. s2) 770 [sc. 0) >/2 [st,
[s 01
(46b)
#:E5;
9E8
b(b:)=b,
0.
(46c)
Furthermore, by Lemma
j7' [b)
Σ
p(())
(si, 0lb:) 7/2 (sc, 0) - pp()) (b)) 5% [sp(be, 8z), 0]
BEB: ((b))=b,
S.
FEE
Σ
bb bb)
p(()
(s:1b,)
po(() (0lbe, si) [1/ 0] - 0.0
(47a)
BEB:
S;ES;
858
o(b.)=b,
l p(i (silbi)
Σ
A b
Σ R.ES,
(47b)
18
BEB:
d(.)=b.
&
Σ
b
(47c)
18
BcB: d(b.)=b,
(47d)
Also in this case, by linearity and by definition of we get
B
(C,le,, + (1- 33) 3))
l
(48a)
18
BEB: (bb)=bb.
pl
Σ [b C,(bs, +
(48b)
18p + 45 +
BEB:
(b,)=bb
pl
pb
((bb), + 65
(48c)
BEB: bb.
where to obtain Equation 48b
substituted the definition of B and Equation (48c) follows from p < 1 (w.l.o.g.) and < (by the stopping condition of Algorithm
Putting all together.
By substituting Equations
45ch and 48c into Equation 41a
we get
pl
F, x) F. Y')
p [CC o(b.))
65"
beB
This concludes the proof.
x²"=""))))))))))"")")) ) is chosen according to AlgorithmB 3 then it IC, i.e., if satisfies Equation (b) of optimization problem (7)
Lemma 8.2. Assume clean events E., E, hold. If mechanism (p², ,a" T²)
33

---

Published as a conference paper at ICLR 2024
Proof. Fix agent E - and deviation policy @, 1p P,. By linearity, we have that Filji ,4) P (i',,')
R ( .59 ax) [ri(it x1) F
(jt
xy)
(49a)
ad F7 [b, -(b;)((())))))))))) ax (1 ax) pl
(49b)
65
bEB
[bb o(b,)) + Apl Apl + Smmpp /65
(49c)
pl + 65A
BEB
7 [bCC o(b.))
(49d)
BEB
where Equation (49b) follows from Lemmas 8.1 and F.4 Equation (49c) follows from the definition
of a in Algorithm 3 and Equation 44d follows from the fact that, since clean event Ep holds, l L. This concludes the proof.
G PROOF OF THEOREM 5.1
Assume clean events & and Ep hold. Notice that by union bound on the results of Lemma 6. and Lemma 7.1 this happens with probability at least From the definition of regret we have that
Rd [U(,", " x²") U( 7 x³)]
Σ
[U(MT Y,, x²) U "0'"",, (a', m²)
R
Let us analyze the two terms separately.
Term R_ Consider the rounds T, in which the principal committed to an uncorrelated mechanism. Since during the commit phase the principal uses only correlated mechanisms, we have that
T.
Σ Tp(() Ta. BER
By Lemma 6.2 and Lemma 7.2 we have that
[Tal S [B] max [N1 k} + 2nk N₂ + nk? Ng = [8] max 2T2 1t///s,,, , + 2nk log(T) + nk 27/33
where π = 280 m² In (2K (8) - Then, since for all t, by definition of we have that Up,,, Y ) (r n²) S nM + 1, we can bound the term R as
2 2
R < (nM +1) (13) 2a x) 32 log(T) + 32
Term R.. The only rounds in which the principal commits to correlated mechanisms are those of the commit phase. Let E To. By definition of x and by linearity of U, we have that
RT
< Σ
[U('' "'u'""""""""" T²)
Up" 7t, +)) + (1 ()) + 11.
(50)
IET.
Furthermore, notice that can bound 1
65A
65
(1 a+)
2M S|m + 1)(v +
+
65A
pe
Recalling that, by Lemma
B.8
In (22k222/ /8)
kt
In In(2nk2/00
kl2 M T
x < 2k2 M
M
2h12 MV
2N,
2N
272/3
34

---

Published as a conference paper at ICLR 2024
and by definition
In (T || S/mm///mmm///
In 12 B S/mm/
max BEB
(b))
272/3
get
780
In (12 mmm 1 T
(1 (1- v M 1 |m pl
(51)
212/33
Let us now consider the term U(4", ,², Let (x", y" 1 2²) be an optimal solution to (P(P, C,0) and let (x', y', u² 2²) be the optimal solution LP(C, A) from which mechanism Ru,,,, x²) was obtained. Furthermore, we recall that the objective function of LP(S, As, 8) is
((
ΣΣΣ bEB #ES ege
(ols, 0)
Σ y 8, aju(a, Eubb,,,auua..000 LAEA
Σ Eoilb, 8, SEN
Then, write the following
Unp " ,
ΣEΣ
11 bJP (8,
Σ x T
Σ
bi 8, 0]
BEB #ES BEB
LaEA
iEN
ΣΣΣ BEB #ES 00B
1 [6]6|1,0 0]
Σ s,
Σ
1b, 8, 0]
+ 2M S |m
LaEA
iEN
ΣΣΣ
Co 0] Σ y 16, s,b
Σ iEN
2; 8,
+2M +2M|Ssmmw
PEB oee
LaEA
Ü (xx y 1 ,T" + 2M Slnn,
where the first inequality follows since, given that clean event holds, |PP (s, Cols, 0] S In similar way, it holds that
Un N., n²)
ΣΣΣ bEB AES BEE
μ P (s, 0|b)
Σ LaEA
n'' 1' ol((a,))
Σ ENN
b 0)
ΣΣΣ beB aES AEB
1 [b]C (s, 0)
Σ n bb s, s))u(a,))))
Σ
Wib 8,
2M S|mn
LaEA
iEN
ΣΣΣ BEB BES BEB
[6(8, 0]
Σ
y' 8, aju(a, 0)
Σ SEN
ailb, 8, 0]
-MMSSmme
LaEA
(x',, y" 4², "²,T") 2M ( mmny
Furthermore, we recall that, by Lemma F.I (x", y", ,,,=") 2²*) a feasible solution to LP(C, while, by definition, (xf, y" ,,,,", 2²) is optimal for eP) Thus, Ü@' , ni, TT)) 2 U(x", , ,²,,", )T), which yields
Σ ( ,²)","")=-"" UW 7, x²) TET.
(a ,²,""""" ( v w. (,') 4M (S] [|mmm]]
TE..
4M|S mnv
LE..
< 4MSS 2/3 (1((12BBTTS)mmmm
Combining the above results, we get
R S Σ [U("",,,,")
Y n²) U'n', 54, n²)] + (1 an)-aMTTMM + 1)
ET.
1564
pe |
|| +
35

---

Published as a conference paper at ICLR 2024
Putting all together. Hence, the final regret bound is
Rd Re R 1567
(x + (nM + 1) log(T), 2 M Mi (VI((2[1B11)))mm + +1) max(T2/3 x,],
ol
which gives the result.
36


Reviews:
[{"review_id": "EgHOVKLiYk", "reviewer": "Reviewer_eEDk", "summary": "The paper is concerned with mechanism design where there is a principle who wants to know some state theta to take an action that maximizes utility. To estimate theta the principle uses reported signals from agents. The paper begins with the correlated mechanism setting and shows how to solve the problem using LP methods with some modifications. The paper then discusses uncorrelated mechanism showing that they are sub-optimal in general settings and optimal in some restricted settings. Finally, the online setting is considered, and the paper proposes an algorithm that follows the classical explore then commit paradigm in bandits.", "questions": "Please see points A and B in the weaknesses above. Especially point B. Another question I have is the following:\n\n-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.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "-The problem seems well-motivated and the model captures a wide set of applications.  \n\n-I think the paper has interesting results such as characterization of optimality and suboptimality of uncorrelated mechanisms in section 4.\n\n-I did not check the proofs carefully. But the technical details in the paper seem interesting.", "weaknesses": "A-The presentation of the paper can be improved. There seem to be some missing text, see the following:\n         \n          1-what is the auxiliary variables z_i in eq (2c) equal to? Further, Theorem 3.1 has a collection of values C_1, C_n, have they been specified? \n\n          2-3rd line in section 2, why are some c’s (for the cost function) capitalized and others are not\n\n          3-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 ”\n\n\nB-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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8fKuS0lLMG", "reviewer": "Reviewer_uose", "summary": "The research paper delves into the dynamics of online information acquisition among multiple agents, providing a comprehensive analysis of how to design the mechanism that influences individuals' decisions. Besides, this paper designs a polynomial-time algorithm to find an optimal incentive compatible mechanism.", "questions": "1. Is there any real examples of the optimal mechanism that are uncorrelated?\n\n2. Is there any simulations, real data to demonstrate the effective of this ETC algorithm?\n\n3. Typo: $\\alpha ==$ to $\\alpha=$.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Algorithmic Design and Optimization in Multi-Agent Settings: This paper works on designing an efficient algorithm for the multi-agent information acquisition problem, addressing both the optimization and online learning dimensions of interactions between a principal and unknown agents. The proposed algorithm, which navigates through a quadratic optimization problem via linear relaxation, culminates in a polynomial-time solution to the original problem. \n\n2. Addressing Uncertainty in Online Learning: The transition to online learning scenarios, characterized by the principal’s lack of knowledge regarding game parameters, is handled with a robust algorithmic approach, achieving a ($\\tilde{O}(T^{2/3})$) regret. This aligns with state-of-the-art benchmarks in single-agent settings.\n\n3. Ensuring Truthfulness and Optimality: They first discussed the relationship between the optimal design and the correlated and uncorrelated mechanism. They also introduce the novel definition of regret as the difference between the optimal (correlated + IC) and suboptimal (uncorrelated + IC, correlated + NonIC). The final phase of the algorithm, committed to achieving an approximately optimal strategy while upholding truthfulness under uncertainty. The authors leverage estimations from previous phases to find an approximately optimal and incentive-compatible mechanism, subsequently combining it with a strictly incentive-compatible scoring rule. This approach demonstrates a sophisticated understanding of the trade-offs and complexities involved in designing mechanisms that balance optimality and incentive compatibility.", "weaknesses": "1. This paper would benefit significantly from the inclusion of empirical demonstrations to substantiate the theoretical assertions made therein. \n\n2. 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.\n\n3. The articulation throughout the paper necessitates refinement. This is particularly pertinent in relation to the elucidation of the implications associated with the various theorems and lemmas presented, which requires additional clarity and precision.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xCzUCYOtis", "reviewer": "Reviewer_cMnb", "summary": "The authors study the problem of online acquiring information of the unobserved world state ($\\theta$) from a group of strategic agents under the principal-agent framework.\nThe challenges of the online problems are in three folds:\n\n1. The agents are strategic, meaning they could deviate from the principal's action recommendation and report fraud signals. Thus, the exploration phase (with uncorrelated scoring rule) is needed to ensure IC.\n2. The cost differences $C_i(b_i, b_i')$ are unobservable by the principal, which prohibits standard RL methods (via estimating the agents' cost directly) and essentiates the binary searching method.\n3. In the multiple-agent setup, the number of constraints can be growing dramatically without any reduction. \n\nThis paper formulates the multi-agent information acquisition problem, reduces the problem to linear programming that can be solved in polynomial time, and provide online learning guarantee.\nIn particular, the authors show there is a clear separation between the uncorrelated and the correlated mechanism.", "questions": "1. 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. \n2. If the costs of the follower are directly observable, can the learning rate be improved?\n3. Is the independency assumption $\\mathbb{P}^{(i)}(s_i| b, \\theta) = \\mathbb{P}^{(i)}(s_i| b_i, \\theta)$ necessary? If so, without the independency assumption, what could be added to the difficulty in terms of computation and statistical learning?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "For originality, the authors formulation of the information elicitation problem under the multi-agent setting. I appreciate the discussions of the computation issue and the separation between the correlated/uncorrelated scoring mechanism. Overall, the paper is well written, but a little bit redundant in terms of the notations. The paper achieves state-of-art learning guarantee for the multiple-agent setting. The algorithm design and the analysis look sound to me.", "weaknesses": "1. The authors should make it clear if agents can communicate with each other their signals/actions or not, as this can cause a huge difference. I understood that the agents cannot communicate with each other by forms of the deviation functions. Please correct me if I'm wrong. \n2. There are some typos that could cause confusions, e.g., it should be $\\sum_{s'\\in\\mathcal{S}:s_i'=s_i\\mathbb{P}(s' \\| b, \\theta)}$ at the bottom of Page 2.\n3. The authors may need to justify Assumption 1, perhaps by providing examples where the set of scoring rules known by the principal in advance can be effectively learned, e.g., by random searching, or constructed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TSioiBCei9", "reviewer": "Reviewer_CwwP", "summary": "The paper studies an online information acquisition problem. In the model, a principal interacts with a group of agents. The principal uses a mechanism to recommend actions for the agents to perform and to decide payments for the agents. The mechanism also elicits information from the agents about their observations of the state of nature. Besides the interactions, the principal also takes an action after the agents perform actions and report their observations. The paper first presents an algorithm based on linear programming to compute the optimal mechanism in the full information setting. It then studies a learning problem where the transition probabilities are unknown. A no-regret algorithm that gurantees sublinear regret is provided for the learning setting.", "questions": "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. \n\nSimilarly, 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. \n\nSome typos: \n\n- In Equation (2b), in the term z_i[b_i, b_i', s], the \"s\" should be \"s_i\"?\n\n- On page 5, there is a displayed equation that defines \\mathcal{U}. In the part \\gamma_i: S_i \\times \\Theta \\in [0, M], the symbol \"\\in\" should be \"\\to\"?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem studied is well-motivated. The paper presented a number of results and is mostly clear. The analysis looks solid and technically sound.", "weaknesses": "The algorithms presented look very standard even though the model is a more complicated one. The LP algorithm, for example, is based on the same formulation for standard principal-agent mechanism design problem -- by maximizing the principal's utility under the agents' truthful behavior and using IC constraints to enforce this behavior. While I appreciate the effort it takes to set up the constraints for this more complicated model, the insights the approach yields are somewhat limited. The same can be said about the learning algorithms. \n\nBesides that, some specifications of the uncorrelated mechanisms are not well justified (see Questions). The model itself does not look scalable with respect to the number of agents because of the exponential growth of joint action profiles.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)