Two-sided Competing Matching Markets With Complementary Preferences

My main concern, which motivates my low score, concerns the model. Furthermore, I find the discussion on incentive compatibility (postponed to the appendix) not satisfactory.

(a) it is unclear to me why we need learning at all: the vanilla deferred acceptance mechanism is truthful on the workers’ side, meaning that the workers have no incentive to lie. It is not clear to me whether this is the case for the matching algorithm (Algorithm 3) used by the authors. There are two options: either this new mechanism is truthful for the workers, in which case the platform should ask the workers about their preferences, with no learning involved, or it is not, in which case the workers may not respond truthfully to the queries of the learning algorithm. In both cases, there is an issue with the model.

(b) Concerning firms’ valuations, where are they used? Algorithms 4 and 5 are based on the rankings and make no use of the valuations, so what is the point of learning valuations? Also, it is suspicious that an algorithm agnostic to the valuations manages to perform, on average, close to the optimal stable matching, given that many stable matching may exist.

(c) Concerning truthfulness, what the authors prove is not an incentive compatibility result, as incentive compatibility means that agents have no incentive to deviate from truth-telling, regardless of what other agents do. The authors prove some kind of equilibrium result that says that truthtelling is a Nash equilibrium up to a lower-order term. This latter result is weaker and does not guarantee truthfulness.

Weakness:

1. It seems the major contributes is on the formulation of CMCP into a bandit learning framework, with relatively standard analysis technique.
2. Assumptions: The authors consider the marginal preferences (MP) rather than joint (couple) preferences (JP), more justifications could be helpful.
3. The paper discusses the centralized setting, which may not be practical, as in the motivating examples provided by the authors. With these strong assumptions, the technical novelty is limited.

I am not an expert in this area and provide the following suggestions, mostly on writings, for the authors’ consideration. These are not necessarily weaknesses of the paper.

1. I am not sure if the title (complementary preferences) is proper as the authors actually study the matching with upper and lower quotas.

2. The introduction section can be expanded and better motivated.

The model with complementary preferences is only motivated in the first paragraph of the introduction with one sentence of examples. I would recommend the authors expand this paper, possibly starting with an intuitive and informal definition of complementary preferences, followed by these real-world examples with detailed explanations.

I think the authors also need to explain why these real-world problems can be modeled as a bandit learning framework.

The authors claim that “Matching markets often consist of participants with complementary preferences that can lead to instability (Che et al., 2019).” I do not understand this sentence, as I think the “instability” is caused by the algorithm instead of the model.

3. I have some problems with the problem section.

The authors claim that the time horizon T can be assumed to be known without loss of generality using the doubling trick (Auer et al., 1995). I am not familiar with this trick and a short explanation may be helpful, but the authors can ignore this comment if this assumption is common and the technique is well-known.

The assumption of strict preferences can be explained in detail. The authors explained that strict preference is not necessary for stable matching and regret metric, and for simplicity, the assumption is made. In the conclusion section, the scenarios where agents have indifferent preferences are left for future work. I think the open problems can be made more specific, and the effect of indifferent preferences can be better highlighted.

I think it looks neat if “$m -$ type” is written as “$m$-type”.

4. The sections of algorithms and properties:

It is good that the authors provide explanations of the algorithms which are helpful for me to understand the design. However, due to space limit, Algo 4 and 5 can only be put in the appendix. To understand the main algorithms, since the authors actually need to know the properties of these algorithms (e.g., each firm will not propose to the previous workers who rejected him/her in Algo 5), I am wondering if it is possible to include a short description of how these algorithms run.

For me, I think it is a quite good result that the double matching technique can provide stable matching solutions in the complete information setting, although the algorithm does not provide much technical contribution. I am also surprised this is not known in the literature.

I did not check the proof of Theorem 4.1.

The writing can be consistent. For example, Page 5, “Step 2: Double Matching Stage” and Page 3, “Definition 1 (Blocking Pair)”.

5. Related work. I personally think this section can be expanded (some materials in the appendix can be mentioned in the main body). I guess the audience may want to know for what variants, the existence and computational complexity of stable matchings are known.

• I'm not sure about the motivation for some aspects of the problem setting and how the MMTS algorithm is defined to address it. E.g. in each round of MMTS, in Step 1, it seems like every firm samples the utility that every worker generates to the firm. Is this correct? Further, agents seem to report these utilities and induced rankings to the double matching stage (Step 2). Is this correct? Are the reports made in a way to strategically maximize the firm's reward? I'm unsure of what the role of Thompson sampling is in this context.
• There are several missing details and inconsistencies in the notation due to which I am unsure about the significance and soundness of some of the claims in the paper. I will provide some examples below, although they are not exhaustive.
• It is not clear to me how preferences are modeled exactly.
  • First, there seem to be some typos in the notation. E.g. from a strict reading of the notation in Section 2.1 parts II a and II b, a worker's preferences is given by a function that maps an agent to the set of firms. I believe the authors mean that each worker is mapped to a permutation over the firms, but the notion of permutations over firms are not formally introduced. Also, I am not familiar with the phrase "subset of the permutation", although I believe I understand what the authors mean. I hope the authors will consider a thorough rewriting of Section 2.1.
  • Please consider defining \mu_{i,j}^{m} in the first paragraph of Section 2.1 part II b.
  • I do not understand Figure 1. First, the notation used is not consistent with Section 2.1 part I. Next, it appears from the figure that the item b_1 of type 2 has a positive value for both \mu_i^1 and \mu_i^2. Does this mean b_1 provides agent i utilities for both types? In Fig 1, top row, left figure, what is the utility agent i gets from the matching {a_1, b_2}? What does the bidirectional edge between a_1 and a_2 represent? Aren't preferences strict as discussed earlier in the paper? Please also consider increasing the font size.
  • Section 2.1 part III. u_t^m(p_i) \in \K_m \cup \emptyset. Do you mean u_t^m(p_i) \subseteq \K_m \cup \emptyset since each firm can be matched to multiple workers of type m?
• Importantly it appears that the MMTS algorithm, and in particular, the output of the dual matching algorithm is only stable under the assumption that the firms' preferences can be marginalized, i.e. the preferences over workers of one type do not depend on the preferences over workers of other types that are matched to the firm. Am I missing something?
• Section 2.1 part V: Could you please define the optimal stable matching oracle policy \bar{u}_i^m?