acceptodds
Under review as a conference paper at ICLR 2027

Learning Stable Matchings under Social Influence: A Bandit Approach

Abstract

In many matching markets, participants evaluate options individually, discuss them with peers, and revise their preferences before a final matching is made. The preferences governing stability therefore reflect both personal experience and social influence. However, existing learning models in matching markets abstract away this deliberation stage, treating preferences as fixed lists to be learned in isolation through direct interaction feedback. We study a pure-exploration setting where direct interactions reveal noisy intrinsic evaluations, but the preferences that determine stability emerge only after these evaluations propagate through a social network. Our goal is to identify the player-optimal socially stable matching with as few evaluations as possible. The central difficulty is a decoupling of evidence and decision: uncertainty in one player’s final ranking often originates from the intrinsic evaluations of others. Consequently, observing an unresolved ranking does not reveal which player–arm pairs should be sampled next. We characterize this challenge by establishing an instance-dependent lower bound through a network-weighted information-allocation problem over intrinsic source pairs, capturing necessary evidence to rule out alternatives that make the target matching unstable or no longer player-optimal. Guided by this variance structure, we design Source-Aware Elimination with Quadratic Allocation (SAE-Q), an algorithm that coordinates evaluations across source pairs to resolve network-propagated uncertainties. We prove that SAE-Q identifies the target matching with probability at least , achieving instance-dependent sample complexity guarantees explicitly governed by network topology and social preference gaps. Our results show that social influence shapes not only which matching is stable, but also where evidence must be collected to identify it.

Primary area:
learning theory
Keywords:
Matching Market, Bandit Algorithm, Social Network, Online Learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_SwKpOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Most existing work on learning stable matchings assume that participants collect data separately and choose preferences based on that data. This paper asks how communication among the participants can shape this process. The paper formulates this using the DeGroot model of opinion dynamics. Specifically, each player has an intrinsic valuation μplayer,arm\mu_{player, arm} for each arm. However, their "post-talk" valuation is θplayer,arm\theta_{player, arm} that emerges after discussing with peers in the DeGroot model with some non-negative column-stochastic matrix PP. Note that the same PP is used for all arms.

Formally, they study the following multi-round pure-exploration problem. In each round, the platform uses past data to assign some matchigng$M_t$ to players and arms. The players then observe and report to the platform a (noisy) estimate of the valuation of the arm they are assigned to. At some point, the platform decides to stop the protocol. When this occurs, the players use current estimates and the DeGroot process to form the vector θ^\hat{\theta}, and the platform allocates a stable matching by feeding θ^\hat{\theta} to the Gale–Shapley algorithm. Total cost is the total number of evaluations made by players across the rounds (note that the per-round sum can vary as some matchings tried may be smaller than others)

The paper asks the question of how we can minimize the number of evaluations used to find a (player-optimal) stable matching. Note that this matching is unique. The key difficulty is that quiet often the reason a participant may be uncertain about a ranking is noise on other participants' data. As such, knowing which rankings are uncertain does not directly tell use which participant-item pair we need to sample.

To address this, the authors design the SAE-Q algorithm which takes into account the source of uncertainty for each player-arm pair. On a high-level, the algorithm is based on the following intuition. For a matching to be stable, we requires that for any pair (u,a)(u, a) and (u′,b)(u', b) in the matching such that bb prefers uu to u′u' we must have θu,a>θu,b)\theta_{u, a} > \theta_{u, b}). Given this, we want to make sure that we have enough samples to avoid getting the sign of θu,a−θu,b\theta_{u, a} -\theta_{u, b} wrong. The algorithm operates in multiple epochs and in each epoch tries to take the minimum number of samples necessary to certify pairs with growing accuracy; when the sign of a pair is decided, the algorithm stops reasoning about it.

Critical strengths
  • I think the paper studies an interesting amalgamation of matching and opinion dynamics.
  • Main body is fairly well-written, though I would have preferred to see more details about the model in the introduction.
Critical weaknesses
  • While I find the problem interesting, the exact protocol is a bit weird. Basically, the paper assumes that we as algorithm designer know who will talk to whom and given this we are optimizing the sampling process. In general, I think assumptions on platform knowledge need to be motivated well.
Questions for authors
  • While not necessary for this paper, I wonder what happens if players use different PP matrices for different arms. For instance, I may trust one friend more on one topic and another on another topic.
  • The notation nmn^{m} is not great as it implies taking power. Please consider revising this notation. More generally, using superscript for mm is a bit confusing cause in many cases you do not take a power and are only using the notation to denote dependence on mm.
  • Is the algorithm computationally efficient?
  • Theorem 2 and 1 seem to involve pretty different parameters. Any thoughts on what lower bounds (whether theorem 1 or otherwise) can say about whether theorem 2 can be improved?
