Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a generalization of the stable matching problem to the case of uncertain input on agent preferences, which are learned via bandit feedback, with a loss function aiming to minimize instability. To define this loss function, the notion of transferable utility is used, whereby monetary subsidies offered by the platform to agents, in addition to transfer between those agents, quantify the instability of a certain matching.
main_review: The paper proposes novel algorithms that learn user preferences via optimism in the face of uncertainty from noisy user feedback in a multi-armed bandit setting, aiming to minimize a measure of instability in lieu of producing strictly stable matchings, providing near-optimal bounds. This economically motivated formulation extends to the case of structured preferences.

The work is well motivated by the case of data-driven markets, where agents may be incentivized to participate in a matching via monetary transfers. The concept of a stable matching, whereby the sum of agent utilities is maximized, is well generalized to the case of uncertainty, where users cannot report their full preferences, and instead those are learned via bandit feebdack.
limitations_and_societal_impact: The paper considers  a problem where the objective is to achieve social benefit.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: The paper considers two-sided platforms who seek to match users on
  both sides under uncertainty about user preferences. The focus is on
  the transferable utility setting, where the platform, in addition to
  orchestrating a matching, imposes transfers between each pair (as
  well as from the platform to the pair). After each matching, the
  platform receives noisy (bandit) feedback regarding the utilities
  received by each member in a matched pair. The goal of the platform
  is to learn a stable market outcome efficiently. To capture the
  (in)efficiency of learning, the authors introduce a measure of
  instability of any matching, namely subsidy instability, which is
  equal to the smallest total (non-negative) transfer the platform
  needs to make to the users so that matching is stable. The regret of
  any learning algorithm is then defined as the total subsidy
  instability accumulated over a time horizon.

  The authors first show that the subsidy instability is indeed an
  appropriate notion to capture learning efficiency, by providing
  natural economic interpretations as well as exhibiting a number of
  smoothness properties and bounds. The authors then propose a natural
  UCB-type algorithm, where each agent reports upper confidence bounds
  on their preferences and the platform computes the optimal stable
  matching and transfers under these reported preferences. The authors
  show that this algorithm achieves an expected regret that is of
  order $O(\sqrt{T\log T})$, and furthermore provide a matching lower
  bound. (The bounds also establish regret dependence on other model
  parameters.) 
main_review: * Pros:
  - The authors consider a natural learning setting that is
    practically important and relevant to many online platforms.
  - The main contribution of the work is in introducing/using the
    notion of subsidy instability to measure the efficiency of the
    learning algorithm. Since subsidy instability accurately captures
    the economic incentives of such platforms, exhibiting the
    performance of any algorithm in the terms of subsidy instability
    would be appealing to practitioners.
  - The resulting algorithm is simple and intuitive, and uses natural
    UCB-type ideas to achieve low regret. This simplicity would also
    be appealing in practice.
  - The paper is very well written, and the main results and the
    contributions are described with clarity.

Overall, the paper provides a clean and complete characterization of a practically relevant learning problem. 
limitations_and_societal_impact:  Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper aims at learning stable matchings in settings with monetary transfers, when the learner does not initially know agents’ preferences and has to learn them over time. The authors provide a no-regret algorithm to do so, based on the idea of upper confidence bounds (UCB).
main_review: Strengths: 
- I like the subsidy instability notion. I think this is a good notion of instability as it measures exactly how far you are (monetarily) from a stable solution. Proposition 3.3 strengthens this notion, by showing that the instability notion is well-behaved and upper bounds the utility difference, which implies convergence to a socially optimal matching.
- The algorithms and results of the paper do not directly follow from applying UCB to the Lipschitz case. The authors use a primal-dual approach to compute the solutions they work with at each time step, in a way that they show reduces the size of the confidence interval at each step. The authors are then able to get an instance-independent regret of $\sqrt{T}$.
- The authors show a matching lower bound for the expected regret
- The authors also provide instance-dependent bounds.

