Deep Learning for Two-Sided Matching

## Abstract

Abstract We initiate the study of deep learning for the automated design of two-sided matching mechanisms. What is of most interest is to
use machine learning to understand
the possibility of new tradeoffs between strategy-proofness and stability .
These properties cannot be achieved simultaneously, but the efficient frontier is not understood.
We introduce novel differentiable surrogates for quantifying ordinal strategy-proofness and stability and use them to train differentiable matching mechanisms that map discrete preferences to valid randomized matchings. We demonstrate that the efficient frontier characterized by these learned mechanisms is substantially better than that achievable through a convex combination of baselines of deferred acceptance (stable and strategy-proof for only one side of the market), top trading cycles (strategy-proof for one side, but not stable), and randomized serial dictatorship (strategy-proof for both sides, but not stable).
This gives a new target for economic theory and opens up new possibilities for machine learning pipelines in matching market design.

## 1 Introduction

Two-sided matching markets, classically used for settings such as high-school matching, medical residents matching, and law clerk matching, and more recently used in online platforms such as Uber, Lyft, Airbnb, and dating apps, play a significant role in today’s world. As a result, there is a significant interest in designing better mechanisms for two-sided matching.

The seminal work of Gale and Shapley () introduces a simple mechanism for stable, one-to-one matching in two-sided markets—*deferred-acceptance* (DA)—which has been applied in many settings, including doctor-hospital matching (Roth and Peranson, ), school choice (Abdulkadiroğlu and Sönmez, ; Pathak and Sönmez, ; Abdulkadiroğlu et al., ), and cadet-matching (Sönmez and Switzer, ; Sönmez, ).
The DA mechanism is *stable*, i.e., no pair of participants prefer each other to their match (or to being unmatched, if they are unmatched in the outcome). However, the DA mechanism is not *strategy-proof* (SP),
and a participant can
sometimes misreport their preferences to obtain a better outcome
(although it is SP
for participants on one side of the market).
Although widely used, this failure of SP for the DA mechanism
presents a challenge for two main reasons. First, it can lead to unfairness, where better-informed participants
can gain an advantage in knowing which misreport
strategies can be helpful.
Second, strategic behavior can lead to lower quality, unintended outcomes,
and outcomes that are unstable with respect to true preferences.

In general, it is well-known
that there must necessarily be a tradeoff between stability and strategy-proofness:
it is provably
impossible for a mechanism to achieve
both stability and strategy-proofness (Dubins and Freedman, ; Roth, ).
A second example of a matching mechanism
is
*random serial dictatorship* (RSD) (Abdulkadiroglu and Sönmez, ),
which is typically adopted for one-sided assignment problems rather than two-sided matching.
When adapted to two-sided matching, RSD
is SP but not stable. In fact,
a participant may even prefer to remain unmatched
than participate in the outcome of the matching.
A third example of a matching mechanism
is
the top trading cycles (TTC) mechanism (Shapley and Scarf, ),
also typically adopted for one-sided assignment problems rather than
problems of two-sided matching.
In application to two-sided matching, TTC is neither SP nor stable (although it is SP
for participants on one side of the market).

There have been various research efforts to circumvent this impossibility result. Some relax the definition of strategyproofness (Mennle and Seuken, ) while others characterize the constraints under which stability and strategyproofness are achieved simultaneously (Kamada and Kojima, ; Hatfield et al., ; Hatfield and Milgrom, ).
The tradeoff between these desiderata remains poorly understood beyond the existing point solutions of DA, RSD, and TTC. However, we argue that real-world scenarios demand a more nuanced approach that considers both properties. The case of the Boston school choice mechanism highlights the negative consequences of lacking strategy-proofness, resulting in unfair manipulations by specific parents (Abdulkadiroglu et al., ).
At the same time, the importance of stability in matching markets is well understood (Roth, ).

Recognizing this, and inspired by the success of
deep learning in the
study of revenue-optimal auction design (Duetting et al., ; Curry et al., ; Shen et al., ; Rahme et al., ),
we initiate the study of deep learning for the design of two-sided matching mechanisms
We ask whether deep learning
frameworks can enable a systematic study of this tradeoff. By answering this question affirmatively, we open up the possibility of using machine learning pipelines to open up new opportunities for economic theory—seeking theoretical characterizations
of mechanisms that can strike a new balance between strategyproofness and stability.

We use a neural network to represent the rules of a matching mechanism, mapping preference reports to a distribution over feasible matchings, and show how we can use an unsupervised learning pipeline to characterize the efficient frontier for the design tradeoff between stability and SP.
The main methodological challenge in applying neural networks to two-sided matching comes from handling the ordinal preference inputs (the corresponding inputs are cardinal in auction design) and identifying suitable, differentiable surrogates for approximate strategy-proofness and approximate stability.

We work with randomized matching mechanisms, for which the strongest SP concept is ordinal strategy-proofness. This aligns incentives with truthful reporting, whatever an agent’s utility function (i.e., for any cardinal preferences consistent with
an agent’s ordinal preferences). Ordinal SP is equivalent to the property of first-order stochastic dominance (FOSD) (Erdil, ), which
suitably defines the property that
an agent has a
better chance of getting their top, top-two, top-three, and so forth choices when they report truthfully.
As a surrogate for SP, we quantify during training the degree to which FOSD is violated. For this, we adopt an adversarial learning approach, augmenting the training data with defeating misreports that reveal the violation of FOSD.
We also define a suitable surrogate to quantify the degree to which stability is violated. This surrogate aligns with the notion of ex ante stability—the strongest stability concept for randomized matching.

We train neural network representations of matching mechanisms
by adopting stochastic gradient descent (SGD) for loss functions that
are defined on different convex combinations of the two surrogate quantities,
and construct the efficient frontier for stability and strategy-proofness for different market settings.
A further challenge with ordinal preference inputs as opposed to cardinal inputs
arises because ordinal preferences are discrete.
In the present work, we simply
enumerate the possible
misreports of an agent
as a step
when evaluating the derivative of error
for a particular training example. In contrast, the use of
deep-learning approaches
for the design
of revenue-optimal auctions
works with
a continuous
space of agent valuations
and
gradient-ascent in this adversarial step of identifying
useful misreports (Duetting et al., ).
As discussed at the end of the paper,
the challenge that this presents in
scaling to large numbers of agents
can be resolved
by assuming a suitable structure on preference orderings
in the domain,
or on the language that is
made available to agents in
reporting their preferences to the mechanisms.

Our main experimental results demonstrate that this novel
use of deep learning can strike a much better trade-off between stability and SP than that achieved by a convex combination of the DA, TTC, and RSD mechanisms. Taken as a whole, these results suggest that deep learning pipelines can be used to identify new opportunities for matching theory.
For example, we identify mechanisms
that are provably almost as stable as DA and yet considerably more strategy-proof. We also identify mechanisms
that are provably almost as strategy-proof as RSD and yet considerably more stable.
These discoveries raise opportunities for future work in economic theory, in regard to understanding
the structure of these two-sided matching mechanisms as well as
characterizing the preference distributions for which this is possible.

## 2 Related work.

Dubins and Freedman () and Roth () show the impossibility of achieving both stability and SP in two-sided matching. Alcalde and Barberà () also show the impossibility of individually rational, Pareto efficient, and SP allocation rules, and this work has been extended to randomized matching (Alva and Manjunath, ). RSD is
SP but may not be stable or even individually rational (IR) (Abdulkadiroglu and Sönmez, ). We will see that the top trading cycles (TTC) mechanism (Shapley and Scarf, ), when applied in a two-sided context, is only SP for one side, and is neither stable nor IR.
The DA mechanism (Gale and Shapley, ) is stable but not SP; see also (Roth et al., ), who study the polytope of stable matchings. The stable improvement cycles mechanism (Erdil and Ergin, ) achieves as much efficiency as possible on top of stability but fails to be SP even for one side of the market. Finally, a series of results show that DA becomes SP for both sides of the market in large-market limit contexts (Immorlica and Mahdian, ; Kojima and Pathak, ; Lee, ).

