Decentralized Matching in a Probabilistic Environment
Decentralized Matching in a Probabilistic Environment
复制标题
概率环境中的分散匹配
DOI：
10.1145/3465456.3467652
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Saberi, Amin
中科院分区：
文献类型：
--
作者：
Jeloudar, Mobin Y.;Lo, Irene;Pollner, Tristan;Saberi, Amin
我们考虑了一个重复随机匹配模型，其中兼容性是概率的，在第一次匹配代理时实现，并在未来持续存在。这样的模型在零工经济、肾脏交换和导师匹配中都有应用。我们问分散的匹配过程是否能逼近最优在线算法。特别是，我们考虑了一个分散的稳定匹配过程，其中代理与不喜欢与其他人匹配的最相容的伙伴匹配，已知的相容对在未来的所有回合中继续匹配。我们证明了上述过程为一般图上的最优在线匹配算法提供了0.316的近似。我们还给出了多对一二部匹配的1/7近似，一般图上容量限制匹配的1/11近似，以及至多k个代理组成团队的1/2k近似。我们的结果依赖于一个新的耦合论点，该论点根据最优在线算法的逐轮比较和稳定匹配来分解成功的边。
We consider a model for repeated stochastic matching where compatibility is probabilistic, is realized the first time agents are matched, and persists in the future. Such a model has applications in the gig economy, kidney exchange, and mentorship matching. We ask whether adecentralized matching process can approximate the optimal online algorithm. In particular, we consider a decentralizedstable matching process where agents match with the most compatible partner who does not prefer matching with someone else, and known compatible pairs continue matching in all future rounds. We demonstrate that the above process provides a 0.316-approximation to the optimal online algorithm for matching on general graphs. We also provide a 1/7-approximation for many-to-one bipartite matching, a 1/11-approximation for capacitated matching on general graphs, and a 1/2k-approximation for forming teams of up to k agents. Our results rely on a novel coupling argument that decomposes the successful edges of the optimal online algorithm in terms of their round-by-round comparison with stable matching.
登录
查看更多内容
DOI：
10.2139/ssrn.3802624
发表时间：
2020
期刊：
Proceedings of the 21st ACM Conference on Economics and Computation
影响因子：
--
作者：
V. Manshadi;Scott Rodilitz
通讯作者：
Scott Rodilitz
论匹配队列的动态控制
影响因子：
1
作者：
Itai Gurvich;Amy R. Ward
通讯作者：
Amy R. Ward
查询提交问题
DOI：
--
发表时间：
2011
期刊：
arXiv.org
影响因子：
--
作者：
M. Molinaro;R. Ravi
通讯作者：
R. Ravi
DOI：
10.1038/s42256-023-00722-5
发表时间：
2020
期刊：
Proceedings of the 21st ACM Conference on Economics and Computation
影响因子：
--
作者：
Duncan C. McElfresh;Christian Kroer;S. Pupyrev;Eric Sodomka;Karthik Abinav Sankararaman;Zack Chauvin;Neil Dexter;John P. Dickerson
通讯作者：
John P. Dickerson
DOI：
10.2139/ssrn.3067596
发表时间：
2016
期刊：
Proceedings of the 2016 ACM Conference on Economics and Computation
影响因子：
--
作者：
I. Ashlagi;Maximilien Burq;Patrick Jaillet;V. Manshadi
通讯作者：
V. Manshadi