Thank you for carefully reading our submission and positive feedback. The following are our responses and the changes are highlighted in blue in the updated manuscript (pdf). Please refer to the modified draft.

Concern on dictatorship and impossibility theorem

We thank the reviewer for their detailed analysis of the impossibility result. After thoughtful consideration, we agree with the comments on the binary decision case, the definition of dictatorship and the restrictiveness in practice of the counter-example that considers distinct favourite candidates for each agent. The constructive criticism motivated us to reconsider the proof and made us realize that the impossibility of groupthink-proofness does not require considering dictatorship. The new proof relies on the absence of a trivial social consensus, i.e., all agents should not have the same (trivial) utility-maximizing candidate. The proof and relevant impossibility result sections have been updated in the appendix and the main draft respectively.

Concern on Theorem 3.9 Lemma F.3

Yes, your high-level concern is true (although your example does not serve as a counterexample since $u(x^\prime)$ is negative, causing the inequality to flip, we guess typo?). Upon further reflection, we also realized that Lemma F.3 is unnecessary. Instead, we used the properties of generalised Gini social-welfare functions, such as Hardy-Littlewood-Polya inequality, Schur convexity, and additivity. Please refer to the Lemma F.4. for the new proof. This modification leads to a similar, though slightly larger, constant: $\mathcal{L}_\mathcal{A} = \sqrt{n} \lVert w \rVert$. The other elements, including the intuition regarding the aggregation function (where the egalitarian approach is the slowest and the utilitarian approach is the fastest) and the sublinear convergence rate, remain unchanged.

Concern on Theorem 3.12

We agree that worst-case analysis alone may not fully capture evidence of faster convergence. However, we would like to emphasize that focusing on worst-case scenarios is a common practice in the Bayesian optimization community and is not specific to our work. While upper bounds provide insights into worst-case performance, lower bounds similarly reflect only the best-case scenario. In practice, analyzing the average case could indeed offer valuable insights into expected performance, but it is generally difficult to analyze and therefore rarely included. Factors such as multimodality and smoothness can also influence average convergence rates in black-box optimization tasks, which is why empirical evaluations are essential for assessing practical performance (see Figures 3 and 4). Our focus on worst-case scenarios is intended to ensure the algorithm’s robustness and its ability to converge to the global optimum under challenging conditions. We also acknowledge that our original explanation may have overstated the implications of worst-case analysis. To address this, we have revised the manuscript to explicitly clarify that our results are applicable in the worst case for greater accuracy and transparency.

Concern on draft structure

We agree that additional background information would benefit a broader readership; however, we were limited by space constraints. Given that the primary audience we assumed is the Bayesian optimization community, we assumed familiarity with foundational concepts. Including extensive background would necessitate reducing our focus on novel contributions in favor of revisiting established concepts. With our paper already spanning 50 pages, including the Appendix, it is challenging to cover all relevant foundational material, especially as our work bridges the fields of welfare economics and Bayesian optimization, where readers may have expertise in one but not the other. We prioritized discussing the novel aspects for the BO community. The primary reason for adopting this fancy model is that it is the only one allowing for theoretical analysis, as outlined in lines 199-205. For a more intuitive and accessible approach, we also include a popular Gaussian process model in Appendix H.1, which was our initial model. However, we prioritized theoretical insight in this new setting to enable readers to extend the work to different scenarios or practical applications. Despite the model's complexity, we believe Theorem 3.9 offers intuitive and reasonable bounds for understanding this problem. Additionally, we referenced key papers that introduced foundational concepts as a compromise.

Intuition on acquisition function

Firstly, the acquisition function maximization problem itself is a global optimization problem, but with a known explicit functional form. Therefore, it does not encounter the issue of local optima. Secondly, you are correct that we aim to elicit as much information as possible at each step. Similar to standard Bayesian optimization with continuous feedback, there is an exploitation-exploration tradeoff. Exploitation (also known as pessimism) involves relying on the current model to seek its maximization, while exploration (also known as optimism) involves questioning the current model and seeking to maximize information for future iterations. At each step, we select the pair that optimizes the preference based on the current data (exploitation) while simultaneously encouraging a certain level of exploration. This entails optimizing both $x$ over the input space and $u$ over the function confidence set. Intuitively, this approach optimistically explores those $x$ and functions $u$ that have the potential to yield favorable results, employing the popular principle of optimism in the face of uncertainty.

