双边匹配的深度学习_DeepLearningforTwo-SidedMatching资源-CSDN文库

版权申诉

深度学习

人工智能

103 浏览量 2022-01-23 12:02:43 上传评论收藏 808KB PDF 举报

资源推荐

资源详情

资源评论

Deep Learning for Two-Sided Matching

∗

Sai Srivatsa Ravindranath

, Zhe Feng

, Shira Li

, Jonathan Ma

, Scott D. Kominers

, and

David C. Parkes

John A. Paulson School of Engineering and Applied Sciences, Harvard University

saisr,zhe_feng,parkes@g.harvard.edu

Harvard College

shirali@alumni.harvard.edu, jonathan.q.ma@gmail.com

Harvard Business School

kominers@fas.harvard.edu

July 9, 2021

Abstract

We initiate the use of a multi-layer neural network to model two-sided matching and to

explore the design space between strategy-proofness and stability. It is well known that both

properties cannot be achieved simultaneously but the eﬃcient frontier in this design space is

not understood. We show empirically that it is possible to achieve a good compromise between

stability and strategy-proofness—substantially better than that achievable through a convex

combination of deferred acceptance (stable and strategy-proof for only one side of the market)

and randomized serial dictatorship (strategy-proof but not stable).

1 Introduction

Two-sided matching markets, such as Uber, Airbnb, stock markets, and dating apps, play a signiﬁcant

role in today’s world. As a result, there is a tremendous and rising interest to design better mechanisms

for two-sided matching. The seminal work of Gale and Shapley [

] introduced a simple mechanism

for stable matching in two-sided markets—Deferred-acceptance (DA)—which has since has been

applied in doctor-hospital matching [

], school choice [

], and the matching of cadets to

their branches of military service [

]. DA is stable, i.e., no pair of agents mutually prefer each

other to their DA partners. On the other hand, DA is not strategy-proof (SP); that is, under fully

general preferences, it is always possible that some agent can mis-report her preferences to obtain a

better matching than she would receive under the DA mechanism.

Another well-known mechanism,

random serial dictatorship (RSD), is SP but not stable.

More generally, it is well-known that it is

impossible to achieve both stability and strategy-proofness in two-sided matching [

]. At the

same time, there is little understanding of the nature of this tradeoﬀ beyond point solutions such as

∗

This work is supported in part through an AWS Machine Learning Research Award.

As we discuss below, DA is strategy-proof for agents on one side of the market, but not for agents on both sides

of the market simultaneously.

Indeed, RSD is typically studied for one-sided assignment problems rather than for two-sided matching mechanisms.

For two-sided matching, not only is RSD unstable, but it can also fail to match participants in a way that is better

than receiving no match at all. We adopt RSD as a benchmark in this paper—despite its ﬂaws—because we are not

aware of more suitable SP mechanisms for two-sided matching.

arXiv:2107.03427v1 [cs.GT] 7 Jul 2021

DA and RSD—and we are not aware of any work that has attempted to map out the tradeoﬀ more

generally.