4 comments
AuthorsOpenReview ↗

Response to Reviewer SwKp (Part 1/3): Known-Network Assumption & Robustness

We thank Reviewer SwKp for the constructive feedback and positive assessment of our work. We address the reviewer's concerns below.

1. Motivation and Robustness of the Known-Network Assumption

The known-operator assumption reflects an asymmetry between previously available social information and intrinsic utilities that must be learned in the current matching cycle. We clarify this from two parts: (i) practically, social ties persist across matching cycles and can be estimated from historical interactions, whereas intrinsic utilities for new options must be explored afresh, and (ii) theoretically, our results hold under small estimation errors (Appendix C.3) and extend to joint calibration of an unknown Γ\Gamma (Appendix C.4).

▸ (1) Why might the platform have prior knowledge of Γ\Gamma?

Consider the internal talent market in Section 4 (Cowgill et al., 2025), where a firm matches employees to projects over repeated cycles. Employees communicate through relatively stable professional ties—such as team memberships, reporting lines, and prior collaborations. Beyond merely observing who interacts with whom, the platform can leverage interaction records and opinion updates from past cycles to estimate the numerical influence weights (P,A)(P, A), and hence Γ\Gamma (Cross & Parker, 2004; Ravazzi et al., 2018).

By contrast, newly proposed projects have no prior evaluation history, meaning employees' intrinsic utilities μ\mu must be learned from scratch in the current cycle. Our main formulation captures this asymmetry by treating the historically estimated operator Γ\Gamma as given and focusing pure exploration on the unknown intrinsic evaluations.

▸ (2) What if Γ\Gamma is not known exactly?

We also recognize that the influence operator may be estimated imperfectly or may need to be learned alongside intrinsic utilities. Appendices C.3 and C.4 address both possibilities.

First, Proposition 1 (Appendix C.3) quantifies the sensitivity of Γ\Gamma and the resulting social preferences to estimation errors in (P,A)(P, A). Specifically, writing Q=(I−A)P⊤Q=(I-A)P^\top and Q~=(I−A~)P~⊤\tilde{Q}=(I-\tilde{A})\tilde{P}^\top, we show that

∥Γ~−Γ∥1≤∥A−A~∥∞+∥Q−Q~∥∞αmin⁡α~min⁡.\Vert \tilde{\Gamma}-\Gamma \Vert_1 \le \frac{\Vert A-\tilde{A} \Vert_\infty + \Vert Q-\tilde{Q} \Vert_\infty}{\alpha_{\min}\tilde{\alpha}_{\min}}.

Whenever ∥Γ~−Γ∥1<Δmin⁡/2\Vert \tilde{\Gamma}-\Gamma \Vert_1 < \Delta_{\min}/2, every strict social comparison is preserved, leaving the target matching M∗M^\ast unchanged. Small estimation errors in the influence network therefore do not affect the matching outcome.

Furthermore, Appendix C.4 goes beyond perturbation robustness to actively learn an initially unknown Γ\Gamma. Because intrinsic bandit feedback reveals only μ\mu and contains no information about (P,A)(P, A), operator identification requires observing social interactions. We therefore introduce a separate calibration channel that tracks opinion updates under known initial profiles. Proposition 2 provides an explicit confidence bound for the estimated operator, while Proposition 3 combines operator calibration with source-aware bandit exploration in a δ\delta-correct procedure. Crucially, this procedure does not require knowing Γ\Gamma or Δmin⁡\Delta_{\min} in advance. It progressively tightens both estimates and halts once the joint confidence radius certifies the induced social rankings.

We have revised the Information Structure paragraph in Section 4 (p. 6, highlighted in blue) to make this distinction explicit and to direct readers to the robustness and joint-calibration results in Appendices C.3–C.4.

(Continued in Part 2/3 below...)

AuthorsOpenReview ↗

Response to Reviewer SwKp (Part 2/3): Arm-Specific Influence & Lower/Upper Bound Relation

(Continued from Part 1/3)

2. Arm-Specific Influence Matrices

The reviewer raises an interesting extension: a player may trust different peers when evaluating different arms. Our framework can accommodate this without changing its underlying learning mechanism.

The common influence matrix PP is a simplifying modeling choice rather than a requirement of our analysis. Since the opinion dynamics in Eq. (1) evolve independently for each arm, we can introduce an arm-specific matrix P(v)P^{(v)} and, if desired, arm-specific anchoring weights A(v)A^{(v)}. The resulting operator is