Intuition on additional $n$ term on oracle in Theorem 3.9

This is because, even with the given graph $A^{-1}$, it amplifies the noise of $v$, whereas pure private votes do not amplify the noise of $u$. We assumed that both $u$ and $v$ yield the same level of estimation error given the same number of votes (Lemma 3.6 and range preservation, Lemma 2.7). Thus, they should exhibit the same level of noise at the same timestep $t$. However, since $v$ is an indirect observation of $u$, the inversion $\lVert A^{-1} \rVert \leq n$ (Lemma 2.7) introduces inevitable amplification. As a result, the presence of $n$ in the oracle case is unavoidable in the worst-case scenario.

Extention to offline case

Yes, the offline setting will slightly modify the algorithm. If we can obtain a full ranking from each agent, the estimated utility functions remain probabilistic models, where we typically balance exploitation and exploration. However, in the offline setting, where further queries are not possible, optimism no longer applies. Instead, it becomes a pure exploitation problem, specifically maximizing the MAP estimate: $x_\text{final} = \arg\max_{x \in \mathcal{X}} \mathcal{A}[\hat{u}(x,:)] - \mathcal{A}[\hat{u}(x^\prime,:)]$. This approach differs from the acquisition function in Eq. (5), which provides an optimistic estimate by incorporating both exploitation and exploration (i.e., taking the upper bound). In contrast, the offline setting relies solely on exploitation.

Thanks to your feedback, we have improved our manuscript by refining the proofs and enhancing the clarity of our algorithm and theoretical results. These updates have been incorporated into the manuscript, highlighted in blue text, and we believe your concerns have now been addressed.

Thank you for your response! I find them very interesting. Could you please give me a basic idea of what your algorithm is doing? You can assume I have little knowledge of Bayesian estimation, MLE, and MAP beyond the basic notion (so I cannot understand your section 3.3). Your explanation will help me go over your new proof. Thanks!

For example, is $x_t'$ in Algorithm 1 actually $x_{t-1}$, as it is not maximized on and there is no $x_{t-1}$ in the algorithm? Also, in Line 1948, how does you maximizing on $\tilde{u}$ also applies to $u$?

Thank you for reading our submission and positive feedback. The following are our responses and the changes are highlighted in red in the updated manuscript (pdf). Please refer to the modified draft.

On graph estimation error

Firstly, our bounds on cumulative regret and query complexity are derived for the worst-case scenario. This means that if the actual estimation error is better than the worst case, both bounds could be tighter. We can interpret the decay rate $q$ as quantifying the social graph estimation error: a larger $q$ requires more private votes to reduce the estimation error sufficiently to meet the stopping criterion in Line 7 of Algorithm 1. According to Theorem 3.12, the worst-case convergence rate of the graph estimation error is $-1/2$, so we set $q=1/2$ (see line 370). If the estimation error converges faster than $-1/2$, it suggests that an even smaller $q$ could be used, yielding a tighter sample complexity for private votes, $\lvert Q_t^u \rvert$. Because our bound is based on the worst-case scenario, a smaller $q$ results in a looser regret bound. However, if the actual estimation error rate is better than $-1/2$, the regret bound should not heavily depend on the $q$-dependent term. Since we lack access to the ground-truth graph $A$, we cannot dynamically estimate the actual error convergence rate on the fly. Therefore, in practice, we recommend setting $q=1/2$ based on the worst-case rate in Theorem 3.12.

On other graph models (non-linear, peer-pressure, and hierarchical influence)

