Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies many-to-one matching markets - which is a generalization of the one-to-one matching markets studied in recent years in the online learning community. The paper identifies a combinatorial condition that guarantees an unique Nash equilibrium to the underlying game if all participants knew of their preferences. This condition is a multi-way generalization of the recently used alpha condition for one-to-one matching. The paper shows that if the underlying market satisfies this unique Nash Equilibria criteria, then the decentralized learning algorithm yields logarithmic regret. The proposed algorithm is a natural variant of the UCB-D4 which was shown to be a good method for the one-to-one matching case. 
strengths_and_weaknesses: Strengths

1. Comprehensive treatment of the problem
2. Builds and contributes to an emerging theory on decentralized bandit learning in matching markets 
3. Their algorithms and results recover the known results in one-to-one matching market when the system is one-to-one. In this sense the proposed algorithm is a strict generalization of prior algorithms 

Weakness 

1. The paper does not address issues such as competition mechanism while learning. 

However, I believe the weakness to be minor and can be easily addressed in the discussion sections of the revision of the paper. 

questions: 1. What do you think are the additional challenges in extending this to markets with multiple equilibria ?
2. Can this algorithm be generalized if both sides of the market need to perform learning ?
limitations: Yes. This is primarily a theory paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem of bandit learning in many-to-one matching markets. They generalize the $\alpha$-condition in a marriage problem to a proposed $\tilde\alpha$-condition that is a matching guarantee for uniqueness consistency in many-to-one matching markets. Under the proposed condition the authors present a UCB-based arm elimination algorithm that obtains logarithmic regret . The authors verify their proposed algorithm by simulations under several different optimality conditions. 
strengths_and_weaknesses: Strengths:
+ The paper presents a novel algorithm with a competitive regret bound.
+ The new $\tilde\alpha$-condition proposed appears to generalize the $\alpha$-condition from the stable marriage problem, and the discussion for the condition puts it in comparison with prior work.

Weaknesses:
- The paper has sections that are not very well-written. While the authors do a good job of explaining their new stability condition in Section 4.1, the discussion with prior conditions (deferred to 4.3) should essentially be put together. In Section 5, the authors present the technical challenges in extending bandit matching to the many-to-one setting, however it is unclear / difficult to follow how each of the steps translate into the final regret bound which is presented earlier in Section 4.2. 
- Regret Bound: It is not clear which contributions are novel and which proof techniques are reused from prior work. All the proofs are deferred to the appendix, and the proof-sketch provided in Section 4.2 is not very informative. 
- - There are no discussions on which parts of the proof reuse prior work and which parts are novel. 
- - There are no discussions on optimality and lower bounds beyond the mentioning of the logarithmic factor. 
- - There are no discussions on which aspects of the algorithm can be improved in future work, and what the authors conjecture to be the optimal rate. 
- Experiments: While the authors indeed experiment with several different criteria and different number of agents, they do not have any baseline comparisons, making it difficult to compare their experimental results in a relative sense. It would be worthwhile if the authors could come up with some meaningful albeit sub-optimal baselines to highlight the importance of each component in their algorithm design.
questions: Can the authors address some of the queries from the previous section? Specifically, can they contrast their work from prior work in terms of (i) theory and regret bound, (ii) novel components in the regret analysis, (iii) specific shortcomings in prior work, (iv) baselines for experiments, (v) optimality of regret bound?
limitations: The authors do not discuss limitations.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper studies decentralized learning and matching in many-to-one matching markets. They introduce a model for this setting, develop a bandit learning algorithm under a uniqueness assumption about the set of stable matchings, and obtain a logarithmic instance-dependent bound on its regret.
strengths_and_weaknesses: - Strengths:
    - The problem of many-to-one matching that the authors study is well-motivated, as it is a salient aspect of many real-world matching markets (e.g., schools, employment) in which learning and adaptivity could play a useful role.
    - It is nice to see simulations of the algorithm to validate the performance. (However, it would also be nice to see comparisons against other methods.)
- Weaknesses:
    - The writing was difficult to follow, with several crucial definitions and assumptions unclear (see below).
    - The focus on unique stable matching seems like a strong limitation of the results, as in many markets where the preferences are not in a sense “acyclic” or “aligned”, multiple stable matchings exist. The proposed approach does not appear to scale gracefully to this setting.
    - While the consideration of many-to-one matching is new, this work only considers a limited form of many-to-one matching where each “arm” has a total preference ordering agents.
    - The regret bounds are in the minimum reward gap across all agents in arms; this assumption does not permit agents to be indifferent (or nearly indifferent), even for arms far down in their ranking list.
questions: - I was not able to understand the definitions of “left order” and “right order”; it seems like there is a missing clause in the first sentence of the paragraph starting at line 173. Would it be possible to elaborate further on the definition?
- In Definition 2, there appears to be a missing term in the summations. What should that term be?
- I am also somewhat confused about the comparisons between assumptions on the preferences under “Conditions for Unique Stable matching”. For instance, the condition of Akahoshi is a property of the preference profiles of a single side (under which there exists a unique stable matching). On the other hand, uniqueness consistency is a property of the full preference profiles (for both sides). Could you clarify what the precise comparison being made is?
limitations: The authors describe the limitations of their results in Section C.3. It may be useful to move this discussion into the main body.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors study the problem of minimizing regret in many-to-one matching markets with bandit feedback. In a many-to-one matching markets, each right-side agent (aka arms) can match upto a maximum number of left-side agents (aka agents). The authors develop \tilde{alpha}-condition as a sufficient condition for uniqueness consistency in many-to-one matching markets. Under this condition they provide logarithmic regret for the bandit learning problem for the MO-UCB-D4 algorithm.
strengths_and_weaknesses: Strengths:
- This work is an interesting addition to learning in matching markets with bandit feedback, as it studies the many-to-one matching markets for the first time.
- It develops the \tilde{\alpha}-condition (adapted from one-to-one matching markets) as a sufficient and necessary condition for uniqueness consistency. 

Weaknesses:
- The relationship of capacity q_k and  lr_{max}(j) is not discussed properly, elaboration needed (see questions). 
- Counterexample of Acyclicity* holding and \tilde{\alpha}-condition not holding is missing. This will improve the understanding in section 4.3.
- The \tilde{\alpha} condition is also very closely related to Karpov et al. The difficulty in extending this to the many-to-one matching is unclear.   
- The discussion on why deriving regret bound for many-to-one case is difficult than Basu et al. is not stated clearly. Specifically, the role of moving from ordering of individuals to ordering of sets need to be elaborated (probably in derivation of the \tilde{\alpha} condition as well). 

questions: - The authors' comments on increase in q_k decreases lr_{max}(j) seems a bit less rigorous. Is there a more rigorous statement -- e.g. Does partial ordering of q_k introduces partial order on lr_{max}(j)?

- Please discuss the other points mentioned in the weaknesses. 
limitations: This work seems theoretical in nature, and negative societal impact, if any, is not immediate.
review_title: null

Meta-review: metareview: The paper generalizes one of the results of Basu et al.'s ICML'21 paper to the case of many-to-one matchings, showing a distributed multi-armed bandits mechanism with logarithmic regret for finding a stable matching assuming a strong uniqueness condition on the input. I believe the paper does not meet the bar for acceptance into NeurIPS due to the following major weaknesses:
* The paper is not very well written and it is hard to understand in places.
* It is not clear how difficult the generalization is, given the existing result in the one-to-one matching case.
* The assumptions of the model, in particular the uniqueness assumption, are very strong, and restrict the result to a very limited (and fragile) set of input instances.
confidence: Certain
Decision: Reject