Balancing Bias in Two-sided Markets for Fair Stable Matchings

Thank you for the thorough review and the time invested in it.

discuss the paper’s relevance to the broader AI community and why ICLR would be the right venue for this paper.

The AI and ML communities exhibit a continuous interest in stable matchings problems and their repercussions. Recent work [A] initiated the study of deep learning for the automated design of two-sided matching mechanisms, in order to understand tradeoffs between strategy-proofness and stability, which cannot be achieved simultaneously, training differentiable matching mechanisms that map discrete preferences to valid randomized matchings. We find that our work offers a viable alternative to such learning mechanisms, as it is independent of any mechanism among agents, and works directly in the space of rotations to find the exact optimal matching for balance cost. As machine learning pipelines are introduced in matching market design, we think it is vital to allow space for the publication of exact algorithms in machine learning venues, which provide a standard of comparison that learning-based algorithms will need to strive for.

[A] Sai Srivatsa Ravindranath, Zhe Feng, Shira Li, Jonathan Ma, Scott Duke Kominers, David C. Parkes: Deep Learning for Two-Sided Matching. CoRR abs/2107.03427 (2021)

When reading Figure 4(d), I was initially surprised that ENUM- performs worse on smaller instances than on larger ones. Then I realized that this is because you limited the number of iterations for ENUM-, and for some reason, the smaller instances required more iterations for ENUM-. However, the running time of ENUM- on smaller instances is still much shorter than on larger instances. From a practical perspective, I think it would be more informative to limit the running time of the algorithms instead of the number of iterations.

We limit the number of instances exaimined to $10^7$. Indeed ENUM- finds the optimal when given more time.

In practical applications, what algorithm and performance measure are typically used for the stable marriage problem? Is the balance cost the dominant measure in practice? And does brute-force enumeration suffice in practice?

The Balance cost is a very attractive cost measure, yet it is avoided due to the NP-hardess of the problem.

Have you considered how to construct instances where the proposed algorithm performs poorly?

We construct and present exactly such hard instances in our experimental study.

What are the limitations of the proposed algorithm?

It may eventually encounter the exponential complexity bottleneck in hard problem instances, though that did not happen in our experiments.

Thank you for the elaborate review.

W1: The paper lacks a comprehensive analysis of performance in diverse real-world applications.

We do provide such analysis in our experimental study with diverse real-world data, including synthetic data, spatial data, non-spatial data, and hard instances.

W2: may not align with real-world two-sided markets where preferences are changing over time.

Yes, dynamic preference lists pose an interesting direction for future work. In the current work, we contribute an algorithm that returns the exact solution to the NP-hard problem of minimizing the worst dissatisfaction on one side.

W3: exclud[es] other potentially fair matchings that fall outside the selected subset.
Q2: is there a mathematical guarantee that this focus always yields the exact minimum balance cost?
Q5: Can ISORROPIA guarantee convergence to a global minimum in all instances of the BSM problem?

Yes, Isorropia finds the exact global minimum balance cost in all instances of the BSM problem, as our analysis in Section 4.3 establishes via Theorems 2, 3, and 4. The described bias does not arise, as matchings outside the selected subsets cannot yield an optimal solution to the BSM problem.

W4: [compare] with more recent advancements or adaptive heuristics in stable matching (such as learning-based stable matching).

To our knowledge, such learning-based heuristics, such as [A], do not address the balanced stable matching problem, hence are not directly comparable to our solution.

[A] Sai Srivatsa Ravindranath, Zhe Feng, Shira Li, Jonathan Ma, Scott Duke Kominers, David C. Parkes: Deep Learning for Two-Sided Matching. CoRR abs/2107.03427 (2021)

Q1: What is the theoretical bound on time complexity for extracting and evaluating these promising antichains?
Q4: Can we quantify the relationship between graph properties and the number of steps required to reach the optimal solution?

We discuss the complexity in Lines 438-441 and Appendix A.3 (line 903-913). As our analysis shows, complexity depends on the size $|R|$ of the rotation set and the depth of the rotation graph. In the worst case, the number of stable marriages $N$ can grow exponentially in the market size $n$, rendering all methods infeasible. Table 10 presents empirical statistics that illustrate the relationship between the number of rotations and the number of stable marriages.

Q3: What is the sensitivity of ISORROPIA’s performance to these initial stable marriages?

These initial stable marriages do not alter the sets of promising antichains which Isorropia searches to find the exact optimal solution and which hence affect its performance; these sets depend on the rotation graph structure.

Dear Reviewers,

As we approach the end of the rebuttal phase, we look forward to receiving your feedback. Please feel free to share any additional concerns you may have. If our response addresses your concerns and clarifies any potential misunderstandings, we would greatly appreciate it if you could reconsider the rating.

Thank you for the thorough review and the time invested in it.

W1: provide intuition throughout the presentation of the algorithm.