Aziz and Klaus () discuss different stability and no envy concepts. We focus on ex ante stability (Kesten and Ünver, ), also discussed by (Roth et al., ) as strong stability. Mennle and Seuken () discuss different notions of approximate strategy-proofness in the context of matching and allocation problems. In this work, we focus on ordinal SP and its analog of FOSD (Erdil, ). This is a strong and widely used SP concept in the presence of ordinal preferences.
There are a lot of other desiderata, such as efficiency, that are also incompatible with strategyproofness. Mennle and Seuken () study this trade-off through hybrid mechanisms which are convex combinations of a mechanism with good incentive properties with another which is efficient. In the context of social choice, other work studies the trade-off between approximate SP and desiderata, such as plurality and veto voting (Mennle and Seuken, ).

Conitzer and Sandholm (, ) introduced the automated mechanism design (AMD) approach that framed problems as a linear program.
However, this approach faces severe scalability issues as the formulation scales exponentially in the number of agents and items (Guo and Conitzer, ).
Overcoming this limitation,
more recent work seeks to use deep neural networks to address problems of economic design (Duetting et al., ; Feng et al., ; Golowich et al., ; Curry et al., ; Shen et al., ; Rahme et al., ; Duan et al., ; Ivanov et al., ), but not until now to matching problems.
As discussed in the introduction,
two-sided matching brings about new challenges, most notably
in regard to
working with discrete,
ordinal preferences and adopting the right surrogate loss functions for approximate SP and approximate stability.
Other work has made use of support vector machines to search for stable mechanisms, but without considering strategy-proofness (Narasimhan et al., ).
A different line of research
is also considering
stable matching together with bandits problems,
where agent preferences are unknown a priori (Das and Kamenica, ; Liu et al., ; Dai and Jordan, ; Liu et al., ; Basu et al., ; Sankararaman et al., ; Jagadeesan et al., ; Cen and Shah, ; Min et al., ).

There have also been other recent efforts that leverage deep learning for matching (in the context of online bipartite matching (Alomrani et al., )) and other related combinatorial optimization problems (Bengio et al., ). Most of these papers adopt a reinforcement learning based approach to compute their solutions. Our approach, on the other hand, is not sequential but rather end-to-end differentiable, and our parameter weights are updated through a single backward pass. Additionally, the focus of our work is on matching markets and mechanism design, and is concerned with capturing core economic concepts within a machine learning framework and balancing the trade-offs between stability and strategy-proofness.

## 3 Preliminaries

Let $W$ denote a set of $n$ workers and $F$ denote a set of $m$ firms. A feasible matching, $\mu$, is a set of (worker, firm) pairs, with each worker and firm participating in at most one match. Let ${\mathcal{B}}$ denote the set of all matchings. If $(w,f)\in\mu$, then $\mu$ matches $w$ to $f$, and we write $\mu(w)=f$ and $\mu(f)=w$. If a worker or firm remains unmatched, we say it is matched to $\bot$. We also write $(w,\bot)\in\mu$ (resp. $(\bot,f)\in\mu$).
Each worker has a strict preference order, $\succ_{w}$, over the set $\overline{F}=F\cup\{\bot\}$. Each firm has a strict preference order, $\succ_{f}$, over the set $\overline{W}=W\cup\{\bot\}$.
Worker $w$ (firm $f$) prefers remaining unmatched to being matched with a firm (worker) ranked below $\bot$ (the agents ranked below $\bot$ are said to be unacceptable).
If worker $w$ prefers firm $f$ to $f^{\prime}$, then we write $f\succ_{w}f^{\prime}$, similarly for a firm’s preferences. Let $P$ denote the set of all preference profiles, with $\succ=(\succ_{1},\ldots,\succ_{n},\succ_{n+1},\succ_{n+m})\in P$ denoting a preference profile comprising of the preference order of the $n$ workers and then the $m$ firms.

A pair $(w,f)$ forms a blocking pair for matching $\mu$ if $w$ and $f$ prefer each other to their partners in $\mu$ (or $\bot$ in the case that one or both are unmatched). A matching $\mu$ is stable if and only if there are no blocking pairs.
A matching $\mu$ is individually rational (IR) if and only if it is not blocked by any individual; i.e., no agent finds its match unacceptable and prefers $\bot$.(^1^11Stability precludes empty matchings. For example, if a matching $\mu$ leaves a worker $w$ and a firm $f$ unmatched, where $w$ finds $f$ acceptable, and $f$ finds $w$ acceptable, then $(w,f)$ is a blocking pair to $\mu$.)

### 3.1 Randomized matchings.

We work with randomized matching mechanisms, $g$, that map preference profiles, $\succ$, to distributions on matchings, denoted $g(\succ)\in\triangle({\mathcal{B}})$ (the probability simplex on matchings).
Let $r\in[0,1]^{(n+1)\times(m+1)}$ denote the marginal probability, $r_{wf}\geq 0$, with which worker $w$ is matched with firm $f$, for each $w\in\overline{W}$ and $f\in\overline{F}$. We require $\sum_{f^{\prime}\in\overline{F}}r_{wf^{\prime}}=1$ for all $w\in W$, and $\sum_{w^{\prime}\in\overline{W}}r_{w^{\prime}f}=1$ for all $f\in F$. For notational simplicity, we write $g_{wf}(\succ)$ for the marginal probability of matching worker $w$ (or $\bot$) and firm $f$ (or $\bot$).

###### Theorem 1 (Birkhoff von-Neumann) .

Given any randomized matching $r$, there exists a distribution on matchings, $\Delta({\mathcal{B}})$,
with marginal probabilities equal to $r$.

The following definition is standard (Budish et al., ), and generalizes stability to randomized matchings.

###### Definition 2 (Ex ante justified envy) .

A randomized matching $r$ causes ex ante justified envy if:
(1) some worker $w$ prefers $f$ over some fractionally matched firm $f^{\prime}$ (including $f^{\prime}=\bot$) and firm $f$ prefers $w$ over some fractionally matched worker $w^{\prime}$ (including $w^{\prime}=\bot$) (“$w$ has envy towards $w^{\prime}$" and “$f$ has envy towards $f^{\prime}$"), or
(2) some worker $w$ finds a fractionally matched $f^{\prime}\in F$ unacceptable, i.e. $r_{wf^{\prime}}>0$ and $\bot\succ_{w}f^{\prime}$, or some firm $f$ finds a fractionally matched $w^{\prime}\in W$ unacceptable, i.e. $r_{w^{\prime}f}>0$ and $\bot\succ_{f}w^{\prime}$.

A randomized matching $r$ is ex ante stable if and only if it does not cause any ex ante justified envy. Ex ante stability reduces to the standard concept of stability for deterministic matching.
Part (1) of the definition includes non-wastefulness: for any worker $w$, we should have $r_{w\bot}=0$ if there exists some firm $f^{\prime}\in F$ for which $r_{w^{\prime}f^{\prime}}>0$ and $w\succ_{f^{\prime}}w^{\prime}$ and for for any firm $f$, we need $r_{\bot f}=0$ if there exists some worker $w^{\prime}\in W$ for which $r_{w^{\prime}f^{\prime}}>0$ and $f\succ_{w^{\prime}}f^{\prime}$. Part (2) of the definition captures IR: for any worker $w$, we should have $r_{wf^{\prime}}=0$ for all $f^{\prime}\in F$ for which $\bot\succ_{w}f^{\prime}$, and for any firm $f$, we need $r_{w^{\prime}f}=0$ for all $w^{\prime}\in W$ for which $\bot\succ_{f}w^{\prime}$.

To define strategy-proofness, say that $u_{w}:\overline{F}\to\mathbb{R}$ is a $\succ_{w}$-utility for worker $w$ when $u_{w}(f)>u_{w}(f^{\prime})$ if and only if $f\succ_{w}f^{\prime}$, for all $f,f^{\prime}\in\overline{F}$. We similarly define a $\succ_{f}$-utility for a firm $f$.
The following concept of ordinal SP is standard (Erdil, ), and generalizes SP to randomized matchings.