Γ(v)=A(v)[I−P(v)(I−A(v))]−1.\Gamma^{(v)} = A^{(v)} \left[ I - P^{(v)}(I - A^{(v)}) \right]^{-1}.

For a comparison c=(u,a,b)c=(u,a,b), the social gap and propagated variance become

gc=∑w(Γw,u(a)μw,a−Γw,u(b)μw,b),g_c = \sum_w \left( \Gamma^{(a)}_{w,u}\mu_{w,a} - \Gamma^{(b)}_{w,u}\mu_{w,b} \right),

Vc(x)=∑w((Γw,u(a))2xw,a+(Γw,u(b))2xw,b).V_c(x) = \sum_w \left( \frac{(\Gamma^{(a)}_{w,u})^2}{x_{w,a}} + \frac{(\Gamma^{(b)}_{w,u})^2}{x_{w,b}} \right).

The key observation is that each comparison remains a linear combination of intrinsic source evaluations. The analysis in Appendix E already works with general comparison coefficients (Eq. (76)), and the relevant operator properties continue to hold for each arm. Consequently, Theorems 1 and 2 extend to known arm-specific influence operators using the corresponding comparison coefficients and variance constraints.

This extension also offers an interesting interpretation of source–destination mismatch: resolving a player's preference between aa and bb may require sampling different peers for the two arms, depending on whose opinions the player trusts on each topic. We have formalized the arm-specific operators and the resulting comparison coefficients and variance constraints in Appendix B.4 (pp. 22–23, highlighted in blue). The shared-operator formulation remains our main model in Section 4.

3. Comparing Theorems 1 and 2, and Whether Theorem 2 Can Be Improved

This question brings out the distinction between identifying the target matching and recovering every social ranking. Theorem 2 can be improved for matching identification, but its dependence on H2H_2 is unavoidable in general if an algorithm must recover all social rankings. Our additional results in Appendix F make this distinction precise.

▸ (1) How are the lower and upper bounds related?

Theorem 1 establishes the Gaussian information lower bound Eμ[Cτ]≥kδHopt(μ)\mathbb{E}_\mu[C_\tau] \ge k_\delta H_{\mathrm{opt}}(\mu), where kδ=kl(1−δ,δ)k_\delta=\mathrm{kl}(1-\delta,\delta), while Theorem 2 bounds SAE-Q's expected cost by 2FQ2F_Q, with leading instance complexity H2(μ)H_2(\mu).

Although these quantities appear different, they arise from the same network-propagated variance structure. The main difference is what the algorithm must distinguish. The lower bound HoptH_{\mathrm{opt}} considers only alternative instances that change the player-optimal stable matching, whereas SAE-Q certifies every pairwise social ranking.

To make this relationship precise, Proposition 9 (Appendix F.1) introduces the full-ranking information complexity HrankH_{\mathrm{rank}} and establishes

Hopt(μ)≤Hrank(μ)≤2H2(μ).H_{\mathrm{opt}}(\mu) \le H_{\mathrm{rank}}(\mu) \le 2H_2(\mu).

The first inequality follows because any alternative that changes the target matching must also change at least one social ranking. The second follows from the Gaussian information geometry: for a comparison cc, the minimum information required for an unconstrained ranking reversal is Δc2/(2Vc(x))\Delta_c^2/(2V_c(x)). Therefore, unit-information constraints correspond to Vc(x)≤Δc2/2V_c(x) \le \Delta_c^2/2, yielding 2H22H_2.

The remaining inequality reflects the bounded intrinsic-mean domain (0,1]N×K(0,1]^{N\times K}, which may restrict the available alternatives. In particular, when Γ=I\Gamma=I, the minimum-information reversals remain feasible and Proposition 9 gives Hrank=2H2H_{\mathrm{rank}}=2H_2 exactly.

Beyond this difference in instance complexity, Theorem 2 incurs confidence and epoch factors. These arise from time-uniform concentration under adaptive source allocation (Lemma 11) and from maintaining the correctness of previously eliminated comparisons as cumulative estimates evolve (Lemmas 13–14).

(Continued in Part 3/3 below...)

AuthorsOpenReview ↗

Response to Reviewer SwKp (Part 3/3): Improving Theorem 2, Notation & Efficiency

(Continued from Part 2/3)

▸ (2) Can the dependence on H2H_2 be improved?

This is where the distinction between learning a matching and learning complete rankings becomes important.

Proposition 10 (Appendix F.2) constructs a two-player, two-arm family μ(ϵ)\mu^{(\epsilon)} on a fixed connected social network, for which