For non-linear cases, we can employ a graph convolutional kernel network approach [1]. Using the kernel trick and Nyström method, this approach can transform non-linear functions into effectively linear forms. Popular graph neural network models can also be seen as special cases of [1]. Once the model is linearized, our approach can be applied directly. The linearized graph has $m$ components, where $m$ represents the number of Nyström model centroids. By applying the Cauchy-Schwarz inequality, our bounds in Theorems 3.9 and 3.12 become looser by a factor of $\sqrt{m}$. However, since this is a constant, the order of the asymptotic convergence rate remains the same at $-1/2$. The Nyström method provides an eigendecomposition-based approximation of the non-linear network, where $m$ reflects the complexity of the non-linear social graph. This adjustment is reasonable, as a more complex ground-truth social graph would naturally lead to a slower convergence.

Regarding the other models you mentioned, our approach is adaptable. For instance, in a peer-pressure scenario, we assume a setting where a minority of agents may shift their votes toward the majority. This minority or majority could vary based on the option $x$, creating a heterogeneous setting. If the setting is homogeneous, our algorithm can model peer pressure directly. For a heterogeneous setting, as noted in L535-536, we can incorporate diversity using a probabilistic choice function (Benavoli et al., 2023b). While regret bounds for this model are not yet established in the literature—given that even linear graphs are novel in this context—the submodularity of the probabilistic choice function suggests sublinear convergence.

For hierarchical influence, we are unsure of its relevance in settings where all participants vote in the same room. This scenario may arise when influence propagates slowly among voters, as in presidential voting. Our target tasks, however, are in an online setting where voting is iterative and occurs at a relatively faster pace than in presidential elections (see Section 5). Still, if it does occur, a grey-box Bayesian optimization approach [2] could be applied, where the hierarchical graph structure is known but the specific attributions remain unknown. Under these assumptions, we can demonstrate the same convergence rate as in Theorem 3.9 with high probability, although this analysis is beyond the scope of the current paper.

Lastly, as noted by all reviewers, our paper is the first-of-its-kind to explore group consensus-building under social influence. We believe it is reasonable to start with the simplest setting, where the graph is linear. Linear graphs are widely studied and applied in the literature, particularly in social network modeling (e.g., [3,4,5,6]), supporting their practical effectiveness. As Reviewer DMB8 highlighted, even with this basic linear setting, our contribution remains substantial, with the proof spanning 50 pages. We argue that this choice does not compromise the completeness of our paper and have demonstrated that our algorithm is extendable.

Citations

• [1] Chen, D. et al., "Convolutional Kernel Networks for Graph-Structured Data", ICML (2020)
• [2] Xu, W., et al., "Bayesian Optimization of Expensive Nested Grey-Box Functions", arXiv:2306.05150 (2023)
• [3] Ding, Yuxin, et al. Computer Communications 73 (2016): 3-11.

• [4] Li, Yanying, et al. "Fairlp: Towards fair link prediction on social network graphs." AAAI (2022)
• [5] Liang, H. et al., "Bayesian Optimization of Functions over Node Subsets in Graphs." NeurIPS (2024).
• [6] Wan, X. et al., "Bayesian optimisation of functions on graphs." NeurIPS (2023)

On contribution of each voting system

In Appendix F.2.2, line 2065, we present a decomposition of the regret bound to show how each voting system independently contributes to cumulative regret. An imbalance between the number of public votes ($T$) and private votes ($\lvert Q^u_t \rvert$) affects two terms: $(T - \lvert Q \rvert)$ and the maximum information gains $\gamma^{uu^\prime}_T$ and $\gamma^{vv^\prime}_T$, both of which depend on the total number of votes (see details of this dependency for each kernel in F.3).

Instead of focusing solely on imbalance, we can intuitively understand this relationship by considering $\lvert Q^u_t \rvert$ alone. When $\lvert Q^u_t \rvert = T$, the second and third terms become zero $(T - \lvert Q^u_t \rvert = 0)$, and the regret bound relies solely on private votes. Reducing $\lvert Q^u_t \rvert$ introduces an additional term in the regret, meaning that fewer private votes $\lvert Q^u_t \rvert$ lead to higher regret. Therefore, smaller values of $\lvert Q^u_t \rvert$—that is, greater imbalance—result in increased regret.

