- 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 for each arm. However, their "post-talk" valuation is that emerges after discussing with peers in the DeGroot model with some non-negative column-stochastic matrix . Note that the same 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 , and the platform allocates a stable matching by feeding 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 and in the matching such that prefers to we must have . Given this, we want to make sure that we have enough samples to avoid getting the sign of 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 matrices for different arms. For instance, I may trust one friend more on one topic and another on another topic.
- The notation is not great as it implies taking power. Please consider revising this notation. More generally, using superscript for is a bit confusing cause in many cases you do not take a power and are only using the notation to denote dependence on .
- 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
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 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 and, if desired, arm-specific anchoring weights . The resulting operator is
For a comparison , the social gap and propagated variance become
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 and 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 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 , where , while Theorem 2 bounds SAE-Q's expected cost by , with leading instance complexity .
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 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 and establishes
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 , the minimum information required for an unconstrained ranking reversal is . Therefore, unit-information constraints correspond to , yielding .
The remaining inequality reflects the bounded intrinsic-mean domain , which may restrict the available alternatives. In particular, when , the minimum-information reversals remain feasible and Proposition 9 gives 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...)
Response to Reviewer SwKp (Part 3/3): Improving Theorem 2, Notation & Efficiency
(Continued from Part 2/3)
▸ (2) Can the dependence on 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 on a fixed connected social network, for which
Here, one player's preference gap shrinks with , but that comparison has no effect on the target matching. Nevertheless, any uniformly -correct full-ranking identification algorithm must spend at least 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 comparisons.
Theorem 6 replaces the full-ranking complexity and minimum gap with their matching-specific counterparts and .
On the same family instance as in Proposition 10, Corollary 2 gives
independently of . Consequently, SAE-Q-SD achieves an expected-cost upper bound that remains bounded as , while full-ranking identification requires evaluations. Figure 4a illustrates this separation empirically.
More generally, Appendix F.8 shows that whenever 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 and 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 variables and 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.
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.
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 Γ (Appendix C.4).
▸ (1) Why might the platform have prior knowledge of Γ?
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), and hence Γ (Cross & Parker, 2004; Ravazzi et al., 2018).
By contrast, newly proposed projects have no prior evaluation history, meaning employees' intrinsic utilities μ must be learned from scratch in the current cycle. Our main formulation captures this asymmetry by treating the historically estimated operator Γ as given and focusing pure exploration on the unknown intrinsic evaluations.
▸ (2) What if Γ 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 Γ and the resulting social preferences to estimation errors in (P,A). Specifically, writing Q=(I−A)P⊤ and Q~=(I−A~)P~⊤, we show that
∥Γ~−Γ∥1≤αminα~min∥A−A~∥∞+∥Q−Q~∥∞.
Whenever ∥Γ~−Γ∥1<Δmin/2, every strict social comparison is preserved, leaving the target matching M∗ 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 Γ. Because intrinsic bandit feedback reveals only μ and contains no information about (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 δ-correct procedure. Crucially, this procedure does not require knowing Γ or Δ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...)