Hrank(μ(ϵ))=2H2(μ(ϵ))=8ϵ2,Hopt(μ(ϵ))=128.H_{\mathrm{rank}}(\mu^{(\epsilon)}) = 2H_2(\mu^{(\epsilon)}) = \frac{8}{\epsilon^2}, \qquad H_{\mathrm{opt}}(\mu^{(\epsilon)}) = 128.

Here, one player's preference gap shrinks with ϵ\epsilon, but that comparison has no effect on the target matching. Nevertheless, any uniformly δ\delta-correct full-ranking identification algorithm must spend at least (8/ϵ2)kδ(8/\epsilon^2)k_\delta evaluations in expectation.

This example shows both the limitation of SAE-Q's current certificate and where improvement is possible: instead of resolving every social ranking, an algorithm should identify which comparisons actually matter to the final matching.

▸ (3) Can this improvement be achieved algorithmically?

Yes, under a common-priority structure. In Appendix F, we develop SAE-Q-SD (Algorithm 3), which exploits the serial-dictatorship characterization of the stable matching. Rather than recovering complete rankings, it adaptively identifies the relevant comparisons and uses tree-to-star compression to retain a matching-specific certificate containing at most O(NK)O(NK) comparisons.

Theorem 6 replaces the full-ranking complexity H2H_2 and minimum gap Δmin⁡\Delta_{\min} with their matching-specific counterparts HSDH_{\mathrm{SD}} and ΔSD\Delta_{\mathrm{SD}}.

On the same family instance as in Proposition 10, Corollary 2 gives

HSD=64,Hopt=2HSD=128,H_{\mathrm{SD}} = 64, \qquad H_{\mathrm{opt}} = 2H_{\mathrm{SD}} = 128,

independently of ϵ\epsilon. Consequently, SAE-Q-SD achieves an expected-cost upper bound that remains bounded as ϵ→0\epsilon \to 0, while full-ranking identification requires Ω(ϵ−2)\Omega(\epsilon^{-2}) evaluations. Figure 4a illustrates this separation empirically.

More generally, Appendix F.8 shows that Hopt=2HSDH_{\mathrm{opt}}=2H_{\mathrm{SD}} whenever Γ=I\Gamma=I or the interior-reversal condition of Proposition 12 holds. Therefore, under these conditions, the matching-specific allocation complexity aligns with the information-theoretic lower bound.

In summary, our analysis reveals that the gap between Theorems 1 and 2 reflects an intrinsic structural separation between global preference recovery and targeted matching identification. While SAE-Q-SD demonstrates that exploiting matching structure can substantially close this gap under serial dictatorship, extending such compact certificates to general preferences—where certifying player-optimality additionally accounts for competing stable matchings (Appendix F.9)—represents a promising direction for future work.

4. Notation and Computational Efficiency

Notation. We have standardized epoch-indexed quantities using subscripts such as nmn_m and NmN_m instead of superscript notation (see Eq. (5), Algorithm 1, and Appendix E), so that epoch indices are not confused with powers.

Computational efficiency. Each epoch of SAE-Q solves one convex allocation problem (Eq. (5)). We have added an explicit second-order cone programming formulation in Appendix E.2 (Eq. (80), p. 45, highlighted in blue), with O(NK)O(NK) variables and O(NK2)O(NK^2) constraints. Its integer demands can be scheduled in polynomial time using Algorithm 2. SAE-Q requires neither enumeration of alternative stable matchings nor solution of the information-theoretic lower-bound program.

Thank you for your detailed rebuttal! I have no more questions.

Reviewer_RkakOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies pure exploration for two-sided matching where players’ preferences are shaped by both personal evaluation and social opinions. The authors assume that network influence strength and anchoring parameters are known, while the personal preferences are learned from experience. In the main paper, only player-side have socially formed preferences, while the employer side preferences are fixed. The goal is to identify the player-optimal stable matching with high confidence via as few individual evaluation steps as possible. The authors characterize the key challenge: source–destination mismatch, pointing out the difficulty of determining which evaluations are most informative for identifying a stable matching. The authors prove the lower bound and propose SAE-Q to recover the target matching.

Critical strengths

The idea of socially formed preference is well-motivated and interesting, and I like the motivating example. In this model, the source-destination mismatch is a nice way to capture why uncertainty in a player’s final ranking may require sampling other players’ intrinsic evaluations. Example 1 illustrates this phenomenon clearly and makes the learning challenge concrete by showing how little changes in player2's intrinsic utility can lead to different stable matchings. Moreover, the paper is theoretically substantial: it provides an instance-dependent lower bound, a high-probability sample-complexity guarantee for SAE-Q, and extensive appendix proofs and extension methods for SAE-Q.

