No-Regret Online Prediction with Strategic Experts
Authors: Omid Sadeghi
Maryam Fazel
Venue: NeurIPS 2023 poster (2023)
Keywords: incentive-compatible
online prediction with expert advice
forecasting
TL;DR: We propose the first no-regret and incentive-compatible algorithms for a generalization of the experts problem (called the "m-experts" problem)

Abstract: We study a generalization of the online binary prediction with expert advice framework where at each round, the learner is allowed to pick $m\geq 1$ experts from a pool of $K$ experts and the overall utility is a modular or submodular function of the chosen experts. We focus on the setting in which experts act strategically and aim to maximize their influence on the algorithm's predictions by potentially misreporting their beliefs about the events. Among others, this setting finds applications in forecasting competitions where the learner seeks not only to make predictions by aggregating different forecasters but also to rank them according to their relative performance. Our goal is to design algorithms that satisfy the following two requirements: 1) \emph{Incentive-compatible}: Incentivize the experts to report their beliefs truthfully, and 2) \emph{No-regret}: Achieve sublinear regret with respect to the true beliefs of the best fixed set of $m$ experts in hindsight. Prior works have studied this framework when $m=1$ and provided incentive-compatible no-regret algorithms for the problem. We first show that a simple reduction of our problem to the $m=1$ setting is neither efficient nor effective. Then, we provide algorithms that utilize the specific structure of the utility functions to achieve the two desired goals.

No- No-Regret Online Prediction with Strategic Experts
Omid Sadeghi
Maryam Fazel University Washington Seattle, WA 98 98195 (fmide,,maazel @uw edu}
Abstract
We study a generalization of the online binary prediction with expert advice framework where at each round, the learner is allowed to pick m 2 experts from pool of K experts and the overall utility is modular or submodular function of the chosen experts. We focus on the setting in which experts act strategically and aim to maximize their influence on the algorithm's predictions by potentially misreporting their beliefs about the events. Among others, this setting finds applications forecasting competitions where the learner seeks not only to make predictions by aggregating different forecasters but also to rank them according to their relative performance. Our goal is to design algorithms that Incentivize the
satisfy the following two requirements: 1) Incentive-comppttibe experts to report their belief' truthfully, and 2) No-regret: Achieve sublinear regret with respect the true beliefs of the best-fixed set of experts in hindsight. Prior works have studied this framework when m = and provided incentive comppiiblee no-regret algorithms for the problem. We first show that simple reduction of our problem to the m = 1 setting is neither efficient nor effective. Then, we provide algorithms that utilize the specific structure of the utility functions to achieve the two desired goals.
Introduction
Learning from a constant flow of information is one of the most prominent challenges in machine learning. In particular, online learning requires the learner iteratively make decisions and the time of making each decision, the outcome associated with it is unknown to the learner. The experts problem is perhaps the most well-known problem in online learning 2 3 In this problem, the learner aims to make predictions about a sequence of T binary events. To do so, the learner has access to the advice of K experts who each have internal beliefs about the likelihood of each event. At each round E [7], the learner has to choose one among the advice of K experts and upon making her choice, the 1-th binary event is realized and a loss bounded between zero and one revealed. The goal of the learner is to have regret, i.e., to perform as well as the best-fixed expert in hindsight. In many applications, however, the experts are strategic and wish to selected by the learner as often as possible. To this end, they may strategically misreport their beliefs about the events. For instance, Eighh Jaggregates different pollsters according to their past performance to make a single prediction for elections and sports matches. To do so, FiveThirtyEigh maintains publicly available pollster rating=" A low rating can be harmful to the pollster's s credibility and adversely impact their revenue opportunities in the future. Therefore, instead of maximizing their expected performance by reporting their predictions truthfully, the pollsters may decide to take risks and report more extreme beliefs to climb higher the leaderboard. Therefore, it is important to design algorithms that not only achieve no-regrel but also motivate the experts to report their true beliefs fincenive-compaiiie
inttss/fiieehhiryigght.comm hhtps://pojoct..ffccthtttiiggg
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

