Summary
The paper studies the sample complexity of finding a stable matching under the probably approximately (PAC) framework.
In the model, $N$ agents are to be matched with $K \ge N$ arms. Each arm has an (a priori unknown) utility to each agent, inducing the agents’ preferences; Arms also has strict preferences over the agents. Agents learn about their rewards by pulling the arms and observing stochastic rewards with means equal to the utilities. The objective is to find a matching that is stable with the desired probability with least possible samples (pullings of arms).
The paper proposes an arm-proposing deferred acceptance (DA) algorithm with action elimination (AE). The algorithm implements the arm-proposing DA, with the modification where, in face of uncertain preferences over a new proposal and the current match, the agent uses AE to reach a decision of rejection. The sample complexity of the algorithm is analyzed and simulations are used to evaluate the algorithm empirically.
Strengths
The paper combines the online learning from stochastic observations with the classic literature on stability of matchings, a novel and important direction. While intuitive, the algorithmic combination of arm-proposing DA with AE is novel to my understanding.
The paper is overall clearly written, with consistent notations and clear definitions. I find it easy to follow. The claims seem reasonable, although I did not go over all the proofs.
Weaknesses
While the results may be new and interesting, I do not find them sufficiently significant. From the theoretical perspective, the algorithm proposed and its analysis both seem fairly standard. The algorithmic improvement also seem marginal, as Theorem 5 only seem to provide a weak improvement on existing results, and nor do the simulations (which are run in a very restrictive setting with a specific form of preferences) seem conclusive on the superiority of the main algorithm. [Edit: From the discussion, I understand that there is some valid rationales behind the simulations (the choice of utility distribution in particular). I think it is worth more discussion and justification.]
On the empirical front, the paper would benefit from additional motivating examples on why the results can be impactful in real world applications. As will be mentioned in one of my questions, I am not sure how the proposed algorithm can be applied to settings such as school admission, ride share, etc. - in particular, the assumption that rewards are iid and that an arm can be pulled (sampled) repeatedly in an arm-proposing fashion seems hard to interpret in these settings. Without sufficient practical motivation, the results seem only a nice yet marginal theoretical exercise.
Questions
- Can the authors elaborate on the assumption that $N \le K$? Note that, since the main algorithm is an arm-proposing DA variant, the two sides are not symmetric and such an assumption requires justification. When $N > K$ we know that the entire set of stable matchings can exhibit strikingly different behaviors than when $N\le K$ [1].
- Is there any reason why the experiment is only carried out on the specific utility model with utilities 1 through 20? What if they come from other distributions, e.g., exponentially or polynomially growing? The additional SPC setting is also quite restrictive in my understanding.
- Have the authors considered relaxing the notion of stability in such stochastic settings (e.g., [2,3])? Ultimately, strict stability is a rather restricted solution concept and often beyond hope, and an approximate notion may be both more realistic and also more tractable.
- How should one reason about the minimum preference gap? In general, I would expect this quantity to scale down as the market size increases; realistically speaking, at most $1/n$.
- Further, indifference can be common in real world applications, and I would hope that the model and the algorithm should allow for such scenarios - pressing a student to form a precise preference over schools that are otherwise entirely comparable seems unnecessary. Maybe approximate stability could be one way to resolve this? E.g., maybe there is a better measure of “average stability” that accounts for utility gap rather than just the probability of stability (Line 324, in my understanding).
[1] Itai Ashlagi, Yash Kanoria, and Jacob D. Leshno. 2017. Unbalanced Random Matching Markets: The Stark Effect of Competition." Journal of Political Economy.
[2] Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, and Will Rosenbaum. 2015. A Stable Marriage Requires Communication. In Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).
[3] Itai Ashlagi, Mark Braverman, and Geng Zhao. 2023. Welfare Distribution in Two-sided Random Matching Markets. In Proceedings of the 24th ACM Conference on Economics and Computation (EC '23).
Minor comments:
- Line 135: typo. “… leads to unique …” => “… leads to a unique …”
- Line 359-360: “such variations often introduce computational complexity with known preferences” - I might be missing something obvious, but in the hope to understand this claim better, I hope the authors could clarify what “computational complexity with known preferences” they are referring to here. In my understanding, with known preferences, the vanilla DA should work fine with ties and is efficient.
- When the problem is formulated as agents pulling arms, I find it hard to reasonable arms proposing. To me, this means that the side that bears the burden of exploration in fact does not control their very own action? Is there a better setup or application that motivates the study?
Limitations
Limitations are discussed in Section 7: Conclusion and Future Work. The paper is mostly of a theoretical nature.