Critical weaknesses

From my perspective, \Gamma is a key parameter in this model, yet the main paper does not explicitly discuss how the algorithm’s behavior and sample efficiency change as \Gamma varies. Similarly, Example 1 illustrates the source–destination mismatch, it would be better to add a discussion on how the strength of this mismatch depends on \Gamma.

Questions for authors
  1. In the LLM simulation, it seems that the LLM agents are given full descriptions of all five employers. Why does the Independent agent (Agent 5), who is described as ignoring peer pressure and making decisions independently, show a large drop on dimension 2 (employer 2) after social interaction?
  2. Intuitively, \Gamma should substantially affect the optimal exploration strategy. I am curious how SAE-Q performs in populations with strong versus weak conformity, and how its sample efficiency varies.
4 comments
AuthorsOpenReview ↗

Response to Reviewer Rkak (Part 1/4): Q2 & Main Weakness — Mismatch Strength

We thank Reviewer Rkak for the positive assessment of our work and for the thoughtful questions. We first address Question 2 and the Critical Weakness concerning how Γ\Gamma affects source–destination mismatch, SAE-Q's exploration strategy, and sample complexity. We then clarify the behavior of Agent 5 in the motivating LLM simulation (Question 1).

1. Response to Question 2 and Critical Weakness (Effect of Γ\Gamma, mismatch strength, and strong vs. weak conformity)

Changing the strength of social influence affects both the difficulty of matching identification and where SAE-Q collects evidence. We address these effects from two perspectives: (1) a parametric extension of Example 1, now detailed in Appendix D.3 and summarized in Section 5.1, which makes the mismatch and its sample-complexity consequences explicit, and (2) the behavior and theoretical guarantee of SAE-Q on general networks, now summarized in the Effect of Social Influence on Exploration discussion in Section 6. These additions are highlighted in blue in the revised manuscript.

▸ (1) Strength of the mismatch and problem difficulty across networks

The source–destination mismatch arises because a player's social comparison depends on others' intrinsic evaluations:

=\sum_w\Gamma_{w,u}(\mu_{w,a}-\mu_{w,b}).$$ Therefore, resolving player $u$'s comparison may require sampling other players $w$ with $\Gamma_{w,u} > 0$. To quantify how this dependence changes with $\Gamma$, we extend Example 1 to a parametric family. Consider the same two-player, two-arm market, where both arms prefer player 1. Fix $$\mu=\begin{pmatrix}0.6 & 0.4 \\\\ 0.3 & 0.5\end{pmatrix}, \qquad P=\begin{pmatrix}0 & 1 \\\\ 1 & 0\end{pmatrix}.$$ With anchoring weights $\alpha_1,\alpha_2\in(0,1]$, the social operator becomes $$\Gamma= \frac{1}{\alpha_1+\alpha_2-\alpha_1\alpha_2} \begin{pmatrix} \alpha_1 & \alpha_1(1-\alpha_2) \\\\ \alpha_2(1-\alpha_1) & \alpha_2 \end{pmatrix}.$$ This family includes the isolated network ($\alpha_1=\alpha_2=1$), one-way influence ($\alpha_2=1$, with $\alpha_1=1/2$ recovering Example 1), and mutual influence ($\alpha_1,\alpha_2 < 1$). Because both arms prefer player 1, the target matching $M^\star$ is determined by player 1's social gap: $$g_1=\theta_{1,a}-\theta_{1,b} =\Gamma_{1,1}(\mu_{1,a}-\mu_{1,b}) +\Gamma_{2,1}(\mu_{2,a}-\mu_{2,b}).$$ Here, player 1 is the destination, while player 2 is an external source with weight $\Gamma_{2,1}$. Applying the comparison-specific information constraint (4) and minimizing the total allocation cost gives, under the feasibility conditions of Corollary 1, $$\mathbb{E}_\mu[C_\tau] \ge \frac{8\\,\mathrm{kl}(1-\delta,\delta)}{g_1^2}.$$ The minimum allocation satisfying this comparison constraint assigns a fraction $\Gamma_{w,1}$ of observations to source player $w$. The matching-specific information bound and this optimal source allocation are derived in Appendix D.3 (pp. 42–43, highlighted in blue). **This gives a direct interpretation of mismatch strength.** For this decisive comparison, a fraction $\Gamma_{2,1}=1-\Gamma_{1,1}$ of the optimal allocation goes to player 2, even though the matching decision belongs to player 1. More generally, the off-diagonal mass $1-\Gamma_{u,u}$ measures the influence of external sources on player $u$'s comparison, with $1-\Gamma_{u,u}\le 1-\alpha_u$ by Lemma 3. Stronger conformity (smaller $\alpha_u$) allows a larger mismatch, while the network topology determines how much external influence actually reaches the player. The three network structures illustrate this distinction: - **Isolated network:** $\Gamma_{2,1}=0$, so there is no source–destination mismatch. - **One-way network:** $\Gamma_{2,1}=1-\alpha_1$, attaining the upper bound from Lemma 3 and approaching $1$ as $\alpha_1\to 0$. - **Symmetric mutual network:** With $\alpha_1=\alpha_2=\alpha$, we have $\Gamma_{2,1}=(1-\alpha)/(2-\alpha) < 1/2$. This weight increases with conformity but remains below $1/2$, because player 2 also incorporates player 1's opinions. *(Continued in Part 2/4 below...)*
AuthorsOpenReview ↗