On inconsistent feedback

To clarify, while feedback follows a Bernoulli distribution and is therefore stochastic (Assumption 2.2), the ground-truth utility function itself is deterministic (Assumption 2.6). We must estimate the ground-truth utility function from stochastic feedback, making our estimated model probabilistic, with its worst-case error bounded by a confidence set (Lemma 3.6). Feedback becomes nearly random when the utility difference $u(x,i) - u(x^\prime,i)$ is small (Assumption 2.2) but is less noisy when this difference is large. If this feedback noisiness aligns with your notion of "inconsistency," our model can indeed handle such inconsistent feedback. Our regret bound is derived based on the worst-case utility function estimation error in Lemma 3.6, where the error bounds, represented by $\beta^u_T$ and $\beta^v_T$, appear as constants in Theorem 3.9. Thus, less noisy feedback corresponds to a smaller $\beta$, resulting in a tighter regret bound.

If, however, your notion of inconsistency refers to something else, such as transitivity or completeness, please note that these are fundamental assumptions in both social choice theory and preference-based Bayesian optimization, as employed in all nine papers accepted at top ML conferences listed in lines 387-391. These assumptions are standard and widely applied in real-world settings.

On optimization parameters

To clarify, while the decay rate is a hyperparameter that users of our algorithm can control, the weight of the aggregation function is uncontrollable, as it is part of the problem definition we aim to optimize. The effect of this weight is discussed in lines 356-357, where the egalitarian aggregation has the slowest rate ($L_A \rightarrow \sqrt{n}$) and the utilitarian aggregation the fastest ($L_A = 1$). For the decay rate $q$, line 370 already states that $q = 1/2$ can be optimal, though we unpack more on this point for clarity. Generally, $q$ controls the trade-off between cumulative regret $R_T$ and the number of queries $\lvert Q_t^u \rvert$, with optimality depending on the user’s query budget. This can be viewed as the task of minimizing the cost function $C_T := \lambda_u \lvert Q_t^u \rvert + \lambda_v T$ (see line 323), where $\lambda_u$ and $\lambda_v$ represent the costs of private and public votes, respectively. Under Assumption 3.4, we assume $\lambda_v \gg \lambda_u$, meaning faster convergence in $\lvert Q_t^u \rvert$ is preferable. Recall that private votes are queried to estimate the graph $A$, with a convergence rate of $\mathcal{O}(\lvert Q^u_t \rvert^{-1/2})$ (Theorem 3.12). Additionally, $\lvert Q^u_t \rvert$ is bounded by the condition in line 7 of Algorithm 1 ($1/t^q$). Setting $q=1/2$ (i.e., $t^{-1/2}$) ensures that the cumulative error $\sum_{i\in[T]} t^{-1/2} \leq \mathcal{O}(T^{1/2})$ aligns with the convergence rate of graph estimation error, making it optimal under a high-cost scenario $\lambda_v \gg \lambda_u$. The theoretical limit on $q$ is further discussed in Appendix F.2.2, lines 2099-2108, and in Theorem 3.9, line 339.

Thanks to your feedback, we could improve our manuscript by enriching the discussion on the extendability and flexibility of our algorithm, as well as clarifying the assumptions and theoretical framework. We have incorporated these updates into the manuscript, highlighted in red text, and believe that your concerns have now been addressed.

Thank you for reading our submission and positive feedback. The following are our responses and the changes are highlighted in cyan in the updated manuscript (pdf). Please refer to the modified draft.

Our assumption is actually weaker than the existing literature.

Your concern made us realize that the term "truthful" can be misleading. In this work, what we meant by "truthful" is social-influence-free. While private voting can guarantee social-influence-free utilities, the reports can still be non-truthful in the sense that agents can act strategically and misreport their votes. To address this, we have replaced the term "truthful" with "social-influence-free" and the term "non-truthful" with "influenced" throughout the manuscript, including in the title.

