Deep Learning for Two-Sided Matching

We thank you for the thoughtful review and constructive feedback.

Scalability:
We acknowledge that scalability to larger markets is an important challenge. While our current implementation focuses on markets with up to 50 agents per side by restricting the support of the preference distributions, we appreciate your suggestion to use truncated preference lists. This approach could effectively reduce the size of preference domain for misreports and allow for additional scaling.

At the same time, the market size addressed in this study is significantly larger than that explored in prior work. Moreover, insights and mechanisms developed for smaller markets can be applied to larger settings by decomposing them into smaller zones or segments. For instance, in a workers-firms scenario, a country-wide job market could be segmented into smaller metro areas, with each segment solved independently. This locality-based approach aligns with practical constraints.

Real-World Problems:
Please refer to the comment here

Loss functions:
Our approach employs the strongest notions of stability (strong-stability) and strategy-proofness (SP), specifically using first-order stochastic dominance (FOSD). Relaxing these notions to study trade-offs with weaker variants could be a valuable direction for future exploration.

To balance the multi-objective trade-off between stability and SP, we utilize a linear scalarization method with the trade-off parameter $\lambda$. This method is effective and computationally scalable. Investigating alternative multi-objective optimization techniques or adaptive methods to precisely target specific regions of the frontier represents an exciting avenue for future research.

Thank you for your thoughtful review and recognition of our work's novelty and contribution to mechanism design.

For concerns regarding real-world data, please refer to the comment here.

The problem has the assumption that the market is one-to-one, and there are no ties. How will the problem formulation be different if these assumptions are removed?

Ties:
We do allow for ties. Randomization (and the CNN architecture) ensures that agents that have similar preferences and are similarly liked by other firms will have equal marginal probabilities over their outcomes.

Extensions to many-to-one Matching:
In many-to-one matching problems, the row sums of the output must be at most 1 (workers matched to one firm), and the column sums must not exceed the capacities of the firms. To ensure valid matchings, we output two sets of scores: one with row sums normalized to 1 and another with column sums normalized to 1, scaled by firm capacities. The final matching is the element-wise minimum of these scores, satisfying all constraints. (Section 4.1, under outputs)

The Birkhoff-von Neumann theorem applies only to one-to-one matchings. However, Theorem 1 in Budish et al. (2013) guarantees that an output structure that adheres to the bi-hierarchy structure proposed in that paper corresponds to a distribution over deterministic many-to-one assignments with marginal probabilities equal to the neural network output. This can be used to extend our work to many-to-one matchings.

The loss functions we use are compatible with many-to-one settings but require adjustments for non-wastefulness in stability violations, where residuals should be computed as $q_f - \sum_w g_{wf}$ where $q_f$ is the capacity for firm ‘f’. For strategyproofness (SP) violations, we can model firms potentially misreporting their capacities by treating (in addition to misreporting the preferences) by taking into account the capacity as an input to the neural network. This input would be used exclusively for normalization in the output layer.

Thank you for your thoughtful review and positive assessment of our work.

Diagrams:
Thanks for suggesting this. We are currently working on one and will incorporate your feedback into our paper.

Explanation of preferences generation for different market settings:

Thanks for this question. We will improve our exposition to improve clarity.
As a reminder: A dataset is a collection of $\ell$ profiles. A profile is a collection of $m$ + $n$ rank orders.

Uncorrelated Preferences
Here’s how we generate a rank order for the uncorrelated preference. For each profile in the dataset, for each firm/worker:

• First we sample a complete rank order (A complete order over 4 workers may look like this: $w_1 \succ w_2 \succ w_3 \succ w_4 \succ \bot$
• With 20% chance (if $p_{trunc}$ = 0.2), such rank orders are to be truncated.
• If a rank order is chosen to be truncated, a truncation length is chosen at random. For example, if the above profile is chosen to be truncated, a truncation length picked at random is say 2, the above profile becomes $w_1 \succ w_2 \succ \bot$.

Correlated Preferences
Here’s how we generate our preferences for the uncorrelated preference setting

• Generate a dataset of uncorrelated preferences as above.
• For each profile, sample a new rank order for the worker. (This new rank order is sampled uniformly at random over all possible rank orders).
• With 75% chance (if $p_{corr}$ = 0.75), replace each of the worker’s rank order with the common order sampled in the step above.

Higher the $p_{corr}$, higher the likelihood that all the workers have the same preference order within a profile.