Response to Reviewer Rkak (Part 2/4): Q2 & Main Weakness — Conformity & Sample Complexity

(Continued from Part 1/4)

Importantly, a stronger mismatch does not necessarily imply higher sample complexity. The latter also depends on the social gap g1=(1−Γ2,1)d1+Γ2,1d2g_1=(1-\Gamma_{2,1})d_1+\Gamma_{2,1}d_2, where dw=μw,a−μw,bd_w=\mu_{w,a}-\mu_{w,b}. Since g1g_1 is a convex combination of the intrinsic gaps, two situations arise. When the intrinsic gaps have the same sign, ∣g1∣≥min⁡w∣dw∣|g_1|\ge\min_w|d_w|; social aggregation cannot create an arbitrarily small gap through cancellation. When they have opposite signs, however, aggregation can make g1g_1 approach zero, sharply increasing the required number of evaluations.

In our example, d1=0.2d_1=0.2 and d2=−0.2d_2=-0.2, giving g1=0.2(1−2Γ2,1)g_1=0.2(1-2\Gamma_{2,1}). The gap vanishes at Γ2,1=1/2\Gamma_{2,1}=1/2, equivalently α1=α2/(1+α2)\alpha_1=\alpha_2/(1+\alpha_2). This tie lies outside the strict-preference domain DΓ\mathcal{D}_\Gamma, but the sample-complexity bound diverges as admissible instances approach it. The original Example 1 corresponds precisely to this critical regime, where uncertainty in μ2,a\mu_{2,a} can change player 1's ranking and hence the stable matching.

More concretely, the three cases exhibit different sample-complexity trends as conformity increases:

  • Isolated network (α1=α2=1\alpha_1=\alpha_2=1): Γ2,1=0\Gamma_{2,1}=0 and g1=0.2g_1=0.2, giving the baseline lower bound 200,kl(1−δ,δ)200\\,\mathrm{kl}(1-\delta,\delta).

  • One-way network (α2=1\alpha_2=1): Here Γ2,1=1−α1\Gamma_{2,1}=1-\alpha_1 and g1=0.2(2α1−1)g_1=0.2(2\alpha_1-1), so the bound is 200,kl(1−δ,δ)/(2α1−1)2200\\,\mathrm{kl}(1-\delta,\delta)/(2\alpha_1-1)^2. As α1\alpha_1 decreases toward 1/21/2, the opposing evaluations increasingly cancel, and the bound diverges. Once α1<1/2\alpha_1 < 1/2, player 2's preference dominates, the target matching flips to {(1,b),(2,a)}\lbrace(1,b),(2,a)\rbrace, and the bound decreases again as conformity strengthens further.

  • Symmetric mutual network (α1=α2=α\alpha_1=\alpha_2=\alpha): Here Γ2,1=(1−α)/(2−α)\Gamma_{2,1}=(1-\alpha)/(2-\alpha) and g1=0.2α/(2−α)g_1=0.2\alpha/(2-\alpha), yielding 200,kl(1−δ,δ)(2−α)2/α2200\\,\mathrm{kl}(1-\delta,\delta)(2-\alpha)^2/\alpha^2. Unlike the one-way case, g1g_1 remains positive for every α>0\alpha > 0, so the matching never flips. Instead, the gap decreases monotonically toward zero, and the bound increases, reaching 1800,kl(1−δ,δ)1800\\,\mathrm{kl}(1-\delta,\delta) at α=1/2\alpha=1/2.

These examples distinguish two effects of Γ\Gamma: its off-diagonal weights determine where information must be collected, while its aggregation of intrinsic gaps determines how much information is needed. In particular, stronger conformity can increase difficulty by creating near-ties, but it can also reduce difficulty after the social ranking reverses. Therefore, neither strong nor weak conformity is uniformly harder.