However, we also want to clarify that our assumptions are, in fact, weaker than those in existing literature. For example, preferential Bayesian optimization (referenced in nine papers accepted at top ML conferences, listed in lines 390–394) typically assumes that feedback always reflects truthful utility, an assumption widely applied in real-world settings. In contrast, our work adopts a more realistic approach by accounting for social influence, which may skew votes.

As noted in Assumption 3.4, private votes are social-influence-free but costly, with the cost of querying private votes significantly higher than that of public votes, i.e., $\lambda_v \gg \lambda_u$. Consequently, $\lvert Q_t^u \rvert$ dominates the total cost $C_T := \lambda_u \lvert Q_t^u \rvert + \lambda_v T$, so we aim to minimize $\lvert Q_t^u \rvert$ to reduce costs while still minimizing cumulative regret. Lines 62–65 and Figure 1 illustrate scenarios with high costs. Public votes, such as a show of hands in a meeting, are inexpensive and allow rapid iteration, though they may not be social-influence-free. In contrast, private votes require one-on-one interviews, necessitating that agents meet separately, which is especially costly.

We have justified the limitations.

We outlined and justified the limitations of our approach in Section 5 (lines 532-539), which include high-dimensional inputs, batch settings, and heterogeneous or dynamic aggregation functions. For example, techniques such as additive kernels (Kandasamy et al., 2015) can improve scalability in high dimensions (line 358), and batch acquisition is well studied, allowing us to apply standard methods (e.g., via the BoTorch library). These aspects are orthogonal to our primary focus. As recognized by all reviewers, our paper is the first to explore group consensus-building under social influence. We believe it is reasonable to start with the simplest setting, assuming a homogeneous and stationary aggregation function. As noted in lines 535-536, the probabilistic choice function (Benavoli et al., 2023b) can address more complex scenarios, but such an extension would warrant a separate paper—especially considering that our proof in this simplest setting already spans 50 pages.

Our paper is the first step for preference aggregation in Bayesian Optimization.

Our paper is the first-of-its-kind to investigate preference aggregation under social influence within a Bayesian optimization (BO) framework, demonstrated through four real-world examples in Section 5 (Figure 4). While preference aggregation is new, preference maximization is a well-studied and widely applied area—with examples in visual design optimization (Koyama et al., 2020), thermal comfort optimization (Abdelrahman & Miller, 2022), collaborative filtering (Schafer et al., 2007), robotic gait optimization (Li et al., 2021), and autonomous driving policy design (Astudillo et al., 2024)—each of these applications typically iterates over 50 to 500 samples (see also the references in lines 390-394 of Section 4). We are not aware of any learning algorithm that converges in as few as 10 samples. Scarlett et al. (2017) established a lower bound (theoretical limit) on the convergence rate of cumulative regret in BO, $\Omega(\sqrt{T} (\log T)^d)$, which precludes convergence within such a limited sample size. In our experiments, however, our algorithm (yellow) achieves a sufficiently small regret in around 20 samples, with two of the tasks reaching small regret in fewer than 10 samples, suggesting that our approach empirically meets your strong requirement (in comparison to other baselines).

Thanks to your feedback, we could improve our manuscript by clarifying the assumptions and significance of our new settings and the theoretical framework. We have incorporated these updates into the manuscript, highlighted in cyan text, and believe that your concerns have now been addressed.

Clarification on dictatorship.

We thank the reviewer for pointing out our typo in the definition, the quantifiers should have been swapped. However, note that our original proof was based on the correct definition of dictatorship. Furthermore, after taking Reveiwer DBM8's comment into consideration, we have improved the proof of the impossibility result by relaxing the need for the dictatorship requirement, please check the new Definition 3.2 and Theorem 3.3.

Clarification on Readability.

Our contribution bridges the fields of welfare economics and Bayesian optimization, where readers may have expertise in one but not necessarily both. We acknowledge that our interdisciplinary topic is inherently complex, and the challenges in comprehension extend beyond mere readability. Within the 10-page limit, we aimed to introduce the novel concepts as explicitly as possible, structuring them as assumptions and supplementing them with a 50-page appendix. The appendix includes hyperlinks to relevant topics as the table of contents and a summarized notation table for ease of reference.