###### Definition 3 (Ordinal strategy-proofness) .

A randomized matching mechanism $g$ satisfies
ordinal SP if and only if, for all agents $i\in W\cup F$, for any preference profile $\succ$, and any $\succ_{i}$-utility for agent $i$,
and for all reports $\succ^{\prime}_{i}$, we have

$$ $\displaystyle\mathbf{E}_{\mu\sim g(\succ_{i},\succ_{-i})}[u_{i}(\mu(i))]\geq\mathbf{E}_{\mu\sim g(\succ^{\prime}_{i},\succ_{-i})}[u_{i}(\mu(i))].$ (1) $$

By this definition, no worker or firm can improve their expected utility (for any utility function consistent with their preference order) by misreporting their preference order. For a deterministic mechanism, ordinal SP reduces to standard SP. Erdil () shows that first-order stochastic dominance is equivalent to ordinal SP.

###### Definition 4 (First Order Stochastic Dominance) .

A randomized matching mechanism $g$ satisfies
first order stochastic dominance (FOSD) if and only if, for worker $w$, and each $f^{\prime}\in\overline{F}$ such that $f^{\prime}\succ_{w}\bot$,
and all reports of others $\succ_{-w}$, we have (and similarly for the roles of workers and firms transposed),

$$ $\displaystyle\!\!\sum_{f\in F:f\succ_{w}f^{\prime}}\!\!\!g_{wf}(\succ_{w},\succ_{-w})$ $\displaystyle\!\geq\!\!\!\sum_{f\in F:f\succ_{w}f^{\prime}}\!\!g_{wf}(\succ^{\prime}_{w},\succ_{-w}).\!$ (2) $$

FOSD states that, whether looking at its most preferred firm, its two most preferred firms, or so forth, worker $w$ achieves a higher probability of matching on that set of firms for its true report than for any misreport. We make use of a quantification of the violation of this condition to provide a surrogate for the failure of SP during learning.

###### Theorem 5 ( (Erdil, 2014 ) ) .

A two-sided matching mechanism is ordinal SP if and only if it satisfies FOSD.

###### Theorem 1 (Birkhoff von-Neumann) .

###### Definition 2 (Ex ante justified envy) .

###### Definition 3 (Ordinal strategy-proofness) .

###### Definition 4 (First Order Stochastic Dominance) .

###### Theorem 5 ( (Erdil, 2014 ) ) .

### 3.2 Deferred Acceptance, RSD, and TTC.

We consider three benchmark mechanisms: the stable but not SP *deferred-acceptance* (DA) mechanism, the SP but not stable *randomized serial dictatorship* (RSD) mechanism, and the *Top Trading Cycles* (TTC) mechanism, which is neither SP nor stable.
The DA and TTC mechanisms are ordinal SP for the proposing side of the market but not for agents on both sides of the market.

###### Definition 6 (Deferred-acceptance (DA)) .