Otherwise, the quality of the learner's predictions may be harmed. As we have mentioned in Section I.I all the previous works on this topic have focused on the standard experts problem where the goal is to choose single expert among the K experts. In the offline setting, this is equivalent to forecasting competition in which only the single highest-ranked forecaster wins and receives prizes. However, in many applications, set of top-performing forecasters are awarded perks and benefits. For instance, in the Good Judgement Project, a recent geopolitical forecasting tournament, the top 2% of forecasters were given the "superforecaster" status and received benefits such as paid conference travel and employment opportunities [5]. Similarly, in the latest edition of Kaggle's 's annual machine learning competition to predict the match outcomes of the NCAA March Madness college basketball tournament (called "March Machine Learning Mania 2023' the top 8 forecasters on the leaderboard received monetary prizes.
Variants of the m-experts problem have been previously studied in 66 7 g however, all of these works focused only on providing no-regret algorithms for the problem and the incentive compatibility considerations were not taken into account. To the best of our knowledge, this is the first work that focuses on the strategic m-experts problem where the experts may misreport their true beliefs to increase their chances of being chosen by the learner.
For the setting with modular utilities, perhaps the simplest approach to learning well compared to the best-fixed set of m experts while maintaining incentive compatibility is to run the incentive- compatible WSU algorithm of [T] for the standard experts problem (the setting with m = 1) over the set of (()) meta-experts where each meta-expert corresponds to one of the sets of size m. This approach has two major drawbacks: 1) There are exponentially many meta-experts and maintaining weights per each meta-expert and running the WSU algorithm computationally expensive, and 2) The dependence of the regret bound on m is sub-optimal. Therefore, for our setting, it is preferable to design algorithms that are tailored for the m-experts problem.
1.1 Related work
Prior works have studied the experts problem under incentive compatibility considerations for two feedback models: In the full information setting, the learner observes the reported prediction of all experts at each round. In the partial information setting. however, the learner is restricted to choosing single expert at each round and does not observe the prediction of other experts. [IT] considered algorithms that maintain weights over the experts and choose experts according to these weights. They assumed that experts' incentives are only affected by the unnormalized weights of the algorithm over the experts. However, since the probability of an expert being chosen by the learner equals her normalized weight, the aforementioned assumption might not be suitable. Later on, [I0] made the assumption that at each round é E [?"], incentives are tied to the expert's normalized weight (i.e., the probability of being chosen round ++ 1) and studied this problem under both feedback models. They proposed the WSU and WSU-UX algorithms for the full information and partial information settings respectively where both algorithms are mncettive-oopptible and they obtained O(vTln) and (TT2/3 [K (KlK))2/5) regret bounds for the algorithms. Then, 11) considered non-myopic strategic experts where the goal of each expert is to maximize a conic combination of the probabilities of being chosen in all subsequent rounds (not just the very next round). They showed that the Follow the Regularized Leader (FTRL) algorithm with the negative entropy regularizer obtains a regret bound of O(vT In K) while being O / approximately incentive-compatibee i.e., it is a strictly dominated strategy for any expert make reports O ( distant from their true beliefs. For the non-strategic m-experts problem with modular utilities. proposed the Component Hedge (CH) algorithm and obtained a regret bound of / 22ml" In( k + m () where 8* is the cumulative loss of the best-chosen set in hindsight. They also gave a matching lower bound for this problem. X
studied the FTPL algorithm with Gaussian noise distribution and provided an Omm O(m//Tin /T'n( K regret bound for this setting. For the non-strategic m-experts problem with submodular utility functions, [ proposed the online distorted greedy algorithm (with dual averaging algorithm as the algorithm A,
for i = ,,..., m. whose regret bound is O( 0(/mT)n In( (K) )). More recently, [9 studied the m-experts
problem under various choices of the utility function (sum-rewar neward rex-reward, pairwise-rewarc and monotone reward). In particular, for the setting with modular utilities (sum-reward), they proposed

---

an algorithm that matches the optimal regret bound of the CH algorithm while being computationally more efficient.
1.2 Contributions
In this paper, we focus on a generalization of the experts problem (called "m-experts problem") where at each round, instead of picking single expert, are allowed to pick m experts and our utility is either a modular or submodular function of the chosen experts. In particular, at round f E [T]
and for a set of experts St S [K], the utility function is defined f((S.) |
Eies, Li, and
f(())) = 1 - l,, in the modular and submodular cases respectively where Ci [0. 1] is the loss of expert at round t. The goal is to design algorithms that perform as well as the best-fixet set of m experts in hindsight (no-regret) and incentivize the experts to report their beliefs about the events truthfully
siiceniive-oomatibbee
Towards this goal, we build upon the study of the Follow the Perturbed Leader (FTPL) algorithm for the m-experts problem with modular utility functions by [8] and derive a sufficient condition for the perturbation distribution to guarantee approximate incentive compatibility. Furthermore, we show how this condition is related to the commonly used bounded hazard rate assumption for noise distribution. In particular, we show that while FTPL with Gaussian perturbations is not incentive- compatible, choosing Laplace or hyperbolic noise distribution guarantees approximate incentive compatibility.
Moreover, inspired by Algorithm 1 of [13] for online monotone submodular maximization subject to a matroid constraint, we first introduce simpler algorithm (called the "online distorted greedy algorithm"" for the special case of cardinality constraints. This algorithm utilizes incentive- compatible algorithms for the standard experts problem (i.e., m combined predictions. We provide (1 )-egrett bounds for the algorithm where E [0. 1] is the average curvature of the submodular utility functions. Therefore, applying the algorithm the setting where the utility functions are modular (i.e., c 0), the approximation ratio is 1. For submodular utility functions, the algorithm achieves the optimal Finally, we validate our theoretical results through experiments on data gathered from forecasting competition run by EivrttityEighht in which forecasters make predictions about the match outcomes of the recent 2022 2023 National Football League (NFL).
setting) and outputs their
approximation ratio.
2 Preliminaries
Notation. The set (1.2....,,)) is denoted by [n). For vectors Ft, y E IR", Ii.r and yı denote their
i-th entry respectively. Similarly, for matrix A E RR we use Ai, to indicate the entry in the matrix's i-th row and j-th column. The inner product of two vectors x, y E R." is denoted by either (a, 9) or xx' y. For set function f, use f [A) to denote f(A U {i})
f(A).
A set function f defined over the ground set V is monotone if for all A C B CV f(A) < f(B) holds. f is called submodular if for all A C B C. V and j $ B, f(]AA)=
fG(BB holds. In other words, the marginal gain of adding the item j decreases as the base set gets larger. This property is known the diminishing returns property. If equality holds in the above inequality for all A, B, and j. the function is called modular. As mentioned in Section 1.2 at round E [T] and for a set of experts S C [K], the submodular utility function is defined as (s,) = 1 lless E,, where la,t [0, 1] is the loss of expert at round f. To show that this function is submodular, note that have:
f(AU f(A) (1 (.,) II
4. 2 (1- Cj.e) iEB
II ((B((() -(B),
REA
where the inequality follows from l,,1 E [0. 1] for E B \ A. For normalized monotone submodular set function f (i.e., f(0) = 0), the curvature cy is defined as
- min f(/V \ (i1)
Cj 1-
jev f((})
easy to see that ej E [0, 1] always holds. ej S is due to monotonicity of ʃ and ef 2
follows from being submodular. Curvature characterizes how submodular the function is. If 0. the function modular, and larger values of ef correspond to the function exhibiting a stronger diminishing returns structure.
3

---

3 m-experts problem
We introduce the m-experts problem in this section. In this problem, there are K experts available and each expert makes probabilistic predictions about a sequence of 'I' binary outcomes. At round t E [T]. expert [K] has private belief by, E [0. 1] about the outcome rt E {0, 1), where re and {b,,)}=1 are chosen arbitrarily and potentially adversarially. Expert i reports Pt. E [0, 1] as her prediction to the learner. Then, the learner chooses set St containing m of the experts. Upon committing to this action, the outcome ry revealed, and expert incurs a loss of l,, (b rt) where e: [0. 1] x {0, 1 + [0, 1] is a bounded loss function. In this paper, we focus on the quadratic loss function defined as E(b, r) = (b- r)2 The utility of the learner round t one of the following:
Modular utility function: ft(S.)
[ Eres, l, = |5 L EiEs, Elbeas v2). Submodular utility function: ft(S.) = - L,, = = -
((b,,:TT)..
It is easy to see that ft is monotone in both cases and f((S.) E [0, 1] holds. Note that the utility at each round defined with respect to the true beliefs of the chosen experts rather than their reported beliefs.
The goal of the learner twofold:
1) Minimize the a-regret defined as a-Ry = EE| a maxsc E fi(S) - -Ee [..)..] where the expectation is taken with respect to the potential randomness of the algorithm. For the modular utility function, a = and for the submodular setting, we set a = 인 (where
f f= fi) which is the optimal approximation ratio for any algorithm making polynomially many queries to the objective function.
2) Incentivize experts report their private belief's truthfully. To be precise, each round E [T] each expert i E [K] acts strategically to maximize their probability of being chosen at round + 1 and the learner's algorithm is called reporting Pı. = bu.t- To be precise, we define the incentive compatibility property below.
if expert maximizes this probability by
Definition 1. An online learning algorithm is incentive-comp incentivecomppatble if for every l. E (T), every expert i E [K] with belief by,t. every report P., reports of other experts p-i,t, every history of reports {pj,)]je[K)ss and outcomes {relect we have:
Ere-Bem(be,.) [Tie+1 bigsP-its (Ps sett)r) (ratsct]
2 Bre Tii++ Pitt.Piits (PJ.s Selk),s (ra)act),
where Bern(b) denotes a Bernoulli distribution with probability of success b and n1,4 is the probability of expert being chosen at round t
In other words, an online learning algorithm is incentive compatie-e if it is in the best interest of the experts to report their private beliefs truthfully to maximize the probability of being chosen for the next round.
As mentioned earlier, we focus on the quadratic loss function in this paper. The quadratic loss function is an instance of proper loss functions 13), i.e., the following holds:
BeyB))())) [C(p. r)) 2 (em)(( [E(b, r)] Vp + b,
i.e., each expert minimizes her expected loss (according to their true belief b) by reporting truthfully.
3.1 Motivating applications
Several interesting motivating applications could be cast into our framework. We mention two classes of such applications below.
Forecasting competitions: In this problem, there are a of K forecasters who aim to predict the outcome of sports games or elections (between two candidates). At each round & E [2]. information on the past performance of the two opposing teams or candidates is revealed and forecasters provide probabilistic prediction (as value between [0, 1) about which team or candidate will win. The learner can choose up to m forecasters at each round and her utility is simply the average of the utilities of chosen experts.
There a library (1,..., N) of distinct files. A cache with limited storage capacity can store at most vn files at any time. At each round / E [7). user arrives and requests one file. The learner has access to a pool of K experts where each expert i [K] observes the user history and makes probabilistic prediction Pi, E [0, 1]d8 for the next file
Online paging problem with advice 16:

---

request (where Pt. = 1). For instance, Pt, = e if expert predicts the file j E [N] where ej is the j-th standard basis vector. Also, r e; the j-th file requested round E [T]. The learner can choose of these experts at each round and put their predictions in the cache. The learner's prediction for round is correct if and only if one of the m chosen experts has correctly predicted the file. Thus, the loss of expert i can be formulated as L,, llpr.: rellă and the utility at round t could be written as f:(S,) = 2 - liees l,, which is exactly our submodular utility function. Note that this is slight generalization of our framework where instead of binary outcomes, we consider nonbinary (categorical) outcomes, All our results could be easily extended to this setting as well.
3.2
Naive approach
The WSU algorithm of [0 for the standard experts problem is derived by drawing connection
between online learning and wagering mechanisms. The framework of one-shot wagering mechanisms
was introduced by [17] and is as follows: There are K' experts and each expert i E [K] holds belief b; E [0. 1] about the likelihood of an event. Expert reports a probability p: E [o. 1] and wager ui 0. A wagering mechanism I' is mapping from the reports
(p),.... PP)) wagers w = (W1.... wx) and the realization r of the binary event to the payments [, wi, r) to expert i. It is assumed that (p,,w,,) r) 2 0 vi [K], i.e., expert loses more than her wager. A wagering ii=1- mechanism is called pudget-balanced if K [p w. = Σ Wi [7 18 introduced class of excentivecooppttbee budget-balanced wagering mechanisms called the Weighted Score Wagering Mechanisms (WSWMs) which defined as follows: For a fixed proper loss function bounded in [0, 1], the payment to expert i is
(p,,0,r wi ((ps,)) r) + Σ wyl(psrr))
The proposed algorithm in [10 called Weighted-Score Update (WSU) and the update rule for the weights of the experts { 1 is the following:
Ti.+1 mplss Te, T.) + (1-1)
where TT,1 K Vi [K]. In other words, the normalized weights of the experts round t are interpreted as the wager the corresponding expert, and the normalized weights at round + 1 are derived using convex combination of the weights at the previous round and the payments in WSWM. Note that since WSWM is budget-balancedd the derived weights at each round automatically sum to and there is need to normalize the weights (which might break the incentive compatibility). Also, considering the incentive compatibility of WSWM, the WSU algorithm is incentive-compatible well.
The update rule of WSU could be rewritten as follows:
K
1)TTE, - lit +
Σ
jalss,) +
(1 +(1
m) = nT,e(1 - -nI,)),
where Lip lep Σø= J.t Therefore, the WSU update rule is similar that of the Mul- tiplicative Weights Update (MWU) algorithm [19 with the relative loss Li instead of L.p, in the formula.
simple approach solving the m-experts problem with modular utilities (Ls,, 1 to define an "expert" for each of the possible (*) sets of size m and apply the incentive-compatibe WSU algorithm of [00] for the standard experts problem to this setting. Note that we still define
m Ejes b,,) is
incentive compatibility with respect to individual experts (instead of the (K) meta-experts). To be precise, we define Ti,t Es:ssi T.S We can show the following:
Σ
T [T, 17 (.
17
Σ
T..))..t.
imss
Given that 7i,41 is linear in Li,t, Li,1 -1,1 EK E. is linear in & and the loss function is proper, we can conclude that incentive compatibility holds in this setting as well.
We summarize the result of this approach in the theorem below.
5

---

Theorem 1. we apply the WSU algorithm of [10] to a standard experts problem with (n)
experts
corresponding to each S with |S| = m, and set = Inf compatible and its regret is bounded as follows:
Ke
the algorithm is incentive-
T
K ElL-Rr]= & Oy In =)).
This approach has two major drawbacks:
Computational complexity of maintaining weights for each (x) feasible sets, In particular, have to do exponentially many queries to the objective function at each round to update these weights. 2) The regret bound has /m dependence In the subsequent sections, we propose two efficient algorithmic frameworks that exploit the modular or submodular structure of the utility function and obtain the desired regret and incentive compatibility guarantees.
the number of experts that is suboptimal.
4 Follow the Perturbed Leader (FTPL) algorithm
In this section, study the well-known Follow the Perturbed Leader (FTPL. algorithm for the m-experts problem with modular utility functions and study its regret and incentive compatibility guarantees. The algorithm is follows: At each round t E [T], first take K i.i.d. samples {rr,) from the noise distribution D. In particular, we focus on zero-mean symmetric noise distributions from the exponential family, i.e., f(T,,) X exp(-v(7r,)) where
R R4 is
symmetric about the origin. At round t, we simply keep track of Σ 4, + 17% for each (where 7) is the step size) and pick the experts for whom this quantity is the smallest. [8] previously studied the FTPL algorithm for a class problems that includes the m-experts problem. However, they only focused on the setting with zero-mean Gaussian perturbations. In contrast, we not only extend this analysis to all zero-mean symmetric noise distributions from the exponential family, but we also analyze the incentive compatibility guarantees of the algorithm and determine a sufficient condition for the perturbation distribution under which the algorithm is approximately incentive-compatibl. This condition is provided below.
Condition 1. For all R. |<((=)) B holds for some constant B 0.
We have x22) |2| for Laplace distribution. Therefore, 22(2) sign(z) and B 1. For symmetric
hyperbolic distribution, v(z) vI + d² holds. So, |x'(2] vI+=² S and B
|=|
Condition T is closely related to a boundedness assumption on the hazard rate of the perturbation distribution. We first define the hazard rate below.
Definition 2. The hazard rate D
'D at R. is defined
hazo(2) = [T((2)
FFD(z)
where Jo and F.D are the probability density function (pdf) and the cumulative density function (cdf)
of the noise distribution D. The maximum hazard rate of is hazp supzeR hazp(z).
The hazard rate is statistical tool used in survival analysis that measures how fast the tail of distribution decays. The theorem below shows the connection between Condition and the bounded hazard rate assumption.
Theorem 2. If Condition 7 hools for the perturbation distribution D with the constant B > O, have hazp S B.
However, there are distributions with bounded hazard rates for which max, [z((2) unbounded (i.e., Condition [ does not hold). For instance, consider the standard Gumbel distribution. In this case, u(2) = z + exp(-=2 -2). Therefore, we have (=(=)
exp( -z). So, if = - -xo, |r'(=)] - oo. Therefore, Condition is strictly stronger than the bounded hazard rate assumption for the noise distribution D.
We show how Condition guarantees approximate notion of incentive compatibility for FTPL.

---

Theorem 3. For the FTPL algorithm with a noise distribution satisfying Condition 2 with a constant B > at round t forr an expert i [K], the optimal report the expert is perspective Pi, is at most 2B 9-2B away from her belief bi i.e., the following holds:
2B
10 bu.
17 -- 2B
Note that while we focused on the incentive structure in which each round & [T), experts wish to maximize their probability of being chosen at round + 1, the same argument could be applied to more general setting where the goal is to maximize a conic combination of probabilities of being chosen at all subsequent round t. Therefore, FTPL is approximately incentive compatible with respect to this more general incentive structure as well.
Theorem 3 allows to bound the regret of the FTPL algorithm with respect to the true beliefs of the experts. First, note that FTPL obtains the following bound with respect to the reported beliefs of the experts.
Theorem 4. For the FTPL algorithm with noise distribution D satisfying Condition 7 with the constant > 0, if we set V
BT the following holds:
y
((p...))) min ΣΣ
Σ
(ppantd BT In
K BT
8:1 =m
t=less
t=1 JE8
Using the result Theorem we have lps. - b = Ip., by,ll S n-2B- Moreover, one can easily show that the quadratic loss function is 2-Lipschitz. Therefore, for all t e (7) and i E [K], we have:
2B
4B
((p,,, -
7 2B
Putting the above results together, we can obtain the following regret bound for the FTPL algorithm.
T
T
B[[-RT] = E
Σ ((bi,,
min
Σ Σ ((b),,,r)]
r.)] r:)
O(y BT In
8BT
S:S
7 2B
I= KES.
JES
Given that BT
in Theorem 4 the expected regret bound is Oly BT In ()) This result is
summarized in the following theorem.
Theorem 5. For the FTPL algorithm with noise distribution satisfying Condition with the constant > 0, if we set 1) Inf 3 the regret bound is O(y BT Bn K
In order to ensure approximate incentive compatibility, the probability density function of the noise distribution ff needs to be such that J(+1ī _(x) does not grow to infinity for very large z. One way to enforce this condition is via a Lipschitzness assumption on In f. Condition implies that In f is B-Lipschitz. That why smaller values of B lead to better approximate incentive compatibility which in turn results in smaller regret bounds (given that the term 47' appears in the regret bound where C' is the bound on the approximate incenive-coompatiilitt derived in Theorem (3).
We can use the FTPL al algorithm to obtain results for the partial information setting as well. (20 showed that if the hazard rate of the noise distribution is bounded by B, applying the FTPL algorithm to the partial information setting for the 1-expert problem leads to (OVBKTT K) regret bounds. Using the result of Theorem 2 we know that if Condition | holds, the hazard rate is bounded. Therefore, if the noise distribution satisfies Condition FTPL applied to the m-experts problem
approximately incentive-compatible and achieves O( BKT In
K m
regret bound.
5 Online distorted greedy algorithm
In this section, we study the setting where the utility function submodular. In this case, we have f(())) 1 liss, li Iles, ((bra,re). The problem in this setting could be
7

---

written as an online monotone submodular maximization problem subject to a cardinality constraint of size m. [2T proposed the online greedy algorithm for this problem whose (1 - ) is bounded by O(vmT'n In K). The algorithm works as follows: There are m instantiations ......: Am of no-regret algorithms for the 1-expert problem. At each round E [T], A, selects an expert 2/.t E [K] and the set St = {vI,...... Um.e] is selected. A, observes the reward f((rt,))
where Syt = (UI........ U33. }-
Inspired by Al Algorithm of [3] for online monotone submodular maximization subject to a matroid constraint, we propose the online distorted greedy in Algorithm for the special case of cardinality constraint. The algorithm is similar to the online greedy algorithm of [21] discussed above. However, in the online distorted greedy algorithm, after choosing the set S, and observing the function ft. we first compute the modular lower bound he defined as (s()) = Lies fa(ī][K] {i}). We define gr = ft lt. Note that Sr is monotone submodular as well. The reward of A, for choosing vi, at round is (1 - mt ) go (vs,, (S, + (vs,) (in case V4,e E S we repeatedly take samples from the weight
distribution of A, over the experts until observe expert not in the set 1,,,,)) This technique was first introduced by [22) for the corresponding offline problem and allows us to obtain (1 - _ }-regret bounds (where f = >x ft) with the optimal approximation ratio (optimality was shown by 23 ) instead of the (1 >-regret bounds for the online greedy algorithm.
One particular choice for ) is the WSU algorithm of 10] We summarize the result for this choice in the theorem below.
Theorem 6. For all E [m], let A, be an instantiation of the WSU algorithm of [10] for the 1-expert problem and denote f = E'= St. The online distorted greedy algorithm applied to the m-experts problem obtains the following regret bound:
[E L )-R S m
where Bi is the regret of algorithm A, If = =0, the algorithm is incentive-
cf (0, can use the online greedy algorithm of [21] instead to ensure incentive compatibility while maintaining similar bounds for the (1 ) regret. IT] provided O O(vT K) regret bounds for the WSU algorithm. If we plug in this bound in the result of Theorem 6 the regret bound of the online distorted greedy algorithm is Om K). However, this bound depends linearly on m which is suboptimal. To remedy this issue, we first provide an adaptive regret bound for the WSU algorithm below.
Theorem 7. The regret of the WSU algorithm of [10] is bounded by O(v LT| In K + In K) where |LT| is the cumulative absolute loss of the algorithm.
Note that the bound in Theorem 7 adapts to the hardness of the problem. In the worst case, we have |Lr| T and recover the O ((VTIn K)) bound proved in [10]. However, for smaller values of Lrl. improves that of [0. For the non-strategic setting with modular utilities,
the bound Theorem 7
proposed the Component Hedge (CH) algorithm and obtained a regret bound of / /2ml In( (
m In( K) where 8" is the cumulative loss of the best-chosen set in hindsight. They also gave a matching lower bound for this problem. Applying the same analysis as in Theorem 7 to the setting of
the naive approach with (M) meta-experts, can show that the regret bound of WSU matches the aforementioned lower bound.
We can use the above adaptive regret bound to improve the regret bound of the online distorted greedy algorithm. First, note that at round t E [T'. the sum of the absolute value of losses incurred by {AA,), pm is bounded as follows:
m
1 -ym 99( (S-11))) + ho(v),)) 7
((1
(ge(vu,) SL + he(()))) = f((.)) 1.
Therefore, if we denote the cumulative absolute losses incurred by Ar with |249] we have:
m
Σ
TT ST.
1=1
8

---

Algorithm Online distorted greedy algorithm
Initialization: Initialize m instances A1, ......; An of online algorithms for the 1-expert problem.
for t =1...., T do
. l..... do for
AA chooses the expert Vi,t and Si, = foi,e..... Uart-
end for
Play the set S, = S.. (u u. and observe ft. Compute the modular function (s) = Eies fe(il[K] \ (i)) and set 9r Se he-
for i I.... m do
Feedback the cost -(1 1 end for end for
he (v(,)) A.
Using the result of Theorem we know that the regret bound of the online distorted greedy algorithm
is E VIL (0) In K + K. Ex=1 V [ is maximized when |L I for all i E [m]] Thus, in the worst case, the expected (1 Sc) )reggett bound is D(VmT'nn K + m In K). While we focused on submodular utility functions this section, we can also apply the online distorted greedy algorithm to the setting with modular utilities. In this case, we have cf = O, and therefore, the algorithm is incentive-compatio and its 1-regret is bounded by O(vmT In K + In K). Unlike the FTPL algorithm that is only approximately incentive-compatible, the online distorted greedy algorithm applied to modular utility functions is incentive-compatibee However, this comes the price of an extra /m term in the regret bound.
6 Experiments
In this section, we evaluate the performance our proposed algorithms for modular utility functions on publicly available dataset from Five FivethirtEight forecasting competition in which forecasters make predictions about the match outcomes of the 2022-2023 National Football League (NFL). Before each match, FiveThiityEight provides information the past performance of the two opposing teams. Forecasters observe this information and make probabilistic predictions about the likelihood of each team winning the match. Considering that there 284 different matches in the dataset, we set T = 284. Out of the 9982 forecasters who participated this competition, only 274 made predictions for every single match. We consider two cases: K 20 and K = 100. To reduce variance, for each case, we sample 5 groups of K forecasters from the 274 and run FTPL and Online Distorted Greedy (ODG) 10 times. We m = 5, Given that FTPL is only approximately incentive- compatible and according to the result of Theorem the reported beliefs could be
2B distant from 7-2B
28 to the true beliefs to the true beliefs, we add uniformly random value in the range 1 2- model this fact. We use the standard Laplace distribution as the perturbation for FTPL. Hence, we set B 1. For both algorithms, the step size 17 is chosen according our theoretical results. In Figure
plot the average regret 1 max Σ fS) -t (S,)] of the two algorithms over time (along with error bands corresponding to 20th and 80th percentiles) along with that of the FiveThirtyEight aggregated predictions for K 20 and K 100 settings. Note that while our proposed algorithms choose m predictions at each round t E [T). the FiveThirtyEight aggregated prediction is single scalar value. The plots suggest that while the regret of all three algorithms converges to zero as gets larger, both our proposed algorithms have superior performance compared to that of the FiveThirtyEight predictions.
7 Conclusion and future directions
In this paper, studied the m-experts problem, a generalization of the standard binary prediction with expert advice problem where at each round E [T]: 1) The algorithm is allowed to pick m 2 1 experts and its utility is modular submodular function of the chosen experts, and 2) The experts are strategic and may misreport their true beliefs about the f-th event to increase their probability of

---

1e-1
1e-1
Running Regret
1.0
ODG
Running Average of Regret
1.75
ODG
FTPL
1.50
FTPL
0.8
538
538
0.6
1.00
0.75
0.4
0.50
0.2
0.25
0.0
50
100
150
200
250
50
100
150
200
250
Number of Rounds
Number of Rounds T
(a)
(b)
Figure I; Running average of regret over time for (a) K = 20 and (b) K 100.
being chosen at the next round (round + The goal is to design algorithms that incentivize experts to report truthfully (i.e., incentive-compatile) and obtain sublinear regret bounds with respect to the true beliefs of the experts (i.e., no-regret). We proposed two algorithmic frameworks for this problem. In S we introduced the Follow the Perturbed Leader (FTPL) algorithm. Under certain condition for the noise distribution (Condition [], this algorithm approximately incentive- compatible and achieves sublinear regret bounds for modular utility functions. Moreover, in Section 5) we proposed the online distorted greedy algorithm that applies to both modular and submodular utility functions. This algorithm is incentive-coppatibe but its regret bound is slightly worse than that FTPL.
This work could be extended in several interesting directions. First, none of the algorithms discussed here or in prior works have taken into account the properties of the quadratic loss function. In particular, this loss function is exp-concave, and 4 showed that for exp-concave loss functions in the 1-expert problem, the regret bound could be improved (In K) using the Hedge algorithm without the incentive compatibility property. Designing improved regret bounds for the 1-expert and m-experts problems is yet to be done. order to obtain the OIn K") regret bound for the 1-expert problem (with squared loss) using the Hedge algorithm, the algorithm makes a single prediction Σ Ti,Pii, at round t E [T] and loss (Ee Ti,tPi.t 2.) In other words, choosing an expert i [K] with probability wi, at round f is not good enough to obtain the improved O(In K') regret bound. Moving on to the m-expert problem, main challenge for obtaining regret bounds better than (vT)) to decide how to aggregate K predictions as scalar values. Second, while we focused the particular choice of quadratic loss functions, the setting could be extended to other loss functions as well. is not clear to what extent results hold when moving beyond the quadratic loss function. Finally, [16] introduced framework for augmenting online algorithms for various online problems with predictions or pieces of advice. An interesting future research direction is to extend this setting the where the predictions are given by strategic experts and study incentive compatibility guarantees for online problems beyond the m-experts problem.
wwwentive-compattee
algorithms with similarly
Acknowledgments and Disclosure of Funding
This work supported in part by the following grants: NSF TRIPODS II 2023166. NSF CIF 2212261, NSF CIF 2007036, NSF AI Inst 21 12085.
References
[1] Volodimir G Vovk. Aggregating strategies. In Annual Workshop Computational Learning Theory: Proceedings of the third annual workshop on Computational learning theory, 1990. Association for Computing Machinery, Inc, 1990.
10

---

[2] Nicolo Cesa- Cesa-Bianchi, Yoav Freund, David Haussler, David P Helmbold, Robert E Schapire. and Manfred K Warmuth. How use expert advice. Journal of the ACM (JACM). 44(3):427-485, 1997.
[3] Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation,, 108(2):212-206 1994.
[4] Jyrki Kivinen and Manfred K Warmuth. Averaging expert predictions. In European Conference on Computational Learning Theory, pages 153-167. Springer, 1999.
[5] Philip E Tetlock and Dan Gardner. Superforecasting: The art and science of prediction. Random House, 2016.
[6] Manfred K Warmuth and Dima Kuzmin. Randomized online pea algorithms with regret bounds that are logarithmic in the dimension. Journal of Machine Learning Research, 90cc):22877- 2320, 2008.
[7] Wouter M Koolen, Manfred K Warmuth, Jyrki Kivinen, et al. Hedging structured concepts. In COLT, pages 93-105. Citeseer, 2010.
[8] Alon Cohen and Tamir Hazan. Following the perturbed leader for online structured learning, In International Conference on Machine Learning, pages 1034-1042. PMLR, 2015.
[9] Samrat Mukhopadhyay, Sourav Sahoo, and Abhishek Sinha. k-experts-online policies and fundamental limits. In International Conference on Artificial Intelligence and Statistics, pages 342-365, PMLR, 2022.
[10] Rupert Freeman, David M Pennock, Chara Podimata, and Jennifer Wortman Vaughan. No-regret and ioopative online learning. arXiv preprint arXiv:2002.08877 2020.
[11] Tim Roughgarden and Okke Schrijvers. Online prediction with selfish experts. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 1300-1310. Curran Associates,
Inc., 2017.
[12] Rafael Frongillo, Robert Gomez, Anish Thilagar, and Bo Waggoner. Efficient competitions and online learning with strategic forecasters. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 479-496, 2021.
[13] Nicholas Harvey, Christopher Liaw, and Tasuku Soma. Improved algorithms for online submod- ular maximization via first-order regret bounds. Advances in Neural Information Processing Systems, 33:123-1333 2020.
[14] Michele Conforti and Gérard Cornuéjols. Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discrete applied mathematics, 7(3):251225 1984.
[15] Mark D Reid and Robert Williamson. Surrogate regret bounds for proper losses. In Pro- ceedings of the 26th Annual International Conference on Machine Learning, pages 897-904, 2009.
[16] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1-25, 2021.
[17] Nicolas Lambert, John Langford, Jennifer Wortman, Yiling Chen, Daniel Reeves, Yoav Shoham, and David M Penno k. Self-finacced wagering mechanisms for forecasting. In Proceedings of the 9th ACM conference on Electronic commerce, pages 170-179, 2008
[18] Nicolas S Lambert, John Langford, Jennifer Wortman Vaughan, Yiling Chen, Daniel M Reeves, Yoav Shoham, and David M Pennock. An axiomatic characterization of wagering mechanisms. Journal of Economic Theory, 156:389-416, 2015.
[19] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: aeta-algorithm and applications. Theory of computing, 8(1):121-164 2012.
[20] Jacob D Abernethy, Chansoo Lee, and Ambuj Tewari. Fighting bandits with new kind of smoothness. Advances in Neural Information Processing Systems, 28, 2015.
[21] Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. Advances in Neural Information Processing Systems, 21, 2008.
[22] Moran Feldman. Guess free maximization of submodular and linear sums. Algorithmica, 83(3):853-877 878, 2021.

---

[23] Maxim Sviridenko, Jan Vondrák, and Justin Ward. Optimal approximation for submodular and supermodular optimization with bounded curvature. Mathematics of Operations Research, 197-)11197,1218, 2017.
12

---

Appendix
A Missing proofs
A.1 Proof of Theorem 1
At time = 1, we set TT11
for each set where |S] = m and update these weights as follows:
T = =T, s,,,
where Lg, = ls.t Estist= T beri and E3 1 Eies li If we denote the optimal set as S", we can write:
12 T+
II LL
Taking the natural logarithm of both sides, we have:
K
T
2 - In
Σ
In(1 - Ls+
m
We can the inequality In(1 - x) x
x² for x S (we choose 17 later such that this inequality
holds) to obtain:
K
T
2 in
L
17
L2
m
Rearranging the terms and dividing both sides by 77, we have:
T
T + 1
Ls
L
Using the fact that Ry = Ei= - Lg t the inequality (K))
Ke ) and Ls, S 1 VSS. we can <
write:
Rr < m Iu(
+ nT.
Setting =
we obtain the regret bound O( m2 (n( Note that the assumption nLs.. < (used in the proof) holds T 2 4m In Ke). satisfy this inequality.
Inf T
m Therefore, we assume T' is large enough to
A.2 Proof of Theorem 2
We can show that if B max, [=((z), the hazard rate of the distribution is bounded above by as f(-#) f(x)
well. To see this, fix 2 0. Note that I-P(-z) 1-F(-2) S I-F(a) for symmetric zero-mean distribution and therefore, only need to bound the hazard rate at 0 to bound hazp. We can
f(z)
13

---

write:
fD(z)
fD(x)
FD (z)
1 fD(2)dz
exp( (p((((x))
1 exp( -V(2)dz
1
1xd exp(v(x) vx)))dz
S exp((x 2)///( (2)) (20)) 1
JN exp(B(x - 2)
(1/B) B,
where we have used the mean-value theorem in (a) and Zn is in the line segment between & and z. Also, note that since æ, >> 0, 2z > holds as well and therefore, (2z) 0. We have used this fact along with x 2 < 0 to obtain (b). Therefore, we have hazp S B.
A.3 Proof of Theorem 3
Let's fix round t E [2'] and expert i E [K]. For j * i, denote 23,0 E.= li. + p3, + Mia as the total losses of expert j to round t plus noise if 0. Similarly, we can define 2j = E f,,- (1 1-)p;)) My.a- Define x (x(*) the m-th smallest value in { (f liti).
Note that (x( (t) - x (1) < holds because for each * i, we have 105500 "j1 I 1. Also, let
(1)
L L -- 4,,- If 0, expert i is chosen at round t + if and only if L + pf. + Mi, <= x²
Similarly, for the case 1, expert i is chosen if and only if L + (1 pt,)) Mia <= x1(). Rearranging the terms, we can write:
7he + L - xx -p,, if O,
Mi. + - x(() - -(1 p=,))² if = 1.
Given that f(H,)) & exp(- if we define Yo = 77/18 + L - ( and Y1 = m/, + L - x-(1) we have:
fo(Y)) x exp(-v( v( (L -6- ) )),
17
fi( x exp(- Vi (I. x((1) -1)
r7
Therefore, Fo and F, denote the cdf, we can write the probability of expert being chosen at round 1+ Fo(-pī,) and (- pt.r) for the cases r, and r. 1 respectively. Putting the above results together, we can write the expected utility of expert i (according to her belief by.)) at round as follows:
E Bemoullln))) (U,d)] (1 b..))oo(-PP.)) bi,Fi(((11 p).
14

---

Taking the derivative and setting it to zero, we have:
d
Bermoallll) (11,,. -2p,, -1,))f((- 2(1 -Pis)bbefi((( p(.,) 0,
dpi,t
fol fo(-pi,t)
2/1(-11 -Pt,.) pr,e(1 (1- be.e) fi(-(1 pi.,))) + +(1 -pi.))))..) = 0,
exp(-u) Ph. (1.- xx
-Pia(1 birs)
+ ++11 - --Piie). = 0,
exp( exp(-v( v( (1 pt,12 (1- (1--x, 2
9)
-Prs(1 ba.)) exp(p( -11 p(.t) -(I- (I- )() V( Pt,t (L x(())
11 )) +(1 Piaa)ba 0.
Ideally, we want A to be as close to possible because if A 1, Pi, bir and the algorithm would be incentive-come compatible In general, we have:
b
Pi. bir +1- b1,)
Note that this is not a closed-form solution for P because A is also a function of Piạ- We can observe that for Pt, Pi,e- the derivative of the utility function is positive, and for Pi >> pi the derivative is negative.
We can bound A as follows: Let g(u) = f(( -((=ii-aa-ll'-p) where a L xx10 + - 2pr.c.
a' == - -- and f(2) exp(-v(2)) Taking derivative of g with respect to obtain:
(a' - a)) pi, aa-aaa-'
f( ph. - a - ulaa -a)) (a' a)v/ ph. a ula' aa)
g'(u)
7
g(u).
n
n
Therefore, we can write:
In f( ph a'
1/.
In
Ing(1) In
11
L' g((u) du g(u)
ua-laa-
(a' -a)''
du.
We have a' x((0 - xx(0) 2p;,: 1. Therefore,
-2 d' 2 holds. Moreover, Putting the above results together, the
ph. phaa-au((aaaa) < B due to Condition
have -B < v'(
following holds:
2B
ph. a'
Př, -0) <
2B
< In = IIn f(
In ʃ(
Therefore, A [exp( -2B ), exp( ). Let h(pL.) Pt, Př, Pi, b +11bb11,))4 b.
b
Since we
Pī, E [0, 1], we have (10) and h(11) > O. Taking the derivative of h with respect to Pi.s have:
1+ be. - bi.e) A 221- vl (1-P) pL.) (L P (L-XX() + 2put D'( Pi. PL. ((-X(1)
dh
dp..
(b, + (1 bx,2
Using Condition
we have 1
2Bb, (1.,)
< dpa."
Therefore, we can write:
71b;,1+(1-b,, (1-b,.)))))) b.,()
dh 1- 2Bb by.e)AA
+ (1 2 2b, bb,) 2 1- 2Bb
2Bb, ( b
b.,)A
B
1
1-
0.
dpi,t
1bbb (1 A),
1162 1,t
2nb
b
7
15

---

We choose 1 later such that 17 > B for the last inequality to hold. So, h is strictly increasing, there is exactly one solution p and the derivative is positive below it and negative above it. If we replace A with something larger in p the value decreases and vice versa. Therefore, we can write:
pl.+ S
b,.t (1
bi,e Jexp(
21
bi,t
exp(
-2
+ be,e -exp(
21
bir
exp( 22
bi.r
2B
nbi,
2B
2Bb,a
bi, +
17 2B
2B
< b + 2B"'
Similarly, we can lower bound P.. as follows:
bitt
pl. 2
di. + (1
texp)
2B
biet
exp( 2B
(e.p
(2B) 1)
77
by,t
exp( 2B
-2B
:,,,ep((
17
2B
2 (1,r(1
2B
b
11
Putting the above results together, we conclude that |pt, - biel S
2B n-28
holds.
A.4 Proof of Theorem
1) > 0 and X' be the set of (k) feasible sets of size m for this problem. Denote L, R as the partial sum of losses for all experts before round t, i.e., [Le]== = = li,.. The update rule of FTPL at round E [T'] is ग. = arg min (I, Le + 77)). First, we analyze the expected regret of the algorithm below.
Define (0(
Then, we have Vor(Le) E, [arg min L, + my)l = En [iTe] and (Vor(Le), 4)) = E ((Te,
ENN [minzex (x., 0 + mi))
Using the Taylor's 's expansion of o,, we can write:
(e, (o)(L))) = di (L (ITT, 4.) 41)+ (be, (L))))))))
(.(L411) - -u
where Lí is in the line segment between L, and L++1 = LL + l. By definition, di is the minimum of linear functions and therefore, it is concave, Thus, (Por is negative semidefinite. Note that since 2/ is simply K i.i.d. samples of the noise distribution for all t [T]. we have (r) x(0)
16

---

BYND (mi (2, 0 + mm)) Taking the sum over E [T] and rearranging the terms, we obtain:
E
(Te -.,61==66 - 0f 11
le V (L)))))
1=1
t=1
Using Jensen's inequality, write:
((T++1) B [min(x, IT41 m7) min ByND" x (rr, LT+1 m7) = min LT+1)- =Et
#EX
sE
Therefore, rearrange the terms and bound the expected regret as follows:
E RTT - E
(TT, 41)
1
min LT+1) S m 6(0)
2m Σ (4, v (L))).
1
m
m DEd
t=1
To bound the first term on the right hand side, we can use the fact that D is symmetric to write:
(p( = - Exyx [min(x, m/)) -),_y> [max(x, -7>] BByDDD [maa((x,)) 7)]-
"Ex""
Now, we move on to bound the second term in the regret bound. Given that the losses of the experts each round & [T] are bounded between and 1, have l| I 1. Therefore, have:
(le, V 0. (L))))
E (E,))
JJE|K]
By definition, if we denote #(0) = arg min (a, 0), we have:
o 1 By- (A, m7); do(w))) 17
d%
Given the concavity of 6, diagonal entries of the Hessian Va are non-positive. We can also use 1 (0) = m to show that the off-diagonal entries are non-negative and each row or column of the
Hessian sums up to O. Therefore, we have ΣijE(K V - -E Vi, Putting the above results together, we can bound the regret as follows:
T
EYDDN [+(L: m7); du(tz)
B[Rr] S We can bound the first term as follows:
7 m EE mmxx(x, 7 +
Σ
ZEX
Tpm
dys
E D [max(x, ?>1 S inf In Σ
E BRNDA (exp(s(x, 7)11
TEX
#1030
xEX
inf
In
E ~ (exp((xxx))))
#:030 8
1
inf
In (B (D (exp(87) m)
s:s30 s
1 In |
inf
In (eEmn-/eexpppp)
s:s30
s
Ke
< inf
In m
) +
In D.ExD//ex((s7))
#:830
s
K
S 0m In(
)) + (m)
m
K
0m In(
m ))-
To bound the second term in the regret bound, we can use Condition | to write:
du(
K
Σ EnDDiT(Li my),
B
Σ E ByNolE(L, m7) BE D -(L 77){
Bm.
dr:
Putting the above results together, we have:
E[Rr] S In) ))+ BT
Therefore, if we set
Ind 3 the regret bound is O BT ()). the proof of Theorem 3
assumed that 77 is chosen such that 77 B. So. assume T > B In K)
17

---

A.5 Proof of Theorem 6
For E [m] and E [T], define:
(s,((S) - -m- (e) + hr(S).
(8)
For all E [m], we write
(s.e(S,,)) 0i (1 = (1 j (c((),)) + he((st)) (1- 1 y gi ( - h44 (5:
m
m (9(()()) (c( + (e(((i.)) + - -11 1 m ge
= [1
m
m
Taking the sum over t E [T), we obtain:
1
Σ (S.,)) 01-1,(((-1,,)) (1
m - -S(()-1,)) + Σ he(vi,))
+
-
ym
9e (s,
m
m
m
T
T
Σ (es,)st) 1
(1 m
m-
Σ gi
9t 15:
m
m
the regret of A; is bounded above by n and the optimal benchmark solution OPT {v],... m. , for all j E [m]] we can write:
Σ (1--- 90(03 ( Me(rg)
Σ
mm -m
[(1-
9(0 + he(v)))) ng.
m
Putting the above inequalities together, we have:
Σ (S.,) (5 2
1
T m
1
m
he(0))
m
m
m
b=
t=1
1 mm
9r (S - -1e40
m
t=1
We can use submodularity and monotonicity of ge to write:
m >
9e (OOPP)) S g. (OOTTUS--L)- = _.
s
ge
1=1
j=1
We can combine the last two inequalities to write:
1
1
(Sr,.) (1-1,(()-1,,))
2 (1
(OP)) (S:-,,)))) +
ku()))
m
m
t=1
[=1 j=
T
+ - (1
1
9t (S, -R44
m
1 (OPT) +
ha(07)- - 12
m
t=
Taking the sum over i E [m]] we have:
T
T
(Si.)) - 01-1..
m
(PP)) +
he(e))
R
1=1
t=1
1=1
i=
T
m Σ
= (1 (1
m
9 (OPT)
(OPT)
R
m
1=
T
2 (1 (OPT)
h (OPT) Σ R (8)
18

---

On the other hand, we have:
T m
T
T
T
Σ> (
Σ
Σ
(o.( = Σ S(())).
=
1=1
Combining the last two inequalities, we obtain:
Σ f((S.) 2 (1 (1-
96 (OPT) Σ (OPT) Σ R
T
T
T
= Σ
f((PTT) - -(1
(OPT) + Σ ((PT)
- -
R
2=1
= (1
1
Σ [((PPT)
(OPT)
R(0
1=1
t=1
21 1
Σ [((PPT)
1 Cf
[(OPT)) Σ
m
RT
i=1
L (OPT)
R
where Et
Rearranging the terms, obtain the (1 L distorted greedy algorithm as follows:
regrett bound of the online
T
(1 2 M(PPT) - ((S)) < Σ 2
1=1
1=1
To see why the online greedy algorithm incentive-compatibl, note that at round E [T], the loss of expert E [K] for the instance A,; i [K] is:
- -
II
Eaallj, 1).
KES:-1.t
( we use jit+1 to denote the probability expert j being chosen at round L+ 1 by A,, we can write:
( (2) 33 (1
II KES;-1.
Cx,e
(1) (.l))))
Jitt1
"jt+1 is linear in li.r and expert j does not have control over the term ILEES lR,t (because S,-1, is unknown to the expert). Therefore, to maximize "j expert j can only aim to minimize Br.-Bem((b..) L9. -EK (. Given that the quadratic loss function is proper,
(6)
conclude that A, is incentive-com nnceativecoompatibe.. Moreover, since the online greedy algorithm simply outputs the predictions of [A, this algorithm is incentive-compatible as well. For the case with C = 0, the loss expert j E [K] for each instance Aū E [K] in both online greedy algorithm and online distorted greedy algorithm is simply (l 1) and the same argument holds.
A.6 Proof of Theorem 7
First, assume that the losses are non-negative, Using the update rule of the algorithm, we can write:
T
2 Te = Ne,
II
nbr,,)
1=1
(1 mLr
(1 (L-n,a))
K
E:I,,,
20
19

---

We can use the inequalities 1 111 2 (1 (1- - for r E [0, and 1- -1 2 (1+ for x E [-1.0] write:
1 K
(1 (1-1)) Mave II (1 (1+ hu
(tl.",1100
0 2 K +
Σ
Li In - 11)
Σ
Li In(1 + n).
Given the inequalities In(1 x) 2 - - x and In(1 + x) 2 x² for S 2/4 we have:
0 - In K (-1- )
Σ
I (n 11-17² n/2
Σ Le
1:be0 20
0 KnKK 1)
Li 1
Le
t=1
InK
RT T
+
Given that Li-,e = l,0 T,E,, l,, we can write:
RT < InK +1 Σ 16,, m. 4
In K
In
+
+ +|+T)),
where | and |Ll are the cumulative absolute loss of the benchmark and the algorithm respectively. respccii Therefore, if we 7) min (1, V Lr 1
In ). obtain O( //waaaa/rriiii//////// [ In K + In K)
regret bound. Given that R7 LT Lj if | LT Li |Lp the regret is negative and if |Tr| LT 2 L |1 the regret bound is ( In + In K). Therefore, the regret bound O ( In K + In K) always holds.
20


Reviews:
[{"review_id": "swB9Y4shW0", "reviewer": "Reviewer_9kMc", "summary": "The paper broadly focuses on the design and analysis of no-regret and incentive-compatible algorithms for the m-experts problem (pick a subset $S_t \\subseteq [K]$ of $m$ experts in each round $t$ to obtain a utility value $f_t(S_t)$ which is a function of the losses $\\ell_{i,t} \\in [0,1]$ for all $i \\in S_t$), with specific utility functions (on the space of m-sized subsets of experts) in each round which are either modular or sub-modular.\n* They try to improve on the inefficient baseline of using the no-regret, incentive-compatible WSU algorithm (Freeman et all 2020) on the set of $\\binom{K}{m}$ meta-experts corresponding to sets of $m$ experts.\n* They analyze the FTPL algorithm in the modular utility function case where the perturbation distribution is zero-mean symmetric from an exponential family. They propose a sufficient-condition for this distribution (related to bounded hazard rate) which implies that FTPL would be no-regret and approximately incentive-compatible. In particular, they show that this condition is satisfied for the Laplace distribution and the symmetric hyperbolic distribution etc.\n* They propose and analyze an \"online distorted greedy algorithm\" (based on earlier work by (Harvey et al. 2020) on online submodular maximizination) for the submodular utility function case. They show that the algorithm has sublinear $\\alpha$-regret bounds and is $\\alpha$-approximately-incentive compatible. where $\\alpha$ may be $ < 1$ for general submodular functions (depending on the \"curvature\") while $\\alpha = 1$ in the modular case. This of course implies that the algorithm has no-regret in the usual sense and is fully incentive compatible in the modular case, but at the expense of more computation and a slightly worse regret bound compared to FTPL.\n\n\n", "questions": "None", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The online $m$-experts problem is well-motivated in the introduction, as is the importance of incentive compatibility for the problem. \n* The algorithms proposed (FTPL and online distorted greedy) are natural for the problem and build nicely on previous work. All the appropriate details are given, along with the code and experiments.\n* The proposed sufficiency condition for the perturbation distribution of FTPL is fairly general, and may be of independent interest in the study of incentive compatibility. \n* Sufficient proof-sketches are given for quite a few of the results in the main paper itself, and more detail is provided in the supplementary material.\n\n", "weaknesses": "* The FTPL analysis applies to a single modular utility function defined in the paper (Line 136). Of course, this utility function is fairly natural for the problem. \n* The necessity of \"Condition 1\" for getting approximate-incentive-compatibility with FTPL is not explored.\n* The experimental evaluation provided is fairly limited (of course, the thrust of the work is theoretical).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for their constructive feedback and comments. We hope our responses below may help and perhaps convince the reviewer to raise their score. We are happy to answer any further questions during the author-reviewer discussion period.\n\n$\\bullet$ **Q:** The FTPL analysis applies to a single modular utility function defined in the paper (Line 136). Of course, this utility function is fairly natural for the problem.\n\n**A:** While the FTPL algorithm is only applicable for the setting with modular utility functions, we can use FTPL as the algorithm $\\mathcal{A}_i$ for $i=1,\\ldots,m$ in the online distorted greedy algorithm, and obtain results for the submodular utility setting as well. In this case, the online distorted greedy algorithm would be only approximately incentive-compatible.\n\n$\\bullet$ **Q:** The necessity of \"Condition 1\" for getting approximate-incentive-compatibility with FTPL is not explored.\n\n**A:** We believe that Condition 1 is not necessary to achieve approximate incentive compatibility. For example, it is well-known that the FTPL algorithm with Gumbel noise distribution is equivalent to the Hedge algorithm. [7] showed that the Hedge algorithm is approximately incentive-compatible for the $1$-expert problem. However, as we have mentioned in lines 248-249 of the paper, Condition 1 does not hold for the Gumbel distribution.\n\n$\\bullet$ **Q:** The experimental evaluation provided is fairly limited (of course, the thrust of the work is theoretical).\n\n**A:** We have provided additional plots that better demonstrate the performance of our proposed algorithms. Please see the \"global\" response to all the reviewers for more details."}, {"review_id": "tfK9LzDRVM", "reviewer": "Reviewer_xXJd", "summary": "- The paper studies the problem of online prediction with expert advice. In their setting, a learner at each round selects $m$ experts, and the loss is determined by a submodular or modular function of the beliefs reported by the selected experts. Each expert, being strategic, may intentionally misrepresent their beliefs to maximize their chances of being selected in the next round. The goal of the learner is to design no-regret algorithms that incentive experts to report their beliefs truthfully (also called IC).\n\n- To tackle this problem, the authors first present an inefficient reduction to the case when $m=1$. Subsequently, they propose two efficient algorithms that are for the specific types of loss functions considered.\n\n    - In the case of the modular loss function, the authors investigate Follow-The-Perturbed-Leader (FTPL) and propose a general condition for the perturbation distribution that ensures approximate IC.\n\n    - For the submodular loss function,they propose a simpler algorithm named the online distorted greedy algorithm. This algorithm not only guarantees exact IC but also attains the optimal approximation ratio.", "questions": "1. Regarding Def 1: \n    - Is this a new concept being proposed, or has it previously been studied in previous works? \n    - The experts are long-standing in this setting, but the focus of the paper is on myopic IC. Although the authors mentioned that the analysis of FTPL could be extended to the more general setting of maximizing a conic combination of probabilities of being chosen at all subsequent rounds, is it also true for the online distorted greedy algorithm? What's the main modification/challenge of extending to non-myopic experts?\n    - Would achieving IC become impossible if the definition is for all $r_t$, rather than the expectation over Bern( $b_{i,t}$ )?\n\n2. In the \"forecasting competitions\" example described in Section 3.1, it seems that the loss function is not captured by the modular function studied in this paper, given it is normalized by $|S_t|$ rather than $m$.\n\n3. About Thm 1, could you clarify why the reduction preserves IC? In particular:\n    - How is the belief of each meta-expert defined in this context? Is the new loss function $\\ell_S$ still proper? How to define IC when the belief of each expert is multi-dimensional?\n    - Even though WSU is IC for the $m=1$ problem, it only guarantees every single expert reports truthfully when fixing other's reports. In particular, it doesn't rule out the possibility that a group of experts form a coalition and misreport together to increase the sum of their probabilities of being selected, which is exactly what would happen when a single expert misreports in the $m$-expert problem -- it results in the simultaneous misreporting of $\\binom{K}{m-1}$ meta-experts.\n\n4. Thm 3 guarantees approximate IC in the sense of $|p^\\star\\_{i,t}-b\\_{i,t}|$ being small. However, a more common notion of approximate IC is through the difference of utility, which, applies to this setting, is the difference in $\\pi_{i,t+1}$ when $p^\\star_{i,t}$ and $b_{i,t}$ are reported respectively. Could the authors include a discussion about this alternative notion?\n\n5. Combining Thm 3 and Thm 5, it seems that as $B$ approaches 0, the FTPL algorithm becomes more IC and also yields a smaller regret. However, this contradicts the intuition that if the learner's decisions are entirely noise-driven (i.e., $B=0$), the regret should be high. Could the authors comment on this?\n\n6. On lines 297-298, you mention that the $(1-\\frac{c_f}{e})$ approximation factor is optimal. Is this claim supported by a lower bound? If so, could you point to the relevant references?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper studies an important and generic problem of online prediction with strategic experts that may find its applications in many scenarios.\n- The proposed algorithms in this paper are not only easy to implement and also enjoy good theoretical guarantees of being (approximate) IC and no regret.", "weaknesses": "1. Several claims may have some issues, see eg Questions 3, 5, 6.\n2. The presentation could be improved. For instance, Section 1.2 titled \"Contributions\" seems to contain some elements of background and motivations which might be more appropriately placed in the introduction of the paper. Moreover, it would be beneficial to include more discussions following important definitions (like Def 1) and theorems to provide more intuitions.\n3. In the experimental section, the authors plot the regret curve that is not normalized. This makes it hard to interpret, as unnormalized regret curves don't explicitly demonstrate the rate at which the algorithms learn. Additionally, to reflect the difference between reported and true beliefs, a uniformly random value within the range guaranteed by Theorem 3 is added, but this theorem doesn't ensure a uniform distribution for this difference. Finally, incorporating a comparison of the proposed algorithms with and aggregated predictions of FiveThirtyEight could potentially enrich the analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for their constructive feedback and comments. We hope our responses below may help and perhaps convince the reviewer to raise their score. We are happy to answer any further questions during the author-reviewer discussion period. Also, given the size limit for the rebuttal, we have included the responses to the rest of your questions at the end of the \"global\" response to all the reviewers.\n\n$\\bullet$ **Q:** The presentation could be improved. For instance, Section 1.2 titled \"Contributions\" seems to contain some elements of background and motivations which might be more appropriately placed in the introduction of the paper. Moreover, it would be beneficial to include more discussions following important definitions (like Def 1) and theorems to provide more intuitions.\n\n**A:** Thanks for your suggestions. We will make sure to use the additional page in the final version of the paper and provide intuitions for the definition of incentive compatibility (Definition 1) and add more discussions following our theorems. Also, we will revise the \"Contributions\" section (Section 1.2) and move the motivations to the \"Introduction\" section (Section 1) and the literature review to the \"Related work\" section (Section 1.2).\n\n$\\bullet$ **Q:** In the experimental section, the authors plot the regret curve that is not normalized. This makes it hard to interpret, as unnormalized regret curves don't explicitly demonstrate the rate at which the algorithms learn. Additionally, to reflect the difference between reported and true beliefs, a uniformly random value within the range guaranteed by Theorem 3 is added, but this theorem doesn't ensure a uniform distribution for this difference. Finally, incorporating a comparison of the proposed algorithms with and aggregated predictions of FiveThirtyEight could potentially enrich the analysis.\n\n**A:** In the plots attached to the \"global'' response to all reviewers, we have plotted the running average of regret $\\frac{1}{t}\\mathbb{E} \\big[\\max_{S\\subseteq [K]:|S|=m}\\sum_{\\tau=1}^t f_{\\tau}(S)-\\sum_{\\tau=1}^t f_{\\tau}(S_{\\tau})\\big]$ for $1\\leq t\\leq T$. In other words, we have normalized the regret by the horizon length (please let us know if we misunderstood your point about normalized regret curves and you had a different type of normalization in mind). Also, we have included the plot for running average regret of the aggregated prediction of FiveThirtyEight to highlight the superior performance of our proposed algorithms. Please see the \"global\" response to all the reviewers for more details. As we have shown in the proof of Theorem 3, at round $t\\in [T]$, expert $i\\in [K]$ needs access to the reports of other experts $p_{j,t}$ for $j\\neq i$ to be able to compute the optimal reported belief $p_{i,t}^*$. Given that this is generally not possible, we have added a uniformly random value in the range derived in Theorem 3 to model the difference between the reported and true beliefs. Note that this uniformly random value adversely affects the performance of the FTPL algorithm because the algorithm receives the noisy reported beliefs, however, its performance is evaluated based on the true beliefs. \n\n$\\bullet$ **Q:** Regarding Def 1: a) Is this a new concept being proposed, or has it previously been studied in previous works? b) The experts are long-standing in this setting, but the focus of the paper is on myopic IC. Although the authors mentioned that the analysis of FTPL could be extended to the more general setting of maximizing a conic combination of probabilities of being chosen at all subsequent rounds, is it also true for the online distorted greedy algorithm? What's the main modification/challenge of extending to non-myopic experts? c) Would achieving IC become impossible if the definition is for all $r_t$, rather than the expectation over $\\text{Bern}(b_{i,t})$?\n\n**A:** Definition 1 was first introduced by [6]. Given that the WSU algorithm of [6] is only incentive-compatible in the myopic setting, we focused on this definition of incentive compatibility to be able to use the WSU algorithm as a sub-routine in the online distorted greedy algorithm. However, as we mentioned in the paper, it is easy to show that FTPL is also approximately incentive compatible with respect to the non-myopic incentive structure (we just need to repeat the same analysis as the one in the proof of Theorem 3 multiple times for the probability of being chosen in each of the subsequent rounds). If we use FTPL as the algorithm $\\mathcal{A}_i$ for $i=1,\\ldots,m$ in the online distorted greedy algorithm, the online distorted greedy algorithm would be approximately incentive-compatible in the non-myopic incentive structure as well. We are not sure if we understand your last question (part c), it would be great if you could clarify it a bit further.\n\n$\\bullet$ **Q:** In the \"forecasting competitions\" example described in Section 3.1, it seems that the loss function is not captured by the modular function studied in this paper, given it is normalized by $|S_t|$ rather than $m$.\n\n**A:** We defined the modular utility function as $f_t(S_t)=\\frac{1}{m}\\sum_{i\\in S_t}(1-\\ell_{i,t})=\\frac{|S_t|}{m}-\\frac{1}{m}\\sum_{i\\in S_t}\\ell_{i,t}$ to make sure that the utility function is monotone and modular so that the online distorted greedy algorithm is applicable. If the cardinality of set $S_t$ is equal to $m$ (which is true for $S_t$ output by our proposed algorithms), the utility $f_t(S_t)$ is simply one minus the average loss of chosen experts. This is the utility function considered for the \"forecasting competitions\" example in Section 3.1.\n\n\n"}, {"review_id": "htskvF4g0B", "reviewer": "Reviewer_Aodd", "summary": "This paper generalizes the problem of online binary prediction with expert advice, where at each round the learner can pick m>1 experts and the overall utility is a modular or submodular utility of the chosen experts. The experts are strategic and wish to be selected by the algorithm as often as possible hence they may misreport their beliefs about the events. They design algorithms that are incentive-compatible and achieve sublinear regret in the hindsight.\nPrevious work has studied this problem for m=1. In the case of m>1, previous work have focused on designing no-regret algorithms and did not take into consideration the incentive-compatibility issues. \nTheir algorithm builds on a prior work that studies the FTPL algorithm for the m-expert problem with modular utility functions and derive conditions for the perturbation function to guarantee approximate incentive compatibility. In particular, they show that FTPL while Gaussian perturbations is not incentive-compatible, Laplace or hyperbolic noise distribution guarantees approximate incentive-compatibility.\n\nMoreover, they propose an algorithm that builds upon online monotone submodular maximization s.t. matroid constraints that takes m incentive-compatible for standard experts problem (i.e. m=1) and outputs their combined prediction. Compared to the first algorithm, this one achieves exact incentive-compatibility however, at the price of an extra \\sqrt{m} term in the regret bound.\n", "questions": "Minor comments:\nThe citations need to be fixed, they do not show the authors' name, need to use \\citet.\nLine 268, can you expand on why this holds?\n\nQuestion : What is the lower bound for the regret of this problem? Can you give a lower bound that is stronger than the case for m=1?\n", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is written nicely and is easy to follow. The problem seems to be well-motivated. I did not go through the proofs. The second algorithm is more straightforward, however, I think it is nice that they included it and compared it with their first algorithm.\n", "weaknesses": "It might be helpful to add a discussion on the regret lower bound for this problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for their constructive feedback and comments. We hope our responses below may help and perhaps convince the reviewer to raise their score. We are happy to answer any further questions during the author-reviewer discussion period. Also, we have provided additional plots that better demonstrate the performance of our proposed algorithms. Please see the \"global\" response to all the reviewers for more details.\n\n$\\bullet$ **Q:** It might be helpful to add a discussion on the regret lower bound for this problem. What is the lower bound for the regret of this problem? Can you give a lower bound that is stronger than the case for m=1?\n\n**A:** For the non-strategic setting with modular utilities (and without using the fact that losses are quadratic), [10] proposed the Component Hedge (CH) algorithm and obtained a regret bound of $\\sqrt{2m\\ell^*\\ln(\\frac{K}{m})}+m\\ln(\\frac{K}{m})$ where $\\ell^*$ is the cumulative loss of the best-chosen set in hindsight. They also gave a matching lower bound for this problem. Applying the same analysis as in Theorem 7 to the setting of the naive approach with $K \\choose m$ meta-experts, we can show that the regret bound of WSU matches the aforementioned lower bound. For the non-strategic setting with submodular utility functions (and without using the fact that losses are quadratic), [13] proposed the online distorted greedy algorithm (with dual averaging algorithm as the algorithm $\\mathcal{A}_i$ for $i=1,\\ldots,m$) whose $(1-\\frac{c}{e})$-regret bound is $\\mathcal{O}(\\sqrt{mT\\ln (\\frac{K}{m})})$ and this is the best bound for submodular utilities. While there are lower bounds for the $m$-experts problem without the incentive compatibility property (and without using the fact that losses are quadratic) as discussed above, neither the prior works ([6,7]) nor our work provides lower bounds under the incentive compatibility assumption (and using the fact that losses are quadratic). That being said, we thought a lot about this and we conjecture that incurring an $\\mathcal{O}(\\sqrt{T})$ regret is inevitable in the strategic setting (and considering the fact that losses are quadratic). In particular, approximately incentive-compatible algorithms typically incur an $\\mathcal{O}(\\sqrt{T})$ term in their regret bound only due to not being fully incentive-compatible. Therefore, even if the algorithm has better regret bounds in the non-strategic setting (i.e., the equivalent of Theorem 4 for FTPL) (e.g., $\\mathcal{O}(\\ln K)$ regret bound of Hedge as discussed in lines 361-363 of the paper), the overall regret would be $\\mathcal{O}(\\sqrt{T})$. We also came up with multiple fully incentive-compatible algorithms, however, it seems that obtaining regret bounds better than $\\mathcal{O}(\\sqrt{T})$ is at odds with the algorithm being fully incentive-compatible.\n\n$\\bullet$ **Q:** The citations need to be fixed, they do not show the authors' name, need to use citet.\n\n**A:** We will make sure to fix this in the final version of the paper.\n\n$\\bullet$ **Q:** Line 268, can you expand on why this holds?\n\n**A:** We can write:\n\\begin{equation*}\n    \\mathbb{E}[\\frac{1}{m}\\sum_{t=1}^T\\sum_{i\\in S_t}\\ell(b_{i,t},r_t)-\\min_{S:|S|=m}\\frac{1}{m}\\sum_{t=1}^T\\sum_{j\\in S}\\ell(b_{j,t},r_t)]=\\mathbb{E}[\\frac{1}{m}\\sum_{t=1}^T\\sum_{i\\in S_t}\\ell(p_{i,t},r_t)-\\min_{S:|S|=m}\\frac{1}{m}\\sum_{t=1}^T\\sum_{j\\in S}\\ell(p_{j,t},r_t)]+\\mathbb{E}[\\frac{1}{m}\\sum_{t=1}^T\\sum_{i\\in S_t}\\ell(b_{i,t},r_t)-\\frac{1}{m}\\sum_{t=1}^T\\sum_{i\\in S_t}\\ell(p_{i,t},r_t)]+\\mathbb{E}[\\min_{S:|S|=m}\\frac{1}{m}\\sum_{t=1}^T\\sum_{j\\in S}\\ell(p_{j,t},r_t)-\\min_{S:|S|=m}\\frac{1}{m}\\sum_{t=1}^T\\sum_{j\\in S}\\ell(b_{j,t},r_t)].\n\\end{equation*}\nLet $S_1=\\text{arg}\\min_{S:|S|=m}\\frac{1}{m}\\sum_{t=1}^T\\sum_{j\\in S}\\ell(b_{j,t},r_t)$ and $S_2=\\text{arg}\\min_{S:|S|=m}\\frac{1}{m}\\sum_{t=1}^T\\sum_{j\\in S}\\ell(p_{j,t},r_t)$. We have:\n\\begin{equation*}\n    \\mathbb{E}[\\frac{1}{m}\\sum_{t=1}^T\\sum_{i\\in S_t}\\ell(b_{i,t},r_t)-\\min_{S:|S|=m}\\frac{1}{m}\\sum_{t=1}^T\\sum_{j\\in S}\\ell(b_{j,t},r_t)]\\leq\\mathbb{E}[\\frac{1}{m}\\sum_{t=1}^T\\sum_{i\\in S_t}\\ell(p_{i,t},r_t)-\\min_{S:|S|=m}\\frac{1}{m}\\sum_{t=1}^T\\sum_{j\\in S}\\ell(p_{j,t},r_t)]+\\mathbb{E}[\\frac{1}{m}\\sum_{t=1}^T\\sum_{i\\in S_t}\\ell(b_{i,t},r_t)-\\frac{1}{m}\\sum_{t=1}^T\\sum_{i\\in S_t}\\ell(p_{i,t},r_t)]+\\mathbb{E}[\\frac{1}{m}\\sum_{t=1}^T\\sum_{j\\in S_1}\\ell(b_{j,t},r_t)-\\frac{1}{m}\\sum_{t=1}^T\\sum_{j\\in S_1}\\ell(p_{j,t},r_t)]\\leq \\mathcal{O}(\\sqrt{BT\\ln (\\frac{K}{m})})+\\frac{1}{m}\\sum_{t=1}^T\\sum_{i\\in S_t}\\frac{4B}{\\eta-2B}+\\frac{1}{m}\\sum_{t=1}^T\\sum_{j\\in S_1}\\frac{4B}{\\eta-2B}=\\mathcal{O}(\\sqrt{BT\\ln (\\frac{K}{m})})+\\frac{8BT}{\\eta-2B},\n\\end{equation*}\nwhere the last inequality follows from line 265 and line 267 of the paper."}, {"review_id": "dla2uwWVTi", "reviewer": "Reviewer_oxKD", "summary": "This submission studies the problem of online decision-making using predictions given by experts with incentives to behave strategically. In particular, at each time-step, K experts hold a belief about a binary outcome. Each expert reports a prediction to a learner, who picks a set of m experts. The learner then suffers a loss which is a function of both the binary outcome and the chosen experts' true beliefs about the outcome. The goal of the learner is to achieve no-regret with respect to the best-in-hindsight choice of m experts while maintaining incentive compatibility, i.e. reporting their true belief as their prediction is a weakly-dominant strategy for each expert at every time-step. \n\nThe authors study two settings: one in which the learner has a modular utility function and one in which their utility function is submodular. An existing algorithm (WSU, [6]) for the 1-expert version of this problem (i.e. the version of the problem where the learner selects one expert at each time-step) is capable of getting sublinear regret in both settings, albeit at the cost of exponential runtime. For modular utility functions, authors show how to use a variant of the well-known Follow the Perturbed Leader (FTPL) algorithm under a sufficient condition for the perturbation distribution to guarantee both no-regret and approximate incentive compatibility. \n\nFor submodular utility functions, the authors use an \"online distorted greedy algorithm\" to obtain no-regret while maintaining incentive compatibility constraints exactly. At a high level, the online distorted greedy algorithm runs m algorithms for the strategic 1-expert problem concurrently. At each time-step, each of the m sub-algorithms selects an expert, and the learner uses these m experts as their selection. Based on the loss the learner receives, they set the loss of each sub-algorithm in a particular way. The authors use the WSU algorithm of [6] as their sub-algorithm. Along they way, they derive an adaptive regret bound for the WSU algorithm, which may be of independent interest. \n\nFinally, the authors empirically evaluate their two algorithms on a dataset from a FiveThrityEight forecasting competition to predict the outcomes of games in the 2022-2023 NFL football season. They find that both algorithms obtain similar performance in this setting. ", "questions": "What are the runtimes of both algorithms? \n\nWhat regret rates are obtained for the non-strategic m-experts problem with squared loss? ", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "While others have studied the (non-strategic) m-expert problem, as well as the strategic 1-expert problem, the authors are the first to study the strategic m-expert problem. This setting is well-motivated by applications such as forecasting competitions. While the algorithms presented by authors are not particularly novel, their application to the strategic m-expert problem requires non-trivial theoretical analysis, as well as some new ideas, such as (1) the sufficient condition for the perturbation distribution to guarantee approximate incentive compatibility in the modular setting, and (2) the adaptive regret bound for the WSU algorithm used as a subroutine for the submodular setting. \n\nWhile I would normally consider the experimental results on real-world data as a strength, their impact is limited due to the lack of relevant comparisons (see Weaknesses for more details).  \n\nFinally the writing is clear, which makes the authors' contributions easy to understand. ", "weaknesses": "The lack of any sort of lower bound is a weakness, especially since (as the authors point out) the loss function they consider is exp-concave, and thus the regret rates of Hedge in the non-strategic version of the problem where one expert is selected scale only logarithmically in the number of experts (and independently of the time horizon). While it may indeed be the case that going from constant-in-T to T^{1/2} regret rates is the price to pay for incentive compatibility in the m-expert problem, this submission presents no evidence either for or against this claim. \n\nIt would be nice to have provide some background on the current state of the (non-strategic) m-expert problem in the related work. \n\nFinally, the experimental results would be strengthened considerably if (1) the theoretical rates and (2) the regret of the naive application of the WSU algorithm were also plotted. Currently, it is not easy to see how well the algorithms are actually doing without the relevant baselines. Additionally, it would be interesting to see how closely the empirical performance of the algorithms match their corresponding theoretical bounds. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for their constructive feedback and comments. We hope our responses below may help and perhaps convince the reviewer to raise their score. We are happy to answer any further questions during the author-reviewer discussion period.\n\n$\\bullet$ **Q:** The lack of any sort of lower bound is a weakness, especially since (as the authors point out) the loss function they consider is exp-concave, and thus the regret rates of Hedge in the non-strategic version of the problem where one expert is selected scale only logarithmically in the number of experts (and independently of the time horizon). While it may indeed be the case that going from constant-in-$T$ to $T^{1/2}$ regret rates is the price to pay for incentive compatibility in the $m$-expert problem, this submission presents no evidence either for or against this claim.\n\n**A:** While there are lower bounds for the $m$-experts problem without the incentive compatibility property (and without using the fact that losses are quadratic) (see the response to your next question), neither the prior works nor our work provides lower bounds under the incentive compatibility assumption (and using the fact that losses are quadratic). That being said, we thought a lot about this and we conjecture that incurring an $\\mathcal{O}(\\sqrt{T})$ regret is inevitable in the strategic setting. In particular, approximately incentive-compatible algorithms typically incur an $\\mathcal{O}(\\sqrt{T})$ term in their regret bound only due to not being fully incentive-compatible. Therefore, even if the algorithm has better regret bounds in the non-strategic setting (i.e., the equivalent of Theorem 4 for FTPL) (e.g., $\\mathcal{O}(\\ln K)$ regret bound of Hedge as discussed in lines 361-363 of the paper), the overall regret would be $\\mathcal{O}(\\sqrt{T})$. We also came up with multiple fully incentive-compatible algorithms, however, it seems that obtaining regret bounds better than $\\mathcal{O}(\\sqrt{T})$ is at odds with the algorithm being fully incentive-compatible.\n\n$\\bullet$ **Q:** It would be nice to have provide some background on the current state of the (non-strategic) $m$-expert problem in the related work.\n\n**A:** For the non-strategic setting with modular utilities, [10] proposed the Component Hedge (CH) algorithm and obtained a regret bound of $\\sqrt{2m\\ell^*\\ln(\\frac{K}{m})}+m\\ln(\\frac{K}{m})$ where $\\ell^*$ is the cumulative loss of the best-chosen set in hindsight. They also gave a matching lower bound for this problem. Applying the same analysis as in Theorem 7 to the setting of the naive approach with $K \\choose m$ meta-experts, we can show that the regret bound of WSU matches the aforementioned lower bound. [11] studied the FTPL algorithm with Gaussian noise distribution and provided an $\\mathcal{O}(m\\sqrt{T\\ln (\\frac{K}{m}}))$ regret bound for this setting. For the non-strategic setting with submodular utility functions, [13] proposed the online distorted greedy algorithm (with dual averaging algorithm as the algorithm $\\mathcal{A}_i$ for $i=1,\\ldots,m$) whose regret bound is $\\mathcal{O}(\\sqrt{mT\\ln (\\frac{K}{m})})$. More recently, [12] studied the $m$-experts problem under various different choices of the utility function (sum-reward, max-reward, pairwise-reward and monotone reward). In particular, for the setting with modular utilities (sum-reward), they proposed an algorithm that matches the optimal regret bound of the CH algorithm while being computationally more efficient. We will make sure to add this discussion to the \"Related work\" Section (Section 1.1) in the final version of the paper.\n\n$\\bullet$ **Q:** The experimental results would be strengthened considerably if (1) the theoretical rates and (2) the regret of the naive application of the WSU algorithm were also plotted. Currently, it is not easy to see how well the algorithms are actually doing without the relevant baselines. Additionally, it would be interesting to see how closely the empirical performance of the algorithms match their corresponding theoretical bounds.\n\n**A:** We tried to implement the naive application of the WSU algorithm in our experiments. However, the number of meta-experts for our two experiments was $20 \\choose 5$$=15504$ and $100\\choose 5$$=75287520$ and the experiments did not finish (we waited for a few hours). In the \"global\" response to all the reviewers, we have included two new plots in which we have compared the running average of the regret of our proposed algorithms with that of the FiveThirtyEight aggregated predictions as the baseline. Please see the \"global\" response for more details.\n\n$\\bullet$ **Q:** What are the runtimes of both algorithms?\n\n**A:** Both algorithms had similar runtime for our experiment which was around 3-4 minutes for each.\n\n$\\bullet$ **Q:** What regret rates are obtained for the non-strategic $m$-experts problem with squared loss?\n\n**A:** While there exist prior works on the non-strategic $m$-experts problem (discussed above), none of these papers take the structure of the loss function (quadratic loss in our setting) into account. In order to obtain the $O(\\ln K)$ regret bound for the $1$-expert problem (with squared loss) using the Hedge algorithm, the algorithm makes a single prediction $\\sum_{i=1}^K \\pi_{i,t}p_{i,t}$ at round $t\\in[T]$ and its loss is $(\\sum_{i=1}^K \\pi_{i,t}p_{i,t}-r_t)^2$. In other words, choosing an expert $i\\in[K]$ with probability $\\pi_{i,t}$ at round $t$ is not good enough to obtain the improved $\\mathcal{O}(\\ln K)$ regret bound. Moving on to the $m$-experts problem, the main challenge for obtaining regret bounds better than $\\mathcal{O}(\\sqrt{T})$ is to decide how to aggregate the $K$ predictions as $m$ scalar values."}]

Author rebuttal:
In the attached file, we have included two additional figures plotting the running average of regret $\frac{1}{t}\mathbb{E} \big[\max_{S\subseteq [K]:|S|=m}\sum_{\tau=1}^t f_{\tau}(S)-\sum_{\tau=1}^t f_{\tau}(S_{\tau})\big]$ for $1\leq t\leq T$ for our proposed algorithms and also the FiveThirtyEight aggregated predictions in the $K=20$ and $K=100$ settings. Note that while our proposed algorithms choose $m$ predictions at each round $t\in[T]$, the FiveThirtyEight aggregated prediction $\bar{p}_t\in [0,1]$ is a single scalar value and we measure its loss as $(\bar{p}_t-r_t)^2$. As could be seen in the plots, while the regret of all three algorithms converge to zero as $t$ gets larger, both our proposed algorithms have a superior performance compared to that of the FiveThirtyEight prediction. It is also noteworthy that the overall regret of both our algorithms is way better than the corresponding theoretical bounds proved in the paper. Given the huge distance between the theoretical bounds and the regret curves, we decided not to include them.

# Rest of Response to Reviewer xXJd:

$\bullet$ **Q:** About Thm 1, could you clarify why the reduction preserves IC?

**A:** Note that for the naive approach discussed in Section 3.2, we still define incentive compatibility with respect to individual experts (instead of the $K \choose m$ meta-experts). To be precise, we define $\pi_{i,t}=\sum_{S:|S|=m,i\in S}\pi_{S,t}$. For both choices of the loss function ($\ell_S=\frac{1}{m}\sum_{j\in S}\ell_{j,t}$ and $\ell_S=\prod_{j\in S}\ell_{j,t}$ where $i\in S$), the loss of the set is linear in $\ell_{i,t}$ and given the fact that the loss function is proper, we can show that in such cases, the WSU algorithm applied to $K \choose m$ meta-experts is incentive-compatible. For example, for the setting with modular utility function ($\ell_S=\frac{1}{m}\sum_{j\in S}\ell_{j,t}$), we can show the following:
\begin{equation*}
\pi_{i,t+1}=\sum_{S:|S|=m,i\in S}\pi_{S,t+1}=\pi_{i,t}(1-\frac{\eta}{m} L_{i,t})-\frac{\eta}{m} \sum_{s\neq i}(\sum_{S:|S|=m,\{i,s\}\subseteq S}\pi_{S,t})\ell_{s,t}.
\end{equation*}
Given that $\pi_{i,t+1}$ is linear in $L_{i,t}$, $L_{i,t}=\ell_{i,t}-\sum_{j=1}^K \pi_{j,t}\ell_{j,t}$ is linear in $\ell_{i,t}$, and the loss function is proper, we can conclude that incentive compatibility holds in this setting. Thanks for your question, we will make sure to clarify this point in the final version of the paper.

$\bullet$ **Q:** Thm 3 guarantees approximate IC in the sense of $|p_{i,t}^*-b_{i,t}|$ being small. However, a more common notion of approximate IC is through the difference of utility, which, applies to this setting, is the difference in $\pi_{i,t+1}$ when $p_{i,t}^*$ and $b_{i,t}$ are reported respectively. Could the authors include a discussion about this alternative notion?

**A:** As we have shown in the proof of Theorem 3, the expected utility of expert $i$ (according to her belief $b_{i,t}$) at round $t$ (i.e., her probability of being chosen at round $t+1$) is $(1-b_{i,t})F_0(-p_{i,t}^2)+b_{i,t}F_1(-(1-p_{i,t})^2)$, where $Y_0=\eta \gamma_{i,t} + L - X_0^{(t)}$, $Y_1=\eta \gamma_{i,t} + L - X_1^{(t)}$, $f_{0}(Y_0)\propto \text{exp}\Big(-\nu\big(\frac{Y_0-(L-X_0^{(t)})}{\eta}\big)\Big)$, and $f_{1}(Y_1)\propto \text{exp}\Big(-\nu\big(\frac{Y_1-(L-X_1^{(t)})}{\eta}\big)\Big)$. Also, $F_0$ and $F_1$ denote the cdf corresponding to $f_0$ and $f_1$ respectively. Given that $F_0$ and $F_1$ are Lipschitz (because $f_0$ and $f_1$ are bounded), the difference in $\pi_{i,t+1}$ when $p_{i,t}^*$ and $b_{i,t}$ are reported can be bounded as a constant times $|p_{i,t}^*-b_{i,t}|$ and therefore, this alternative notion of incentive-compatibility is satisfied as well.

$\bullet$ **Q:** Combining Thm 3 and Thm 5, it seems that as $B$ approaches 0, the FTPL algorithm becomes more IC and also yields a smaller regret. However, this contradicts the intuition that if the learner's decisions are entirely noise-driven (i.e., $B=0$), the regret should be high. Could the authors comment on this?

**A:** In this paper, we focused on zero-mean symmetric noise distributions from the exponential family, i.e., $f(\gamma)\propto \text{exp}(-\nu(\gamma))$. Given that $|\nu'(z)|\leq B$, if $B=0$, $\nu(\cdot)$ needs to be constant which corresponds to the uniform distribution (note that in this case, the decisions are not entirely noise-driven). However, uniform distribution does not belong to the exponential family. Therefore, $B>0$. As we have mentioned in the proof of Theorem 3, we have:
\begin{equation*}
    p_{i,t}^*=\frac{b_{i,t}}{b_{i,t}+(1-b_{i,t})A},
\end{equation*}
where $A=\text{exp}\big(\nu(\frac{-(1-p_{i,t})^2-(L-X_1^{(t)})}{\eta})-\nu(\frac{-p_{i,t}^2-(L-X_0^{(t)})}{\eta})\big)$. Ideally, we want $A$ to be as close to 1 as possible because if $A=1$, $p_{i,t}^*=b_{i,t}$ and the algorithm would be incentive-compatible. In order to ensure approximate incentive compatibility, the pdf of the noise distribution $f$ needs to be such that $\frac{f(z)}{f(z+1)}$ does not grow to infinity for very large $z$. One way to enforce this condition is via a Lipschitzness assumption on $\ln f$. Condition 1 implies that $\ln f$ is $B$-Lipschitz. That is why smaller values of $B$ lead to better approximate incentive compatibility which in turn results in smaller regret bounds (given that the term $4TC$ appears in the regret bound where $C$ is the bound on the approximate incentive compatibility derived in Theorem 3).

$\bullet$ **Q:** On lines 297-298, you mention that the $(1-\frac{c_f}{e})$ approximation factor is optimal. Is this claim supported by a lower bound? If so, could you point to the relevant references?

**A:** You can find the reference paper below, we will make sure to include this in lines 297-298 of the paper:

Sviridenko, M., Vondrák, J., \& Ward, J. (2017). Optimal approximation for submodular and supermodular optimization with bounded curvature. Mathematics of Operations Research, 42(4), 1197-1218.

Meta-review: The paper discusses expert advice settings, under the assumption that experts (agents) are strategic.
All reviewers made a terrific job by delving deep into the paper, and have raised several point which were discussed with the authors. Eventually, all reviewers are satisfied with the responses of the authors and with the paper's contribution, and unanimously vote for acceptance.
Decision: Accept (poster)