The parts of the paper you deemed irrelevant are, in fact, central to motivating our problem setup. Arrow’s impossibility theorem underpins the need for the facilitator assumption (Assumption 2.1), and the Generalized Social Function (GSF, Proposition 2.4) addresses how the facilitator can intuitively control the relaxation of rationality axioms through a single parameter, $\rho$. Furthermore, the GSF is directly incorporated into our objective function in Eq. (1), making it an essential part of our framework (see line 118 where this is mentioned).

Despite these challenges, we have further improved the readability of the manuscript by incorporating the reviewer’s feedback. Thank you for your detailed comments on unclear sections and your more direct suggestions as minor points. We have updated the manuscript to enhance clarity on these aspects with magenta-coloured texts and believe that the readability and previously unclear contributions have been clarified now.

Thank you for the valuable feedback. The following are our responses and the changes are highlighted in magenta in the updated manuscript (pdf).

Confusion on our contribution

Short answer. We are not attempting to enhance the regret bound by using private votes. Instead, our goal is to achieve a regret bound similar to the best case (private-votes-only) by primarily using noisy public votes while requiring fewer private votes. Estimating the consensus from cheap public votes is far more cost-effective than relying solely on expensive private votes. As demonstrated in Theorem 3.9, the regret bound is comparable, but the sample complexity of private votes is sublinear (better than linear, i.e., private-vote-only). This represents our primary algorithmic contribution, demonstrating improved sample complexity and regret across four real-world and six synthetic tasks. Another contribution is the impossibility theorem of groupthink-proof aggregation, which we proved and is not part of existing results. We unpack each part in the following.

Confusion on impossibility theory

Your quote (lines 47-48) refers to the well-known Arrow's impossibility theorem, which demonstrates that no aggregation function can simultaneously satisfy all four mild rational axioms outlined by Arrow. This result is independent of the corruption of utility by social influence. In fact, we have formalised the discrepancy challenge you mentioned in Theorem 3.3 already. We mentioned Arrow's theorem to highlight that any consensus-building problem cannot be solved merely by designing a new aggregation function. The standard approach in the literature to circumvent such impossibility is to relax one or more of the rationality axioms. As such, in our work, we adopt the assumption of a facilitator or social planner (Assumption 2.1), who determines the aggregation function. Selecting a certain aggregation function inherently entails compromising on some of the axioms, but the social planner can decide which aspects to relax. The social planner assumption is widely accepted in welfare economics (Jehle & Reny, Advanced Microeconomic Theory, 2011). However, the task of selecting an appropriate aggregation function is non-trivial; therefore, we introduced the GSF (Proposition 2.4), which simplifies this challenging decision process to a single parameter, $\rho$, representing an additional contribution of our work. Our new impossibility theorem of groupthink-proofness (Theorem 3.3) highlights why direct access to private votes is necessary; without it, truthful consensus-building under a given aggregation function (GSF) is impossible. This motivates our dual voting system.

Confusion on Theorem 3.9 and Sample Complexity.

Regarding sample complexity, Theorem 3.9 answers your question directly. The third row, "None," represents the "private votes alone" scenario (see Remark 3.10). The second column, $\lvert Q_t^u \rvert$, denotes the total number of private votes, quantifying the "sample complexity" (see definition in lines 209-211). For "None," the sample complexity is linear, $T$, meaning that private voting must continue indefinitely to converge, as we are using only private votes. By contrast, SBO has a sublinear bound, indicating that the total number of private votes asymptotically converges to a certain constant, allowing us to stop querying private votes at some point and estimate the global optimum based on noisy public votes alone. See Section 3.3, lines 293-294 "Line 7 outlines the stopping criterion, which halts the expensive private queries when the graph $A$ is accurately estimated." This is the benefit of the dual voting system: unlike "private votes alone," we can stop querying private votes, or at least $\lvert Q_t^u \rvert$ grows slower than linear $T$.