We provide such intuition in Sections 4.2 and 4.3. We first divide the entire solution space into three sets (i.e., the blue, pink and grey parts in Figure 2, Line 289), and then prune these three sets (cf. dotted box in Figure 2). To make it more intuitive, we provide examples of the construction of these antichains in Table 4 and explain them in Lines 359-361 and Lines 385-386.

Our algorithm is rooted in the structure of all solutions, which includes transformations among stable matchings, antichains, and closed subsets, based on the rotation structure. As readers may not be familiar with this background, we provide a comprehensive review of the preliminaries in Appendix A.1, including a toy example to illustrate the elimination process.

W1: why does the pruning of the search space not seem to lead to significantly suboptimal solutions?

This pruning allows for finding the optimal solution, as that is guaranteed to lie within the non-pruned part of the search space. Our analysis in Section 4.3 establishes that via Theorems 2, 3, and 4, consistently with the graph in Figure 2.

W2: show how the performance degrades in size and complexity of the problem.

We have included a wide array of experiments within the space allowed, which allow for conclusions on practical applicability to be made.

W3: it is not clear that ICLR is the right venue for this work as there doesn't seem to be any learning component.

First, the AI and ML communities exhibit a continuous interest in stable matching problems and their repercussions [A, B, C, D], aiming to compute equitable and efficient solutions balancing disparate impacts in multi-agent systems. Besides, recent work [E] initiated the study of deep learning for the automated design of two-sided matching mechanisms, in order to understand tradeoffs between strategy-proofness and stability, which cannot be achieved simultaneously, training differentiable matching mechanisms that map discrete preferences to valid randomized matchings. We find that our work offers a viable alternative to such learning mechanisms, as it is independent of any mechanism among agents, and works directly in the space of rotations to find the exact optimal matching for balance cost. As machine learning pipelines are introduced in matching market design, we think it is vital to allow space for the publication of exact algorithms in machine learning venues, which provide a standard of comparison that learning-based algorithms will need to strive for.

Further, matching problems have been adopted in learning models themselves. For example, the multi-object tracking model requires matching algorithms to solve the data association problem [F], while learning techniques in point cloud completion leverage a matching-based loss function [G].

[A] Piotr Dworczak: Deferred acceptance with compensation chains. EC 2016

[B] Nikolaos Tziavelis, Ioannis Giannakopoulos, Katerina Doka, Nectarios Koziris, and Panagiotis Karras: Equitable stable matchings in quadratic time. NeurIPS 2019

[C] Nikolaos Tziavelis, Ioannis Giannakopoulos, Rune Quist Johansen, Katerina Doka, Nectarios Koziris, and Panagiotis Karras: Fair procedures for fair stable marriage outcomes. AAAI 2020

[D] Sulian Le Bozec-Chiffoleau, Charles Prud'homme, Gilles Simonin: Polynomial Time Presolve Algorithms for Rotation-Based Models Solving the Robust Stable Matching Problem. IJCAI 2024

[E] Sai Srivatsa Ravindranath, Zhe Feng, Shira Li, Jonathan Ma, Scott Duke Kominers, David C. Parkes: Deep Learning for Two-Sided Matching. CoRR abs/2107.03427 (2021)

[F] Paul Voigtlaender, Michael Krause, Aljosa Osep, Jonathon Luiten, Berin Balachandar Gnana Sekar, Andreas Geiger, Bastian Leibe: MOTS: Multi-Object Tracking and Segmentation. CVPR 2019

[G] Shunran Zhang, Xiubo Zhang, Tsz Nam Chan, Shenghui Zhang, Leong Hou U: A Computation-Aware Shape Loss Function for Point Cloud Completion. AAAI 2024

Dear Reviewers,

As we approach the end of the rebuttal phase, we look forward to receiving your feedback. Please feel free to share any additional concerns you may have. If our response addresses your concerns and clarifies any potential misunderstandings, we would greatly appreciate it if you could reconsider the rating.

We appreciate your comprehensive review and the time invested to it.

We understand the major concern is the fit within ICLR. The AI and ML communities exhibit a continuous interest in stable matchings problems and their repercussions. Recent work [A] initiated the study of deep learning for the automated design of two-sided matching mechanisms, in order to understand tradeoffs between strategy-proofness and stability, which cannot be achieved simultaneously, training differentiable matching mechanisms that map discrete preferences to valid randomized matchings. We find that our work offers a viable alternative to such learning mechanisms, as it is independent of any mechanism among agents, and works directly in the space of rotations to find the exact optimal matching for balance cost. As machine learning pipelines are introduced in matching market design, we think it is vital to allow space for the publication of exact algorithms in machine learning venues, which provide a standard of comparison that learning-based algorithms will need to strive for.

[A] Sai Srivatsa Ravindranath, Zhe Feng, Shira Li, Jonathan Ma, Scott Duke Kominers, David C. Parkes: Deep Learning for Two-Sided Matching. CoRR abs/2107.03427 (2021)

Is there a typo in line 304?

Yes, there was a typo in the subscript. Thank you for noticing.