(Continued in Part 3/4 below...)

AuthorsOpenReview ↗

Response to Reviewer Rkak (Part 3/4): Q2 & Main Weakness — SAE-Q Behavior & Guarantees

(Continued from Part 2/4)

▸ (2) How conformity shapes Γ\Gamma, SAE-Q's behavior, and its guarantee

We next explain how these effects extend to general networks and enter SAE-Q's allocation rule. The revised Section 6 (p. 10, highlighted in blue) now summarizes their consequences for source allocation, cross-player sharing, and gap-dependent sample complexity. For clarity, consider homogeneous anchoring A=αIA=\alpha I (heterogeneous anchoring follows the same principles, with Γu,u≥αu\Gamma_{u,u}\ge\alpha_u).

By Remark 1 (Appendix B.2), the operator admits the expansion

Γ=α∑k=0∞(1−α)kPk.\Gamma=\alpha\sum_{k=0}^{\infty}(1-\alpha)^k P^k.

Here, PkP^k captures influence transmitted along kk-step network walks. Thus, the topology PP determines the paths through which opinions propagate, while α\alpha controls how strongly longer paths contribute.

This gives two limiting regimes. Under weak conformity (α→1\alpha\to 1), Γ→I\Gamma\to I, and social preferences approach intrinsic preferences. Under strong conformity (α→0\alpha\to 0), on a connected network with an irreducible influence matrix, Γ→π1⊤\Gamma\to\pi\mathbf{1}^\top, where π\pi is the stationary distribution of PP. All players then approach a common social utility vector θu,v=∑wπwμw,v\theta_{u,v}=\sum_w\pi_w\mu_{w,v}. For the undirected networks in Appendix F.6, πw\pi_w is proportional to player ww's degree.

In SAE-Q, the allocation is determined by the allocation program (5), with instance complexity

H2(μ)=min⁡x>0{∑w,vxw,v:Vc(x)≤Δc2,∀c∈C}.H_2(\mu) = \min_{x > 0} \left\lbrace \sum_{w,v} x_{w,v} : V_c(x) \le \Delta_c^2,\quad \forall c \in \mathcal{C} \right\rbrace.

As α\alpha varies, Γ\Gamma affects this program through three mechanisms:

  • Within-comparison allocation (column proportions). For a single comparison c=(u,a,b)c=(u,a,b), Cauchy–Schwarz gives an optimal comparison-specific cost of 4/Δc24/\Delta_c^2, with allocation xw,a=xw,b=2Γw,u/Δc2x_{w,a}=x_{w,b}=2\Gamma_{w,u}/\Delta_c^2 on the influence support. Thus, the optimal source allocation follows the column Γ⋅,u\Gamma_{\cdot,u}. Under weak conformity, SAE-Q primarily samples player uu's own evaluations, approaching decoupled per-player elimination. Under strong conformity, the columns approach π\pi, shifting evaluations toward influential source players in proportion to their network centrality.

  • Cross-comparison sharing (inter-column overlap). An evaluation of (w,v)(w,v) reduces uncertainty for every player influenced by source ww. SAE-Q exploits this through the joint allocation in (5). In particular,

    \le H_2(\mu)\le \sum_{c\in\mathcal{C}}\frac{4}{\Delta_c^2}.$$ The lower bound reflects the hardest individual comparison, while the upper bound corresponds to allocating separately without sharing observations. Under weak conformity, distinct players rely on nearly disjoint sources, resulting in essentially $N$ separate ranking tasks. Under strong conformity, all columns approach $\pi$, so comparisons of the same arm pair share the same variance functional and social gap. Consequently, the $N\binom{K}{2}$ constraints asymptotically collapse into $\binom{K}{2}$ shared constraints: certifying one player's ranking simultaneously certifies the others.
  • Social gap aggregation. Each gap satisfies Δc=∣∑wΓw,u(μw,a−μw,b)∣\Delta_c=|\sum_w\Gamma_{w,u}(\mu_{w,a}-\mu_{w,b})|. As conformity strengthens, these gaps approach the corresponding consensus gaps ∣∑wπw(μw,a−μw,b)∣|\sum_w\pi_w(\mu_{w,a}-\mu_{w,b})|. When intrinsic preferences agree, these gaps remain separated from zero; when preferences conflict, cancellation may make them arbitrarily small and substantially increase the required sample budget.