Minor weakness:
- Overall, the algorithm still follows the general idea of UCB (even if there is some additional work to make it work in this setting) and does not seem super novel. Most of the novelty seems to come from understanding the properties of their instability measure/optimization programs.

Typos:
- Is there a sum missing in Equation 2 when defining the utility difference?
limitations_and_societal_impact: Societal impact and fairness are not the primary concern of this paper. The authors acknowledge that computing a stable solution may come with unfairness, and that adding a fairness constraint is an interesting research direction.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors study stability in two-sided markets with transferable utilities where each agent has no a-priori knowledge of her own preference. They introduce the measure of 'Subsidy Instability' that is defined as the minimum total subsidy (extra payment to all the agents) that can stabilize a (matching, transfer) pair. They propose a UCB based primal-dual algorithm that tries to minimize the Subsidy Instability with bandit feedback for the above system. The proposed algorithm is proved to have a O(|A|^3/2\sqrt{T}) regret in a time horizon of T, where A is the set of all agents. They provide an orderwise matching  lower bound for this setting. 
main_review: Pros
- The paper studies an important problem for learning in matching markets, where agents are matched, and transfers are made to distribute the generated welfare in a stable manner.  This captures many important markets as mentioned in the paper.
- The introduction of the Subsidy Instability is interesting as it formulates the stability in two-sided markets in a centralized manner. The provided extensions show the flexibility of the proposed Subsidy Instability framework. 
- The regret upper bound and the matching lower bound in the instance independent setting highlights the optimality (orderwise) of the proposed solution.  
- The theoretical results in the extensions cover many important settings (e.g. instance dependent, linear reward), so the work is quite comprehensive within the scope of the paper. 
- The writing is clear and easy to follow, and highlights the important aspect of the Subsidy Instability metric. 

Drawbacks
-  How does the Subsidy Instability ensure (or fail to do so) the four points in the desiderata of [6]? I think parts of this is discussed in Appendix F, a summary of which is better suited for the main body of the paper. 
- The global minimization of subsidy instability does not capture fairness, as acknowledged by the authors. Some discussion on how the Subsidy Instability per agent/max-min ratio  can grow under their proposed solution will be insightful. 
- The (non)-uniqueness of the solution under Subsidy Instability needs more discussions. If the solutions are non-unique under UCB does the algorithm converge to a single solution? Some numerical validation may shed some light on this.    
- Some discussion on the decentralization of the proposed Subsidy Instability will be useful as centralized algorithms are undesired due to privacy concerns.  
- This paper does not mention some of the related works properly. 
1. The difference from [6] which also study the matching with transfer setting should be elaborated. (see the first bullet)
2. The comparison with learning a stable matching in two sided market without transfer is incomplete. The results in the paper [5], [23], and [28] are not mentioned in the paper, although they are cited. Does the current formulation capture the heterogeneous ranking in both sides therein? 
3. The application of a primal-dual algorithm with bandit feedback in prior works is not discussed. Please cite the appropriate works, e.g. 'An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits', Tirinzoni et al. 
- The instance dependent regret does not capture the dependence on various reward gaps, but  just uses the minimum gap. Can this be made more finer (following Chen et al. and their gap definitions for super-arms) ? In general, the proofs of the extensions are somewhat incomplete (akin to sketches). I encourage the authors to complete the proofs in a technical report. 

Minor
- In Lemma 4.4 it should be \mathcal{A} instead of A.


Note: All the citations are numbered according to the main paper. 
limitations_and_societal_impact: The authors highlight that the paper lacks the study of fairness in utility allocation across agents of the proposed algorithm. They also discuss the scope of social impact of the paper.
review_title: null

Meta-review: Reviewers unilaterally supported the paper - the approach is simple and the introduced subsidy idea aligns well with platform markets' realities, the characterization of the problem is reasonably complete, exposition is good, and the results are clean.  The most critical reviewer, SoA5, brings up solid points about regret and exposition/motivation around the subsidy, and in future versions of this work it would beneficial for the authors to address these concerns directly.
Decision: Accept (Spotlight)