In worker-proposing deferred-acceptance (firm-proposing is defined analogously), each worker $w$ maintains a list of acceptable firms ($f\succ_{w}\bot$) for which it has not had a proposal rejected (“remaining firms"). Repeat until all proposals are accepted:

- •
$\forall w\in W$: $w$ proposes to its best acceptable, remaining firm.
- •
$\forall f\in F$: $f$ tentatively accepts its best proposal (if any), and rejects the rest.
- •
$\forall w\in W$: If $w$ is rejected by firm $f$, it updates its list of acceptable firms to remove $f$.

###### Theorem 7 (see (Roth and Sotomayor, 1990 ) ) .

DA is stable but not Ordinal SP.

###### Definition 8 (Randomized serial dictatorship (RSD)) .

In the two-sided version of RSD, we first sample a priority order, $\pi$, on the set $W\cup F$, uniformly at random, such that $\pi=(\pi_{1},\pi_{2},\ldots,\pi_{m+n})$ is a permutation on $W\cup F$ in decreasing order of priority. For the one-sided version, we sample a priority order $\pi$ on either $W$ or $F$.

Proceed as follows:

- •
Initialize matching $\mu$ to the empty matching.
- •
In round $k=1,\ldots,|\pi|$:
–
If $\pi_{k}$ is not yet matched in $\mu$, then add to
$\mu$ the match between $\pi_{k}$ and its most preferred
unmatched agent, or $\bot$ if all
remaining agents are unacceptable to $\pi_{k}$.

###### Theorem 9 .

RSD satisfies FOSD—and thus is ordinal SP by Theorem [5](#Thmtheorem5)—but is not stable.

###### Proof.

We defer the proof to appendix [A](#A1)
∎

###### Definition 10 (Top Trading Cycles (TTC)) .

In worker-proposing TTC (firm-proposing is defined analogously), each agent (worker or firm) maintains a list of acceptable firms. Repeat until all agents are matched:

- •
Form a directed graph with each unmatched agent pointing to their most preferred option. The agents can point at themselves if there are no acceptable options available. Every worker that is a part of a cycle is matched to a firm it points to ( or itself, if the worker is pointing at itself). The unmatched agents remove from their lists every matched agent from this round.

###### Theorem 11 .

TTC is neither strategy-proof nor stable for both sides.

###### Proof.

Example [17](#Thmtheorem17) in Appendix [B](#A2) shows that TTC is neither strategyproof nor stable.
∎

###### Remark 12 .

TTC, like RSD, is usually used in one-sided assignment problems, where it is SP, and where the notion of stability which is an important consideration in two-sided matching, is not a concern.

###### Definition 6 (Deferred-acceptance (DA)) .

###### Theorem 7 (see (Roth and Sotomayor, 1990 ) ) .

###### Definition 8 (Randomized serial dictatorship (RSD)) .

###### Theorem 9 .

###### Proof.

###### Definition 10 (Top Trading Cycles (TTC)) .

###### Theorem 11 .

###### Proof.

###### Remark 12 .

## 4 Two-Sided Matching as a Learning Problem

In this section, we develop the use of deep learning for the design of two-sided matching mechanisms.

### 4.1 Neural Network Architecture

Figure: Figure 1: Matching network $g$ for a set of $n$ workers and $m$ firms. Given inputs $p,q\in\mathbb{R}^{n\times m}$ the matching network is a feed-forward network with $R$ hidden layers that uses softplus activation to generate non-negative scores and normalization to compute the randomized matching. We additionally generate a Boolean mask matrix, $\beta$, and multiply it with the score matrix before normalization to ensure IR by making the probability of matches that are unacceptable zero.

We use a neural network to represent a matching mechanism. Let $g^{\theta}:P\to\triangle({\mathcal{B}})$ denote the mechanism, for parameters $\theta\in\mathbb{R}^{d}$.
The input is a preference profile, and the output defines a distribution on matchings.
We use a feed-forward neural network with $R=4$ fully connected hidden layers, $J=256$ units in each layer, leaky ReLU activations, and a fully connected output layer.(^2^22Leaky ReLU is a variation of ReLU that addresses the issue of dead neurons by allowing a small positive gradient for negative input values, thereby preventing gradients from getting stuck at 0 0). See Figure [1](#S4.F1).

To represent an agent’s preference order in the input, we adopt a
utility for each agent on the other side of the
market that has a constant offset in utility across successive agents in the preference order. This is purely a representation choice and does not imply that we use this particular utility to study SP (on the contrary, we work with a FOSD-based quantification of the degree of approximation to ordinal SP).
In particular, let $p^{\succ}_{w}=(p_{w1}^{\succ},\ldots,p_{wm}^{\succ})$ and $q^{\succ}_{f}=(q_{1f}^{\succ},\ldots,q_{nf}^{\succ})$
represent the preference order of a worker and firm, respectively.
We define $p^{\succ}_{w\bot}=0$ and $q^{\succ}_{\bot f}=0$, and to further illustrate this representation:

- •
For a preference order $\succ$ with $f_{1}:w_{2},w_{1},w_{3}$, we represent this at the input as $q^{\succ}_{f_{1}}=(\frac{2}{3},1,\frac{1}{3})$.
- •
For a preference order $\succ$ with $w_{1}:f_{1},f_{2},\bot,f_{3}$, we represent this as $p^{\succ}_{w_{1}}=(\frac{2}{3},\frac{1}{3},-\frac{1}{3})$.
- •
For a preference order $\succ$ with $w_{1}:f_{1},f_{2},\bot,f_{3},f_{4}$, we represent this as $p^{\succ}_{w_{1}}=(\frac{2}{4},\frac{1}{4},-\frac{1}{4},-\frac{2}{4})$.

Formally, we have:

$$ $\displaystyle p_{wj}^{\succ}$ $\displaystyle=\frac{1}{m}\left(\mathbf{1}_{j\succ_{w}\bot}+\sum_{j^{\prime}=1}^{m}\left(\mathbf{1}_{j\succ_{w}j^{\prime}}-\mathbf{1}_{\bot\succ_{w}j^{\prime}}\right)\right)$ (3) $\displaystyle q_{if}^{\succ}$ $\displaystyle=\frac{1}{n}\left(\mathbf{1}_{i\succ_{f}\bot}+\sum_{i^{\prime}=1}^{n}\left(\mathbf{1}_{i\succ_{f}i^{\prime}}-\mathbf{1}_{\bot\succ_{f}i}\right)\right)$ (4) $$

where $\mathbf{1}_{X}$ is the indicator function for event $X$.

Taken together, the input is vector $(p_{11}^{\succ},\ldots,p_{nm}^{\succ},q_{11}^{\succ},\ldots,q_{nm}^{\succ})$ of
$2\times n\times m$ numbers.

The output of the network is a vector $r\in[0,1]^{n\times m}$, with $\sum_{j=1}^{m}r_{wj}\leq 1$ and
$\sum_{i=1}^{n}r_{if}\leq 1$ for every every $w\in[n]$ and $f\in[m]$.
This defines the marginal probabilities in a randomized matching for this input profile.
The network first outputs two sets of scores $s\in\mathbb{R}^{(n+1)\times m}$ and $s^{\prime}\in\mathbb{R}^{n\times(m+1)}$.
We apply the softplus function (denoted by $\sigma_{+}$) element-wise to these scores, where $\sigma_{+}(x)=\ln(1+e^{x})$.
To ensure IR, we first construct a Boolean mask variable $\beta_{wf}$, which is zero only when the match is unacceptable to one or both the worker and firm, i.e., when $\bot\succ_{w}f$ or $\bot\succ_{f}w$. We set $\beta_{n+1,f}=1$ for $f\in F$ and $\beta_{w,m+1}=1$ for $w\in W$. We multiply the scores $s$ and $s^{\prime}$ element-wise with the corresponding Boolean mask variable to compute $\bar{s}\in\mathbb{R}_{\geq 0}^{(n+1)\times m}$ and $\bar{s}^{\prime}\in\mathbb{R}_{\geq 0}^{n\times(m+1)}$.

For each $w\in\overline{W}$, we have $\bar{s}_{wf}=\beta_{wf}\ln(1+e^{s_{wf}})$, for all $f\in F$. For each $f\in\overline{F}$, we have $\bar{s}^{\prime}_{wf}=\beta_{wf}\ln(1+e^{s^{\prime}_{wf}})$, for all $w\in W$.
We normalize $\bar{s}$ along the rows and $\bar{s}^{\prime}$ along the columns to obtain normalized scores, $\hat{s}$ and $\hat{s}^{\prime}$ respectively. The match probability $r_{wf}$, for worker $w\in W$ and firm $f\in F$, is computed as the minimum of the normalized scores:
$r_{wf}=\min\left(\frac{\bar{s}_{wf}}{\sum_{f^{\prime}\in\overline{F}}\bar{s}_{wf^{\prime}}},\frac{\bar{s}^{\prime}_{wf}}{\sum_{w^{\prime}\in\overline{W}}\bar{s}^{\prime}_{w^{\prime}f}}\right)$.
We have $r_{wf}=0$ whenever $\beta_{wf}=0$, ensuring that every matching
in the support of the distribution will be IR.
Based on our construction, the allocation matrix $r$ is weakly doubly stochastic, with rows and columns summing to at most 1.
Budish et al. () show that any weakly doubly stochastic matrix can be decomposed to a convex combination of 0-1, weakly doubly stochastic matrices.

### 4.2 Formulation as a Learning Problem

We formulate a loss function $\mathcal{L}$ that is defined on training data of $\ell$ preference profiles, $D=\{\succ^{(1)},\ldots,\succ^{(\ell)}\}$. Each preference profile $\succ$ sampled i.i.d. from a distribution on profiles.
We allow for correlated preferences; i.e., workers may tend to agree that one of the firms is preferable to one of the other firms, and similarly for firms.
The loss function captures a tradeoff between stability and ordinal SP.
Recall that $g^{\theta}(\succ)\in[0,1]^{n\times m}$ denotes the randomized matching. We write $g^{\theta}_{w\bot}(\succ)=1-\sum_{f=1}^{m}g^{\theta}_{wf}(\succ)$ and $g^{\theta}_{\bot f}{(\succ)}=1-\sum_{w=1}^{n}g^{\theta}_{wf}(\succ)$ to denote the probability of worker $w$ and firm $f$ being unmatched, respectively.

Stability Violation.
For worker $w$ and firm $f$, we define the stability violation
at profile $\succ$ as

$$ $\displaystyle\mathit{stv}_{wf}($ $\displaystyle g^{\theta},\succ)\!=\!\left(\sum_{w^{\prime}\in\overline{W}}g^{\theta}_{w^{\prime}f}(\succ)\cdot\max\{q_{wf}^{\succ}-q_{w^{\prime}f}^{\succ},0\}\right)$ $\displaystyle\times\!\left(\sum_{f^{\prime}\in\overline{F}}g^{\theta}_{wf^{\prime}}(\succ)\cdot\max\{p_{wf}^{\succ}-p_{wf^{\prime}}^{\succ},0\}\!\!\right).$ (5) $$

This captures the first kind of ex ante justified envy in Definition [2](#Thmtheorem2).
We can omit the second kind of ex ante justified envy because the learned mechanisms satisfy IR through the use of the Boolean mask matrix (and thus, there are no violations of the second kind).

The average stability violation (or just stability violation) of mechanism $g^{\theta}$ on profile $\succ$
is $\mathit{stv}(g^{\theta},\succ)=\frac{1}{2}\left(\frac{1}{m}+\frac{1}{n}\right)\sum_{w=1}^{n}\sum_{f=1}^{m}\mathit{stv}_{wf}{(g^{\theta},\succ)}.$
We define the expected stability violation, $\mathit{STV}(g^{\theta})=\mathbb{E}_{\succ}\mathit{stv}(g^{\theta},\succ)$.
We also write $\mathit{stv}(g^{\theta})$ to denote the average stability violation on the training data.

###### Theorem 13 .

A randomized matching mechanism $g^{\theta}$ is ex ante stable up to zero-measure events if and only if $\mathit{STV}(g^{\theta})=0$.

###### Proof.

We defer the proof to appendix [C](#A3)
∎

Ordinal SP violation.
We turn now to quantifying the degree of approximation to ordinal SP. Let $\succ_{-i}=(\succ_{1},\ldots,\succ_{i-1},\succ_{i+1},\ldots,\succ_{n+m})$. For a valuation profile, $\succ\ \in P$, and a mechanism $g^{\theta}$, let $\Delta_{wf}(g^{\theta},\succ^{\prime}_{w},\succ)=g^{\theta}_{wf}(\succ^{\prime}_{w},\succ_{-w})-g^{\theta}_{wf}(\succ_{w},\succ_{-w})$. The regret to worker $w$ (firm $f$) is defined as:

$$ $\begin{split}\mathrm{regret}_{w}(g^{\theta},\succ)&=\max_{\succ^{\prime}_{w}\in P}\left(\max_{f^{\prime}\succ_{w}\bot}\sum_{f\succ_{w}f^{\prime}}\Delta_{wf}(g^{\theta},\succ^{\prime}_{w},\succ)\right).\\ \mathrm{regret}_{f}(g^{\theta},\succ)&=\max_{\succ^{\prime}_{f}\in P}\left(\max_{w^{\prime}\succ_{f}\bot}\sum_{w\succ_{f}w^{\prime}}\Delta_{wf}(g^{\theta},\succ^{\prime}_{f},\succ)\right).\end{split}$ (6) $$

The average regret on profile $\succ$ is:

$$ $\displaystyle\mathit{regret}(g^{\theta},\succ)=\frac{1}{2}\left(\frac{1}{m}\sum_{w\in W}\mathrm{regret}_{w}(g^{\theta},\succ)+\frac{1}{n}\sum_{f\in F}\mathrm{regret}_{f}(g^{\theta},\succ)\right)$ (7) $$

The expected regret is $\mathit{RGT}(g^{\theta})=\mathbb{E}_{\succ}\mathit{regret}(g^{\theta},\succ)$. We can also write $\mathit{rgt}(g^{\theta})$ to denote the average regret
on training data.

###### Theorem 14 .

The regret to a worker (firm) for a given preference profile
is the maximum amount by which the worker (firm) can increase their expected normalized utility through a misreport, fixing the reports of others.

###### Proof.

Consider some worker $w\in W$. Without loss of generality, let $\succ_{w}:f_{1},\ldots,f_{k},\bot,f_{k+1},\ldots,f_{m}$. Any normalized $\succ_{w}$-utility  function, $u_{w}$, consistent with ordering given by $\succ_{w}$ satisfies $1\geq u_{w}(f_{1})\geq u_{w}(f_{2})\geq\ldots u_{w}(f_{k})\geq 0\geq u_{w}(f_{k+1})\geq\ldots u_{w}(f_{m})$. Let $U_{w}$ be the set of all such consistent utility functions.

Consider some misreport $\succ^{\prime}_{w}$. We have $\Delta_{wf}(g^{\theta},\succ^{\prime}_{w},\succ)=g^{\theta}_{wf}(\succ^{\prime}_{w},\succ_{-w})-g^{\theta}_{wf}(\succ_{w},\succ_{-w})$. The increase in utility for worker $w$ when the utility function is $u_{w}$ is given by $\sum_{f\in F}u_{w}(f)\Delta_{wf}(g^{\theta},\succ^{\prime}_{w},\succ)$. The maximum amount by which worker $w$ can increase their expected normalized utility through misreport $\succ_{w}^{\prime}$ is given by the objective: $\max_{u_{w}\in U_{w}}\sum_{f\in F}u_{w}(f)\Delta_{wf}(g^{\theta},\succ^{\prime}_{w},\succ)$.

Since $g^{\theta}$ always guarantees IR, we have:

$$ $\sum_{f\in F:\bot\succ f}u_{w}(f)\Delta_{wf}(g^{\theta},\succ^{\prime}_{w},\succ)=\sum_{f\in F:\bot\succ_{w}f}u_{w}(f)g^{\theta}_{wf}(\succ^{\prime}_{w},\succ_{-w})\leq 0$ (8) $$

.
Thus, we can simplify our search space by only considering $u_{w}\in U_{w}$ where $u_{w}(f_{k+1}),\ldots,u_{w}(f_{m})=0$.

Define $\delta_{k}=u_{w}(f_{k}),\delta_{k-1}=u_{w}(f_{k-1})-u_{w}(f_{k}),\delta_{1}=u_{w}(f_{1})-u_{w}(f_{2})$. This objective can thus be rewritten as:

$$ max $\displaystyle\sum_{f=1}^{k}\left(\sum_{i=f}^{k}\delta_{i}\right)\Delta_{wf}(g^{\theta},\succ^{\prime}_{w},\succ)$ (9) such that $\displaystyle\sum_{i=1}^{k}\delta_{i}\leq 1\text{~{}and~{}}\delta_{1},\ldots\delta_{k}\geq 0$ (10) $$

Changing the order of summation, we have the following optimization problem:

$$ $\displaystyle\text{max}\sum_{i=1}^{k}\delta_{i}$ $\displaystyle\left(\sum_{f=1}^{i}\Delta_{wf}(g^{\theta},\succ^{\prime}_{w},\succ)\right)$ (11) $\displaystyle\text{such that}\sum_{i=1}^{k}\delta_{i}$ $\displaystyle\leq 1\text{~{}and~{}}\delta_{1},\ldots\delta_{k}\geq 0$ (12) $$

This objective is of the form $\max_{\|x\|_{1}\leq 1}x^{T}y$ and it’s solution is given by the $||y||_{\infty}$. Thus, the solution to the above maximization problem is given by $\max_{i\in[k]}\sum_{f=1}^{i}\Delta_{wf}(g^{\theta},\succ^{\prime}_{w},\succ)$. But this is the same as $\max_{f^{\prime}:f^{\prime}\succ_{w}\bot}\sum_{f:f\succ_{w}f^{\prime}}\Delta_{wf}(g^{\theta},\succ^{\prime}_{w},\succ)$. Computing the maximum possible increase over all such misreports gives us $\max_{\succ_{w^{\prime}}\in P}\left(\max_{f^{\prime}:f^{\prime}\succ_{w}\bot}\sum_{f:f\succ_{w}f^{\prime}}\Delta_{wf}(g^{\theta},\succ^{\prime}_{w},\succ)\right)$. This quantity is exactly $\mathit{regret}_{w}(g^{\theta},\succ)$. The proof follows similarly for any firm $f$.
∎

###### Theorem 15 .

A randomized mechanism, $g^{\theta}$,
is ordinal SP up to zero-measure events if and only if $\mathit{RGT}(g^{\theta})=0$.

The proof is similar to Theorem [13](#Thmtheorem13), and deferred to Appendix [D](#A4).

###### Theorem 13 .

###### Proof.

###### Theorem 14 .

###### Proof.

###### Theorem 15 .

### 4.3 Training Procedure

For a mechanism parameterized as $g^{\theta}$, the training problem that we formulate is,

$$ $\displaystyle\min_{\theta}\,\lambda\cdot\mathit{stv}(g^{\theta})+(1-\lambda)\cdot\mathit{rgt}(g^{\theta}),$ (13) $$

where $\lambda\in[0,1]$
controls the tradeoff between approximate stability and approximate SP.
We use SGD to solve ([13](#S4.E13)). The gradient of the degree of violation of stability with respect to network parameters is straightforward to calculate. The gradient of regret is complicated by the nested maximization in the definition of regret. In order to compute the gradient, we first solve the inner maximization by checking
possible misreports. Let $\hat{\succ}^{(\ell)}_{i}$ denote the defeating preference report for agent $i$ (a worker or firm) at preference profile $\succ^{(\ell)}$ that maximizes $regret_{i}(g^{\theta},\succ^{(\ell)})$. Given this, we obtain the derivative of regret for agent $i$ with respect to the network parameters, fixing the misreport to the defeating valuation and adopting truthful reports for the others.

For the case of TTC and RSD, we also need to quantify the IR violation (this is
necessarily zero for the other mechanisms). We define the IR violation
at profile $\succ$ as:

$$ $\displaystyle\mathit{irv}(g,\succ)$ $\displaystyle=\frac{1}{2m}\sum_{w=1}^{n}\sum_{f=1}^{m}g_{wf}(\succ)\cdot\left(\max\{-q_{wf}^{\succ},0\}\right)$ (14) $\displaystyle+\frac{1}{2n}\sum_{w=1}^{n}\sum_{f=1}^{m}g_{wf}(\succ)\cdot\left(\max\{-p_{wf}^{\succ},0\}\right)$ $$

For the case of RSD, we also include the average IR violation on test data when reporting the stability violation.

## 5 Experimental Results

We report the results on a test set of 204,800 preference profiles, and use the Adam optimizer to train our models for 50,000 mini-batch iterations, with mini-batches of 1024 profiles.
We use the PyTorch deep learning library, and all experiments are run on a cluster of NVIDIA GPU cores.

We study the following market settings:

- •
For uncorrelated preferences, for each worker or firm, we sample uniformly at random from all preference orders, and then, with probability 0.2 (truncation probability), we choose at random a position at which to truncate this agent’s preference order.
- •
For correlated preferences, we sample a preference profile as in the uncorrelated case. We also sample a common preference order on firms and a common preference order on workers. For each agent, with probability, $p_{\mathrm{corr}}>0$, we replace its preference order with the common preference order for its side of the market.

Specifically, we consider matching problems with $n=4$ workers and $m=4$ firms with uncorrelated preference and varying probability of correlation $p_{\mathrm{corr}}=\{0.25,0.5,0.75\}$.

Figure: Figure 2: Comparing stability violation and strategy-proofness violation from the learned mechanisms for different choices of $\lambda$ (red dots) with the best of worker- and firm-proposing DA, as well as TTC, and RSD, in $4\times 4$ two-sided matching, and considering uncorrelated preference orders as well as markets with increasing correlation ($p_{\mathrm{corr}}\in\{0.25,0.5,0.75\}$). The stability violation for TTC and RSD includes IR violations.
Refer to caption: /html/2107.03427/assets/x1.png

We compare the performance of our mechanisms, varying parameter $\lambda$ between 0 0 and $1$,
with the best of worker- and firm- proposing DA and TTC (as determined
by average SP violation over the test data) and RSD(^3^33We only plot the performance of one-sided RSD as it achieves lower stability violation the two-sided version). We also compare against convex combinations of DA, TTC, and RSD.
We plot the resulting frontier on stability violation ($\mathit{stv}(g^{\theta})$) and SP violation ($\mathit{rgt}(g^{\theta})$) in Figure [2](#S5.F2). As explained above, because TTC and RSD mechanisms do not guarantee IR, we include the IR violations in the reported stability violation (none of the other mechanisms fail IR).

At $\lambda=0.0$, we learn a mechanism that has very low regret ($\approx 0$) but poor stability. This performance is similar to that of RSD. For large values of $\lambda$, we learn a mechanism that approximates DA. For intermediate values, we find solutions that dominate the convex combination of DA, TTC, and RSD and find novel and interesting tradeoffs between SP and stability. Notably, for lower levels of correlations we see substantially better SP than DA along with very little loss in stability. Given the importance of stability in practice, this is a very intriguing discovery. For higher levels of correlations, we see substantially better stability than RSD along with very little loss in SP. It is also interesting to see that TTC itself has intermediate properties, between those of DA and RSD. Comparing the scale of the y-axes, we can also see that increasing correlation tends to reduce the opportunity for strategic behavior across both the DA and the learned mechanisms.

Figure: Figure 3: Left and Middle: Comparing welfare per agent of the learned mechanisms for different values of the tradeoff parameter $\lambda$ with the best of the firm- and worker- proposing DA, as well as TTC, and RSD. Right, Top: Comparing the average instance-wise max similarity scores ($\mathit{sim}(g^{\theta})$) of the learned mechanisms with worker- and firm-proposing DA. Right, Bottom: Normalized entropy of the learned mechanisms for different values of the tradeoff parameter $\lambda$. The results are shown for uncorrelated preferences as well as an increasing correlation between preferences ($p_{\mathrm{corr}}\in\{0.25,0.5,0.75\}$)
Refer to caption: /html/2107.03427/assets/x5.png

Figure [3](#S5.F3) shows the expected welfare for the learned mechanisms, measured here for the equi-spaced utility function (the function used in the input representation). We define the welfare of a mechanism $g$ (for the equi-spaced utility function) on a profile $\succ$ as:

$$ $\displaystyle\mathit{welfare}(g,\succ)=\frac{1}{2}\left(\frac{1}{n}+\frac{1}{m}\right)\sum_{w\in W}\sum_{f\in F}g_{wf}(\succ)\left(p^{\succ}_{wf}+q^{\succ}_{wf}\right).$ (15) $$

We compare against the maximum of the expected welfare achieved by the worker- and firm- proposing DA and TTC mechanisms, as well as that from RSD.
As we increase $\lambda$, and the learned mechanisms come closer to DA, the welfare of the learned mechanisms improves.
It is notable that for choices of $\lambda$ in the range 0.8 and higher, i.e., the choices of $\lambda$ that provide interesting opportunities for improving SP relative to DA, we also see good welfare. We also see that TTC, and especially RSD have comparably lower welfare.
It bears emphasis that when a mechanism is not fully SP, as is the case for all mechanisms except RSD,
this is an idealized view of welfare since it assumes truthful reports. In fact, we should expect welfare to be reduced through strategic misreports and the substantially improved SP properties of the learned mechanisms relative to DA (Figure [2](#S5.F2)) would be expected to further work in favor of improving the welfare in the learned mechanisms relative to DA.(^4^44In fact, the same is true for the stability of a non-SP mechanism such as DA, but it has become standard to assume truthful reports to DA in considering the stability properties of DA.)
Lastly, we observe that for small values of $\lambda$ the learned mechanisms have relatively low welfare compared to RSD. This is interesting and suggests that achieving IR together with SP (recall that RSD is not IR!) is very challenging in two-sided markets.
In interpreting the rules of the learned mechanisms, and considering the importance of DA, we can also compare their functional similarity with DA. For this, let $w$-DA and $f$-DA denote the worker- and firm-proposing DA, respectively. For a given preference profile, we compute the similarity of the learned
rule with DA as

$$ $\mathit{sim}(g^{\theta},\succ)=\max_{\mathcal{M}\in\{w\text{-DA},f\text{-DA}\}}{\frac{\sum_{(w,f):g^{\mathcal{M}}_{wf}(\succ)=1}g^{\theta}_{wf}(\succ)}{\sum_{(w,f):g^{\mathcal{M}}_{wf}(\succ)=1}1}}.$ (16) $$

This calculates the agreement between the two mechanisms, normalized by the size of the DA matching,
and taking the best of $w$-DA or $f$-DA. Let $\mathit{sim}(g^{\theta})$
denote the average similarity score on test data.
As we increase $\lambda$, i.e., penalize stability violations more, we see in
Figure [3](#S5.F3) that the learned matchings get increasingly close to
the DA matchings, as we might expect.
We also quantify the degree of randomness of the learned mechanisms,
by computing the normalized entropy per agent, taking the expectation over all preference profiles. For a given profile $\succ$, we compute normalized entropy
per agent as (this is 0 for a deterministic mechanism):

$$ $\displaystyle H(\succ)$ $\displaystyle=-\frac{1}{2n}\sum_{w\in W}\sum_{f\in\overline{F}}\frac{g_{wf}(\succ)\log_{2}g_{wf}(\succ)}{\log_{2}m}$ (17) $\displaystyle-\frac{1}{2m}\sum_{f\in F}\sum_{w\in\overline{W}}\frac{g_{wf}(\succ)\log_{2}g_{wf}(\succ)}{\log_{2}n}.$ $$

Figure [3](#S5.F3) shows how the
entropy changes with $\lambda$.
As we increase $\lambda$ and the mechanisms come closer to DA, the
allocations of the
learned mechanisms
also becomes less stochastic.

## 6 Discussion

The methodology and results in this paper give a first
but crucial step towards using machine learning to
understanding the structure of mechanisms that achieve nearly the same stability as DA while surpassing DA in terms of strategy-proofness. This is
an interesting observation, given the practical
and theoretical importance of the DA mechanism.
Our experimental results
also suggest that achieving IR together with SP (recall that RSD is not IR) is challenging in two-sided markets,
and this is reflected in the lower welfare
achieved by our learning mechanisms
in the part of the frontier that emphasizes SP. The experimental results also show that for larger
weights assigned to the importance of stability,
the learned mechanisms recover the
DA mechanism, whereas when more emphasis
is given to the importance of strategy-proofness,
the learned mechanisms are more randomized. There are other interesting questions waiting to be addressed. For instance, can we use this kind of framework to understand other tradeoffs, such as
tradeoffs between strategy-proofness and efficiency?

As discussed in the introduction, a challenge in scaling to larger problems is the
need to find defeating misreports,
as exhaustively enumerating all misreports
for an agent
becomes intractable as the number of agents on the other side of the market
increases (and thus the preference domain increases).
A simple remedy is to restrict the language available to agents in making preference reports; e.g.,
it is commonplace to only allow for “top-$k$ preferences" to be reported. Another remedy is to work in domains where there exists some structure on the preference domain, so that not all possible preference orders exist; e.g., single-peaked preferences are an especially stark example (Black, ).
It will also be interesting to study complementary approaches that relax the discrete set of preference orderings to a continuous convex hull such as the Birkhoff polytope. Confining these preference orderings to the Birkhoff polytope can be accomplished using differentiable operations, such as the sinkhorn operator (Adams and Zemel, ). Such continuous relaxation allows misreports to be identified through gradient ascent rather than sampling (and would be similar to working with continuous valuations when learning revenue-optimal auctions (Duetting et al., )).
Despite this limitation, our current approach scales much further than other, existing methods for automated design, which are not well suited for this problem. For instance, methods that use linear programs or integer programs
do not scale well because of the number of variables(^5^55$(m+1)!^{n}\cdot(n+1)!^{m}\cdot nm$ output variables) required to make explicit the input and output structure of the functional that must be optimized over.

A second
challenge is that
we have not been able to find a suitable, publicly available dataset to test our approach. As a fallback, we have endeavored to capture some real-world structures by varying the correlation between
agent preferences
and the truncation probabilities of preferences. Using such stylized, probabilistic models and simulations for validating approaches is a well-established and prevalent practice, consistently utilized
when investigating two-sided matching markets (Chen and Sönmez, ; Echenique and Yariv, ; Das and Kamenica, ; Liu et al., ; Dai and Jordan, ). For instance, Chen and Sönmez (Chen and Sönmez, ) design an environment for school choice where they consider six different schools with six seats each
and where the students’ preferences
are simulated to depend on proximity, quality, and a random factor. Echenique an Yariv (Echenique and Yariv, ) use a simulation study with eight participants on each side of the market, with the payoff matrix designed such that there are one, two, or three stable matches. Further, recent papers on bandit models for stable matching
model agent preferences through synthetic datasets (Das and Kamenica, ; Liu et al., ; Dai and Jordan, ).

In closing, we see exciting work ahead in advancing the design of matching mechanisms that strike the right balance between stability, strategyproofness, and other considerations that are critical to real-world applications.
As an example, it will be interesting to extend the learning framework to encompass desiderata such as capacity limitations or fairness considerations.
Also relevant is to explore additional kinds of neural network architectures, such as
attention mechanisms (Vaswani et al., ) or architectures that incorporate permutation equivariance (Rahme et al., ; Duan et al., ), with the advantage that they can
significantly reduce the search space.

## Acknowledgements

The source code for all experiments along with the instructions to run it is available from Github at [https://github.com/saisrivatsan/deep-matching/](https://github.com/saisrivatsan/deep-matching/). This work is supported in part through an AWS Machine Learning Research Award.

## Appendix A RSD is ordinal SP but not Stable

We first show RSD satisfies FOSD and is thus ordinal SP. Consider agent $i$ in some position $k$ in the order. The agent’s report has no effect on the choices of preceding agents, whether workers or firms (including whether agent $i$ is selected by an agent on the other side). Reporting its true preference ensures, in the event that it remains unmatched by position $k$, that it is matched with its most preferred agent of those remaining.
For the one-sided version, the same argument holds for agents that are in the priority order. If an agent isn’t on the side that’s on the priority order, then that agent’s report has no effect at all.

In the following example, we show RSD mechanism is not stable.

###### Example 16 .

Consider $n=3$ workers and $m=3$ firms with the following preference orders:

$$ $\displaystyle w_{1}:f_{2},f_{3},f_{1},\bot\quad f_{1}:w_{1},w_{2},w_{3},\bot$ $\displaystyle w_{2}:f_{2},f_{1},f_{3},\bot\quad f_{2}:w_{2},w_{3},w_{1},\bot$ $\displaystyle w_{3}:f_{1},f_{3},f_{2},\bot\quad f_{3}:w_{3},w_{1},w_{2},\bot$ $$

The matching found by worker-proposing DA is $(w_{1},f_{3}),(w_{2},f_{2}),(w_{3},f_{1})$. This is a stable matching. If $f_{1}$ truncates and misreports its preference as $f_{1}:w_{1},w_{2},\bot,w_{3}$, the matching found is $(w_{1},f_{1}),(w_{2},f_{2}),(w_{3},f_{3})$. Firm $f_{1}$ is matched with a more preferred worker, and hence the mechanism is not strategy-proof.
Now consider the matching under RSD. The marginal matching probabilities $r$ is given by:

$$ $r=\left(\begin{matrix}\frac{11}{24}&\frac{1}{4}&\frac{7}{24}\[4.0pt] \frac{1}{6}&\frac{3}{4}&\frac{1}{12}\[4.0pt] \frac{3}{8}&0&\frac{5}{8}\end{matrix}\right)$ $$

$f_{2}$ and $w_{2}$ are the most preferred options for $w_{2}$ and $f_{2}$ respectively and they would prefer to be matched with each other always rather than being fractionally matched with each other. Here $(w_{2},f_{2})$ is a blocking pair and thus RSD is not stable.

###### Example 16 .

## Appendix B TTC is neither Stable nor Strategyproof

###### Example 17 .

Consider $n=4$ workers and $m=4$ firms with the following preference orders:

$$ $\displaystyle w_{1}:f_{1},\bot$ $\displaystyle\quad f_{1}:w_{2},w_{3},w_{4},\bot$ $\displaystyle w_{2}:f_{2},\bot$ $\displaystyle\quad f_{2}:w_{1}\bot$ $\displaystyle w_{3}:f_{1},\bot$ $\displaystyle\quad f_{3}:w_{3}\bot$ $\displaystyle w_{4}:f_{3},\bot$ $\displaystyle\quad f_{4}:\bot$ $$

Figure: Figure 4: Round 1 of TTC. The solid lines represent workers and firms pointing to their top preferred agent truthfully. The dashed line represents a misreport by $f_{1}$

If all agents report truthfully, $w_{1}$ is matched with $f_{1}$. This violates IR as $\bot\succ_{f_{1}}w_{1}$ and thus the matching is not ex-ante stable. If $f_{1}$ misreports its preference as $f_{1}:w_{4},w_{3},\bot$, then $w_{3}$ is matched with $f_{1}$. Since $f_{1}$ is matched with a more preferred worker $w_{3}$ with $w_{3}\succ_{f_{1}}\bot\succ_{f_{1}}w_{1}$, TTC is not strategyproof.

###### Example 17 .

## Appendix C Proof of Theorem 13

###### Proof.

Since $\mathit{stv}(g^{\theta},\succ)\geq 0$ then $\mathit{STV}(g^{\theta})=\mathbb{E}_{\succ}\mathit{stv}(g^{\theta},\succ)=0$ if and only if $\mathit{stv}(g^{\theta},\succ)=0$ except on zero measure events.
Moreover, $\mathit{stv}(g^{\theta},\succ)=0$ implies $\mathit{stv}_{wf}(g^{\theta},\succ)=0$ for all $w\in W$, all $f\in F$. This is equivalent to no justified envy.
For firm $f$, this means $\forall w^{\prime}\neq w$, $q^{\succ}_{wf}\leq q^{\succ}_{w^{\prime}f}$ if $g^{\theta}_{w^{\prime}f}>0$ and $q\succ_{wf}\leq 0$ if $g^{\theta}_{\bot f}>0$. Then there is no justified envy for a firm $f$. Analogously, there is no justified envy for worker $w$. If $g^{\theta}$ is ex ante stable, it trivially implies $STV(g^{\theta})=0$ by definition.
∎

###### Proof.

## Appendix D Proof of Theorem 15

###### Proof.

Since $\mathit{regret}(g^{\theta},\succ)\geq 0$ then $\mathit{RGT}(g^{\theta})=\mathbb{E}_{\succ}\mathit{regret}(g^{\theta},\succ)=0$ if and only if
$\mathit{regret}(g^{\theta},\succ)=0$ except on zero measure events.
Moreover, $\mathit{regret}(g^{\theta},\succ)=0$ implies $\mathit{regret}_{w}(g^{\theta},\succ)=0$ for any worker $w$ and $\mathit{regret}_{f}(g^{\theta},\succ)=0$ for any firm $f$. Thus, the maximum utility increase on misreporting is at most zero, and hence $g^{\theta}$ is ordinal SP. If $g^{\theta}$ is Ordinal-SP, it is also satisfies FOSD [5](#Thmtheorem5) and it is straightforward to show that $\mathit{regret}(g^{\theta},\succ)=0$.
∎

###### Proof.

## Appendix E Training Details and Hyperparameters

We use a neural network with $R=4$ hidden layers with $256$ hidden units each for all our settings. We use the leaky ReLU activation function at each of these layers. To train our neural network, we use the Adam Optimizer with decoupled weight delay regularization (implemented as AdamW optimizer in PyTorch) We set the learning rate to $0.005$ for uncorrelated preferences setting and $0.002$ when $p_{corr}=\{0.25,0.5,0.75\}$. The remaining hyperparameters of the optimizer are set to their default values. We sample a fresh minibatch of 1024 profiles and train our neural networks for a total of 50000 minibatch iterations. We reduce the learning rate by half once at $10000^{th}$ iteration and once at $25000^{th}$ iteration. We report our results on 204800 preference profiles. For our training, we use a single Tesla V-100 GPU. For each setting, the neural network takes 4.6 hours to train.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: The market settings are unclear to me. Could you formally describe how the agents' preferences are generated? I didn't understand how to truncate the preference order, and what is the common preference order for firms (or workers).
soundness: 3
strengths: 1. The paper initiates the study of using neural networks to discover two-sided mechanisms from data. The idea of employing neural networks for mechanism learning is compelling.
2. The learned mechanism is capable of identifying a more efficient frontier than traditional approaches.
3. The paper establishes a bridge between deep learning and traditional algorithmic game theory, which I believe is interesting to ICLR community.
summary: This paper proposes a deep learning-based mechanism for two-sided matching that explores the Pareto frontier between strategy-proofness (SP) and stability—two properties that are theoretically impossible to satisfy simultaneously. The authors parameterize the matching mechanism using a neural network that takes participants' reported preferences from both sides as input and outputs a randomized matching result. The loss function is designed as a convex combination of SP and stability violations. Experimental results demonstrate that the proposed method finds a more efficient frontier than classical mechanisms.
weaknesses: 1. The experiments are limited to two prior distributions of preferences; incorporating additional distributions would be beneficial.
2. There are no diagrams to illustrate the architecture of the proposed neural network.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: 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?
soundness: 3
strengths: The idea of studying the tradeoff between SP and stability with deep learning is novel and intuitive. The paper opens up a new direction in mechanism design with machine learning techniques. I generally believe that this is a good paper with novel ideas and clear presentation.
summary: The paper proposes a deep learning pipeline to study the tradeoff between strategy-proofness and stability in two-sided matching markets. The paper formulates SP violation and stability violation quantitatively as a machine learning problem. Extensive experiments are conducted to verify the claim.
weaknesses: The experiment is conducted on synthetic data as compared to real-world data.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1 How do the authors envision scaling this framework to larger markets with thousands of agents on each side? Are there specific techniques or optimizations being considered to extend the approach beyond the current limit of 50 agents? one good way should be as follows. Considering the scalability challenges, is it possible to reduce the computational complexity by focusing on truncated preference lists rather than allowing for empty sets? In real-world markets with thousands of workers and firms, where each participant's preference list is limited to a fixed number (e.g., 10 items), using truncated preferences could significantly reduce the matching time. Could this modification lead to more efficient random matching generation while maintaining strong tradeoffs between stability and strategy-proofness?

2 Given the limited availability of public datasets, what kinds of real-world matching problems do the authors envision their approach being most applicable to? Are there any ongoing efforts to test this framework in partnership with real-world markets?Have you ever considered partnering with educational institutions or job placement agencies to obtain anonymized matching data, or inquired about potential synthetic datasets that might closely mimic real-world scenarios?


3  Is there a better way to design the loss function that could more effectively balance the tradeoff between strategy-proofness and stability, or perhaps other properties? Could alternative loss formulations lead to better performance or more efficient training?
soundness: 4
strengths: 1 The use of deep learning to design two-sided matching mechanisms is highly innovative and represents a significant shift from traditional economic approaches. By employing neural networks, the paper opens up new possibilities for discovering previously unknown tradeoffs between stability and strategy-proofness.

2 The paper successfully demonstrates that deep learning can uncover a superior tradeoff frontier compared to traditional convex combinations of existing mechanisms (DA, TTC, and RSD). This is a substantial contribution, highlighting the potential of machine learning in economic theory and mechanism design.

3 The introduction of both fully connected and convolutional neural network architectures, especially the CNN designed for matching mechanisms using 1×1 convolutions, shows a thoughtful adaptation of neural networks for this domain. The use of permutation equivariance in the CNN design is particularly commendable, as it enhances the generalization and scalability of the approach.
summary: This paper presents an innovative study on using deep learning for the automated design of two-sided matching mechanisms. The core contribution is the exploration of the tradeoff between strategy-proofness and stability, two critical properties that cannot be fully achieved simultaneously in traditional matching mechanisms. The authors introduce novel differentiable surrogates to quantify ordinal strategy-proofness and stability, training neural networks to generate randomized matchings. The results show that the efficient frontier, characterized by the learned mechanisms, outperforms traditional baselines like Deferred Acceptance (DA), Top Trading Cycles (TTC), and Random Serial Dictatorship (RSD). This approach sets a new direction for economic theory, especially in the design of mechanisms that improve on current tradeoffs.
weaknesses: 1 One major limitation of the proposed method is its scalability. While the paper claims to scale efficiently to markets with up to 50 agents on each side, this size is relatively small for many real-world applications. In large-scale matching markets, such as job markets or school admissions, the number of participants can easily reach into the thousands. Therefore, the current methodology may struggle to handle the complexity of large-scale matching problems, where the number of workers and firms is significantly higher. The approach should be optimized to better handle larger scales, with at least the capability to manage thousands of participants on both sides of the market.

2 The lack of publicly available datasets for testing the approach is a notable shortcoming. While the authors attempt to capture real-world structures through simulations, real-world validation remains essential to prove the practical viability of the proposed mechanisms. Without such validation, the generalizability of the findings remains uncertain.

3 The adversarial learning approach, where defeating misreports are generated to quantify violations of first-order stochastic dominance (FOSD), may introduce significant computational overhead. This could become more problematic as the size of the market increases, further exacerbating scalability issues.

Meta-review: This is a cute paper on using deep-learning to design some data-driven matching strategy.

The reviewers rather enjoyed this paper, but I am a bit concerned by the technical contributions. This approach has been investigated in many other economic similar contexts (namely auctions, where the one of the first papers introducing MyersonNet has created a large literature).

The theoretical contributions are very thin, hence we should focus on the practical and technical ones. And on those questions, I have troubles being excited about the "novelty" as I find this paper rather incremental. It is very cute and interesting, but quite incremental, in particular, this topic has already a bunch of papers published (see eg the chapter Machine Learning for Matching Markets).

All in all, I do not think the contributions are sufficient enough with respect to the literature to reach the ICLR acceptance bar

Decision: Reject