These effects are reflected in Theorem 2, where SAE-Q's sample-complexity bound is FQ=d(MΔ+1)+36B0H2(μ)MΔ(MΔ+3)F_Q=d(M_\Delta+1)+36B_0H_2(\mu)M_\Delta(M_\Delta+3). The leading complexity term H2(μ)H_2(\mu) captures both source-level allocation and cross-player sharing. For example, in the one-way network above, when Γ2,1≥1/4\Gamma_{2,1}\ge 1/4 (with Γ2,1≠1/2\Gamma_{2,1}\neq 1/2), player 1's comparison dominates and H2(μ)=4/g12H_2(\mu)=4/g_1^2, consistent with the comparison-specific information lower bound up to its confidence factor. Meanwhile, MΔ=⌈log⁡2(6/Δmin⁡)⌉M_\Delta=\lceil\log_2(6/\Delta_{\min})\rceil increases when social aggregation creates small gaps.

The confidence coefficient B0B_0 also depends on Γ\Gamma, but only through the maximum influence-support size s=2max⁡u∣supp(Γ⋅,u)∣s=2\max_u|\mathrm{supp}(\Gamma_{\cdot,u})|. This factor changes from s=2s=2 when Γ=I\Gamma=I to s=2Ns=2N on a connected network with α<1\alpha < 1. The discontinuity reflects a conservative union bound over nonzero influence coefficients, rather than an abrupt change in the underlying exploration difficulty. A tighter analysis using an effective influence dimension could potentially capture this dependence more smoothly.

Overall, the net effect depends on both the network structure and the alignment of intrinsic preferences.

(Continued in Part 4/4 below...)

AuthorsOpenReview ↗

Response to Reviewer Rkak (Part 4/4): Q1 — Behavior of Agent 5 in Figure 2b

(Continued from Part 3/4)

2. Response to Question 1 (Behavior of Agent 5 on Employer 2 in Figure 2b)

Although Agent 5 is described as Independent, its evaluation of Employer 2 drops considerably after social interaction in Figure 2b. This distinction between independence and complete immunity to social influence can be understood from two observations.

▸ (1) The Independent persona resists conformity, rather than all social influence.

In Table 2, Agent 5 is described as someone who "ignores peer pressure" and "makes decisions independently." These traits mean that the agent does not simply adopt others' opinions to agree with the group. They do not necessarily prevent it from considering information provided by others.

This distinction is well established in social psychology: normative influence concerns conformity to others' judgments, whereas informational influence involves using others' opinions as evidence (Deutsch & Gerard, 1955). An independent individual can resist the former while remaining receptive to the latter.

In our simulation, all agents follow the same update procedure (Appendix A.3.4), which asks them to reconsider their evaluations based on their own personalities and their neighbors' opinions. The Independent persona is therefore a qualitative behavioral description, not a strict prohibition against any social response. In the formal model, this corresponds more closely to a large anchoring weight αu\alpha_u, rather than the extreme case αu=1\alpha_u=1, which completely excludes peer influence. This is consistent with the Friedkin–Johnsen framework, where resistance to social influence is a matter of degree (Friedkin & Johnsen, 2011).

▸ (2) Agent 5 largely preserves its strong preferences while revising a weaker evaluation.

Figure 2b illustrates this distinction. Agent 5 consistently ranks Employer 3 first, maintaining a score around 4.34.3–4.84.8, even though three of its four peers evaluate Employer 3 below −4-4. This is quite different from simply following the group.

By contrast, Agent 5 initially assigns Employer 2 a moderate score of approximately 22, less than one point above Employer 5. Its initial preference is therefore less decisive, leaving greater room for negative peer assessments to change the evaluation.

The formal model captures a related mechanism. In the social gap θu,v−θu,v′\theta_{u,v}-\theta_{u,v'}, a player's intrinsic gap retains weight Γu,u≥αu\Gamma_{u,u}\ge\alpha_u, while peers contribute the remaining weight. Therefore, a large αu\alpha_u helps preserve strong intrinsic preferences, but does not rule out changes when the initial gap is small and peer assessments point in the opposite direction.

Finally, Figure 2 reports a single stochastic LLM simulation, so the exact magnitude of Agent 5's score change may vary across runs. We use this experiment as a motivating illustration of how communication can reshape preferences, rather than as a quantitative validation of the subsequent linear opinion-dynamics model. Its central observation remains the contrast between the two network settings: preferences remain unchanged without communication, while social interaction can induce substantial score changes and ranking reversals.

References

  • M. Deutsch and H. B. Gerard (1955). A study of normative and informational social influences upon individual judgment. The Journal of Abnormal and Social Psychology, 51(3), 629–636.
  • N. E. Friedkin and E. C. Johnsen (2011). Social Influence Network Theory: A Sociological Examination of Small Group Dynamics. Cambridge University Press.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.