Estimating consensus using noisy public votes naturally incurs a worse regret bound. Looking at the first column, $R_T$ represents cumulative regret (line 322). SBO has a sublinear regret bound with an additional term compared to the "None" case, a necessary trade-off for the sublinear sample complexity $\lvert Q_t^u \rvert$. See Section 3.4, lines 351-353, "under typical conditions ($T \leq 1000$, $d \geq 2$, RBF kernel), $q$ dependent term is always smaller than non-dependent ones in RT". Thus, in practice, the bound does not differ significantly from the "None" regret bound. These theoretical results are corroborated by our experiments (Fig.3,4), where SBO's regret converges slightly better than the oracle, which has only the second term. This confirms that the additional term for SBO does not have a substantial impact. Moreover, the sample complexity $\lvert Q_t^u \rvert$ shows that SBO requires the fewest private queries among the baselines, while the single-agent baseline (cyan) shows the linear bound $T$. In conclusion, SBO achieves better sample complexity of expensive private votes with minimal compromise in regret, making it better than "private vote alone".

Thank you for your timely response and for investing your time in discussing our paper. Below is our detailed response.

Confusion Regarding Theorem 3.9 and Table 1

First, Theorem 3.9 provides a general bound for an arbitrary kernel. All the kernel-dependent parameters—maximum information gain $\gamma_T$, confidence interval parameter $\beta_T$, and the covering number $\mathcal{N}(\mathcal{B}^n, 1/T, ||\cdot||_\infty)$—depend on $T$. As such, the second term is not as simple as $\sqrt{T}$. To address this, we prepared Table 1 to provide kernel-specific bounds for cumulative regret $R_T$ and sample complexity $|Q_t^u|$ for commonly used kernels: linear, RBF, and Matérn.

In the Bayesian optimization (BO) community, the RBF kernel is typically used. Therefore, we will use the bound for the RBF kernel as an example for further interpretation.

For regret $R_T$, there are two terms: $T^{1-q/4}$ and $T^{3/4} (\log T)^{3/4 (d+1)}$. The latter term is shared with "oracle (public only)" and "None (private-vote-only)." Hence, the first term, $T^{1-q/4}$, is the only additional term compared to the private-only case (see Appendix F.2.3 for details). In other words, if $T^{1-q/4} \ll T^{3/4} (\log T)^{3/4 (d+1)}$, the regret bound for SBO is comparable to the private-only case because convergence is primarily dictated by the dominant term.

Setting $q = 1/2$ (see Line 370), the $T^{1-q/4}$ term becomes $T^{7/8}$, which seems worse than $T^{3/4}$. However, the $(\log T)^{3/4 (d+1)}$ term is substantial for typical values of $T < 1000$ and $d > 2$, making $T^{3/4} (\log T)^{3/4 (d+1)}$ the dominant term. For example, let $T = 50$ and $d = 3$, a typical BO setting also used in our experiments. Here, $T^{7/8} \approx 30$, while $T^{3/4} (\log T)^{3/4 (d+1)} \approx 281$. This demonstrates the dominance of the second term. The disparity grows as $T$ and $d$ increase, which we confirmed experimentally.

In Figures 3–4, SBO (yellow) shows smaller regret than the oracle, which only has the second term. The oracle includes an additional constant $n$ in the second term, $T^{3/4} (\log T)^{3/4 (d+1)}$, meaning SBO outperforms it. This further supports that the enlarged second term $T^{3/4} (\log T)^{3/4 (d+1)}$ has a greater impact on convergence than the additive term $T^{7/8}$, confirming its triviality in convergence.

For sample complexity $|Q_t^u|$, while the private-vote-only approach has linear complexity $T$, SBO achieves sublinear complexity $T^q (\log{T})^{3(d+1)}$. Comparing sublinear and linear complexities, the latter is the worst-case scenario for convergence. To interpret, we consider the sample complexity per iteration, $|Q_t^u| / t$, rather than the cumulative number of private votes, $|Q_t^u|$.

