- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies the centralized matching markets when one side of preference is unknown, and provides a cute refined regret analysis of an existing algorithm UCB-GS (Liu et al. 2020). The original UCB-GS algorithm has player pessimal regret , while this work improves the analysis to /. Also, the authors extend the analysis to many-to-one centralized matching markets and improve upon existing analysis.
Critical strengths
-
The paper provides a clear comparison of assumptions and regret bounds in centralized matching markets. The paper shows the regret bound improvement over previous analysis, especially in terms of and .
-
The paper provides a thorough analysis on both one-to-one matching markets and many-to-one matching markets.
Critical weaknesses
-
My biggest concern is limited significance. The paper provides a cute re-analysis of an existing algorithm, and analyzes its player-pessimal regret when the matching market is centralized. However, existing papers (e.g., Kong & Li 2023) often study the stronger player-optimal regret, and they usually focus on decentralized matching markets. Therefore the current form of the paper has very limited significance, unless the authors can explain clearly why it is meaningful to study a sub-optimal algorithm under a narrower problem setting while we already have nicer solutions. The authors should also state clearly the difference of player-optimal stable matching and player-pessimal stable matching, and there is a line of works on decentralized markets. All these factors put the paper at an awkward position.
-
The novelty of upper-lower bound tightness is unclear. The analysis improves upon the original analysis only if N is much smaller than K. However, the restricted two families seem to suggest N=K. This suggests that the original UCB-GS's regret upper bound is also tight, and it would be nice to derive a lower bound without such restrictions.
-
The experiments are also weak since they only provide , while existing literature often has much larger scales. It is hard to understand whether the analysis scales to large matching markets.
Questions for authors
-
Compared to Liu et. al, what is the insight of your analysis? What can readers learn from your insights and potentially propose new algorithms? Why are your insights significant to matching market designers?
-
UCB-GS is a sub-optimal algorithm because it fails to find a player-optimal solution and only stability is guaranteed. There are some UCB alternatives that have better theoretical guarantees and experimental performance. Can you extend your analysis to those stronger settings and algorithms?
8 comments
Response to Reviewer j33T [2/4]
W2: Tightness of the regret bounds and dependence on and .
A2: We clarify that neither market family in Section 6 assumes , and the original regret bound for UCB-GS (Liu et al., 2020) is not tight on either family. The first family has and (Section 6.1), while the second has (Section 6.2).
On the first family, the original bound for the target player is , whereas this player’s expected regret under UCB-GS is . On the second family, the original bound for the target player is , whereas this player’s expected regret under UCB-GS is . In both cases, the original bound overestimates the expected regret by a factor of , while our refined bounds, on the first family and on the second, match it up to constant factors (Theorems 12–15).
Our analysis establishes tighter regret bounds for UCB-GS in general matching markets, especially when is much smaller than . Compared with the closed-form bound of Liu et al. (2020), our closed-form bound in Theorem 9 reduces to and replaces the gap , the minimum reward gap over all pairs of arms, with , the minimum adjacent reward gap among each player’s top arms. Moreover, our refined bounds satisfy on every market (Theorem 7).
We agree that a lower bound for general markets would be valuable. Sankararaman et al. (2021) establish a regret lower bound with linear dependence on under serial dictatorship. Such markets satisfy the -condition, under which our regret bound for UCB-GS also has linear dependence on (Theorem 11 with unit capacities). Whether the quadratic dependence on in our general regret bound (Theorem 9) is necessary remains open.
W3: Experimental evaluation on larger matching markets.
A3: We would like to note that our regret analysis applies to arbitrary market sizes under the stated assumptions (Theorems 9 and 11) and does not depend on the market sizes used in the experiments.
We have also added experiments with arms and players (Appendix K.4, Figure 6). For each market size, we generate 20 random markets and run UCB-GS 10 times per market over rounds. At , the mean is at least 48.3%, 53.6%, and 53.7% lower than the mean for , respectively. The mean is a further 6.2%, 6.3%, and 7.1% lower than the mean . These results show that both refinements remain effective at larger market sizes.
Response to Reviewer j33T [3/4]
Q1: New analytical insights and implications for algorithm and market design.
A4:
Our main insight is that regret can be bounded more tightly by jointly accounting for different matchings and blocking triplets rather than treating them separately. First, Liu et al. (2020) bound regret by choosing a separate cover of blocking triplets for each arm that the target player may receive. Since the same triplet can block matchings assigning different arms to the target, its count bound may be applied repeatedly. Our first refinement, triplet count sharing, jointly accounts for these matchings through the LP (Section 4.1). Second, different blocking triplets can share the same assigned player-arm pair, so the rounds in which they block the selected matching contribute to the same observation count. Our second refinement, observation count sharing, establishes a new joint count bound of for such triplets with gaps at least , rather than the obtained by summing their individual bounds (Theorem 6). Incorporating this bound yields the stronger LP (Section 4.2).
Our analysis also reveals how the structure of stable matchings limits the number of assigned player-arm pairs that need to be counted. For the second class of matchings in Proposition 10, the blocking triplets in the cover have their assigned arms among the arms used by the player-pessimal stable matching, giving at most assigned player-arm pairs. A further argument based on the player join of stable matchings handles the third class with at most additional blocking triplets. Together, these arguments remove the dependence on from the term of the general regret bound (Theorem 9).
These insights also inform the analysis of player-optimal regret and the design of online learning algorithms. For regret analysis, we apply the idea of triplet count sharing (the first refinement) to establish a player-optimal regret bound of for UCB-GS under Ergin-acyclic arm priorities (Theorem 16). For algorithm design, observation count sharing (the second refinement) suggests coordinating exploration so that observations can be used across successive proposals. Applying this principle, we develop a new algorithm, AETGS-SBU (Appendix L), which uses synchronized exploration blocks to achieve player-optimal regret when and is known, improving upon the published bound for AETGS in the same setting (Theorem 37). For designers of centralized matching platforms, these results identify a sufficient condition on known arm priorities under which UCB-GS guarantees logarithmic player-optimal regret and show how coordinated exploration can improve regret guarantees. We discuss these extensions further in A5.
Response to Reviewer j33T [1/4]
We thank the reviewer for the careful review and for recognizing the improvements in our regret bounds and the thorough analysis of both one-to-one and many-to-one matching markets. We have uploaded a revised manuscript with changes highlighted in blue, and we address the concerns and questions below.
W1: Significance of analyzing the player-pessimal regret of UCB-GS in centralized markets.
A1: We agree that existing algorithms, such as ETGS (Kong & Li, 2023) and AETGS (Kong et al., 2024), provide logarithmic player-optimal regret guarantees in general markets, including in decentralized settings, whereas UCB-GS can incur linear player-optimal regret in some markets (Liu et al., 2020, Example 4). However, we believe that studying UCB-GS and refining its regret analysis remain meaningful. In the revision, we show that UCB-GS can achieve logarithmic player-optimal regret under Ergin-acyclic arm priorities, which allow multiple stable matchings. We also show that UCB-GS can incur lower regret than AETGS on some markets. Moreover, beyond reducing the dependence of its player-pessimal regret bound from NK to N2 in general markets, the counting ideas developed in our analysis also apply to player-optimal regret and lead to a new algorithm, AETGS-SBU, whose player-optimal regret bound improves upon that of AETGS when N=K.
First, UCB-GS can achieve logarithmic player-optimal regret when the market has suitable structure. The player-optimal and player-pessimal stable matchings assign each player its most and least preferred stable partners, respectively. Under the α-condition, the stable matching is unique, and Kong et al. (2024, Theorem 6.2) establish such a guarantee for UCB-GS. In the revision, we further show that under Ergin-acyclic arm priorities, UCB-GS achieves player-optimal regret O(KlogT/Δ4+NlogT/Δ2) for every player, even when multiple stable matchings exist (Theorem 16, Section 7). This condition restricts only the known arm priorities and allows arbitrary strict player preferences.
Second, UCB-GS can incur lower regret than AETGS on some markets. In Appendix N, we construct a family of serial dictatorship markets with N=K and Δ4=Δ. For the highest-priority player, AETGS continues sampling all candidate arms until it can distinguish its two best arms, which are close in mean reward, whereas UCB-GS samples clearly inferior arms less often. For sufficiently large T, this player incurs player-optimal regret O(logT/Δ) under UCB-GS and Θ(NlogT/Δ2) under AETGS with known T (Theorem 40). On 20 random serial dictatorship markets with N=K=8 and T=106, the mean regret is also lower under UCB-GS for all eight players (Appendix N.2).
Third, our analysis not only improves the player-pessimal regret bound of UCB-GS in general markets, but its two counting refinements also apply to player-optimal regret analysis and algorithm design. Liu et al. (2020) bound its player-pessimal regret in general markets by O(NKlogT/Δ22), whereas Kong et al. (2024) establish a sharper bound of O(KlogT/Δ4+NlogT/Δ2) under the α-condition. Our Theorem 9 establishes a bound of O(KlogT/Δ+N2logT/Δ2) without requiring this condition, and we discuss the tightness of our refined bounds in A2. In the revision, we further apply the two refinements developed in our analysis (Section 4) beyond player-pessimal regret. We apply triplet count sharing (the first refinement) to establish that, under Ergin-acyclic arm priorities, UCB-GS achieves player-optimal regret O(KlogT/Δ4+NlogT/Δ2) for every player (Theorem 16). We also apply observation count sharing (the second refinement) to design a new algorithm, AETGS-SBU, which achieves player-optimal regret O(NlogT/Δ42) when N=K and T is known (Theorem 37, Appendix L), improving upon the published O(N2logT/Δ42) bound for AETGS in the same setting. We give further details in A5.
Our analysis focuses on the centralized setting, in which a platform selects the matching in each round. This setting isolates the regret caused by learning preferences from the cost of coordinating players, and our refinements concern the former. Whether they can be extended to decentralized algorithms is an interesting direction for future work.
Finally, as the reviewer suggested, we have clarified in the revised introduction that player-optimal and player-pessimal stable regret coincide when the stable matching is unique and can otherwise differ by a term linear in T.