Inspired by the recent development of deep learning for optimal auction design [

we initiate the study of multi-player neural networks to model two-sided matching. We show how

to use machine learning to characterize the frontier curve of the tradeoﬀ between stability and

strategy-proofness. The main challenges of applying neural networks to two-sided matching come

from handling the ordinal preference inputs, and in identifying suitable diﬀerentiable surrogates for

approximate strategy-proofness and stability.

For randomized matching mechanisms, the strongest SP concept is that of ordinal strategy-

proofness. This aligns incentives with truthful reporting whatever the utility function of an agent.

Ordinal SP is equivalent to a property of ﬁrst-order stochastic dominance (FOSD) [

], which means

that agents have a weakly higher chance of getting their top-ranked choices when they report their

preferences truthfully. Our metric for SP quantiﬁes the degree to which FOSD is violated. For this,

we adopt an adversarial approach, seeking to augment the training data with suitable defeating

mis-reports. We also provide a metric to quantify the degree to which stability is violated. We show

that a loss function built from these quantities can be trained through SGD, and illustrate the use of

the framework to identify the stability-strategyproofness frontier. We run simulations to validate the

eﬃciency of our approach, demonstrating for diﬀerent preference distributions that our approach can

strike much better trade-oﬀs between stability and strategyproofness than the convex combination

of DA and RSD.

Related work.

This work lies at the intersection of two-sided matching [

] and the role of

machine learning within economics [

]. The matching mechanisms learned by our neural networks are

randomized, approximately strategy-proof, and approximately stable. Budish et al. [

] and Mennle

and Seuken [

] discuss diﬀerent notions of approximate strategy-proofness in the context of

matching and allocation. In this work, we focus on ordinal SP and its analog of FOSD [

]. This is

a strong and widely-used SP concept in the presence of ordinal preferences.

Classic results of Dubins and Freedman [

] and Roth [

] show that it is impossible to achieve both

stability and strategy-proofness in two-sided matching simultaneously—although strategy-proofness

for one side of the market is achieved by the Deferred Acceptance (DA) mechanism.

Thus market

designers have looked at mechanisms that relax one or both of these conditions. The Random serial

dictatorship (RSD) mechanism [

] is SP but typically fails to produce stable outcomes (and indeed, it

may even fail to be individually rational).

On the other hand, Roth et al. [

] study the polytope of

stable matchings and provide a wide class of stable matchings beyond the well-known DA outcome.

The stable improvement cycles mechanism of Erdil and Ergin [

], meanwhile, achieves as much

eﬃciency as possible on top of stability, but fails to be SP even for one side of the market. Finally, a

series of results have shown that DA becomes SP for both sides of the market in certain large-market

limit contexts; these results typically also require additional, structural assumptions on market

participants’ preferences (see, e.g., [16, 17, 18]).

This work belongs to the emerging literature on machine learning for economic design. Narasimhan

et al. [

] utilize support vector machines to search for good mechanisms among the weighted polytope

mechanisms. Recently, many papers [

] apply deep neural networks to optimal

auction design and facility location problems. In this work, and inspired by the neural network

Alcalde and Barberà [

] also showed the impossibility of individually rational, Pareto eﬃcient, and SP allocation

rules. Alva and Manjunath [5] extended this result to randomized matching contexts.

The Top Trading Cycles (TTC) mechanism is likewise SP—but it eﬀectively treats the market as one-sided,

producing outcomes that do not reﬂect the other side’s preferences.

architecture proposed by Dütting et al. [

], we use neural networks to model the design of two-sided

matching markets.

2 Preliminaries

Let

be a set of

workers and

a set of

ﬁrms, and suppose that each worker can be matched

to at most one ﬁrm and each ﬁrm to at most one worker. A matching

is a set of (worker, ﬁrm)

pairs, with each worker and ﬁrm participating in at most one match. Let

denote the set of all

matchings. If a worker or ﬁrm remains unmatched, we say that it is matched to

⊥

. If (

w, f

)

∈ µ

, then

matches

, and we write

(

) =

and

(

) =

. We write (

w, ⊥

)

∈ µ

(resp. (

⊥, f

)

∈ µ

) to

denote that w (resp. f ) is unmatched.

Each worker has a strict preference order



over the set

F ∪ {⊥}

. Each ﬁrm has a

strict preference order



over the set

W ∪ {⊥}

. Worker

(ﬁrm

) prefers remaining

unmatched to being matched with a ﬁrm (worker) that is ranked below

⊥

(the agents ranked

below

⊥

are unacceptable). If worker

prefers ﬁrm

then we represent this as

f 

and similarly for the preferences of a ﬁrm. Let

denote the set of all preference proﬁles, with



= (



, . . . , 

, 

n+1

, 

n+m

)

∈ P

denoting the preference proﬁle that comprises all workers and

ﬁrms.

A pair (

w, f

) forms a blocking pair for matching

and

prefer each other to their partners

(or

⊥

in the case that either or both are unmatched). A matching

is stable if and only if

there are no blocking pairs. A matching

is individually rational (IR) if it is not blocked by any

individual, i.e., there is no worker or ﬁrm that ﬁnds its partner unacceptable and prefers ⊥.

2.1 Randomized matchings

We work with randomized matching mechanisms

that map preference proﬁles



to distributions on

matchings, denoted

(



)

∈ 4

(

). This provides for diﬀerentiable mechanisms. Here,

(

) denotes

the probability simplex on the set of matchings.

We write

r ∈

(n+1)×(m+1)

to deﬁne the marginal probability

≥

0 with which worker

is matched with ﬁrm

, for each

w ∈ W

and each ﬁrm

f ∈ F

. We require

∈F

= 1 for all

w ∈ W

, and

∈W

= 1 for all

f ∈ F

. For notational simplicity, we also write

(



) to denote

the marginal probability of matching worker w (or ⊥) and ﬁrm f (or ⊥).

Theorem 1

(Birkhoﬀ von-Neumann)

Given any randomized matching

, there exists a distribution

on matchings, ∆(B), with marginal probabilities equal to r.

The following deﬁnition is standard [7] and generalizes stability to randomized matchings.

Deﬁnition 2 (Ex ante justiﬁed envy). A randomized matching r causes ex ante justiﬁed envy if

(1) some worker

prefers

over some (fractionally) matched ﬁrm

(including

⊥

) and ﬁrm

prefers

over some (fractionally) matched worker

(including

⊥

) (“

has envy towards

" and “f has envy towards f

"), or

(2) some worker

ﬁnds a (fractionally) matched

∈ F

unacceptable, i.e.

0 and

⊥ 

or some ﬁrm f ﬁnds a (fractionally) matched w

∈ W unacceptable, i.e. r

> 0 and ⊥ 

A randomized matching

is ex ante stable if and only if it does not cause any ex ante justiﬁed

envy. Ex ante stability reduces to the standard concept of stability for a deterministic matching.

Part (2) of the deﬁnition of ex ante justiﬁed envy captures the idea that a randomized matching

Stability precludes empty matchings. For example, if a matching

leaves a worker

and a ﬁrm

unmatched,

where w ﬁnds f acceptable and f ﬁnds w acceptable, then (w, f) is a blocking pair to µ.

剩余14页未读，继续阅读

评论收藏

内容反馈

版权申诉

易小侠

粉丝: 6515
资源: 9万+

双边匹配的深度学习_Deep Learning for Two-Sided Matching

最新资源

双边匹配的深度学习_Deep Learning for Two-Sided Matching

Platform Competition in Two-Sided Markets

Cyclic stable matching for three-sided networking services

variable neighborhood search for the second type of two-sided assembly line balancing problem

A truthful double auction for two-sided heterogeneous mobile crowdsensing markets

two-sided correlation transformation_DOA_music_correlation_wideb

论文研究-The Algorithm for the Special Case of Two-sided SF-MNSA Problem.pdf

The effects of man-marking on work intensity in small-sided soccer games.pdf

One-sided empirical Bayes test for location parameter in Gamma distribution

Two-sided M-Bayesian credible limits of reliability parameters in the case of zero-failure data for exponential distribution

Nonexistence of UMYUE for the Parameter of a Two-sided Trancated Family* (1984年)

一个可双向滑块选择器的微信小程序组件double-sided-slider-master.zip

Distributed Matching Schemes for Multi-source and Multi-relay Cooperative Wireless Networks

Convert to One-sided FFT（real） labview源文件

maplogic layout manager for ArcGis

Deform_3D_v6&#46;01.pdf

One-sided Precoder Designs for Interference Alignment

Near-optimal One-sided Scheduling for Coded Segmented Network Coding

Facile Preparation of Magnetic Graphene Double-sided Mesoporous Composites for the Selective Enrichment and Analysis of Endogenous Peptides

Syn_FivemToDiscord:FiveM脚本登录到不一致的内容

Cobalt Strike下载

北京邮电大学计算机考研复试笔试资料

计算机系统-笔记-HUN2021级

cs1.6老版本供下载

合成孔径雷达的经典成像算法cs(matlab)仿真代码（吐血整理，内容全，注释全）

港大CS（MSC）面试整理

合成孔径雷达RD CS OmegaK算法点目标仿真.rar

计算机科学导论原书第二版答案.zip

Cobalt-Strike-4.5

cobaltstrike4.3.zip

最新资源

Deform_3D_v6.01.pdf