For private-vote-only, $\lim_{t \rightarrow \infty} |Q_t^u| / t = t / t = 1$, which is expected as private votes are required for every iteration, even as $t \to \infty$. In contrast, SBO’s sublinear convergence implies $\lim_{t \rightarrow \infty} |Q_t^u| / t = 0$, meaning private vote queries can effectively stop after some point. Thus, sublinear convergence is always better than linear in terms of convergence.

You might question whether $T^q (\log{T})^{3(d+1)}$ could exceed $T$ in certain scenarios, making it worse in the short-term. However, our theoretical bound represents a worst-case scenario. In practice, Line 7 in Algorithm 1 defines the stopping criterion for querying private votes. This ensures that the actual number of private votes per iteration averages between 0 and 1. Thus, even if $T^q (\log{T})^{3(d+1)} / T > 1$, it is effectively capped at 1 in reality. As a result, our sample complexity is always better than linear in expectation for any iteration $t$.

Intuitively, probabilistically selecting between 0 and 1 queries is inherently smaller than deterministically selecting 1 query. This is confirmed experimentally in Figures 3–4, where SBO (yellow) has a smaller sample complexity $|Q_t^u|$ than the linear case (single agent, light blue).

Possible Confusion Regarding the $q$ Setting

Another potential source of confusion is the interpretation of $q$ as an optimization hyperparameter. Users have the flexibility to freely select its value within the range $0 < q < 1$. This means users can choose $q \rightarrow 1$, but they are not required to do so. As stated on Line 370, our recommendation is $q = 1/2$ because it aligns the convergence rate with the worst-case estimation error of graph identification (Theorem 3.12).

CONTINUE TO THE NEXT RESPONSE

Thank you for taking the time to review and discuss our paper. We hope our responses have adequately addressed your concerns regarding the soundness of our theoretical results. Should you have any further questions or require additional clarification, we would be happy to assist.

To briefly recap our previous response: Theorem 3.9 applies to a general kernel, which is why the rate is not as simple as $\sqrt{T}$. Table 1, on the other hand, focuses on specific popular kernels, and we use the RBF kernel in our experiments, as is standard practice in the Bayesian optimization community. The term $T^{1-q/4}$ is smaller than $T^{3/4} (\log T)^{3/4(d+1)}$, making the additional regret term negligible.

Our sample complexity for private votes, denoted $|Q^u_t|$, is sublinear, which is an improvement over the linear complexity in the private-votes-only case. This is because our algorithm selects either 0 or 1 private vote per iteration, whereas the private-votes-only approach always selects 1 private vote per iteration. As a result, $|Q^u_t|$ is sublinear and converges to zero private votes asymptotically. Consequently, Theorem 3.9 and Table 1 together clearly demonstrate the advantages of our algorithm over the private-votes-only approach. These benefits are also examined in the experiments shown in Figures 3 and 4.

Finally, we use regret as our primary evaluation metric, as it is the standard metric in all Bayesian optimization and bandit papers. Regret measures the "estimation error of the global maximum," which aligns with our goal of global optimization, rather than the "estimation error of model prediction." Prediction itself is not our end goal; instead, the predictive model is a tool to enhance the global optimization process.

I want to clarify that while I appreciate your effort to enhance the paper, due to time constraints, I have not reviewed, nor will I be able to review, your new impossibility results.

Thank you for your response! While it is fair to say the result is neutral in terms of correctness for you, we would like to emphasize that your original concern has been addressed (see the copy below), as we no longer rely on the assumption of non-dictatorship. Additionally, we would like to clarify that our original definition of dictatorship aligned precisely with Arrow's original definition, though it contained some typographical errors, which Reviewer DBM8 rightly pointed out and also confirmed its correctness.

The impossibility result in Theorem 3.3 is strange, particularly in its nonstandard definition of dictatorship. Unlike traditional definitions, where one dictator determines the order of all items, Definition 3.2 allows for different dictators for each item pair. Under this definition, even majority voting or a simple average function might satisfy their dictatorship definition. This nonstandard definition undermines the impossibility result.